Fetching the paper…
Reading the bibliography…
Quantum information and computation provide a fascinating twist on the notion of proofs in computational complexity theory.
On the Einstein–Podolsky–Rosen paradox
J. Bell · 1964
Earlier work this paper cites.
Minimum partition of a matroid into independent subsets
J. Edmonds · 1965
Earlier work this paper cites.
Paths, trees, and flowers
J. Edmonds · 1965
Earlier work this paper cites.
Proposed experiment to test local hidden-variable theories
J. Clauser, M. Horne, A. Shimony, and R. Holt · 1969
Earlier work this paper cites.
The complexity of theorem proving procedures
S. Cook · 1971
Earlier work this paper cites.
Reducibility among combinatorial problems
R. Karp · 1972
Earlier work this paper cites.
Universal sequential search problems (English translation)
L. Levin · 1973
Earlier work this paper cites.
On relating time and space to size and depth
A. Borodin · 1977
Earlier work this paper cites.
Parallel computation for well-endowed rings and space-bounded probabilistic machines
A. Borodin, S. Cook, and N. Pippenger · 1983
Earlier work this paper cites.
On the complexity of matrix group problems I
L. Babai and E. Szemerédi · 1984
Earlier work this paper cites.
The complexity of facets (and some facets of complexity)
C. Papadimitriou and M. Yannakakis · 1984
Earlier work this paper cites.
Trading group theory for randomness
L. Babai · 1985
Earlier work this paper cites.
The knowledge complexity of interactive proof systems
S. Goldwasser, S. Micali, and C. Rackoff · 1985
Earlier work this paper cites.
A fast parallel algorithm for determining all roots of a polynomial with real roots
M. Ben-Or, E. Feig, D. Kozen, and P. Tiwari · 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.
Quantum analogues of the Bell inequalities: The case of two spatially separated domains
B. Tsirel’son · 1987
Earlier work this paper cites.
Arthur–Merlin games: a randomized proof system, and a hierarchy of complexity classes
L. Babai and S. Moran · 1988
Earlier work this paper cites.
Multi-prover interactive proofs: how to remove intractability assumptions
M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson · 1988
Earlier work this paper cites.
On the power of multi-prover interactive protocols
L. Fortnow, J. Rompel, and M. Sipser · 1988
Earlier work this paper cites.
The complexity of perfect zero-knowledge
L. Fortnow · 1989
Earlier work this paper cites.
Complexity-Theoretic Aspects of Interactive Proof Systems
L. Fortnow · 1989
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.
Private coins versus public coins in interactive proof systems
S. Goldwasser and M. Sipser · 1989
Earlier work this paper cites.
Simple unified form for the major no-hidden-variables theorems
D. Mermin · 1990
Earlier work this paper cites.
Incompatible results of quantum measurements
A. Peres · 1990
Earlier work this paper cites.
Statistical zero-knowledge languages can be recognized in two rounds
W. Aiello and J. Håstad · 1991
Earlier work this paper cites.
Local expansion of vertex-transitive graphs and random generation in finite groups
L. Babai · 1991
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.
Two-prover one-round proof systems: Their power and their problems
U. Feige and L. Lovász · 1992
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.
Self-testing/correcting with applications to numerical problems
M. Blum, M. Luby, and R. Rubinfeld · 1993
Earlier work this paper cites.
On non-semisplit extensions, tensor products and exactness of group C ∗ C^{*} -algebras
E. Kirchberg · 1993
Earlier work this paper cites.
Specified precision polynomial root isolation is in NC
C. Neff · 1994
Earlier work this paper cites.
Algorithms for quantum computation: discrete logarithms and factoring
P. Shor · 1994
Earlier work this paper cites.
Interactive proofs and the hardness of approximating cliques
U. Feige, S. Goldwasser, L. Lovász, S. Safra, and M. Szegedy · 1996
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
L. Grover · 1996
Earlier work this paper cites.
Quantum randomness and nondeterminism
E. Knill · 1996
Earlier work this paper cites.
Quantum computability
L. Adleman, J. DeMarrais, and M. Huang · 1997
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
P. Shor · 1997
Earlier work this paper cites.
Towards a Formal Definition of Security for Quantum Protocols
J. van de Graaf · 1997
Earlier work this paper cites.
Quantum circuits with mixed states
D. Aharonov, A. Kitaev, and N. Nisan · 1998
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.
Computing matrix eigenvalues and polynomial zeros where the output is real
D. Bini and V. Pan · 1998
Earlier work this paper cites.
Quantum algorithms revisited
R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca · 1998
Earlier work this paper cites.
Honest verifier statistical zero knowledge equals general statistical zero knowledge
O. Goldreich, A. Sahai, and S. Vadhan · 1998
Earlier work this paper cites.
A parallel repetition theorem
R. Raz · 1998
Earlier work this paper cites.
Complexity limitations on quantum computation
L. Fortnow and J. Rogers · 1999
Earlier work this paper cites.
PSPACE has constant-round quantum interactive proof systems
J. Watrous · 1999
Earlier work this paper cites.
Two-prover protocols—low error at affordable rates
U. Feige and J. Kilian · 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. Nielsen and I. Chuang · 2000
Earlier work this paper cites.
On relationships between statistical zero-knowledge proofs
T. Okamoto · 2000
Earlier work this paper cites.
Succinct quantum proofs for properties of finite groups
J. Watrous · 2000
Earlier work this paper cites.
Bell’s theorem without inequalities and without probabilities for two observers
A. Cabello · 2001
Earlier work this paper cites.
Some optimal inapproximability results
J. Håstad · 2001
Earlier work this paper cites.
Degrees of concealment and bindingness in quantum bit-commitment protocols
R. Spekkens and T. Rudolph · 2001
Cited alongside, same era.
A simple demonstration of Bell’s theorem involving two observers and no probabilities or inequalities
P. Aravind · 2002
Cited alongside, same era.
Zero-knowledge twenty years after its invention
O. Goldreich · 2002
Cited alongside, same era.
Quantum NP - a survey
A. Grilo, I. Kerenidis, and J. Sikora · 2002
Cited alongside, same era.
Classical and Quantum Computation
A. Kitaev, A. Shen, and M. Vyalyi · 2002
Cited alongside, same era.
Limits on the power of quantum statistical zero-knowledge
J. Watrous · 2002
Cited alongside, same era.
Parallel approximation of non-interactive zero-sum quantum games
R. Jain and J. Watrous · 2009
Later among the works it cites.
Using entanglement in quantum multi-prover interactive proofs
J. Kempe, H. Kobayashi, K. Matsumoto, and T. Vidick · 2009
Later among the works it cites.
Computational Distinguishability of Quantum Channels
B. Rosgen · 2009
Later among the works it cites.
Monogamy of non-local quantum correlations
B. Toner · 2009
Later among the works it cites.
Bounding the dimension of bipartite quantum systems
T. Vértesi and K. Pál · 2009
Later among the works it cites.
Zero-knowledge against quantum attacks
J. Watrous · 2009
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Classical deterministic complexity of Edmonds’ problem and quantum entanglement
L. Gurvits · 2003
Cited alongside, same era.
3-local Hamitonian is QMA-complete
J. Kempe and O. Regev · 2003
Cited alongside, same era.
Non-interactive quantum perfect and statistical zero-knowledge
H. Kobayashi · 2003
Cited alongside, same era.
Quantum multi-prover interactive proof systems with limited prior entanglement
H. Kobayashi and K. Matsumoto · 2003
Cited alongside, same era.
Quantum Merlin–Arthur proof systems: Are multiple Merlins more helpful to Arthur?
H. Kobayashi, K. Matsumoto, and T. Yamakami · 2003
Cited alongside, same era.
A complete promise problem for statistical zero-knowledge
A. Sahai and S. Vadhan · 2003
Cited alongside, same era.
A. Ben-Aroya, O. Schwartz, and A. Ta-Shma · 2010
Later among the works it cites.
Strong NP-hardness of the quantum separability problem
S. Gharibian · 2010
Later among the works it cites.
Equilibrium value method for the proof of QIP=PSPACE
X. Wu · 2010
Later among the works it cites.
Quantum interactive proofs with short messages
S. Beigi, P. Shor, and J. Watrous · 2011
Later among the works it cites.
A quasipolynomial-time algorithm for the quantum separability problem
F. Brandão, M. Christandl, and J. Yard · 2011
Later among the works it cites.
Efficient algorithm for a quantum analogue of 2-SAT
S. Bravyi · 2011
Later among the works it cites.
Rank-one quantum games
T. Cooney, M. Junge, C. Palazuelos, and D. Pérez-García · 2011
Later among the works it cites.
Classical cryptographic protocols in a quantum world
S. Hallgren, A. Smith, and F. Song · 2011
Later among the works it cites.
QIP = PSPACE
R. Jain, Z. Ji, S. Upadhyay, and J. Watrous · 2011
Later among the works it cites.
Connes’ embedding problem and Tsirelson’s problem
M. Junge, M. Navascues, C. Palazuelos, D. Perez-Garcia, V. Scholz, and R. Werner · 2011
Later among the works it cites.
Entangled games are hard to approximate
J. Kempe, H. Kobayashi, K. Matsumoto, B. Toner, and T. Vidick · 2011
Later among the works it cites.
Parallel repetition of entangled games
J. Kempe and T. Vidick · 2011
Later among the works it cites.
Lower bounds on the entanglement needed to play XOR non-local games
W. Slofstra · 2011
Later among the works it cites.
Tsirelson’s problem and Kirchberg’s conjecture
T. Fritz · 2012
Later among the works it cites.
Hardness of approximation for quantum problems
S. Gharibian and J. Kempe · 2012
Later among the works it cites.
Quantum interactive proofs with weak error bounds
T. Ito, H. Kobayashi, and J. Watrous · 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.
Robust self-testing of the singlet
M. McKague, T. Yang, and V. Scarani · 2012
Later among the works it cites.
A classical leash for a quantum system: Command of quantum systems via rigidity of CHSH games
B. Reichardt, F. Unger, and U. Vazirani · 2012
Later among the works it cites.
Quantum proofs of knowledge
D. Unruh · 2012
Later among the works it cites.
Guest column: the quantum PCP conjecture
D. Aharonov, I. Arad, and T. Vidick · 2013
Later among the works it cites.
Improved soundness for QMA with multiple provers
A. Chiesa and M. Forbes · 2013
Later among the works it cites.
Quantum 3-SAT is QMA1-complete
D. Gosset and D. Nagaj · 2013
Later among the works it cites.
Parallel approximation of min-max problems
G. Gutoski and X. Wu · 2013
Later among the works it cites.
Testing product states, quantum Merlin–Arthur games and tensor optimization
A. Harrow and A. Montanaro · 2013
Later among the works it cites.
Stronger methods of making quantum interactive proofs perfectly complete
H. Kobayashi, F. Le Gall, and H. Nishimura · 2013
Later among the works it cites.
Coherent state exchange in multi-prover quantum interactive proof systems
D. Leung, B. Toner, and J. Watrous · 2013
Later among the works it cites.
About the Connes embedding conjecture
N. Ozawa · 2013
Later among the works it cites.
Quantum XOR games
O. Regev and T. Vidick · 2013
Later among the works it cites.
Classical command of quantum systemes
B. Reichardt, F. Unger, and U. Vazirani · 2013
Later among the works it cites.
A full characterization of quantum advice
S. Aaronson and A. Drucker · 2014
Later among the works it cites.
On physical problems that are slightly more difficult than QMA
A. Ambainis · 2014
Later among the works it cites.
Quantum attacks on classical proof systems: The hardness of quantum rewinding
A. Ambainis, A. Rosmanis, and D. Unruh · 2014
Later among the works it cites.
QMA-complete problems
A. Bookatz · 2014
Later among the works it cites.
Parallel repetition of entangled games with exponential decay via the superposed information cost
A. Chailloux and G. Scarpa · 2014
Later among the works it cites.
Complexity classification of local Hamiltonian problems
T. Cubitt and A. Montanaro · 2014
Later among the works it cites.
Analytical approach to parallel repetition
I. Dinur and D. Steurer · 2014
Later among the works it cites.
A parallel repetition theorem for entangled projection games
I. Dinur, D. Steurer, and T. Vidick · 2014
Later among the works it cites.
Ground state connectivity of local Hamiltonians
S. Gharibian and J. Sikora · 2014
Later among the works it cites.
QMA with subset state witnesses
A. Grilo, I. Kerenidis, and J. Sikora · 2014
Later among the works it cites.
Two-message quantum interactive proofs and the quantum separability problem
P. Hayden, K. Milner, and M. Wilde · 2014
Later among the works it cites.
Parallelization of entanglement-resistant multi-prover interactive proofs
T. Ito · 2014
Later among the works it cites.
A parallel repetition theorem for entangled two-player one-round games under product distributions
R. Jain, A. Pereszlényi, and P. Yao · 2014
Later among the works it cites.
Anchoring games for parallel repetition
M. Bavarian, T. Vidick, and H. Yuen · 2015
Later among the works it cites.
Small value parallel repetition for general games
Mark Braverman and Ankit Garg · 2015
Later among the works it cites.
A multiprover interactive proof system for the local Hamiltonian problem
J. Fitzsimons and T. Vidick · 2015
Later among the works it cites.
Quantum interactive proofs and the complexity of separability testing
G. Gutoski, P. Hayden, K. Milner, and M. Wilde · 2015
Later among the works it cites.
Classical verification of quantum proofs
Z. Ji · 2015
Later among the works it cites.
Parallel repetition for entangled k k -player games via fast quantum search
X. Wu, K.-M. Chung, and H. Yuen · 2015
Later among the works it cites.