QIP = PSPACE
- 1 December 2010
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 53 (12), 102-109
- https://doi.org/10.1145/1859204.1859231
Abstract
The interactive proof system model of computation has been studied extensively in computational complexity theory and theoretical cryptography for more than 25 years, and has driven the development of interesting new techniques and insights in those fields. This work considers the quantum interactive proof system model, which is the classical model's natural quantum computational analog. 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 with an ordinary classical computer using at most a polynomial amount of memory (or QIP = PSPACE in complexity-theoretic terminology). One striking implication of this characterization is that it implies quantum computing provides no increase in computational power whatsoever over classical computing in the context of interactive proof systems.Keywords
This publication has 14 references indexed in Scilit:
- A combinatorial, primal-dual approach to semidefinite programsPublished by Association for Computing Machinery (ACM) ,2007
- Online Variance MinimizationLecture Notes in Computer Science, 2006
- Quantum Arthur–Merlin gamescomputational complexity, 2005
- Exponential separation of quantum and classical communication complexityPublished by Association for Computing Machinery (ACM) ,1999
- Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channelsPhysical Review Letters, 1993
- IP = PSPACEJournal of the ACM, 1992
- Quantum theory, the Church–Turing principle and the universal quantum computerProceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences, 1985
- The knowledge complexity of interactive proof-systemsPublished by Association for Computing Machinery (ACM) ,1985
- Simulating physics with computersInternational Journal of Theoretical Physics, 1982
- On Relating Time and Space to Size and DepthSIAM Journal on Computing, 1977