2009

Two-message quantum interactive proofs are in PSPACE

Jain, Rahul, Upadhyay, Sarvagya, Watrous, John

Understand

We prove that QIP(2), the class of problems having two-message quantum interactive proof systems, is a subset of PSPACE.

This relationship is obtained by means of an efficient parallel algorithm, based on the multiplicative weights update method, for approximately solving a certain class of semidefinite programs.

Built on

Linear transformations which preserve trace and positive semidefiniteness of operators
A. Jamiołkowski · 1972
Earlier work this paper cites.
Completely positive linear maps on complex matrices
M.-D. Choi · 1975
Earlier work this paper cites.
Fast parallel matrix inversion algorithms
L. Csanky · 1976
Earlier work this paper cites.
The ”transition probability” in the state space of a ∗ \ast -algebra
A. Uhlmann · 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.
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.
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.

Similar

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
Cited alongside, same era.
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.
Parallel linear algebra
J. von zur Gathen · 1993
Cited alongside, same era.
Geometric Algorithms and Combinatorial Optimization
M. Grötschel, L. Lovász, and A. Schrijver · 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.
Cryptographic distinguishability measures for quantum-mechanical states
C. Fuchs and J. van de Graaf · 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.
Limits on the power of quantum statistical zero-knowledge
J. Watrous · 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.

Then

Quantum Arthur-Merlin games
C. Marriott and J. Watrous · 2005
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.
Online variance minimization
Original
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.
Toward a general theory of quantum games
G. Gutoski and J. Watrous · 2007
Later among the works it cites.
Efficient algorithms using the multiplicative weights update method
S. Kale · 2007
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.
Using entanglement in quantum multi-prover interactive proofs
J. Kempe, H. Kobayashi, K. Matsumoto, and T. Vidick · 2008
Later among the works it cites.
General properties of quantum zero-knowledge proofs
H. Kobayashi · 2008
Later among the works it cites.
On the complexity of approximating the diamond norm
A. Ben-Aroya and A. Ta-Shma · 2009
Closest in time.
Parallel approximation of non-interactive zero-sum quantum games
R. Jain and J. Watrous · 2009
Closest in time.
Quantum computational complexity
J. Watrous · 2009
Closest in time.
Semidefinite programs for completely bounded norms
J. Watrous · 2009
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…