Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

ACM Symposium on Theory of Computing (STOC)

QIP = PSPACE

Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous

Published Jun 5, 2010• 53 citations
Publisher

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.

DOI
10.1145/1806689.1806768

Related papers

QIP = PSPACE

Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay +1 more

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.

arXiv:0907.4737•Jul 27, 2009•0 citations

QIP = PSPACE

Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay +1 more

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.

•Jul 27, 2009•0 citations

Beyond IP = PSPACE and QIP = PSPACE: Interactive Proofs in Arbitrary Physical Theories

Kishor Bharti

The equalities IP = PSPACE and QIP = PSPACE, the latter achievable with three messages, raise a basic question: how much of an interactive proof's power comes from the underlying physical theory? We study interactive proofs in general probabilistic theories, which include classical and quantum theory. The answer depends on what the prover and verifier exchange and how the theory specifies efficient operations. When they exchange only classical messages, protocols in every theory satisfying our standard assumptions decide exactly PSPACE. For protocols with a quantum verifier and quantum messages, allowing a prover to use any theory containing quantum theory does not increase the maximum acceptance probability. Thus, the three-message PSPACE result remains valid against such provers. When messages may be arbitrary systems, the interactive-proof class can strictly exceed PSPACE.

quant-pharXiv:2610.00847•Oct 2, 2026•0 citations

QIP = PSPACE

Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay +1 more

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.

Journal of the ACM•Dec 1, 2011•59 citations

Two-Message Quantum Interactive Proofs Are in PSPACE

Rahul Jain, Sarvagya Upadhyay, John Watrous

We prove that QIP(2), the class of problems having two-message quantum interactive proof systems, is a subset of PSPACE. This relationship is obtained by means of an efficient parallel algorithm, based on the matrix multiplicative weights update method, for approximately solving a certain class of semidefinite programs.

arXiv:0905.1300•Annual Symposium on Foundations of Computer Science•Oct 1, 2009•57 citations

Equilibrium Value Method for the Proof of QIP=PSPACE

Xiaodi Wu

We provide an alternative proof of \class{QIP}=\class{PSPACE} to the recent breakthrough result. Unlike solving some semidefinite programs that captures the computational power of quantum interactive proofs, our method starts with one \class{QIP}-Complete problem which computes the diamond norm between two admissible quantum channels. The key observation is that we can convert the computation of the diamond norm into the computation of some equilibrium value. The later problem, different from the former semidefinite programs, is of better form, easier to solve and could be interesting for its own sake. The multiplicative weight update method is also applied to solve the equilibrium value problem, however, in a relatively simpler way than the one in the original proof. As a direct byproduct, we also provide a NC algorithm to compute the diamond norm of a class of quantum channels. Furthermore, we provide a generalized form of equilibrium value problems that can be solved in the same way as well as comparisons to semidefinite programs.

arXiv:1004.0264•Apr 2, 2010•10 citations
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.
The equalities IP = PSPACE and QIP = PSPACE, the latter achievable with three messages, raise a basic question: how much of an interactive proof's power comes from the underlying physical theory? We study interactive proofs in general probabilistic theories, which include classical and quantum theory. The answer depends on what the prover and verifier exchange and how the theory specifies efficient operations. When they exchange only classical messages, protocols in every theory satisfying our standard assumptions decide exactly PSPACE. For protocols with a quantum verifier and quantum messages, allowing a prover to use any theory containing quantum theory does not increase the maximum acceptance probability. Thus, the three-message PSPACE result remains valid against such provers. When messages may be arbitrary systems, the interactive-proof class can strictly exceed PSPACE.
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.
We provide an alternative proof of \class{QIP}=\class{PSPACE} to the recent breakthrough result. Unlike solving some semidefinite programs that captures the computational power of quantum interactive proofs, our method starts with one \class{QIP}-Complete problem which computes the diamond norm between two admissible quantum channels. The key observation is that we can convert the computation of the diamond norm into the computation of some equilibrium value. The later problem, different from the former semidefinite programs, is of better form, easier to solve and could be interesting for its own sake. The multiplicative weight update method is also applied to solve the equilibrium value problem, however, in a relatively simpler way than the one in the original proof. As a direct byproduct, we also provide a NC algorithm to compute the diamond norm of a class of quantum channels. Furthermore, we provide a generalized form of equilibrium value problems that can be solved in the same way as well as comparisons to semidefinite programs.