A Quantum Lovasz Local Lemma

Abstract

The Lovasz Local Lemma (LLL) is a powerful tool in probability theory to show the existence of combinatorial objects meeting a prescribed collection of "weakly dependent" criteria. We show that the LLL extends to a much more general geometric setting, where events are replaced with subspaces and probability is replaced with relative dimension, which allows to lower bound the dimension of the intersection of vector spaces under certain independence conditions. Our result immediately applies to the k-QSAT problem: For instance we show that any collection of rank 1 projectors with the property that each qubit appears in at most $2^k/(e\cdot k)$ of them, has a joint satisfiable state. We then apply our results to the recently studied model of random k-QSAT. Recent works have shown that the satisfiable region extends up to a density of 1 in the large k limit, where the density is the ratio of projectors to qubits. Using a hybrid approach building on work by Laumann et al. we greatly extend the known satisfiable region for random k-QSAT to a density of $\Omega (2^k/k^2)$. Since our tool allows us to show the existence of joint satisfying states without the need to construct them, we are able to penetrate into regions where the satisfying states are conjectured to be entangled, avoiding the need to construct them, which has limited previous approaches to product states.

19 pages

References in corpus (10)

• Clustering of solutions in the random satisfiability problem
• The Satisfiability Threshold of Random 3-SAT Is at Least 3.52
• On product, generic and random generic quantum satisfiability
• The Complexity of the Consistency and N-representability Problems for Quantum States
• Consistency of Local Density Matrices is QMA-complete
• Derandomizing the Lovasz Local Lemma more effectively
• Efficient algorithm for a quantum analogue of 2-SAT
• Phase transitions and random quantum satisfiability
• Bounds on the quantum satisfiability threshold
• A new upper bound for 3-SAT

Cited by in corpus (17)

• Correlation Length versus Gap in Frustration-Free Systems
• Quantum Max-flow/Min-cut
• When a local Hamiltonian must be frustration-free
• On preparing ground states of gapped Hamiltonians: An efficient Quantum Lovász Local Lemma
• A constructive commutative quantum Lovasz Local Lemma, and beyond
• Clustering in Hilbert space of a quantum optimization problem
• An Information-Theoretic Proof of the Constructive Commutative Quantum Lovász Local Lemma
• Bounds on the ground state energy of quantum $p$-spin Hamiltonians
• A Constructive Quantum Lovász Local Lemma for Commuting Projectors
• On efficiently solvable cases of Quantum k-SAT
• Variable Version Lovász Local Lemma: Beyond Shearer's Bound
• Total Functions in QMA
• Area laws and tensor networks for maximally mixed ground states
• Quantum Lovász Local Lemma: Shearer's Bound is Tight
• Testing quantum satisfiability
• The SAT-UNSAT transition in the adversarial SAT problem
• Classical-Quantum Mixing in the Random 2-Satisfiability Problem