Noncryptographic classical verification of BQP

The verifier must be genuinely classical and the honest prover efficient. The inclusion $\mathsf{BQP}\subseteq\mathsf{IP}=\mathsf{PSPACE}$ alone does not provide an efficient honest prover. Conversely, a protocol sound only against efficient quantum cheats does not meet the information-theoretic soundness target stated here.

Mahadev's classical-verification protocol is a landmark positive result with computational soundness under a quantum-hard lattice assumption. Protocols with a small trusted quantum verifier or multiple separated provers solve different resource models.

An April 2026 preprint by Aaronson–Natarajan–Tal–Villanyi proves $\mathsf{BQP}^{O}\subseteq\mathsf{MIP}^{O}$ for every classical oracle $O$. It is progress in a relativized multi-prover model and explicitly motivates noncryptographic verification, but does not construct the single efficient prover protocol sought here. Related: A1, A3, A10.

Source catalogue review: 4 September 2026. Improved indicates partial progress, including qualified preprint claims.

published: Mahadev achieves classical verification with computational soundness under a lattice hardness assumption; the assumption-free target is stronger. Evidence

preprint: Relativizing multi-prover containment for BQP with classical oracles, not efficient single-prover noncryptographic verification. Evidence