Fetching the paper…
Reading the bibliography…
The local Hamiltonian problem is famously complete for the class QMA, the quantum analogue of NP.
Computational complexity
C. H. Papadimitriou · 1994
Earlier work this paper cites.
Expander codes
M. Sipser, D. Spielman · 1996
Earlier work this paper cites.
Proof verification and intractability of
S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy · 1998
Earlier work this paper cites.
Probabilistic checking of proofs: A new characterization of 𝖭𝖯 {\sf{NP}}
S. Arora, S. Safra · 1998
Earlier work this paper cites.
Some optimal inapproximability results
J. Håstad · 2001
Earlier work this paper cites.
Randomness conductors and constant-degree lossless expanders
M. R. Capalbo, O. Reingold, S. Vadhan, and A. Wigderson · 2002
Earlier work this paper cites.
On the power of unique 2-prover 1-round games
S. Khot (2002) · 2002
Earlier work this paper cites.
Classical and quantum computation, volume 47 of Graduate Studies in Mathematics. AMS, 2002
A. Yu. Kitaev, A. H. Shen, and M. N. Vyalyi · 2002
Earlier work this paper cites.
Fault-tolerant quantum computation by anyons
A. Yu. Kitaev · 2003
Earlier work this paper cites.
Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation
D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, O. Regev · 2004
Earlier work this paper cites.
The Complexity of the Local Hamiltonian Problem
J. Kempe, A. Kitaev, O. Regev · 2004
Earlier work this paper cites.
Commutative version of the k-local Hamiltonian problem and common eigenspace problem
S. Bravyi, M. Vyalyi · 2005
Earlier work this paper cites.
String-net condensation: A physical mechanism for topological phases
Michael A. Levin, Xiao-Gang Wen, · 2005
Earlier work this paper cites.
Approximation algorithms for unique games
L. Trevisan · 2005
Cited alongside, same era.
The quantum 𝖯𝖢𝖯 {\sf{PCP}} manifesto
S. Aaronson · 2006
Cited alongside, same era.
Efficient algorithm for a quantum analogue of 2-SAT
S. Bravyi · 2006
Cited alongside, same era.
The 𝖯𝖢𝖯 {\sf{PCP}} theorem by gap amplification
I. Dinur · 2006
Cited alongside, same era.
Unique games on expanding constraint graphs are easy
S. Arora, S. Khot, A. Kolla, D. Steurer, M. Tulsiani, N.K. Vishnoi · 2008
Cited alongside, same era.
Simulation of Many-Body Hamiltonians using Perturbation Theory with Bounded-Strength Interactions
S. Bravyi, D. P. DiVincenzo, D. Loss, and B. M. Terhal · 2008
Cited alongside, same era.
Computational complexity of interacting electrons and fundamental limitations of density functional theory
N. Schuch, F. Verstraete · 2009
Later among the works it cites.
Subexponential Algorithms for Unique Games and Related Problems
S. Arora, B. Barak, D. Steurer · 2010
Later among the works it cites.
Graph expansion and the unique games conjecture
P. Raghavendra, D. Steurer · 2010
Later among the works it cites.
On the complexity of Commuting Local Hamiltonians, and tight conditions for Topological Order in such systems
D. Aharonov, L. Eldar · 2011
Later among the works it cites.
A note about a partial no-go theorem for quantum 𝖯𝖢𝖯 {\sf{PCP}}
I. Arad · 2011
Later among the works it cites.
Complexity of commuting Hamiltonians on a square lattice of qubits
N. Schuch · 2011
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
The complexity of quantum spin systems on a two-dimensional square lattice
R. Oliveira, B. M. Terhal · 2008
Cited alongside, same era.
The Detectability Lemma and Quantum Gap Amplification
D. Aharonov, I. Arad, Z. Landau, and U. Vazirani · 2009
Cited alongside, same era.
The power of quantum systems on a line
D. Aharonov, D. Gottesman, S. Irani, J. Kempe · 2009
Cited alongside, same era.
Computational Complexity: A Modern Approach
S. Arora and B. Barak · 2009
Cited alongside, same era.
Classical approximation schemes for the ground-state energy of quantum and classical Ising spin Hamiltonians on planar graphs
N. Bansal, S. Bravyi, and B.M. Terhal · 2009
Cited alongside, same era.
The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems
D. Gottesman, S. Irani · 2009
Cited alongside, same era.
Later among the works it cites.
Approximation algorithms for QMA complete Problems
S. Gharibian, J. Kempe · 2012
Later among the works it cites.
Hardness of Approximation for Quantum Problems
S. Gharibian, J. Kempe · 2012
Later among the works it cites.
Hamiltonian Complexity
Tobias Osborne, · 2012
Later among the works it cites.
Reductions between Expansion Problems
P. Raghavendra, D. Steurer, M. Tulsiani · 2012
Later among the works it cites.
The Quantum 𝖯𝖢𝖯 {\sf{PCP}} Conjecture
D. Aharonov, I. Arad, and T. Vidick · 2013
Closest in time.
Trivial Low Energy States for Commuting Hamiltonians, and the Quantum 𝖯𝖢𝖯 {\sf{PCP}} Conjecture
M. B. Hastings · 2013
Closest in time.