Please use this identifier to cite or link to this item:
https://doi.org/10.1109/FOCS.2009.30
| Title: | Two-message quantum interactive proofs are in PSPACE | Authors: | Jain, R. Upadhyay, S. Watrous, J. |
Keywords: | Matrix multiplicative weights update method Quantum complexity Quantum interactive proof systems |
Issue Date: | 2009 | Citation: | Jain, R., Upadhyay, S., Watrous, J. (2009). Two-message quantum interactive proofs are in PSPACE. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS : 534-543. ScholarBank@NUS Repository. https://doi.org/10.1109/FOCS.2009.30 | 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. | Source Title: | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS | URI: | http://scholarbank.nus.edu.sg/handle/10635/40123 | ISBN: | 9780769538501 | ISSN: | 02725428 | DOI: | 10.1109/FOCS.2009.30 |
| Appears in Collections: | Staff Publications |
Show full item record
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.