A Relativizing MIP for BQP

arXiv:2604.11952 · quant-ph, cs.CC · Submitted 2026-04-13 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: Today's paper: "A Relativizing MIP for BQP".

Mira: A major open question in quantum complexity is whether every language in BQP has an interactive proof system with a polynomial-time classical verifier and a polynomial-time quantum prover,

Kai: First, who's behind it and why it matters.

Title and authors: Kai: Now, let's talk about who wrote this and what exactly this paper is trying to achieve in terms of its title.

Mira: The title "A Relativizing MIP for BQP" immediately signals the central theme: they are tackling the difficulty of proving quantum computations using interactive proofs when you allow for an arbitrary classical oracle.

Lev: That relativization aspect is key because complexity class containments involving interactive proof classes are notoriously nonrelativizing, and this work aims to show progress where it was previously lacking.

Kai: So in simple terms, they are showing that the containment BQP MIP doesn't break when you give the system an oracle O that can be anything classical.

Mira: They achieve this by building a specific PCP proof system for BQPO where the verifier can make polynomially many classical queries to an exponentially long proof, and importantly, these queries can access that oracle O.

Lev: That ability of the verifier to query the oracle O is what separates this construction from previous work that might not have relativized.

Kai: The inspiration for this PCP construction comes from the state synthesis algorithm of Grover and Rudolph, which they use as a complement to earlier work by Aharonov, Arad, and Vidick.

Mira: That contrast is important because the previous constructions achieved similar parameters but were based on different ideas and didn't relativize in the same way this new method does.

Lev: So what we are seeing here is a new axis for measuring progress toward BQP equals IPBQP, which is this specific axis of relativization.

Kai: It sets up a framework where we can measure how well quantum computation translates into classical verification when that verification has oracle access.

Mira: The authors hope that by proving this containment holds for any oracle O, they are making significant progress toward understanding the relationship between BQP and IPBQP in a way that was previously unexplored.

The paper's summary: Kai: So, summarizing what the paper actually does, it builds an exponentially long classical PCP for the two-fold FORRELATION problem, which is BQPO-complete <ref:2604.11952#pg2>.

Mira: They describe this proof as being composed of segments indexed by each gate in the quantum circuit, where each segment describes a quantum state psi i.

Lev: Instead of writing out the full state vector coefficients for that state, they use a different representation based on the state synthesis algorithm.

Kai: This representation is described as a table (gamma, p) of complex phases and conditional probabilities, which they visualize as a prefix-tree structure.

Mira: The crucial part is that this oracle allows a classical algorithm to sample from the distribution obtained by measuring the state in the computational basis using only a polynomial number of queries.

Lev: This sampling access is what enables them to estimate inner products between states, and thus it allows them to certify that the provided proof corresponds to a correct computational history.

Kai: So, they are showing that this structured classical information is enough for a classical verifier with oracle access O to check if the computation was correct.

Mira: They also point out another striking feature of their result, which illustrates a dimension in which BQP is much more "tame" than the polynomial hierarchy.

Lev: This suggests that in this specific context, BQP computations are not as computationally complex to verify classically as we might previously assume based on the polynomial hierarchy structure.

Kai: So they are demonstrating that BQPO MIP (one) for any oracle O, which is the main result they are driving toward resolving the question of whether BQP equals IPBQP <ref:2604.11952#pg2>.

The paper's improvements: Mira: Focusing on how this work improves upon prior knowledge, the paper suggests a few key improvements in its methodology.

Lev: One improvement is moving away from simply writing out the state vector components and instead using the truth table of a classical state synthesis oracle for each timestep t.

Kai: That shift to using the truth table instead of raw coefficients is what enables them to use polynomial queries to sample from the distribution obtained by measuring in the computational basis.

Mira: This specific sampling access capability is what allows them to estimate inner products between states, which in turn certifies the provided proof corresponds to a correct computational history.

Lev: The second improvement they highlight involves using a two-round variant of the PCP system, where Prover one receives a random setting R, and Prover two responds based on that setting <ref:2604.11952#pg2>.

Kai: This two-round variant handles the adaptivity of the PCP verifier by introducing this structure, which leads to specific parameters for soundness and communication complexity.

Mira: The resulting MIP protocol has perfect completeness and a soundness of one - (one - s)/p(n), with communication complexity reaching O(r(n) + p(n)) bits <ref:2604.11952#pg2>.

Lev: That communication complexity bound, O(r(n) + p(n)), is a concrete result that shows how efficiently we can translate the quantum verification into a classical proof system.

Kai: So these improvements are focused on making the translation from quantum computation to a classical proof system as structured and efficient as possible while maintaining strong guarantees against cheating.

Conclusion: Mira: To wrap up, the main implication of this paper is that BQP is always contained in MIP, regardless of the oracle O we choose.

Kai: That means that we've established a relativizing proof system for BQPO, which provides a strong foundation for exploring whether BQP equals IPBQP by showing this containment holds universally.

Lev: For me, the implication is that this work paves the way toward finding an interactive protocol for BQPO where the provers only need to have access to the power of BQP to establish completeness in the unrelativized world.

Mira: I also see it suggesting that there might be a dimension where quantum computation is much more tame than the polynomial hierarchy, which is a significant structural insight into complexity theory.

Lev: If we can follow those lines, it suggests that perhaps we are moving closer to finding an MIP for BQPO where provers require only the power of BQP to establish completeness.

Kai: So in summary, this paper on "A Relativizing MIP for BQP" provides a concrete construction showing how to certify complex quantum computations classically against any oracle.

Mira: It's a result that has deep implications for our understanding of complexity class relationships, suggesting that the relationship between BQP and IPBQP might be settled in the unrelativized world.

Lev: I think this paper provides a solid piece of machinery for future research, especially in exploring how to reduce the computational power of the prover to see if an MIP exists where provers require only "the power of BQP to establish completeness."

Scott Aaronson, Anand Natarajan, Avishay Tal

University of Texas at Austin · Massachusetts Institute of Technology (MIT) · University of California, Berkeley

quant-ph, cs.CC

Submitted: 2026-04-13

Updated: 2026-10-05

Comments: 19 pages, 4 figures

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 91/100

The gist: A major open question in quantum complexity is whether every language in BQP has an interactive proof system with a polynomial-time classical verifier and a polynomial-time quantum prover, which this

Key concepts

BQP
Bounded-error Quantum Polynomial time is the class of decision problems that can be solved by a quantum computer in polynomial time with a small chance of error. This class represents problems efficiently solvable by quantum algorithms.
MIP
MIP stands for Multi-prover Interactive Proof system. It is a framework where one prover convinces another (the verifier) that a statement is true through multiple rounds of interaction, aiming for high certainty in the proof.
Relativizing Proof System
A proof system relativizes to an oracle if the protocol works regardless of what specific information (the oracle O) is provided. This paper demonstrates that the MIP protocol constructed for BQP remains valid even when given any classical oracle.
PCP
Probabilistically Checkable Proofs are a type of proof where a verifier checks only a small, randomly chosen portion of an exponentially long proof string to gain high confidence in the statement's truth.

Terminology

Summary

A major open question in quantum complexity is whether every language in BQP has an interactive proof system with a polynomial-time classical verifier and a polynomial-time quantum prover, which this work addresses by showing that the containment BQP ⊆ MIP holds with respect to any classical oracle. This result is significant because it provides progress towards resolving the question of whether BQP = IPBQP by constructing a relativizing proof system for BQPO.

The Main Result

The central achievement of this work is demonstrating the existence of an MIP protocol for BQP that does relativize to any classical oracle O. This finding can be formally stated as: "For any oracle O, there is an adaptive PCP system for any promise problem in BQPO with perfect completeness and inverse-exponential soundness, where the proof is an exponentially long classical string, and the verifier is a classical PPT machine with oracle access to O that can flip poly(n) random coins and query poly(n) locations (adaptively) in the PCP proof (Theorem 10). This result implies that BQP is always contained in MIP," which contrasts with previous findings where known protocols for BQPO failed to relativize.

The Proof Construction

The protocol is based on constructing an exponentially long classical PCP for a specific problem, the 2-fold FORRELATION problem, which is BQPO-complete. The proof string consists of segments indexed by each gate in the quantum circuit, where each segment describes a quantum state ψ˜i⟩. Instead of writing out the full state vector coefficients, the proof uses a different representation, based on the state-synthesis algorithm of [Aar16, GR02]. This representation is a table (γ, p) of complex phases and conditional probabilities, which can be visualized as a prefix-tree.

The Verifier's Tests

The verifier performs three main types of tests on the proof string π:

  1. (i) Checking that the claimed states ψ˜i⟩ are approximately truthful by verifying local consistency: "for each gate Gi, 1 − ⟨ψ˜i Giψ˜i−1 < 1/ poly(n)."

  2. (ii) Checking the final state's probability: ensuring that the final state assigns a high probability to the desired outcome (e.g., 0n).

  3. (iii) Checking transitions between adjacent states: for each gate Gi, it checks if ψ˜i⟩ ≈ Giψ˜i−1⟩ using a test based on sampling and amplitude access, which confirms the relationship between adjacent states.

Conversion to MIP

The resulting PCP system is then converted into an MIP proof system using a variant of the standard clause-variable transformation. This conversion handles the adaptivity of the PCP verifier by introducing a two-round variant where Prover 1 receives a random setting R, and Prover 2 responds to queries based on that setting. This yields an MIP protocol with specific parameters: perfect completeness, soundness 1 − (1 − s)/p(n), and communication complexity of O(r(n) + p(n)) bits.

Implications for Complexity

The paper illustrates a dimension in which BQP is much more tame than the polynomial hierarchy. Specifically, the result shows that BQP is always contained in MIP, whereas previous oracle separations (like Fortnow and Sipser’s) could separate coNP from MIP as well. This work suggests that progress towards an IP for BQP in the oracle world might lead to a non-cryptographic interactive protocol for proving any quantum computation to a classical skeptic in the unrelativized world. It also opens questions regarding whether there exists an MIP for BQPO where provers require only the power of BQP to establish completeness.

Future Work

The authors suggest several avenues for future research, including finding an oracle separating BQP from IP, or proving a relativizing containment that could pave the way towards a doubly-efficient interactive proof protocol for BQP. Another direction is exploring what happens when reducing the computational power of the prover in their protocol to see if an MIP exists where provers require only the power of BQP to establish completeness. This investigation also focuses on the relativizing behavior of such protocols.

Technical Overview

The proof relies on detailed technical machinery, including Algorithm 1: Computing State Amplitudes and Algorithm 2: Conditional Input Sampling, which use the state synthesis oracle to recover amplitudes. The local checks (Algorithm 3) are tailored based on whether the gate Gi is a single-qubit gate, a two-qubit gate, or an oracle gate, ensuring that each type of operation is verified with appropriate queries to the proof string π and potentially queries to the oracle O.

Improvements for AI systems

Based on this research paper, here are specific improvements for AI systems, focusing on leveraging the theoretical results regarding quantum computation and interactive proofs:

The core contribution of this paper is establishing that for any classical oracle, there exists a Multi-prover Interactive Proof (MIP) system for BQP (Bounded-error Quantum Polynomial time) computations. This translates directly into a powerful framework for certifying the correctness of complex, potentially quantum, processes using classical verification mechanisms.

Here are the specific improvements and what the improved AI system can do:

  1. mathbfCertification of Quantum Computation Correctness (The Quantum Oracle Verifier):

The paper proves that any language in BQPO (a promise problem solvable by a quantum circuit) can be verified by a classical verifier with polynomial queries to an exponentially long proof string, where the verifier has access to an arbitrary classical oracle.

  1. mathbfRobust Verification of Complex Quantum Algorithms:

An AI system could be designed as a Quantum Oracle Verifier that takes the output or execution trace of any quantum algorithm (e.g., a quantum neural network inference or a quantum simulation result) and verifies its correctness against this theorem.

  • The system would use the described PCP structure to check whether the sequence of intermediate states generated by the algorithm is locally consistent with the gates applied, even if those gates include oracle operations (representing complex, non-linear transformations).
  1. mathbfVerifying Quantum State Evolution:

The protocol utilizes a state-synthesis representation (a table of complex phases and conditional probabilities) rather than raw state vectors.

  • An AI system could be specifically trained to process or generate these structured representations of quantum states, allowing it to verify the transition between computational steps in a quantum process by checking consistency against the required local gate operations (single-qubit, two-qubit gates, or oracle queries).
  1. mathbfEnhanced Soundness Against Adversarial Quantum Inputs:

The protocol provides high soundness (soundness of 1 - error, depending on the query complexity and rounds).

  • This means an AI system could be used to detect subtle quantum hallucinations or adversarial inputs that lead a quantum process down an incorrect path. The verifier would use the randomized sampling tests (Algorithm 2) combined with amplitude access checks (Algorithm 3) to find inconsistencies in the proof/trace, rejecting the computation if it deviates significantly from the expected unitary evolution.
  1. mathbfEfficient Compilation of Quantum Programs to Classical Proofs:

The paper shows a reduction from an adaptive PCP system (which verifies quantum computation) to a two-round MIP protocol.

  • An AI compiler could use this framework to automatically translate high-level quantum circuit descriptions into a compact, verifiable classical proof string that is efficient for verification, rather than relying solely on the potentially inefficient standard PSPACE/IP reduction.
  1. mathbfAdaptive and Multi-Round Verification:

The result generalizes to a 2t-round MIPO protocol for soundness at most 1/2 (by setting t = O(p(n)/(1 - s))).

  • This suggests that the AI system can be designed to perform multi-stage, adaptive verification of quantum computations, where subsequent checks can be more stringent or involve deeper analysis of the computation history.

In summary, this research provides a blueprint for an AI system capable of acting as a highly rigorous, classical auditor for quantum processes. It moves beyond simply simulating quantum computers to providing a formal mathematical guarantee (via the MIP/PCP framework) that the quantum computation performed is correct, even in the presence of complex oracle-like operations.

Sources

Related papers