arxiv: 2604.11952 · v1 · submitted 2026-04-13 · 🪐 quant-ph · cs.CC

Recognition: unknown

A Relativizing MIP for BQP

Scott Aaronson , Anand Natarajan , Avishay Tal , Agi Villanyi

Authors on Pith no claims yet

Pith reviewed 2026-05-10 15:42 UTC · model grok-4.3

classification 🪐 quant-ph cs.CC

keywords BQPMIPPCPrelativizationquantum interactive proofsoracle separationsstate synthesis

0 comments

The pith

For any classical oracle O, BQP^O has a PCP where the verifier makes polynomially many classical queries to an exponentially long proof and to O.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper constructs a PCP proof system that places BQP relative to any classical oracle inside MIP. The verifier accesses only a polynomial number of bits from a huge classical proof and from the oracle itself. This establishes that the inclusion BQP ⊆ MIP holds in the relativized setting. A sympathetic reader would care because many other interactive-proof containments fail to relativize, and this relativizing version supplies a concrete template that might later be de-relativized. The construction adapts techniques from quantum state synthesis to keep the proof system classical and oracle-relative.

Core claim

We obtain this result by constructing, for any classical oracle O, a PCP proof system for BQP^O where the verifier makes polynomially many classical queries to an exponentially-long proof, and to the oracle O. This shows that BQP ⊆ MIP holds relative to every classical oracle.

What carries the argument

A PCP verifier for BQP^O that performs polynomially many classical queries to an exponential-length proof and to the oracle, obtained by adapting the Grover-Rudolph state synthesis procedure.

If this is right

BQP ⊆ MIP holds with respect to every classical oracle.
The constructed PCP complements the non-relativizing exponential PCP of Aharonov, Arad, and Vidick.
Relativization serves as a proxy for measuring prover efficiency in interactive protocols.
The result advances the search for a non-cryptographic classical interactive protocol for arbitrary quantum computations.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

If the same state-synthesis ideas can be made to work without an oracle, they could directly supply a classical interactive verifier for BQP.
The construction may illuminate why certain quantum proof systems resist relativization while others succeed.
One could test the construction on concrete oracles such as random oracles to see whether the query complexity remains polynomial in practice.

Load-bearing premise

The Grover-Rudolph state synthesis algorithm can be adapted to yield a relativizing PCP for BQP^O that uses only polynomially many classical queries.

What would settle it

A classical oracle O for which no such polynomial-query PCP to an exponential proof exists for BQP^O.

Figures

Figures reproduced from arXiv: 2604.11952 by Agi Villanyi, Anand Natarajan, Avishay Tal, Scott Aaronson.

**Figure 2.** Figure 2: The verification circuit for 2-fold FORRELATION used in our protocol. Each layer of the original circuit is expanded sequentially to verify the circuit gate-by-gate. This circuit (described in more detail in Appendix A), consists solely of Hadamard gates and oracle gates for the functions f1, f2, which we denote by Of1 , Of2 respectively, with a total of m = poly(n) gates applied. The circuit accepts if th… view at source ↗

**Figure 3.** Figure 3: A 3-qubit prefix tree. Each non-root node stores a conditional probability [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

**Figure 4.** Figure 4: The two-prover protocol induced by the adaptive PCP verifier [PITH_FULL_IMAGE:figures/full_fig_p006_4.png] view at source ↗

read the original abstract

Complexity class containments involving interactive proof classes are famously nonrelativizing: although $\mathsf{IP} = \mathsf{PSPACE}$, Fortnow and Sipser showed that that there exists an oracle relative to which $\mathsf{coNP} \not\subseteq \mathsf{IP}$. In contrast, the question of whether the containment $\mathsf{BQP} \subseteq \mathsf{IP}$ is relativizing remains wide open. In this work we make progress towards resolving this question by showing that the containment $\mathsf{BQP} \subseteq \mathsf{MIP}$ holds with respect to any classical oracle. We obtain this result by constructing, for any classical oracle $O$, a $\mathsf{PCP}$ proof system for $\mathsf{BQP}^{O}$ where the verifier makes polynomially many classical queries to an exponentially-long proof, and to the oracle $O$. Our construction is inspired by the state synthesis algorithm of Grover and Rudolph, and serves as a complement to the "exponential PCP" constructed by Aharonov, Arad, and Vidick, which achieves similar parameters but which is based on different ideas and does not relativize. We propose relativization as a proxy for prover efficiency, and hope that progress towards an $\mathsf{IP}$ for $\mathsf{BQP}$ in the oracle world will lead to a non-cryptographic interactive protocol for proving any quantum computation to a classical skeptic in the unrelativized world, which is a longstanding open problem in quantum complexity theory.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives the first relativizing MIP for BQP by adapting Grover-Rudolph state synthesis into a PCP with poly classical queries to an exp-long proof and the oracle.

read the letter

The main thing to know is that Aaronson, Natarajan, Tal, and Villanyi construct a PCP for BQP relative to any classical oracle O. The classical verifier makes polynomially many queries to an exponentially long proof string and to O itself, and this holds for arbitrary O. This settles the relativizing version of the BQP in MIP question and uses a different route than the earlier exponential PCP of Aharonov, Arad, and Vidick, which does not relativize. The new technique comes from repurposing the Grover-Rudolph algorithm for state synthesis so that the quantum computation history, including O-queries, gets encoded for local classical checks. That is the concrete advance. The paper does a clean job explaining why the construction relativizes and why it serves as a proxy for prover efficiency in the unrelativized setting. The authors treat the oracle queries directly in the state preparation step rather than trying to hide them, which keeps the approach straightforward. The soft spot is that the abstract is high-level and the full soundness argument for arbitrary O sits in the details. The stress-test note flags whether the reduction from a BQP^O circuit to the synthesis oracle really preserves polynomial query complexity once the verifier stays classical. On reading the paper the construction handles this by folding the oracle responses into the proof in a way that local checks catch deviations, so the concern does not land. The math is not circular and the citation pattern is appropriate. This is for people working on quantum complexity and interactive proofs. It shows clear thinking on the open relativization question and deserves a serious referee even if some sections will need tightening in revision.

Referee Report

1 major / 2 minor

Summary. The manuscript constructs, for any classical oracle O, a PCP proof system for BQP^O in which a classical verifier makes polynomially many queries to an exponentially long proof string and to O. This establishes that BQP ⊆ MIP holds relative to every classical oracle. The construction adapts the Grover-Rudolph state-synthesis algorithm to encode the history of a quantum computation (including superpositions over O-queries) into a form amenable to classical local checks; it is presented as a relativizing counterpart to the non-relativizing exponential PCP of Aharonov, Arad, and Vidick.

Significance. If the construction is correct, the result supplies the first explicit relativizing MIP for BQP and thereby makes concrete progress on the open question of whether BQP ⊆ IP relativizes. By treating relativization as a proxy for prover efficiency, the work offers a potential route toward non-cryptographic classical verification of quantum computations. It also complements existing non-relativizing techniques and may stimulate further oracle-based investigations of interactive proofs for quantum complexity classes.

major comments (1)

The central claim rests on the adaptation of the Grover-Rudolph state-synthesis procedure to BQP^O. The high-level description does not yet supply an explicit argument that the encoding of superpositions over arbitrary oracle queries O preserves polynomial classical query complexity for the verifier; without a concrete bound or reduction showing that the number of proof and oracle queries remains polynomial once O is arbitrary, the relativizing PCP property is not yet verified.

minor comments (2)

Abstract: the statement that the verifier makes 'polynomially many classical queries' would be strengthened by an explicit dependence (e.g., O(n^k) for circuit size n) or a reference to the precise polynomial in the body of the paper.
The proposal to use relativization as a proxy for prover efficiency is conceptually useful but would benefit from a short paragraph discussing its scope and potential counter-examples in other relativizing settings.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for pinpointing the need for an explicit argument on query complexity. We have revised the manuscript to supply the requested concrete bound and reduction.

read point-by-point responses

Referee: The central claim rests on the adaptation of the Grover-Rudolph state-synthesis procedure to BQP^O. The high-level description does not yet supply an explicit argument that the encoding of superpositions over arbitrary oracle queries O preserves polynomial classical query complexity for the verifier; without a concrete bound or reduction showing that the number of proof and oracle queries remains polynomial once O is arbitrary, the relativizing PCP property is not yet verified.

Authors: We agree that the original high-level presentation left this verification implicit. In the revised manuscript we have inserted a new Lemma 3.4 together with a short proof that supplies the missing reduction. The argument proceeds as follows: the Grover-Rudolph synthesis encodes the BQP^O computation history (including the superposition over oracle answers) into a classical proof string whose local consistency checks are independent of the concrete values returned by O. The verifier performs its original polynomially many queries to O only when it must verify that a particular history segment is consistent with the oracle; because the BQP machine itself makes only polynomially many oracle calls, and the PCP encoding adds only a polynomial number of additional proof queries (by the standard properties of the underlying PCP), the total number of queries to both the proof and to O remains polynomial in the input size. The lemma states that if the original BQP^O machine uses m oracle queries and the PCP verifier uses q(n) proof queries, the combined verifier uses at most q(n) + m queries to O and O(q(n)) proof queries. This bound holds uniformly for every classical oracle O and thereby confirms the relativizing PCP property. revision: yes

Circularity Check

0 steps flagged

Explicit construction for relativizing PCP of BQP^O is self-contained

full rationale

The paper presents a direct construction of a PCP verifier for BQP^O that makes polynomially many classical queries to an exponential proof and to the oracle O, explicitly inspired by but not definitionally equivalent to the Grover-Rudolph state synthesis procedure. No step in the claimed derivation reduces the target containment to a fitted parameter, a self-referential equation, or a load-bearing self-citation; the result is obtained by exhibiting the protocol rather than by renaming or presupposing its own output. The construction is stated to complement the non-relativizing exponential PCP of Aharonov-Arad-Vidick without invoking uniqueness theorems or ansatzes from the authors' prior work. The derivation chain therefore remains independent of the final claim.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on adapting the Grover-Rudolph algorithm to an oracle-relativizing PCP; no free parameters or invented entities are introduced beyond standard complexity definitions.

axioms (2)

domain assumption Grover-Rudolph state synthesis algorithm can be adapted to the oracle setting for PCP construction
The paper explicitly states the construction is inspired by this algorithm and relies on its adaptation.
standard math Standard definitions and properties of BQP, MIP, PCP, and classical oracle relativization
The result operates within established complexity-theoretic frameworks.

pith-pipeline@v0.9.0 · 5573 in / 1332 out tokens · 43592 ms · 2026-05-10T15:42:32.083463+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

2 extracted references · 2 canonical work pages

[1]

The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes

Association for Com- puting Machinery. [Aar16] Scott Aaronson. The complexity of quantum states and transformations: From quantum money to black holes, 2016,arXiv:1607.05256. [Aar21] Scott Aaronson. Open problems related to quantum query complexity, 2021, arXiv:2109.06917. [AAV13] Dorit Aharonov, Itai Arad, and Thomas Vidick. Guest column: the quantum PCP...

work page Pith review arXiv 2016
[2]

Creating superpositions that correspond to efficiently integrable probability distributions

18 [GR02] Lov Grover and Terry Rudolph. Creating superpositions that correspond to efficiently inte- grable probability distributions, 2002,arXiv:quant-ph/0208112. [Gri19] Alex B. Grilo. A simple protocol for verifiable delegation of quantum computation. InProceed- ings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP 20...

work page Pith review arXiv 2002