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

arXiv:2610.00847

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

Kishor Bharti

quant-phcs.CCSubmitted Oct 1, 2026• Announced Oct 2, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

AI Summary

The paper asks how the power of single-prover interactive proofs depends on the underlying physical theory. It works with general probabilistic theories satisfying local tomography, causality, containment of classical theory, and efficient approximation of a designated finite verifier gate set. With polynomially many rounds and only classical messages, it proves $\mathrm{GIP}_{\mathrm{cl}}(\mathcal G)=\mathrm{PSPACE}$. Conditioning on the transcript reduces any prover to classical response distributions; deterministic strategies suffice, and a sum–maximum recursion with path-sum evaluation gives the polynomial-space upper bound. For an ordinary quantum verifier exchanging quantum messages, any prover from a theory containing quantum theory has exactly the same maximum acceptance probability as a quantum prover. Its induced response map is a completely positive, causal quantum comb, hence quantum-realizable. Consequently, $\mathrm{GIP}_{\mathrm{qm}}(\mathcal G;k)=\mathrm{QIP}(k)$, including the three-message characterization of $\mathrm{PSPACE}$. Arbitrary message systems can exceed $\mathrm{PSPACE}$ under these assumptions. A triangular, abstractly classical state space encodes a real parameter $v$, while verifier gates retain integer or dyadic coordinates. A one-message protocol estimates its maximal measurement probability using $m^4$ systems for an inverse-quadratic promise gap. Noncomputable $v$ yields an undecidable promise problem; a computable construction yields one outside $\mathrm{PSPACE}$ but decidable in space $2^{O(\log^2 m)}$. These separations exploit unrestricted state-space geometry and the designated gate set, not stronger-than-quantum correlations; efficiently approximable $v$ restores $\mathrm{PSPACE}$. The paper leaves open general effectiveness conditions ensuring a polynomial-space upper bound, the arbitrary-message class of boxworld, and extensions beyond local tomography.

No sign of AI-generated textAI use disclosed
AI tools were used more recently to help polish the draft and, during revision, to assist with reference checking and critical examination of the exposition and mathematical arguments.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
36 pages

Related papers

PSPACE has constant-round quantum interactive proof systems

John Watrous

We introduce quantum interactive proof systems, which are interactive proof systems in which the prover and verifier may perform quantum computations and exchange quantum messages. It is proved that every language in PSPACE has a quantum interactive proof system that requires a total of only three messages to be sent between the prover and verifier and has exponentially small (one-sided) probability of error. It follows that quantum interactive proof systems are strictly more powerful than classical interactive proof systems in the constant-round case unless the polynomial time hierarchy collapses to the second level.

Annual Symposium on Foundations of Computer Science•Jan 20, 2003•53 citations

PSPACE has 2-round quantum interactive proof systems

John Watrous

In this paper we consider quantum interactive proof systems, i.e., interactive proof systems in which the prover and verifier may perform quantum computations and exchange quantum messages. It is proved that every language in PSPACE has a quantum interactive proof system that requires only two rounds of communication between the prover and verifier, while having exponentially small (one-sided) probability of error. It follows that quantum interactive proof systems are strictly more powerful than classical interactive proof systems in the constant-round case unless the polynomial time hierarchy collapses to the second level.

arXiv:cs/9901015•Jan 27, 1999•11 citations

Quantum Multiprover Interactive Proofs with Communicating Provers

Michael Ben-Or, Avinatan Hassidim, Haran Pilpel

We introduce a new variant of quantum multiprover interactive proofs (QMIP) where the provers and the verifier are quantum. The verifier can exchange quantum messages with the provers. The provers cannot communicate quantumly between themselves and do not share entanglement, but are unlimited in the classical communication between them, even after receiving messages from the verifier. We show that any language in nondeterministic exponential time (NEXP) can be recognized in this model efficiently, with just two provers and two rounds of communication, and with a constant completeness/soundness gap. This is in contrast to the result of [R. Jain et al., Comm. ACM, 53 (2010), pp. 102--109], which shows that QIP = PSPACE, or equivalently that the set of languages that can be recognized by a quantum verifier communicating with a single quantum prover is equal to PSPACE. To analyze the cheating power of the provers, we give them more power and allow them to perform any separable operation. We then show a unique two-phase protocol in which the provers first commit to a superposition of correct answers to all possible questions, and then in the second phase the verifier opens up the committed answer and checks for correctness and consistency.

SIAM Journal on Computing•Jan 1, 2014•5 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

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•31 citations

owards a quantum-inspired proof for IP = PSPACE

Ayal Green, Guy Kindler, Yupan Liu

We explore quantum-inspired interactive proof systems where the prover is limited. Namely, we improve on a result by \cite{AG17} showing a quantum-inspired interactive protocol ($\IP$) for $PreciseBQP$ where the prover is only assumed to be a $\PreciseBQP$ machine, and show that the result can be strengthened to show an $\IP$ for $\NP^{\PP}$ with a prover which is only assumed to be an $\NP^{\PP}$ machine - which was not known before. We also show how the protocol can be used to directly verify $\QMA$ computations, thus connecting the sum-check protocol by \cite{AAV13} with the result of \cite{AG17,LFKN90}. Our results shed light on a quantum-inspired proof for $\IP=\PSPACE$, as $\PreciseQMA$ captures the full $\PSPACE$ power.

arXiv:1912.11611•Quantum Information and Computation•Mar 22, 2021•4 citations
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.
The paper asks how the power of single-prover interactive proofs depends on the underlying physical theory. It works with general probabilistic theories satisfying local tomography, causality, containment of classical theory, and efficient approximation of a designated finite verifier gate set.
With polynomially many rounds and only classical messages, it proves GIPcl(G)=PSPACE\mathrm{GIP}_{\mathrm{cl}}(\mathcal G)=\mathrm{PSPACE}GIPcl​(G)=PSPACE. Conditioning on the transcript reduces any prover to classical response distributions; deterministic strategies suffice, and a sum–maximum recursion with path-sum evaluation gives the polynomial-space upper bound. For an ordinary quantum verifier exchanging quantum messages, any prover from a theory containing quantum theory has exactly the same maximum acceptance probability as a quantum prover. Its induced response map is a completely positive, causal quantum comb, hence quantum-realizable. Consequently, GIPqm(G;k)=QIP(k)\mathrm{GIP}_{\mathrm{qm}}(\mathcal G;k)=\mathrm{QIP}(k)GIPqm​(G;k)=QIP(k), including the three-message characterization of PSPACE\mathrm{PSPACE}PSPACE.
Arbitrary message systems can exceed PSPACE\mathrm{PSPACE}PSPACE under these assumptions. A triangular, abstractly classical state space encodes a real parameter vvv, while verifier gates retain integer or dyadic coordinates. A one-message protocol estimates its maximal measurement probability using m4m^4m4 systems for an inverse-quadratic promise gap. Noncomputable vvv yields an undecidable promise problem; a computable construction yields one outside PSPACE\mathrm{PSPACE}PSPACE but decidable in space 2O(log⁡2m)2^{O(\log^2 m)}2O(log2m).
These separations exploit unrestricted state-space geometry and the designated gate set, not stronger-than-quantum correlations; efficiently approximable vvv restores PSPACE\mathrm{PSPACE}PSPACE. The paper leaves open general effectiveness conditions ensuring a polynomial-space upper bound, the arbitrary-message class of boxworld, and extensions beyond local tomography.
We introduce quantum interactive proof systems, which are interactive proof systems in which the prover and verifier may perform quantum computations and exchange quantum messages. It is proved that every language in PSPACE has a quantum interactive proof system that requires a total of only three messages to be sent between the prover and verifier and has exponentially small (one-sided) probability of error. It follows that quantum interactive proof systems are strictly more powerful than classical interactive proof systems in the constant-round case unless the polynomial time hierarchy collapses to the second level.
In this paper we consider quantum interactive proof systems, i.e., interactive proof systems in which the prover and verifier may perform quantum computations and exchange quantum messages. It is proved that every language in PSPACE has a quantum interactive proof system that requires only two rounds of communication between the prover and verifier, while having exponentially small (one-sided) probability of error. It follows that quantum interactive proof systems are strictly more powerful than classical interactive proof systems in the constant-round case unless the polynomial time hierarchy collapses to the second level.
We introduce a new variant of quantum multiprover interactive proofs (QMIP) where the provers and the verifier are quantum. The verifier can exchange quantum messages with the provers. The provers cannot communicate quantumly between themselves and do not share entanglement, but are unlimited in the classical communication between them, even after receiving messages from the verifier. We show that any language in nondeterministic exponential time (NEXP) can be recognized in this model efficiently, with just two provers and two rounds of communication, and with a constant completeness/soundness gap. This is in contrast to the result of [R. Jain et al., Comm. ACM, 53 (2010), pp. 102--109], which shows that QIP = PSPACE, or equivalently that the set of languages that can be recognized by a quantum verifier communicating with a single quantum prover is equal to PSPACE. To analyze the cheating power of the provers, we give them more power and allow them to perform any separable operation. We then show a unique two-phase protocol in which the provers first commit to a superposition of correct answers to all possible questions, and then in the second phase the verifier opens up the committed answer and checks for correctness and consistency.
We explore quantum-inspired interactive proof systems where the prover is limited. Namely, we improve on a result by \cite{AG17} showing a quantum-inspired interactive protocol ($\IP$) for PreciseBQPPreciseBQPPreciseBQP where the prover is only assumed to be a $\PreciseBQP$ machine, and show that the result can be strengthened to show an $\IP$ for $\NP^{\PP}$ with a prover which is only assumed to be an $\NP^{\PP}$ machine - which was not known before. We also show how the protocol can be used to directly verify $\QMA$ computations, thus connecting the sum-check protocol by \cite{AAV13} with the result of \cite{AG17,LFKN90}. Our results shed light on a quantum-inspired proof for $\IP=\PSPACE$, as $\PreciseQMA$ captures the full $\PSPACE$ power.