### A quantum Lovász local lemmaA quantum Lovász local lemma

Access Restriction
Subscribed

 Author Ambainis, Andris ♦ Kempe, Julia ♦ Sattath, Or Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2012 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Local lemma ♦ Probabilistic method ♦ Quantum computation ♦ Quanum SAT ♦ Random quantum SAT 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 $\textit{k}-qsat$ problem (quantum analog of $\textit{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$ ċ $\textit{k})$ of them, has a joint satisfiable state. We then apply our results to the recently studied model of random $\textit{k}-qsat.$ Recent works have shown that the satisfiable region extends up to a density of 1 in the large $\textit{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 $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2012-11-05 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 59 Issue Number 5 Page Count 24 Starting Page 1 Ending Page 24

#### Open content in new tab

Source: ACM Digital Library