Quantum Lovász Local Lemma: Shearer's Bound is Tight
arXiv:1804.07055
Abstract
The Lovász Local Lemma (LLL) is a very powerful tool in combinatorics and probability theory to show the possibility of avoiding all bad events under some weakly dependent conditions. In a seminal paper, Ambainis, Kempe, and Sattath (JACM 2012) introduced a quantum version LLL (QLLL) which shows the possibility of avoiding all ``bad" Hamiltonians under some weakly dependent condition, and applied QLLL to the random k-QSAT problem. Sattath, Morampudi, Laumann, and Moessner (PNAS 2015) extended Ambainis, Kempe, and Sattath's result and showed that Shearer's bound is a sufficient condition for QLLL, and conjectured that Shearer's bound is indeed the tight condition for QLLL. In this paper, we affirm this conjecture. Precisely, we prove that Shearer's bound is tight for QLLL, i.e., the relative dimension of the smallest satisfying subspace is completely characterized by the independent set polynomial. Our result implies the tightness of Gilyén and Sattath's algorithm (FOCS 2017), and also implies that the lattice gas partition function fully characterizes quantum satisfiability for almost all Hamiltonians with large enough qudits (Sattath, Morampudi, Laumann and Moessner, PNAS 2015). The commuting LLL (CLLL), which focuses on commuting local Hamiltonians, is also investigated here. We prove that the tight regions of CLLL and QLLL are different in general. This result indicates that it is possible to design an algorithm for CLLL which is still efficient beyond Shearer's bound.
References in corpus (15)
- Fault-tolerant quantum computation by anyons
- The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
- On product, generic and random generic quantum satisfiability
- Unfrustrated Qudit Chains and their Ground States
- A Quantum Lovasz Local Lemma
- The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
- When a local Hamiltonian must be frustration-free
- On preparing ground states of gapped Hamiltonians: An efficient Quantum Lovász Local Lemma
- A new asymptotic enumeration technique: the Lovasz Local Lemma
- Many-body systems with random spatially local interactions
- A constructive commutative quantum Lovasz Local Lemma, and beyond
- An Information-Theoretic Proof of the Constructive Commutative Quantum Lovász Local Lemma
- Unfrustration Condition and Degeneracy of Qudits on Trees
- On the Complexity of Two Dimensional Commuting Local Hamiltonians
- Variable Version Lovász Local Lemma: Beyond Shearer's Bound