DocumentCode
1963884
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
fYear
2009
fDate
25-27 Oct. 2009
Firstpage
534
Lastpage
543
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 2009. FOCS '09. 50th Annual IEEE Symposium on
Conference_Location
Atlanta, GA
ISSN
0272-5428
Print_ISBN
978-1-4244-5116-6
Type
conf
DOI
10.1109/FOCS.2009.30
Filename
5438601
Link To Document