A quantum Lovász local lemma

DOI10.1145/2371656.2371659MaRDI QIDQ5395693zbMATH OpenOpenAlexWikidataFDO

Authors Or Sattath, Andris Ambainis, Julia Kempe

Publication date 17 February 2014

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0911.1696

zbMATH Keywords

local lemmaprobabilistic methodquantum computationquanum SATrandom quantum SAT

Mathematics Subject Classification ID

Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Combinatorial probability (60C05) Quantum algorithms and complexity in the theory of computing (68Q12) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

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/(ecdotk)$ 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.

Recommendations

• A quantum Lovász local lemma
• Quantum Lovász local lemma: Shearer's bound is tight
• The Lovász Local Lemma and Satisfiability
• Random quantum satisfiability
• A constructive proof of the Lovász local lemma

Cited in

(12)

• On efficiently solvable cases of quantum \(k\)-SAT
• A local quantum version of the Kolmogorov theorem
• Total functions in QMA
• A quantum Lovász local lemma
• Quantum max-flow/min-cut
• A Haar component for quantum limits on locally symmetric spaces
• Quantum Loewner evolution
• Quantum Lovász local lemma: Shearer's bound is tight
• Area laws and tensor networks for maximally mixed ground states
• Variable version Lovász local lemma: a tale of two boundaries
• Testing quantum satisfiability
• Bounds on the ground state energy of quantum p-spin Hamiltonians

This page was built for publication: A quantum Lovász local lemma

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5395693)