Title :
Two-Message Quantum Interactive Proofs Are in PSPACE
Author :
Jain, Rahul ; Upadhyay, Sarvagya ; Watrous, John
Author_Institution :
Dept. of Comput. Sci. & Centre for Quantum Technol., Nat. Univ. of Singapore, Singapore, Singapore
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 matrix multiplicative weights update method, for approximately solving a certain class of semidefinite programs.
Keywords :
approximation theory; computational complexity; mathematical programming; parallel algorithms; quantum computing; theorem proving; PSPACE; QIP(2); approximate solution; matrix multiplicative weights update method; parallel algorithm; semidefinite program; two-message quantum interactive proofs; Approximation algorithms; Computational complexity; Computer science; Parallel algorithms; Polynomials; Power system modeling; Quantum computing; Quantum entanglement; Upper bound; Quantum interactive proof systems; matrix multiplicative weights update method; quantum complexity;
Conference_Titel :
Foundations of Computer Science, 2009. FOCS '09. 50th Annual IEEE Symposium on
Conference_Location :
Atlanta, GA
Print_ISBN :
978-1-4244-5116-6
DOI :
10.1109/FOCS.2009.30
