How to Verify a Quantum Computation

Understand

We give a new theoretical solution to a leading-edge experimental challenge, namely to the verification of quantum computations in the regime of high computational complexity.

• Our results are given in the language of quantum interactive proof systems.
• Specifically, we show that any language in $\mathsf{BQP}$ has a quantum interactive proof system with a polynomial-time classical verifier (who can also prepare random single-qubit pure states), and a quantum polynomial-time prover.
• Here, soundness is unconditional--i.e., it holds even for computationally unbounded provers.