Fetching the paper…
Reading the bibliography…
This article surveys quantum computational complexity, with a focus on three fundamental notions: polynomial-time quantum computations, the efficient verification of quantum proofs, and quantum interactive proof systems.
Positive functions on C ∗ C^{\ast} -algebras
W. F. Stinespring · 1955
Earlier work this paper cites.
On the Einstein-Podolsky-Rosen paradox
J. Bell · 1964
Earlier work this paper cites.
Cramming more components onto integrated circuits
G. Moore · 1965
Earlier work this paper cites.
The complexity of theorem proving procedures
S. Cook · 1972
Earlier work this paper cites.
Logical reversibility of computation
C. Bennett · 1973
Earlier work this paper cites.
Universal 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.
Two theorems on random polynomial time
L. Adleman · 1978
Earlier work this paper cites.
The complexity of computing the permanent
L. Valiant · 1979
Earlier work this paper cites.
Reversible computing
T. Toffoli · 1980
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.
Simulating physics with computers
R. Feynman · 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 promise problems with applications to public-key cryptography
S. Even, A. Selman, and Y. Yacobi · 1984
Earlier work this paper cites.
Trading group theory for randomness
L. Babai · 1985
Earlier work this paper cites.
Quantum theory, the Church–Turing principle and the universal quantum computer
D. Deutsch · 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.
Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes
L. Babai and S. Moran · 1988
Earlier work this paper cites.
Quantum computational networks
D. Deutsch · 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.
Non-deterministic exponential time has two-prover interactive protocols
L. Babai, L. Fortnow, and C. Lund · 1991
Earlier work this paper cites.
PP is as hard as the polynomial-time hierarchy
S. Toda · 1991
Earlier work this paper cites.
Bounded round interactive proofs in finite groups
L. Babai · 1992
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.
Quantum complexity theory (preliminary abstract)
E. Bernstein and U. Vazirani · 1993
Earlier work this paper cites.
Gap-definable counting classes
S. Fenner, L. Fortnow, and S. Kurtz · 1994
Earlier work this paper cites.
Computational Complexity
C. Papadimitriou · 1994
Earlier work this paper cites.
Algorithms for quantum computation: discrete logarithms and factoring
P. Shor · 1994
Earlier work this paper cites.
PP is closed under intersection
R. Beigel, N. Reingold, and D. Spielman · 1995
Earlier work this paper cites.
Approximation by quantum circuits
E. Knill · 1995
Earlier work this paper cites.
Relationships among PL, #L, and the determinant
E. Allender and M. Ogihara · 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.
Strengths and weaknesses of quantum computing
C. Bennett, E. Bernstein, G. Brassard, and U. Vazirani · 1997
Cited alongside, same era.
Quantum complexity theory
E. Bernstein and U. Vazirani · 1997
Cited alongside, same era.
Making games short
U. Feige and J. Kilian · 1997
Cited alongside, same era.
Counting complexity
L. Fortnow · 1997
Cited alongside, same era.
Quantum computations: algorithms and error correction
A. Kitaev · 1997
Cited alongside, same era.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
P. Shor · 1997
Cited alongside, same era.
Quantum circuits with mixed states
D. Aharonov, A. Kitaev, and N. Nisan · 1998
Polynomial time quantum computation with advice
H. Nishimura and T. Yamakami · 2004
Later among the works it cites.
Limitations of quantum advice and one-way communication
S. Aaronson · 2005
Later among the works it cites.
Bounds on the power of constant-depth quantum circuits
S. Fenner, F. Green S. Homer, and Y. Zhang · 2005
Later among the works it cites.
On promise problems (a survey in memory of Shimon Even [1935–2004])
O. Goldreich · 2005
Later among the works it cites.
Non-identity-check is QMA-complete
D. Janzing, P. Wocjan, and T. Beth · 2005
Later among the works it cites.
Quantum Arthur-Merlin games
C. Marriott and J. Watrous · 2005
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Proof verification and the hardness of approximation problems
S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy · 1998
Cited alongside, same era.
Probabilistic checking of proofs: a new characterization of NP
S. Arora and S. Safra · 1998
Cited alongside, same era.
Free bits, PCPs, and non-approximability – towards tight results
M. Bellare, O. Goldreich, and M. Sudan · 1998
Cited alongside, same era.
Complexity limitations on quantum computation
L. Fortnow and J. Rogers · 1999
Cited alongside, same era.
Comparing entropies in statistical zero-knowledge with applications to the structure of SZK
O. Goldreich and S. Vadhan · 1999
Cited alongside, same era.
R. Oliveira and B. Terhal · 2005
Later among the works it cites.
Quantum information and the PCP theorem
R. Raz · 2005
Later among the works it cites.
On the hardness of distinguishing mixed-state quantum computations
B. Rosgen and J. Watrous · 2005
Later among the works it cites.
QMA/qpoly is contained in PSPACE/poly: de-Merlinizing quantum protocols
S. Aaronson · 2006
Later among the works it cites.
Complexity Theory: A Modern Approach (Preliminary web draft)
S. Arora and B. Barak · 2006
Later among the works it cites.
The complexity of the local Hamiltonian problem
J. Kempe, A. Kitaev, and O. Regev · 2006
Later among the works it cites.
Consistency of local density matrices is QMA-complete
Y.-K. Liu · 2006
Later among the works it cites.
Zero-knowledge against quantum attacks
J. Watrous · 2006
Later among the works it cites.
Entanglement in interactive proof systems with binary answers
S. Wehner · 2006
Later among the works it cites.
Quantum versus classical proofs and advice
S. Aaronson and G. Kuperberg · 2007
Later among the works it cites.
The power of quantum systems on a line
D. Aharonov, D. Gottesman, S. Irani, and J. Kempe · 2007
Later among the works it cites.
Adiabatic quantum computation is equivalent to standard quantum computation
D. Aharonov, W. van Dam, J. Kempe, Z. Landau, S. Lloyd, and O. Regev · 2007
Later among the works it cites.
On the complexity of computing zero-error and Holevo capacity of quantum channels
S. Beigi and P. Shor · 2007
Later among the works it cites.
Quantum expanders and the quantum entropy difference problem
A. Ben-Aroya and A. Ta-Shma · 2007
Later among the works it cites.
Small depth quantum circuits
D. Bera, F. Green, and S. Homer · 2007
Later among the works it cites.
All languages in NP have very short quantum proofs
H. Blier and A. Tapp · 2007
Later among the works it cites.
Perfect parallel repetition theorem for quantum XOR proof systems
R. Cleve, W. Slofstra, F. Unger, and S. Upadhyay · 2007
Later among the works it cites.
The PCP theorem by gap amplification
I. Dinur · 2007
Later among the works it cites.
Toward a general theory of quantum games
G. Gutoski and J. Watrous · 2007
Later among the works it cites.
An Introduction to Quantum Computing
P. Kaye, R. Laflamme, and M. Mosca · 2007
Later among the works it cites.
Entangled games are hard to approximate
J. Kempe, H. Kobayashi, K. Matsumoto, B. Toner, and T. Vidick · 2007
Later among the works it cites.
The unique games conjecture with entangled provers is false
J. Kempe, O. Regev, and B. Toner · 2007
Later among the works it cites.
Quantum computational complexity of the n
Y.-K. Liu, M. Christandl, and F. Verstraete · 2007
Later among the works it cites.
A quantum time-space lower bound for the counting hierarchy
D. van Melkebeek and T. Watson · 2007
Later among the works it cites.
The complexity of zero knowledge
S. Vadhan · 2007
Later among the works it cites.
The power of unentanglement
S. Aaronson, S. Beigi, A. Drucker, B. Fefferman, and P. Shor · 2008
Closest in time.
Using entanglement in quantum multi-prover interactive proofs
J. Kempe, H. Kobayashi, K. Matsumoto, and T. Vidick · 2008
Closest in time.
General properties of quantum zero-knowledge proofs
H. Kobayashi · 2008
Closest in time.
Distinguishing short quantum computations
B. Rosgen · 2008
Closest in time.