PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Kishor Bharti

arXiv:2610.00847v1quant-phcs.CC

TL;DR

The paper asks how much interactive-proof power comes from the physical theory underlying the verifier and prover. It studies interactive proofs in general probabilistic theories and compares classical messages, quantum messages, and arbitrary systems. Classical-message protocols characterize PSPACE, quantum provers do not improve quantum-verifier acceptance, but arbitrary-system messages can yield classes beyond PSPACE.

  • Problem

    The paper asks whether the physical theory governing an interactive proof can change what a verifier can check or let a stronger-than-quantum prover convince it of a false claim.

    Source: §1 · pp. 1–2

  • Method

    The paper analyzes interactive proofs in general probabilistic theories by reducing prover behavior on classical or quantum message registers to strategies in the corresponding subtheory.

    Source: §9 · p. 30

  • Results

    Classical messages yield PSPACE, quantum messages preserve quantum-prover maximum acceptance, but arbitrary-system messages can make the class exceed PSPACE.

    Source: §1.1 · pp. 2–3

  • Takeaways & Limitations

    The applicable interactive-proof bounds depend on the exchanged systems and, for arbitrary messages, on how state spaces are specified relative to efficient gates.

    Source: §8.4 · p. 29, §9 · p. 30

    The standing assumptions constrain verifier gates but not message state spaces, so upper bounds for arbitrary-message protocols need an additional hypothesis on those spaces.

    Source: §8.4 · p. 29

Abstract

from arXiv · show

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.

1 Introduction

The paper asks whether interactive-proof power depends on the physical theory governing operations and exchanged systems. It studies general probabilistic theories and finds that outcomes depend on message type and efficient-operation specification.

1 Introduction

  • Classical and quantum interactive proofs both characterize PSPACE, but quantum interaction allows three messages whereas any constant number of at least two classical messages gives AM.The paper asks how much interactive-proof power comes from the physical theory governing the agents’ operations and exchanged systems.Source: §1 · p. 1

1.1 Results

  • For every theory satisfying the standing assumptions, classical-message protocols decide exactly PSPACE, even when the prover and verifier use nonclassical private systems.The prover’s behavior reduces to classical conditional answer distributions, and the verifier’s acceptance probabilities can be approximated in polynomial space.Source: §1.1 · p. 2
  • For quantum verifiers exchanging qubits, any prover in a theory containing quantum theory has the same maximum acceptance probability as a quantum prover; thus QIP(3) = PSPACE persists.The proof converts the prover’s strategy into a valid quantum strategy with the same acceptance probability.Source: §1.1 · p. 3
  • With arbitrary messages, some theories exceed PSPACE: noncomputable v gives an undecidable problem, while a computable hierarchy-based v yields one outside PSPACE.The construction estimates v from copies of a state and compares it with the input.Source: §1.1 · p. 3
  • The interactive-proof class is not determined by operational content alone: it depends on how efficient operations are specified, so upper bounds require a hypothesis about that specification.The theories in the construction can be operationally isomorphic to classical or quantum theory with classical systems, while a bias-v measurement may not be efficient in the standard presentation.Source: §1.1 · p. 3

2 Preliminaries

This section establishes promise-problem and complexity-class notation, recalls the classical and quantum interactive-proof results used later, and introduces convex-geometric tools.

2 Preliminaries

  • A promise problem consists of disjoint yes- and no-instances, and an algorithm decides it by accepting every yes-instance and rejecting every no-instance.The section also fixes notation for common complexity classes and states that PSPACE problems are decidable.Source: §2 · p. 4, §2.1 · p. 4

2.1 Complexity classes and interactive proofs

  • Classical interactive proofs characterize PSPACE, while quantum interactive proofs satisfy QIP = QIP(3) = PSPACE.For PSPACE, a public-coin classical protocol can have perfect completeness and soundness 1/3; any constant k ≥ 2 gives IP(k) = AM.Source: §2.1 · pp. 4–5

2.2 Convex geometry

  • The convex-geometry toolkit uses ordered cones and minimal and maximal tensor products; normalized bases are compact, and linear functionals attain maxima at extreme points.These facts support the paper’s treatment of possible state spaces and composites.Source: §2.2 · p. 5

3 General probabilistic theories

This section develops a finite-dimensional framework for general probabilistic theories, defining states, effects, channels, composition, positivity on extensions, and standing operational assumptions. It also explains how complexity classes depend on a theory’s presentation, including its gate set, and illustrates that theories meeting the assumptions can differ in their composites and in whether their isomorphisms preserve computability.

3.1 Systems, states and measurements

  • Systems are finite-dimensional ordered vector spaces with normalized positive states, bounded effects, and measurements whose outcome probabilities are given by effect–state pairings.States form a convex set, and a measurement’s effects sum to the unit effect.Source: §3.1 · p. 6

3.2 Composite systems

  • Composites have tensor-product vector spaces, while the choice of composite cone determines which correlations and entangled states are allowed.Minimal composites admit only mixtures of product states; maximal composites can admit more, including no-signalling boxes for gbits.Source: §3.2 · pp. 7–8

3.3 Channels and instruments

  • Channels preserve the unit effect and remain positive when extended by any system; instruments are outcome-indexed maps whose sum is a channel.A later channel cannot change the probabilities of earlier recorded outcomes, so the joint distribution of the first outcomes in a sequence is independent of later instruments.Source: §3.3 · p. 8

3.4 Theories and the standing assumptions

  • Theories specify allowed systems, channels, and instruments, and throughout the paper they assume local tomography, causality, classical theory’s inclusion, and computable gates.The computable-gates assumption includes bounded dimension for elementary systems.Source: §3.4 · pp. 9–10
  • The standing assumptions constrain the verifier’s finite gate set, not the computability of state cones, and changing gate coordinates can change the class even for isomorphic theories.The designated gates and coordinates form the theory’s presentation; transporting gates with an isomorphism preserves circuit descriptions and acceptance probabilities, while replacing them with a standard gate set may not.Source: §3.4 · p. 10
  • Gmin satisfies the standing assumptions but has no entangled states, and controlled-NOT is not an allowed channel; real quantum theory instead violates (T1) and is excluded.The paper notes that real quantum theory is consistent and experimentally distinguishable from complex quantum theory [RTW+21].Source: §3.4 · p. 11
  • In Gv, the isomorphism to classical theory with an additional three-dimensional system is computable if and only if v is computable.The parameter v appears in the state-cone description but not in any gate.Source: §3.4 · p. 11
  • GE contains quantum theory yet permits a prover to send a verifier a qubit correlated with retained memory through a state outside the quantum cone, without gaining an advantage against a quantum verifier.The prover can prepare 1/2 SWAP on Q ⊗ E, send Q, and keep E; Theorem 7.3 establishes that this gives no advantage.Source: §3.4 · p. 12

4 Circuits and path sums

Adaptive circuits in a general probabilistic theory have efficiently approximable outcome probabilities via polynomial-space path sums. This supplies a computational tool for analyzing the theory’s circuits.

4 Circuits and path sums

  • A circuit is an adaptive, polynomial-time uniform sequence of gates whose next gate can depend on prior outcomes, with acceptance determined by a computable Boolean rule.The path-sum representation generalizes classical computation paths and the paired Feynman paths used for quantum circuits.Source: §4 · pp. 12–13
  • The path-sum method extends the polynomial-space simulation ingredient Lee and Barrett use to place BGP(G) inside AWPP, and hence inside PP.Circuit outcome probabilities expand into sums over paths, with efficiently computable matrix entries.Source: §4 · p. 13
  • A polynomial-space algorithm approximates any circuit-record probability, or a decidable sum of such probabilities, to error 2^-q(|x|).It enumerates rounded path terms and records using polynomial space.Source: §4 · p. 13

5 Interactive proofs in a theory

The section defines interactive protocols through adaptive verifier stages and prover strategies, then assigns values and complexity classes according to acceptance probability and message type. It establishes simulation and error-reduction properties for these classes.

5.1 Verifiers and prover strategies

  • Each round sends a verifier-chosen system to the prover and receives a response, while both retain private systems and begin independently prepared; the prover may use unbounded private systems and any allowed channel.The interaction has a well-defined acceptance probability.Source: §5.1 · p. 14

5.2 Values and classes

  • A verifier’s value is the supremum acceptance probability over prover strategies, with completeness at least 2/3 on yes-instances and soundness at most 1/3 on no-instances.The definitions also distinguish classes by message count and whether messages are classical, quantum, or unrestricted.Source: §5.2 · pp. 14–15
  • Quantum-message classes use a quantum verifier and qubit messages while allowing the prover arbitrary systems; classical-message classes fix effective classical encodings even when internal systems are arbitrary.When the theory contains quantum theory, these quantum verifier conditions include ordinary quantum registers, channels, and gates.Source: §5.2 · p. 15

5.3 Basic properties and error reduction

  • If prover strategies in a larger theory can be simulated with identical acceptance probabilities, the corresponding class inclusion holds; with the same verifier set, the classes are equal.A larger theory can increase a fixed verifier’s value, which may preserve completeness but violate soundness.Source: §5.3 · p. 15
  • Sequential repetition reduces completeness and soundness error exponentially, but increases message count and therefore does not itself amplify fixed-message variants.The soundness argument bounds each repetition’s conditional acceptance by the original value, despite prover correlations across runs.Source: §5.3 · pp. 15–16

6 Classical messages

With classical messages, every theory satisfying the standing assumptions yields exactly PSPACE. Conditioned on the transcript, nonclassical prover resources reduce to classical response distributions, while the protocol value can be computed in polynomial space.

6.1 Conditional product states

  • Conditioned on each classical transcript, the verifier’s and prover’s private systems remain in a product state, so the prover’s responses are classical conditional distributions.This simulation preserves the distribution of records and therefore the acceptance probability.Source: §6 · p. 17, §6.1 · pp. 17–18
  • A deterministic prover attains the optimal value: backward recursion sums over verifier questions and maximizes over prover answers.The recursion uses transcript acceptance weights and yields the value at the empty transcript.Source: §6.1 · p. 18

6.2 The theorem

  • For every theory G satisfying the standing assumptions, classical-message interactive proofs decide exactly PSPACE, including the public-coin subclass.The lower bound imports a public-coin proof for PSPACE; the upper bound computes the protocol value in polynomial space.Source: §6.2 · pp. 18–19
  • The upper bound evaluates the transcript recursion in polynomial space, approximating verifier path-sum probabilities at its leaves.Depth-first evaluation stores a branch index and accumulator at each level.Source: §6.2 · p. 19
  • The theory determines verifier outcome weights, but the theorem applies even to boxworld, where the verifier may prepare and measure PR boxes internally.The paper also reports the classical-message equality for boxworld and for Gv at every v.Source: §6.2 · pp. 19–20
  • The classical-message result does not settle arbitrary messages: the class exceeds PSPACE for Gv with noncomputable v, while the boxworld case is open.For efficiently approximable v, the paper states that the class does not change.Source: §6.2 · p. 20

7 Quantum verifiers

For quantum verifiers exchanging quantum messages, the paper represents prover behavior by quantum combs and shows that even a prover using a theory containing quantum theory cannot exceed the quantum value. The equality preserves the QIP = PSPACE result, including its three-message form, subject to the stated composite-system assumption.

7.1 Quantum combs

  • A prover’s sequential responses are represented by a quantum comb, which captures the channel behavior across message rounds and prevents earlier answers from depending on later questions.Every such comb can be realized by quantum channels with finite-dimensional memory.Source: §7 · p. 20, §7.1 · p. 20

7.2 The theorem

  • For every quantum verifier and input, a prover from any theory containing quantum theory achieves no greater acceptance probability than a quantum prover.The two values coincide because quantum provers are also strategies in the containing theory.Source: §7.2 · pp. 20–21

7.4 Consequences

  • The results recover QIP = PSPACE and QIP(3) = PSPACE, and extend the value equality to every message count for quantum verifiers.They also give GIPcl(G) = GIPqm(G) = PSPACE for every theory G containing quantum theory.Source: §7.2 · p. 20, §7.4 · p. 23

7.2 The theorem

  • The proof reduces a general-theory prover to a quantum prover with the same comb, using local tomography, positivity on extensions, causality, and quantum composites of qubits.The theorem needs no bound on prover memory, purification principle, or information about composites with other systems.Source: §7.2 · p. 21

7.3 Examples

  • A prover of GE holding a state outside the quantum cone gains no advantage in the example, because a quantum prover induces the same comb.The paper compares the resulting unnormalised states from the two strategies.Source: §7.3 · p. 22
  • The composite-system assumption is essential: in Gmin, a prover can apply an orthogonal-complement channel and win the spin-flip test with probability 1, above the quantum value 3/4.The verifier uses only single-qubit operations; the difference lies in how two qubits compose.Source: §7.3 · p. 23

7.4 Consequences

  • With arbitrary message systems, the general class contains PSPACE and equals it only if those remaining protocols can be simulated in polynomial space.The paper notes that the class can exceed PSPACE when message systems encode noncomputable or slowly computable reals.Source: §7.4 · p. 23

8 Arbitrary messages: beyond polynomial space

This section examines interactive proofs with arbitrary messages, focusing on how message state-space geometry and its specification relative to verifier gates shape the resulting class. It describes when a hard-to-compute real can create a separation, when efficient simulation of transported verifier gates removes it, and why upper bounds require additional state-space hypotheses.

8.1 The triangular theory and the problem Lv

  • For noncomputable v, a one-message protocol puts the undecidable promise problem Lv in GMA(Gv), while GIPcl(Gv) = PSPACE and GIP(Gv) strictly contains PSPACE.Gv satisfies (T1)–(T4).Source: §8.1 · p. 24

8.2 A theory containing quantum theory and classical theory

  • Adjoining the triangular system to quantum theory preserves PSPACE for classical-message and quantum-verifier protocols, yet arbitrary-message protocols contain an undecidable promise problem for noncomputable v.The resulting theory contains quantum and classical theory as subtheories; the separation uses protocols where the verifier measures prover-sent triangular systems.Source: §8.2 · pp. 26–27

8.3 Computable presentations do not suffice

  • A computable coordinate can still yield GIP(GQvT) strictly above PSPACE, although classical-message and quantum-subtheory protocols remain in PSPACE.The separating problem LvT is decidable in quasi-polynomial space but lies outside PSPACE; the theories have computable presentations.Source: §8.3 · pp. 27–28

8.4 The role of the presentation

  • If v is efficiently approximable, then GIP(Gv) = GIP(GQv) = PSPACE, because verifiers can be replaced by classical or QC verifiers with value error at most 1/12.The replacements preserve the number of messages.Source: §8.4 · p. 28
  • Changing the state-space coordinate parameter v can yield PSPACE, a class strictly containing PSPACE with a quasi-polynomial-space witness, or a class containing undecidable problems.These outcomes arise within one family of theories with fixed operational content.Source: §8.4 · p. 29
  • Because assumptions (T1)–(T4) constrain gates rather than state spaces, upper bounds for arbitrary messages need hypotheses about state spaces in the gates’ coordinates.One possible condition is efficient approximation of the maximum of an effect with efficiently computable coordinates over a message system’s states.Source: §8.4 · p. 29
  • The construction parallels BQP with arbitrary real gate amplitudes containing undecidable problems, but here the noncomputable number is in the state space, not a gate.The phenomenon therefore occurs only with nonclassical messages and disappears for classical messages and quantum verifiers.Source: §8.4 · p. 29

9 Discussion

Under (T1)–(T4), the results depend on the exchanged systems and the theory’s specification of efficient operations. The discussion identifies limits of the current upper bounds and several open questions.

Message systems

  • Classical messages yield PSPACE in every (T1)–(T4) theory; with quantum messages, stronger-theory provers are no stronger than quantum provers.The proofs reduce prover behavior on the message registers to a strategy in the corresponding subtheory.Source: §9 · p. 30

Specification of efficient operations

  • Arbitrary messages can exceed PSPACE when state-space geometry communicates noncomputable or slowly computable reals, even in theories isomorphic to quantum theory with classical systems.A polynomial-space upper bound for arbitrary messages needs a hypothesis relating message state spaces to gate coordinates; standard gates in the isomorphic theory give GIP = PSPACE.Source: §9 · p. 30

Open question 9.1 (Effectiveness hypotheses)

  • For boxworld, whether GIP = PSPACE remains open; its prover strategies lack a known finite description like the one supplied by the quantum-comb realization theorem.The discussion also asks which effectiveness hypothesis on message state spaces would imply GIP(G) = PSPACE for a natural class of theories.Source: §9 · p. 30

Open question 9.2 (Constant numbers of classical messages)

  • Whether a nonclassical verifier with classical messages has GIPcl(G; k) = AM for every theory is open; for QC, a positive answer would imply BQP ⊆ AM.The Goldwasser–Sipser set-lower-bound protocol does not obviously extend to path-sum transition weights.Source: §9 · p. 30

Open question 9.3 (Several provers)

  • With multiple separated provers, the composition rule can affect the class: shared-randomness provers give MIP = NEXP, while entangled provers give MIP∗ = RE.The classes for boxworld and other theories satisfying (T1)–(T4) remain open.Source: §9 · p. 30

Open question 9.4 (Theories without local tomography)

  • Real quantum theory violates local tomography yet has QIPR(k) = QIP(k) for every k; which parts of the classical-message and quantum-message theorems survive weaker composite assumptions remains open.The stated equality implies its interactive-proof class is PSPACE.Source: §9 · p. 30

Open question 9.5 (Round reduction)

  • No round-reduction theorem follows from (T1)–(T4) alone, since classical theory satisfies them but lacks quantum theory’s three-message compression unless PSPACE = AM.The discussion asks which added assumptions, such as coherent verifier operations on a qubit, imply GIP(G) = GIP(G; 3).Source: §9 · p. 31

Project history and use of generative AI

The project began in 2023, following work on multiplicative updates over symmetric cones, and included preliminary discussions with Antonios Varvitsiotis and Rahul Jain. AI tools were later used to polish and check the draft.

Project history

Use of generative AI

A The unary space hierarchy theorem

The unary space hierarchy argument constructs a language by diagonalizing against an enumeration of machines under a growing space bound. A universal simulation places the language within that bound, while a contradiction excludes smaller constant-exponent bounds.

Construction

  • The construction enumerates every deterministic machine infinitely often, with descriptions computable from unary inputs in O(n) space.It uses a space-constructible bound g(n) = 2n2.Source: A The unary space hierarchy theorem · p. 36

Diagonal language

Decision procedure

  • A universal machine decides T by bounded-space simulation, aborting after a configuration-count bound and accepting exactly when the simulation halts and rejects.The construction uses O(g(n)) space, including the simulated tape and machine-description overhead.Source: A The unary space hierarchy theorem · p. 36

Hierarchy separation

  • The diagonal language lies in its constructed space bound but escapes every constant-exponent bound, because a faithful simulation would make membership equivalent to its own rejection.The contradiction applies for sufficiently large n where the enumerated machine matches the purported decider.Source: A The unary space hierarchy theorem · p. 36
Loading 2610.00847v1…