Please use this identifier to cite or link to this item:
https://doi.org/10.1145/1806689.1806768
| Title: | QIP = PSPACE | Authors: | Jain, R. Ji, Z. Upadhyay, S. Watrous, J. |
Keywords: | matrix multiplicative weights update method quantum computation quantum interactive proof systems semidefinite programming |
Issue Date: | 2010 | Citation: | Jain, R.,Ji, Z.,Upadhyay, S.,Watrous, J. (2010). QIP = PSPACE. Proceedings of the Annual ACM Symposium on Theory of Computing : 573-581. ScholarBank@NUS Repository. https://doi.org/10.1145/1806689.1806768 | Abstract: | We prove that the complexity class QIP, which consists of all problems having quantum interactive proof systems, is contained in PSPACE. This containment is proved by applying a parallelized form of the matrix multiplicative weights update method to a class of semidefinite programs that captures the computational power of quantum interactive proofs. As the containment of PSPACE in QIP follows immediately from the well-known equality IP = PSPACE, the equality QIP = PSPACE follows. © 2010 ACM. | Source Title: | Proceedings of the Annual ACM Symposium on Theory of Computing | URI: | http://scholarbank.nus.edu.sg/handle/10635/40807 | ISBN: | 9781605588179 | ISSN: | 07378017 | DOI: | 10.1145/1806689.1806768 |
| 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.