arXiv:2610.00847
Beyond IP = PSPACE and QIP = PSPACE: Interactive Proofs in Arbitrary Physical Theories
Kishor Bharti
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.
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