Please use this identifier to cite or link to this item: https://doi.org/10.1145/2049697.2049704
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:11:15Z
dc.date.available2013-07-04T08:11:15Z
dc.date.issued2011
dc.identifier.citationJain, R., Ji, Z., Upadhyay, S., Watrous, J. (2011). QIP = PSPACE. Journal of the ACM 58 (6). ScholarBank@NUS Repository. https://doi.org/10.1145/2049697.2049704
dc.identifier.issn00045411
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/40740
dc.description.abstractThis work considers the quantum interactive proof system model of computation, which is the (classical) interactive proof system model's natural quantum computational analogue. An exact characterization of the expressive power of quantum interactive proof systems is obtained: the collection of computational problems having quantum interactive proof systems consists precisely of those problems solvable by deterministic Turing machines that use at most a polynomial amount of space (or, more succinctly, QIP = PSPACE). This characterization is proved through the use of a parallelized form of the matrix multiplicative weights update method, applied to a class of semidefinite programs that captures the computational power of quantum interactive proof systems. One striking implication of this characterization is that quantum computing provides no increase in computational power whatsoever over classical computing in the context of interactive proof systems, for it is well known that the collection of computational problems having classical interactive proof systems coincides with those problems solvable by polynomial-space computations. © 2011.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1145/2049697.2049704
dc.sourceScopus
dc.subjectInteractive proof systems
dc.subjectMatrix multiplicative weights update method
dc.subjectQuantum computation
dc.subjectSemidefinite programming
dc.typeConference Paper
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.doi10.1145/2049697.2049704
dc.description.sourcetitleJournal of the ACM
dc.description.volume58
dc.description.issue6
dc.description.codenJOACF
dc.identifier.isiut000298296000006
Appears in Collections:Staff Publications

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

SCOPUSTM   
Citations

33
checked on Jan 23, 2020

WEB OF SCIENCETM
Citations

23
checked on Jan 23, 2020

Page view(s)

156
checked on Dec 30, 2019

Google ScholarTM

Check

Altmetric


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