Fetching the paper…
Reading the bibliography…
We prove that the complexity class QIP, which consists of all problems having quantum interactive proof systems, is contained in PSPACE.
Fast parallel matrix inversion algorithms
L. Csanky · 1976
Earlier work this paper cites.
On relating time and space to size and depth
A. Borodin · 1977
Earlier work this paper cites.
Fast parallel matrix and GCD computations
A. Borodin, J. von zur Gathen, and J. Hopcroft · 1982
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.
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.
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.
The optimum prover lies in PSPACE
P. Feldman · 1986
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.
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.
Proofs that yield nothing but their validity or 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
Cited alongside, same era.
IP = = PSPACE
A. Shamir · 1992
Cited alongside, same era.
IP = = PSPACE: simplified proof
A. Shen · 1992
Cited alongside, same era.
Parallel linear algebra
J. von zur Gathen · 1993
Cited alongside, same era.
Specified precision polynomial root isolation is in NC
C. A. Neff · 1994
Cited alongside, same era.
Matrix Analysis
R. Bhatia · 1997
Cited alongside, same era.
Making games short
U. Feige and J. Kilian · 1997
Cited alongside, same era.
Fast algorithms for approximate semidefinite programming using the multiplicative weights update method
S. Arora, E. Hazan, and S. Kale · 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.
Quantum Arthur-Merlin games
C. Marriott and J. Watrous · 2005
Later among the works it cites.
M. Warmuth and D. Kuzmin · 2006
Later among the works it cites.
A combinatorial, primal-dual approach to semidefinite programs
S. Arora and S. Kale · 2007
Later among the works it cites.
Efficient algorithms using the multiplicative weights update method
S. Kale · 2007
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
PSPACE has constant-round quantum interactive proof systems
J. Watrous · 1999
Cited alongside, same era.
Parallelization, amplification, and exponential time simulation of quantum interactive proof system
A. Kitaev and J. Watrous · 2000
Cited alongside, same era.
Quantum Computation and Quantum Information
M. A. Nielsen and I. L. Chuang · 2000
Cited alongside, same era.
The Complexity Theory Companion
L. Hemaspaandra and M. Ogihara · 2002
Cited alongside, same era.
Quantum multi-prover interactive proof systems with limited prior entanglement
H. Kobayashi and K. Matsumoto · 2003
Cited alongside, same era.
Later among the works it cites.
Making classical honest verifier zero knowledge protocols secure against quantum attacks
S. Hallgren, A. Kolla, P. Sen, and S. Zhang · 2008
Later among the works it cites.
General properties of quantum zero-knowledge proofs
H. Kobayashi · 2008
Later among the works it cites.
Computational Complexity: A Modern Approach
S. Arora and B. Barak · 2009
Closest in time.
Two-message quantum interactive proofs are in PSPACE
R. Jain, S. Upadhyay, and J. Watrous · 2009
Closest in time.
Parallel approximation of non-interactive zero-sum quantum games
R. Jain and J. Watrous · 2009
Closest in time.
Using entanglement in quantum multi-prover interactive proofs
J. Kempe, H. Kobayashi, K. Matsumoto, and T. Vidick · 2009
Closest in time.
Zero-knowledge against quantum attacks
J. Watrous · 2009
Closest in time.