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
2. B. W. Reichardt, F. Unger and U. Vazirani, "Classical command of quantum systems", Nature 496, 456–460 (2013). doi: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
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
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
6. H. Yuen (contact), "Single-prover interactive proofs for quantum computations", Open Quantum Problems, IQOQI Vienna, problem 45 (posted 2023). Archived page
7. A. Green, "On information-theoretic classical verification of quantum computers", preprint (2021). arXiv:2105.05942

Source

Imported from QIQCOP Zoo 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.