An Information-Theoretic Proof of the Constructive Commutative Quantum Lovász Local Lemma
arXiv:1311.6474
Abstract
The Quantum Lovász Local Lemma (QLLL) [AKS12] establishes non-constructively that any quantum system constrained by a local Hamiltonian has a zero-energy ground state, if the local Hamiltonian terms overlap only in a certain restricted way. In this paper, we present an efficient quantum algorithm to prepare this ground state for the special case of commuting projector terms. The related classical problem has been open for more than 34 years. Our algorithm follows the breakthrough ideas of Moser's [Moser09] classical algorithm and lifts his information theoretic argument to the quantum setting. A similar result has been independently published by Arad and Sattath [AS13] recently.
arXiv comment7 pages, 9 pages appendix
References in corpus (8)
- Hamiltonian complexity
- Coding Theorems of Quantum Information Theory
- Quantum computation, quantum state engineering, and quantum phase transitions driven by dissipation
- Preparing topological PEPS on a quantum computer
- A Quantum Lovasz Local Lemma
- A constructive commutative quantum Lovasz Local Lemma, and beyond
- A Constructive Quantum Lovász Local Lemma for Commuting Projectors
- Complexity of commuting Hamiltonians on a square lattice of qubits