Two-message quantum interactive proofs are in PSPACE

2009/05/08 by Jain, Rahul, Upadhyay, Sarvagya, Watrous, John · 1 citation
#Computational Complexity (cs.CC) #F.1.3 #F.2.1 #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)

paper · doi:10.48550/arxiv.0905.1300

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.

Cited by

• A slightly improved upper bound for quantum statistical zero-knowledge

Related

• QIP = PSPACE
• PSPACE has 2-round quantum interactive proof systems
• QIP ⊆ AM(2QCFA)
• Quantum interactive proofs with weak error bounds
• Equilibrium Value Method for the Proof of QIP=PSPACE