Two-message quantum interactive proofs are in PSPACE
Jain, R. Upadhyay, S. Watrous, J.
Upadhyay, S.
Watrous, J.
Citations
Altmetric:
Alternative Title
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. © 2009 IEEE.
Keywords
Matrix multiplicative weights update method, Quantum complexity, Quantum interactive proof systems
Source Title
Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Publisher
Series/Report No.
Collections
Rights
Date
2009
DOI
10.1109/FOCS.2009.30
Type
Conference Paper