Fetching the paper…
Reading the bibliography…
The classical PCP theorem is arguably the most important achievement of classical complexity theory in the past quarter century.
Can quantum-mechanical description of physical reality be considered complete?
A. Einstein, B. Podolsky, and N. Rosen · 1935
Earlier work this paper cites.
On the Einstein-Podolsky-Rosen paradox
J. S. Bell · 1964
Earlier work this paper cites.
Proposed experiment to test local hidden-variable theories
J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt · 1969
Earlier work this paper cites.
The complexity of theorem-proving procedures
S. A. Cook · 1971
Earlier work this paper cites.
Reducibility Among Combinatorial Problems
R. M. Karp · 1972
Earlier work this paper cites.
Universal sequential search problems
L. A. Levin · 1973
Earlier work this paper cites.
Experimental test of Bell’s inequalities using time-varying analyzers
A. Aspect, J. Dalibard, and G. Roger · 1982
Earlier work this paper cites.
Simulating physics with computers
R. P. Feynman · 1982
Earlier work this paper cites.
A single quantum cannot be cloned
W. K. Wootters and W. H. Zurek · 1982
Earlier work this paper cites.
Trading group theory for randomness
L. Babai · 1985
Earlier work this paper cites.
Quantum mechanical computers
R. P. Feynman · 1986
Earlier work this paper cites.
NP is as easy as detecting unique solutions
L. Valiant and V. Vazirani · 1986
Earlier work this paper cites.
The knowledge complexity of interactive proof systems
S. Goldwasser, S. Micali, and C. Rackoff · 1989
Earlier work this paper cites.
Non-deterministic exponential time has two-prover interactive protocols
L. Babai, L. Fortnow, and C. Lund · 1991
Earlier work this paper cites.
Proofs that yield nothing but their validity for all languages in NP have zero-knowledge proof systems
O. Goldreich, S. Micali, and A. Wigderson · 1991
Earlier work this paper cites.
Algebraic methods for interactive proof systems
C. Lund, L. Fortnow, H. Karloff, and N. Nisan · 1992
Earlier work this paper cites.
IP = PSPACE
A. Shamir · 1992
Earlier work this paper cites.
Quantum randomness and nondeterminism
E. Knill · 1996
Earlier work this paper cites.
Proof verification and the hardness of approximation problems
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 NP
S. Arora and S. Safra · 1998
Earlier work this paper cites.
Lecture given at the Hebrew University, Jerusalem, Israel
A. Kitaev, 1999 · 1999
Earlier work this paper cites.
Distributed entanglement
V. Coffman, J. Kundu, and W. K. Wootters · 2000
Earlier work this paper cites.
Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
A. Kitaev and J. Watrous · 2000
Earlier work this paper cites.
Quantum Computation and Quantum Information
M. A. Nielsen and I. L. Chuang · 2000
Earlier work this paper cites.
Quantum NP — a survey
D. Aharonov and T. Naveh · 2002
Earlier work this paper cites.
Topological quantum memory
E. Dennis, A. Kitaev, A. Landahl, and J. Preskill · 2002
Earlier work this paper cites.
Classical and Quantum Computation
A. Kitaev, A. Shen, and M. Vyalyi · 2002
Cited alongside, same era.
Fault-tolerant quantum computation by anyons
A. Y. Kitaev · 2003
Cited alongside, same era.
3-local hamiltonian is QMA-complete
J. Kempe and O. Regev · 2003
Cited alongside, same era.
QMA=PP implies that PP contains PH
M. Vyalyi · 2003
Cited alongside, same era.
Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation
D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev · 2004
Cited alongside, same era.
Robust PCPs of proximity, shorter PCPs and applications to coding
E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan, and S. Vadhan · 2004
Cited alongside, same era.
Computational complexity: a modern approach
S. Arora and B. Barak · 2009
Later among the works it cites.
The power of quantum systems on a line
D. Aharonov, D. Gottesman, S. Irani, and J. Kempe · 2009
Later among the works it cites.
The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems
D. Gottesman and S. Irani · 2009
Later among the works it cites.
Computational complexity of interacting electrons and fundamental limitations of density functional theory
N. Schuch and F. Verstraete · 2009
Later among the works it cites.
Colloquium: Area laws for the entanglement entropy
J. Eisert, M. Cramer, and M. B. Plenio · 2010
Later among the works it cites.
QIP = PSPACE
R. Jain, Z. Ji, S. Upadhyay, and J. Watrous · 2010
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
R. Cleve, P. Høyer, B. Toner, and J. Watrous · 2004
Cited alongside, same era.
Assignment testers: Towards a combinatorial proof of the PCP-theorem
I. Dinur and O. Reingold · 2004
Cited alongside, same era.
Quantum Arthur-Merlin games
C. Marriott and J. Watrous · 2005
Cited alongside, same era.
The quantum PCP manifesto
S. Aaronson · 2006
Cited alongside, same era.
Lieb-Robinson bounds and the generation of correlations and topological quantum order
S. Bravyi, M. B. Hastings, and F. Verstraete · 2006
Cited alongside, same era.
Expander graphs and their applications
S. Hoory, N. Linial, and A. Wigderson · 2006
Cited alongside, same era.
On the complexity of commuting local Hamiltonians, and tight conditions for topological order in such systems
D. Aharonov and L. Eldar · 2011
Later among the works it cites.
A note about a partial no-go theorem for quantum PCP
I. Arad · 2011
Later among the works it cites.
Approximation algorithms for QMA-complete problems
S. Gharibian and J. Kempe · 2011
Later among the works it cites.
Topological order at nonzero temperature
M. B. Hastings · 2011
Later among the works it cites.
Complexity of commuting Hamiltonians on a square lattice of qubits
N. Schuch · 2011
Later among the works it cites.
Matrix product operators and central elements: Classical description of a quantum state
M. B. Hastings · 2012
Later among the works it cites.
A multi-prover interactive proof for NEXP sound against entangled provers
T. Ito and T. Vidick · 2012
Later among the works it cites.
On the power of a unique quantum witness
R. Jain, I. Kerenidis, G. Kuperberg, M. Santha, O. Sattath, and S. Zhang · 2012
Later among the works it cites.
Achieving perfect completeness in classical-witness quantum merlin-arthur proof systems
S. Jordan, H. Kobayashi, D. Nagaj, and H. Nishimura · 2012
Later among the works it cites.
Approximating CSPs with global cardinality constraints using SDP hierarchies
P. Raghavendra and N. Tan · 2012
Later among the works it cites.
Approximating the commuting local Hamiltonian problem on small-set expanders is in NP
D. Aharonov and L. Eldar · 2013
Closest in time.
Quantum locally testable codes
D. Aharonov and L. Eldar · 2013
Closest in time.
Product-state approximations to quantum ground states
F. G. Brandao and A. W. Harrow · 2013
Closest in time.
Commutative version of the local Hamiltonian problem and common eigenspace problem
S. Bravyi and M. Vyalyi · 2013
Closest in time.
M. H. Freedman and M. B. Hastings · 2013
Closest in time.
Trivial low energy states for commuting Hamiltonians, and the quantum PCP conjecture
M. B. Hastings · 2013
Closest in time.
Testing product states, quantum Merlin-Arthur games and tensor optimization
A. Harrow and A. Montanaro · 2013
Closest in time.
One-sided error QMA with shared EPR pairs – a simpler proof
A. Pereszlényi · 2013
Closest in time.
A classical leash for a quantum system: command of quantum systems via rigidity of CHSH games
B. W. Reichardt, F. Unger, and U. Vazirani · 2013
Closest in time.
Three-player entangled XOR games are NP-hard to approximate
T. Vidick · 2013
Closest in time.