QIP = PSPACE
Open Access
- 1 December 2011
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 58 (6) , 1-27
Abstract
This 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.Keywords
Funding Information
- National Natural Science Foundation of China (6.07E+15)
This publication has 46 references indexed in Scilit:
- Quantum entanglementReviews of Modern Physics, 2009
- Algebraic methods for interactive proof systemsJournal of the ACM, 1992
- IP = PSPACEJournal of the ACM, 1992
- A note on approximate linear programmingInformation Processing Letters, 1992
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systemsJournal of the ACM, 1991
- Non-deterministic exponential time has two-prover interactive protocolscomputational complexity, 1991
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classesJournal of Computer and System Sciences, 1988
- Quantum theory, the Church–Turing principle and the universal quantum computerProceedings of the Royal Society of London. A. Mathematical and Physical Sciences, 1985
- Linear programming is log-space hard for PInformation Processing Letters, 1979
- An Unsolvable Problem of Elementary Number TheoryAmerican Journal of Mathematics, 1936