QI In the literature: open

Classical verification of quantum computation without cryptographic assumptions

In plain words

A purely classical user can check a quantum computer's answer if one assumes certain codes are hard to break, or if two separated quantum computers are questioned. Whether one quantum computer can be checked by a classical user with no such assumption is open.

Precise statement

Does every language in BQP have an interactive proof with a BPP verifier exchanging only classical messages with a single BQP prover, sound against computationally unbounded provers? Known protocols need a verifier holding a few qubits, two non-communicating entangled provers (Reichardt, Unger and Vazirani 2013), or soundness only against provers who cannot solve learning with errors (Mahadev, arXiv:1804.01082, 2018).

What would settle it

An information-theoretically sound single-prover classical-verifier protocol for BQP, or a complexity-theoretic consequence (such as a class collapse) showing it cannot exist.

See also