Unconditional classical verification with one quantum prover
- Field
- Topics
Problem
Does every language \(L\in\mathsf{BQP}\) admit a single-prover interactive proof with a fully classical verifier, an efficient quantum honest prover, and information-theoretic soundness? Precisely, require a probabilistic classical polynomial-time verifier exchanging only classical messages with one prover; a uniform quantum polynomial-time honest prover; acceptance probability at least \(2/3\) for every yes-instance when the honest prover is used; and acceptance probability at most \(1/3\) for every no-instance against every prover, including a computationally unbounded one. Equivalently, can one classically verify an arbitrary efficient quantum computation with one efficient quantum prover, no quantum capability for the verifier, and no cryptographic assumption?
Source
Aharonov, Ben-Or, Eban, and Mahadev explicitly ask whether the verifier’s remaining quantum register can be eliminated from an unconditional single-prover verification protocol [ABE+17].
Progress
The inclusions \(\mathsf{BQP}\subseteq\mathsf{PSPACE}=\mathsf{IP}\) give classical-verifier interactive proofs for \(\mathsf{BQP}\), but do not ensure that the honest prover is implementable in quantum polynomial time [ADH97], [Sha92].
Unconditional protocols with an honest \(\mathsf{BQP}\) prover are known when the verifier retains a constant-size quantum register or exchanges a small number of qubits [ABE+17]. They do not meet the fully classical verifier and classical-message requirements.
A fully classical single-verifier protocol is known under the learning-with-errors assumption [Mah18]. Its soundness is computational against efficient quantum provers, rather than information theoretic against arbitrary provers.
Fully classical and unconditional verification is possible with multiple noncommunicating entangled provers [RUV13]. This changes the single-prover model required in the problem statement.
Comment
Section 1.8 of [ABE+17] explicitly asks whether the verifier’s remaining quantum register can be eliminated. The unresolved conjunction is one prover, a fully classical verifier, a \(\mathsf{BQP}\) honest prover, and unconditional soundness; relaxing any one of these requirements leads to known protocols.