Unconditional Single-Prover Classical Verification of BQP Computations

Unconditional Single-Prover Classical Verification of BQP Computations

Definitions and mathematical statement

An interactive proof consists of a verifier and prover exchanging messages, with acceptance determined after polynomially many rounds. Here the verifier is classical probabilistic polynomial time, every message is classical, and the honest prover is uniform quantum polynomial time. For each $L\in\mathsf{BQP}$ require \[ x\in L\Rightarrow\Pr[\text{accept with honest prover}]\ge2/3,\qquad x\notin L\Rightarrow\sup_{P^*}\Pr[\text{accept with }P^*]\le1/3. \] The supremum includes computationally unbounded cheating provers. There is only one prover, and no computational hardness assumption weakens the information-theoretic soundness requirement.

Formulation and concept references: [S1].

Short English statement

Can a fully classical efficient verifier check arbitrary efficient quantum computations using one prover and unconditional security?

Research attempt

Current frontier and scope.

The original issue formulates a single-prover protocol with a classical efficient verifier, an efficient honest quantum prover, and soundness against an unbounded cheating prover. [S1] Mahadev's classical verification theorem is an important adjacent result, but its security is computational and uses a quantum hardness assumption; it is not the information-theoretic statement selected here. [E1] These distinctions remain part of the target even if one changes round complexity or amplifies the completeness--soundness gap. The literature check, made on 27 September 2026, did not supply a verified general protocol satisfying all the selected requirements.

Attack map.

One possible approach is to make the public interaction small enough that a classical verifier can test all consistency conditions. The lemma below shows that a polynomial-size public transcript tree would actually make the whole language classically decidable with bounded error. A second approach is to use local consistency questions to prevent adaptive cheating; a two-constraint example diagnoses the need for a genuine consistency mechanism. A third is to implement a powerful classical interactive proof using an honest quantum prover; its missing ingredient is an efficient way for that prover to answer all auxiliary queries, not just to compute the final decision bit. None of these obstacles is an unconditional impossibility theorem for the original polynomial-communication problem.

Attempt I: a small-transcript simulation lemma.

Fix an input $x$ of length $n$. Consider an all-classical interaction with a probabilistic polynomial-time verifier $V$. Its private random tape has a polynomial upper length bound and can be sampled in advance. Suppose the legal public transcript tree has at most $L=\operatorname{poly}(n)$ leaves and can be enumerated in polynomial time. For example, a fixed message schedule using at most $C\log_2 n$ communicated bits has this property. Message lengths, stopping signals and any visible scheduling information must be included in this budget; an uncharged timing channel is not permitted.

For a complete public history $h$, define \begin{equation}\label{wsref-0-33-30-30-30-36-37-34-31-3a-6c-65-61-66-77-65-69-67-68-74} w_h=\Pr_R\left[\begin{gathered} V\text{ sends precisely its messages in }h\text{ and accepts,}\\ \text{when supplied the prover messages in }h \end{gathered}\right]. \end{equation} This is an unconditional probability over $R$, not a probability conditioned on reaching a potentially rare transcript. It is classically estimable: sample $R$, simulate $V$ with the designated prover messages, and output zero if any verifier message or stopping decision differs from $h$.

For any deterministic prover strategy $\pi$, let $\mathcal L(\pi)$ be the set of leaves consistent with its choices at prover nodes. Then \begin{equation}\label{wsref-0-33-30-30-30-36-37-34-31-3a-76-61-6c-75-65} \Pr[V^\pi(x)\text{ accepts}]=\sum_{h\in\mathcal L(\pi)}w_h. \end{equation} The acceptance events on the right are disjoint: a random tape and a fixed strategy generate only one transcript. A randomized prover is a distribution over deterministic contingent strategies and cannot exceed the largest deterministic acceptance probability. The same holds for a prover using quantum internal memory when all messages are classical. Its conditional response distributions on classical histories can be reproduced by an unbounded classical randomized strategy, and every such behavioral strategy is a mixture of contingent deterministic choices on this finite tree.

The maximum in (30006741:value) is computable from the leaf weights by a bottom-up recursion. At a prover node take the maximum over its children; at a verifier node take the sum. No fresh branching probabilities are multiplied in at verifier nodes: they have already been included in $w_h$. Choices after different verifier messages may be optimized independently, because the prover sees those messages. Induction on subtrees proves that this recursion equals the optimal unbounded-prover acceptance probability at the root.

Estimate each $w_h$ to additive error $\delta=1/(100L)$ with simultaneous success probability at least $0.99$. Independent Bernoulli sampling and the elementary exponential tail bound require $O(\delta^{-2}\log(100L))$ samples per leaf, a polynomial number overall. For each fixed strategy, replacing $w_h$ by its estimate changes (30006741:value) by at most $L\delta$. Taking a maximum preserves this error bound. Thus the computed optimal acceptance probability has additive error at most $1/100$, except with probability at most $0.01$.

Small-transcript lemma. Any language with such a polynomial-size transcript-tree protocol, completeness at least $2/3$, and soundness at most $1/3$ against every prover lies in $\mathsf{BPP}$.

Proof. On yes-inputs the optimal acceptance probability is at least $2/3$, regardless of how the honest strategy is implemented. On no-inputs the soundness quantifier bounds that optimum by $1/3$. The estimate above, thresholded at $1/2$, decides the language with error at most $0.01$ in polynomial time. $\square$

The proof does not enumerate exponentially many contingent strategies; the dynamic program optimizes them together. It does not divide by a small probability of reaching a history. These two details are essential for a valid polynomial-time simulation of private-coin protocols.

Consequences and the remaining communication gap.

If every $\mathsf{BQP}$ language had a protocol of the stated kind with $O(\log n)$ total public communication and a fixed schedule, the lemma would give $\mathsf{BQP}\subseteq\mathsf{BPP}$; the reverse containment comes from simulating classical randomness quantumly. This is a conditional collapse consequence, not a proved separation that rules out such protocols. It flags the depth of any claimed logarithmic compression of the verification task.

For the actual catalogue problem, polynomially many communicated bits can give exponentially many leaves. The same recursion is still a finite exact characterization, but estimating every leaf to error $O(1/L)$ is no longer a polynomial-time algorithm. Replacing $L$ by its logarithm without a new structural theorem would invalidate both the error budget and the runtime. The original problem permits this large tree; the lemma therefore does not disprove it.

Attempt II: can small local tests enforce one global computation?

A minimal adversarial example is the inconsistent pair of classical requirements $b=0$ and $b=1$. A verifier that asks one uniformly chosen requirement and lets the prover supply the requested bit accepts an adaptive prover with probability one. No fixed bit satisfies both requirements, but the local response need not have been fixed before the challenge. Repeating this interaction without a binding consistency mechanism does not fix the problem.

This example does not prove an impossibility theorem for classical interactive proofs. Such proofs can use algebraic consistency and other mechanisms much richer than this test. It does show that the proposed inference "every local constraint is checked with positive probability, hence one global witness exists" is false. A claimed protocol must prove the existence or adequate consistency of a single underlying computation against an adaptive unbounded strategy.

One can also imagine expressing quantum circuit amplitudes as sums and asking the prover for intermediate sums. Exact circuit expansion has exponentially many paths. The fact that a quantum computer can sample the circuit's output distribution does not furnish exact values of all arbitrary partial path sums requested by a classical verifier. A complete version of that route needs an efficient honest-response algorithm and an information-theoretic consistency proof. Neither is supplied by writing down the path-sum identity. Conversely, a cryptographically binding mechanism does not give the target's unbounded-prover soundness simply because the honest prover is quantum polynomial time; the security distinction in [E1] is substantive.

Stress test.

The small-transcript theorem includes verifier private randomness and adaptive prover responses. It does not assume that all verifier coins are public. Leaf weights can be tiny, since only absolute accuracy is used. Acceptance probabilities for different leaves are not incorrectly normalized as a single strategy-independent distribution: their sum may exceed one when incompatible prover choices are included. The max/sum recursion handles that distinction.

The honest-prover restriction was not needed for the simulation lemma, so no efficient description of its quantum state is hidden in the argument. The classical language formulation is maintained; no oracle or promise-problem statement is substituted. The companion script checks the recursion against explicit enumeration of contingent strategies on small private-coin transcript trees, including rare histories, using rational arithmetic. Those checks do not establish a polynomial-size transcript tree for arbitrary quantum computations.

Outcome.

Outcome: Exploratory approach with unresolved gap.

The proved small-transcript simulation places polynomial-size transcript-tree protocols in $\mathsf{BPP}$. It does not handle the exponential transcript trees allowed by the original problem. A general unconditional protocol or impossibility theorem remains unproved; no priority claim is made.

Sources

• S1 Mario Krenn, Formalize Open Quantum Problem #49: Single-prover interactive proofs for quantum computations, google-deepmind/formal-conjectures issue 3466, opened 6 March 2026. https://github.com/google-deepmind/formal-conjectures/issues/3466. Catalogue formulation source.
• E1 Urmila Mahadev. Classical Verification of Quantum Computations, arXiv:1804.01082 $2018$, abstract and introduction; computational soundness under a hardness assumption. https://arxiv.org/abs/1804.01082. Consulted 27 September 2026 for the indicated result or scope.