Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:0911.1696 · Journal of the ACM

A quantum Lovász local lemma

Andris Ambainis, Julia Kempe, Or Sattath

Published Oct 1, 2012• 36 citations
arXivHTMLPDF

Abstract

The Lovász 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 (quantum analog of k - sat ): For instance we show that any collection of rank-1 projectors, with the property that each qubit appears in at most 2 k /( e ċ 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. [2009, 2010] we greatly extend the known satisfiable region for random k - qsat to a density of Ω(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.

DOI
10.1145/2371656.2371659

Related papers

A quantum lovász local lemma

Andris Ambainis, Julia Kempe, Or Sattath

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.

ACM Symposium on Theory of Computing (STOC)•Jun 5, 2010•8 citations

A constructive commutative quantum Lovasz Local Lemma, and beyond

Toby S. Cubitt, Martin Schwarz

The recently proven Quantum Lovasz Local Lemma generalises the well-known Lovasz Local Lemma. It states that, if a collection of subspace constraints are "weakly dependent", there necessarily exists a state satisfying all constraints. It implies e.g. that certain instances of the kQSAT quantum satisfiability problem are necessarily satisfiable, or that many-body systems with "not too many" interactions are always frustration-free. However, the QLLL only asserts existence; it says nothing about how to find the state. Inspired by Moser's breakthrough classical results, we present a constructive version of the QLLL in the setting of commuting constraints, proving that a simple quantum algorithm converges efficiently to the required state. In fact, we provide two different proofs, one using a novel quantum coupling argument, the other a more explicit combinatorial analysis. Both proofs are independent of the QLLL. So these results also provide independent, constructive proofs of the commutative QLLL itself, but strengthen it significantly by giving an efficient algorithm for finding the state whose existence is asserted by the QLLL. We give an application of the constructive commutative QLLL to convergence of CP maps. We also extend these results to the non-commutative setting. However, our proof of the general constructive QLLL relies on a conjecture which we are only able to prove in special cases.

arXiv:1112.1413•Dec 6, 2011•7 citations

Quantum Lovász local lemma: Shearer’s bound is tight

Kun He, Qian Li, Xiaoming Sun +1 more

Lovász Local Lemma (LLL) is a very powerful tool in combinatorics and probability theory to show the possibility of avoiding all “bad” events under some “weakly dependent” condition. Over the last decades, the algorithmic aspect of LLL has also attracted lots of attention in theoretical computer science. A tight criterion under which the abstract version LLL (ALLL) holds was given by Shearer. It turns out that Shearer’s bound is generally not tight for variable version LLL (VLLL). Recently, Ambainis et al. introduced a quantum version LLL (QLLL), which was then shown to be powerful for the quantum satisfiability problem.

arXiv:1804.07055•ACM Symposium on Theory of Computing (STOC)•Jun 20, 2019•9 citations

A constructive quantum Lovasz local lemma for commuting projectors

Or Sattath, Itai Arad

The Quantum Satisfiability problem generalizes the Boolean satisfiability problem to the quantum setting by replacing classical clauses with local projectors. The Quantum Lov\'asz Local Lemma gives a sufficient condition for a Quantum Satisfiability problem to be satisfiable~\cite{ambainis2012quantum}, by generalizing the classical Lov\'asz Local Lemma. The next natural question that arises is: can a satisfying quantum state be \emph{efficiently} found, when these conditions hold? In this work we present such an algorithm, with the additional requirement that all the projectors commute. The proof follows the information theoretic proof given by Moser's breakthrough result in the classical setting~\cite{moser2009constructiveSTOC}. Similar results were independently published in~\cite{cubitt2011constructive, cubitt2013quantum}.

arXiv:1310.7766•Quantum Information and Computation•Sep 1, 2015•15 citations

Product, generic, and random generic quantum satisfiability

Chris R. Laumann, Andreas Martin Läuchli, Roderich Moessner +2 more

We report a cluster of results on $k$-QSAT, the problem of quantum satisfiability for $k$-qubit projectors which generalizes classical satisfiability with $k$-bit clauses to the quantum setting. First we define the $\mathit{NP}$-complete problem of product satisfiability and give a geometrical criterion for deciding when a QSAT interaction graph is product satisfiable with positive probability. We show that the same criterion suffices to establish quantum satisfiability for all projectors. Second, we apply these results to the random graph ensemble with generic projectors and obtain improved lower bounds on the location of the SAT-unSAT transition. Third, we present numerical results on random, generic satisfiability which provide estimates for the location of the transition for $k=3$ and $k=4$ and mild evidence for the existence of a phase which is satisfiable by entangled states alone.

arXiv:0910.2058•Physical Review A•Jun 28, 2010•43 citations

The PRODSAT phase of random quantum satisfiability

Joon Lee, Nicolas Macris, Jean Bernoulli Ravelomanana +1 more

The $k$-QSAT problem is a quantum analog of the famous $k$-SAT constraint satisfaction problem. We must determine the zero energy ground states of a Hamiltonian of $N$ qubits consisting of a sum of $M$ random $k$-local rank-one projectors. It is known that product states of zero energy exist with high probability if and only if the underlying factor graph has a clause-covering dimer configuration. This means that the threshold of the PRODSAT phase is a purely geometric quantity equal to the dimer covering threshold. We revisit and fully prove this result through a combination of complex analysis and algebraic methods based on Buchberger's algorithm for complex polynomial equations with random coefficients. We also discuss numerical experiments investigating the presence of entanglement in the PRODSAT phase in the sense that product states do not span the whole zero energy ground state space.

arXiv:2404.18447•Apr 29, 2024•2 citations
The Lovász 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 (quantum analog of k - sat ): For instance we show that any collection of rank-1 projectors, with the property that each qubit appears in at most 2 k /( e ċ 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. [2009, 2010] we greatly extend the known satisfiable region for random k - qsat to a density of Ω(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.
The recently proven Quantum Lovasz Local Lemma generalises the well-known Lovasz Local Lemma. It states that, if a collection of subspace constraints are "weakly dependent", there necessarily exists a state satisfying all constraints. It implies e.g. that certain instances of the kQSAT quantum satisfiability problem are necessarily satisfiable, or that many-body systems with "not too many" interactions are always frustration-free. However, the QLLL only asserts existence; it says nothing about how to find the state. Inspired by Moser's breakthrough classical results, we present a constructive version of the QLLL in the setting of commuting constraints, proving that a simple quantum algorithm converges efficiently to the required state. In fact, we provide two different proofs, one using a novel quantum coupling argument, the other a more explicit combinatorial analysis. Both proofs are independent of the QLLL. So these results also provide independent, constructive proofs of the commutative QLLL itself, but strengthen it significantly by giving an efficient algorithm for finding the state whose existence is asserted by the QLLL. We give an application of the constructive commutative QLLL to convergence of CP maps. We also extend these results to the non-commutative setting. However, our proof of the general constructive QLLL relies on a conjecture which we are only able to prove in special cases.
Lovász Local Lemma (LLL) is a very powerful tool in combinatorics and probability theory to show the possibility of avoiding all “bad” events under some “weakly dependent” condition. Over the last decades, the algorithmic aspect of LLL has also attracted lots of attention in theoretical computer science. A tight criterion under which the abstract version LLL (ALLL) holds was given by Shearer. It turns out that Shearer’s bound is generally not tight for variable version LLL (VLLL). Recently, Ambainis et al. introduced a quantum version LLL (QLLL), which was then shown to be powerful for the quantum satisfiability problem.
The Quantum Satisfiability problem generalizes the Boolean satisfiability problem to the quantum setting by replacing classical clauses with local projectors. The Quantum Lov\'asz Local Lemma gives a sufficient condition for a Quantum Satisfiability problem to be satisfiable~\cite{ambainis2012quantum}, by generalizing the classical Lov\'asz Local Lemma. The next natural question that arises is: can a satisfying quantum state be \emph{efficiently} found, when these conditions hold? In this work we present such an algorithm, with the additional requirement that all the projectors commute. The proof follows the information theoretic proof given by Moser's breakthrough result in the classical setting~\cite{moser2009constructiveSTOC}. Similar results were independently published in~\cite{cubitt2011constructive, cubitt2013quantum}.
We report a cluster of results on kkk-QSAT, the problem of quantum satisfiability for kkk-qubit projectors which generalizes classical satisfiability with kkk-bit clauses to the quantum setting. First we define the NP\mathit{NP}NP-complete problem of product satisfiability and give a geometrical criterion for deciding when a QSAT interaction graph is product satisfiable with positive probability. We show that the same criterion suffices to establish quantum satisfiability for all projectors. Second, we apply these results to the random graph ensemble with generic projectors and obtain improved lower bounds on the location of the SAT-unSAT transition. Third, we present numerical results on random, generic satisfiability which provide estimates for the location of the transition for k=3k=3k=3 and k=4k=4k=4 and mild evidence for the existence of a phase which is satisfiable by entangled states alone.
The kkk-QSAT problem is a quantum analog of the famous kkk-SAT constraint satisfaction problem. We must determine the zero energy ground states of a Hamiltonian of NNN qubits consisting of a sum of MMM random kkk-local rank-one projectors. It is known that product states of zero energy exist with high probability if and only if the underlying factor graph has a clause-covering dimer configuration. This means that the threshold of the PRODSAT phase is a purely geometric quantity equal to the dimer covering threshold. We revisit and fully prove this result through a combination of complex analysis and algebraic methods based on Buchberger's algorithm for complex polynomial equations with random coefficients. We also discuss numerical experiments investigating the presence of entanglement in the PRODSAT phase in the sense that product states do not span the whole zero energy ground state space.