A constructive commutative quantum Lovasz Local Lemma, and beyond
arXiv:1112.1413
Abstract
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 comment43 pages, 2 conjectures, no figures; unresolved gap in the proof; see arXiv:1311.6474 or arXiv:1310.7766 for correct proofs of the symmetric case
References in corpus (9)
- Quantum Metropolis Sampling
- Strong Converse to the Quantum Channel Coding Theorem
- A quantum version of Wielandt's inequality
- Coding Theorems of Quantum Information Theory
- Preparing projected entangled pair states on a quantum computer
- A Quantum Lovasz Local Lemma
- Commutative version of the k-local Hamiltonian problem and common eigenspace problem
- On the complexity of Commuting Local Hamiltonians, and tight conditions for Topological Order in such systems
- Cooling and Low Energy State Preparation for 3-local Hamiltonians are FQMA-complete
Cited by in corpus (5)
- On preparing ground states of gapped Hamiltonians: An efficient Quantum Lovász Local Lemma
- An Information-Theoretic Proof of the Constructive Commutative Quantum Lovász Local Lemma
- A Constructive Quantum Lovász Local Lemma for Commuting Projectors
- Total Functions in QMA
- Quantum Lovász Local Lemma: Shearer's Bound is Tight