On preparing ground states of gapped Hamiltonians: An efficient Quantum Lovász Local Lemma
arXiv:1611.08571 · doi:10.1109/FOCS.2017.47
Abstract
A frustration-free local Hamiltonian has the property that its ground state minimises the energy of all local terms simultaneously. In general, even deciding whether a Hamiltonian is frustration-free is a hard task, as it is closely related to the QMA1-complete quantum satisfiability problem (QSAT) -- the quantum analogue of SAT, which is the archetypal NP-complete problem in classical computer science. This connection shows that the frustration-free property is not only relevant to physics but also to computer science. The Quantum Lovász Local Lemma (QLLL) provides a sufficient condition for frustration-freeness. A natural question is whether there is an efficient way to prepare a frustration-free state under the conditions of the QLLL. Previous results showed that the answer is positive if all local terms commute. In this work we improve on the previous constructive results by designing an algorithm that works efficiently for non-commuting terms as well, assuming that the system is "uniformly" gapped, by which we mean that the system and all its subsystems have an inverse polynomial energy gap. Also, our analysis works under the most general condition for the QLLL, known as Shearer's bound. Similarly to the previous results, our algorithm has the charming feature that it uses only local measurement operations corresponding to the local Hamiltonian terms.
arXiv comment39 pages
References in corpus (16)
- Fault-tolerant quantum computation by anyons
- A Class of Quantum Error-Correcting Codes Saturating the Quantum Hamming Bound
- An Area Law for One Dimensional Quantum Systems
- Quantum Computation by Adiabatic Evolution
- Undecidability of the Spectral Gap (short version)
- The power of quantum systems on a line
- The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma
- Rapid adiabatic preparation of injective PEPS and Gibbs states
- Quantum Computing in Plato's Cave
- A Quantum Lovasz Local Lemma
- When a local Hamiltonian must be frustration-free
- A constructive commutative quantum Lovasz Local Lemma, and beyond
- An Information-Theoretic Proof of the Constructive Commutative Quantum Lovász Local Lemma
- A Constructive Quantum Lovász Local Lemma for Commuting Projectors
- A constructive proof of the general Lovasz Local Lemma
- Transfer-Matrix Study of Hard-Core Singularity for Hard-Square Lattice Gas
Cited by in corpus (10)
- Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
- Scalable Benchmarks for Gate-Based Quantum Computers
- The Pursuit of Uniqueness: Extending Valiant-Vazirani Theorem to the Probabilistic and Quantum Settings
- Fault-tolerant quantum algorithms for quantum molecular systems: A survey
- The complexity of simulating local measurements on quantum systems
- The pair-flip model: a very entangled translationally invariant spin chain
- On efficiently solvable cases of Quantum k-SAT
- Total Functions in QMA
- Measurement-driven quantum computing: Performance of a 3-SAT solver
- Quantum Lovász Local Lemma: Shearer's Bound is Tight