Revision 1

Accepted · first revision · record

Title: Classical verification of quantum computation without cryptographic assumptions
Plain: 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: 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).
Settled by: 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.
Kind: well-posed
Answer type: yes-no
References: (empty)
Literature status: open
Status note: (empty)
Posed since: (empty)