Physics – Quantum Physics
Scientific paper
2009-11-09
Physics
Quantum Physics
19 pages
Scientific paper
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.
Ambainis Andris
Kempe Julia
Sattath Or
No associations
LandOfFree
A Quantum Lovasz Local Lemma does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Quantum Lovasz Local Lemma, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Quantum Lovasz Local Lemma will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-660411