Understand
The local Hamiltonian problem plays the equivalent role of SAT in quantum complexity theory.
- Understanding the complexity of the intermediate case in which the constraints are quantum but all local terms in the Hamiltonian commute, is of importance for conceptual, physical and computational complexity reasons.
- Bravyi and Vyalyi showed in 2003, using a clever application of the representation theory of C*-algebras, that if the terms in the Hamiltonian are all two-local, the problem is in NP, and the entanglement in the ground states is local.
- The general case remained open since then.
Built on
Quantum codes on a lattice with boundary
S. Bravyi, A. Kitaev · 1998
Earlier work this paper cites.
Classical and Quantum Computation (Graduate Studies in Mathematics)
A. Yu. Kitaev, A. H. Shen, M. N. Vyalyi · 2002
Earlier work this paper cites.
Fault-tolerant quantum computation by anyons
A. Kitaev · 2003
Earlier work this paper cites.
Commutative version of the k-local Hamiltonian problem and common eigenspace problem
S. Bravyi, M. Vyalyi · 2004
Earlier work this paper cites.
Lieb-Schultz-mattis in higher dimensions
M. B. Hastings · 2004
Earlier work this paper cites.
Similar
The Complexity of the Local Hamiltonian Problem
J. Kempe, A. Kitaev, O. Regev · 2004
Cited alongside, same era.
Efficient algorithm for a quantum analogue of 2-SAT
S. Bravyi · 2006
Cited alongside, same era.
Lieb-Robinson Bounds and the Generation of Correlations and Topological Quantum Order
S. Bravyi, M. B. Hastings, F. Verstraete · 2006
Cited alongside, same era.
An area law for one-dimensional quantum systems
M. B. Hastings · 2007
Cited alongside, same era.
G. Vidal · 2007
Cited alongside, same era.
Adaptive Quantum Computation, Constant Depth Quantum Circuits and Arthur-Merlin Games
B. M. Terhal, D. P. DiVincenzo
Cited in the paper.
Then
The Detectability Lemma and Quantum Gap Amplification
D. Aharonov, I. Arad, Z. Landau, U. Vazirani · 2008
Later among the works it cites.
Entanglement Renormalization and Topological Order
M. Aguado, G. Vidal · 2008
Later among the works it cites.
The complexity of quantum spin systems on a two-dimensional square lattice
R. Oliveira, B. M. Terhal · 2008
Later among the works it cites.
The power of quantum systems on a line
D. Aharonov, D.Gottesman, S. Irani, J. Kempe · 2009
Later among the works it cites.
A short proof of stability of topological order under local perturbations
S. Bravyi, M. B. Hastings · 2010
Later among the works it cites.
Beyond the bibliography
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…