Two-message quantum interactive proofs are in PSPACE

Abstract

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.

24 pages

Cited by in corpus (12)

• Entanglement detection
• Multiplicativity of completely bounded $p$-norms implies a strong converse for entanglement-assisted capacity
• Hedging bets with correlated quantum strategies
• Equilibrium Value Method for the Proof of QIP=PSPACE
• Approximation Theory and the Design of Fast Algorithms
• Quantum State Isomorphism
• Polynomial-Space Approximation of No-Signaling Provers
• A Lower Bound on the Value of Entangled Binary Games
• A Parallel Approximation Algorithm for Positive Semidefinite Programming
• Parallel Repetition of Prover-Verifier Quantum Interactions
• Interactive proofs with competing teams of no-signaling provers
• Entangled games do not require much entanglement (withdrawn)