1. ScholarBank@NUS
  2. 1. Staff
  3. Staff Publications
Please use this identifier to cite or link to this item: https://doi.org/10.1145/1806689.1806768
DC FieldValue
dc.titleQIP = PSPACE
dc.contributor.authorJain, R.
dc.contributor.authorJi, Z.
dc.contributor.authorUpadhyay, S.
dc.contributor.authorWatrous, J.
dc.date.accessioned2013-07-04T08:12:47Z
dc.date.available2013-07-04T08:12:47Z
dc.date.issued2010
dc.identifier.citationJain, 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. <a href="https://doi.org/10.1145/1806689.1806768" target="_blank">https://doi.org/10.1145/1806689.1806768</a>
dc.identifier.isbn9781605588179
dc.identifier.issn07378017
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/40807
dc.description.abstractWe 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.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1145/1806689.1806768
dc.sourceScopus
dc.subjectmatrix multiplicative weights update method
dc.subjectquantum computation
dc.subjectquantum interactive proof systems
dc.subjectsemidefinite programming
dc.typeConference Paper
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.doi10.1145/1806689.1806768
dc.description.sourcetitleProceedings of the Annual ACM Symposium on Theory of Computing
dc.description.page573-581
dc.identifier.isiutNOT_IN_WOS
Appears in Collections:Staff Publications

Show simple item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.