# Unconditional classical verification with one quantum prover

If a quantum computer solves a problem that no classical computer can solve in reasonable time, how can anyone check its answer? The question is whether an ordinary classical computer, by exchanging messages with a single quantum device, can verify any efficient quantum computation so that even an all-powerful cheating device would be caught, without relying on any unproven cryptographic assumption.

## Problem

$\mathsf{BQP}$ is the class of decision problems that a quantum computer solves in polynomial time with error probability at most $1/3$.

**Question.** Does every language $L\in\mathsf{BQP}$ have an interactive proof with all of the following properties?

- The verifier is a classical probabilistic polynomial-time algorithm that exchanges only classical messages with a single prover.
- *Efficient honest prover.* If $x\in L$, some prover running in quantum polynomial time makes the verifier accept with probability at least $2/3$.
- *Unconditional soundness.* If $x\notin L$, every prover, including computationally unbounded ones, makes the verifier accept with probability at most $1/3$.

Each known protocol gives up one requirement: a fully classical verifier, a single prover, an efficient honest prover, or unconditional soundness. The combination is open.

## Background

Gottesman asked in 2004 whether a classical verifier can check the correctness of quantum evolutions, and Vazirani rephrased this as whether quantum mechanics is falsifiable in the regime where its predictions cannot be computed classically [1]. Because $\mathsf{BQP}\subseteq\mathsf{PSPACE}=\mathsf{IP}$, classical interactive proofs for quantum computations exist, but the generic protocol asks its honest prover to solve $\mathsf{PSPACE}$-complete problems, believed to be far beyond a quantum computer [6]. Aharonov, Ben-Or and Eban introduced quantum prover interactive proofs in 2008 and asked whether the verifier can be made entirely classical [1]. Henry Yuen posted the unconditional version as Problem 45 of the IQOQI Vienna Open Quantum Problems in 2023 [6].

## What is known

- With a verifier that also holds a constant number of qubits, every $\mathsf{BQP}$ language has such a protocol, which moreover hides the computation from the prover [1]. Fitzsimons and Kashefi gave unconditionally verifiable blind protocols in which the verifier only prepares single qubits and sends them to the prover [3].
- With two provers that share entanglement but cannot communicate, a fully classical verifier suffices, through the rigidity of CHSH games (Reichardt, Unger and Vazirani, 2013) [2].
- With one prover and a fully classical verifier, Mahadev (2018) gave a protocol whose soundness holds against efficient quantum provers, assuming that the learning-with-errors problem is hard for them [4].
- Aaronson, Cojocaru, Gheorghiu and Kashefi showed that information-theoretically secure blind delegation of $\mathsf{BQP}$ with only $O(n^d)$ bits of classical communication would imply $\mathsf{BQP}\subseteq\mathsf{MA}/O(n^d)$, a containment that fails relative to an oracle [5]. A solution therefore probably cannot also hide the computation, as the protocols of [1, 3] do.
- Green showed that a natural family of single-prover protocols, which generalizes earlier quantum-inspired interactive proofs, needs a prover far more powerful than a quantum computer (preprint, 2021) [7].

## What would count as progress

- A protocol with all three properties for a $\mathsf{BQP}$-complete problem, with full proofs of completeness and soundness.
- Evidence against: a proof that such a protocol, even one that does not hide the computation, would imply an unlikely complexity-class containment, extending the approach of [5] from blind delegation to verification.

## References

1. D. Aharonov, M. Ben-Or, E. Eban and U. Mahadev, "Interactive proofs for quantum computations", preprint (2017), journal version of work reported in 2008. [arXiv:1704.04487](https://arxiv.org/abs/1704.04487)
2. B. W. Reichardt, F. Unger and U. Vazirani, "Classical command of quantum systems", *Nature* 496, 456–460 (2013). [doi:10.1038/nature12035](https://doi.org/10.1038/nature12035)
3. J. F. Fitzsimons and E. Kashefi, "Unconditionally verifiable blind quantum computation", *Physical Review A* 96, 012303 (2017). [doi:10.1103/PhysRevA.96.012303](https://doi.org/10.1103/PhysRevA.96.012303)
4. U. Mahadev, "Classical verification of quantum computations", in *2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)*, 259–267 (2018). [doi:10.1109/FOCS.2018.00033](https://doi.org/10.1109/FOCS.2018.00033)
5. S. Aaronson, A. Cojocaru, A. Gheorghiu and E. Kashefi, "Complexity-theoretic limitations on blind delegated quantum computation", in *46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)*, LIPIcs 132, 6 (2019). [doi:10.4230/LIPIcs.ICALP.2019.6](https://doi.org/10.4230/LIPIcs.ICALP.2019.6)
6. H. Yuen (contact), "Single-prover interactive proofs for quantum computations", Open Quantum Problems, IQOQI Vienna, problem 45 (posted 2023). [Archived page](https://web.archive.org/web/20231029013440/https://oqp.iqoqi.oeaw.ac.at/single-prover-interactive-proofs-for-quantum-computations)
7. A. Green, "On information-theoretic classical verification of quantum computers", preprint (2021). [arXiv:2105.05942](https://arxiv.org/abs/2105.05942)

## Source

Imported from [QIQCOP Zoo op_3770ad932d54692f](https://qiqc-op.com/problem/op_3770ad932d54692f/), curated by Bikun Li, Qicheng Tang, Changhao Li, Chengkai Zhu, Minbo Gao, Zhong-Xia Shang, Bin Cheng and Naixu Guo. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.