Or Sattath, "A Quantum Lovasz Local Lemma"

Thu, Jun 10, 2010, 12:00 pm to 1:30 pm
Jadwin 303

ABSTRACT: The Lovasz Local Lemma is a powerful tool in probability theory to show the existence of combinatorial objects meeting a prescribed collection of ``weakly dependent" criteria. We present a quantum generalization of this result, which replaces probabilities with a weaker notion of relative dimension and allows to lower bound the intersection size of vector spaces under certain independence conditions. Our result immediately applies to the Bounded Occurrence K-QSAT problem: We show for instance that if each qubit appears in at most 2^k/(e \cdot k) projectors, there is a joint satisfiable state. We then apply our results to the recently studied model of RANDOM-K-QSAT with the density (ratio of projectors to qubits) as a control parameter. Recent works have shown that the satisfiable region extends up to a density of $1$ in the large k limit. 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 had limited previous approaches to product states. This is joint work with Andris Ambainis (Univesity of Latvia) and Julia Kempe (Tel-Aviv University). CONTACT: Chris Laumann. SPEAKER AFFILIATION: Hebrew U. and Tel Aviv U. SPONSOR: Chris Laumann.