Theory of Computing
-------------------
Title : How to Verify a Quantum Computation
Authors : Anne Broadbent
Volume : 14
Number : 11
Pages : 1-37
URL : http://www.theoryofcomputing.org/articles/v014a011
Abstract
--------
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 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. Compared to prior work achieving similar results,
our technique does not require the encoding of the input or of the
computation; instead, we rely on encryption of the input (together
with a method to perform computations on encrypted inputs), and show
that the random choice between three types of input (defining a
_computational run_, versus two types of _test runs_) suffices.
Because the overhead is very low for each run (it is linear in the
size of the circuit), this shows that verification could be achieved
at minimal cost compared to performing the computation. As a proof
technique, we use a reduction to an entanglement-based protocol; to
the best of our knowledge, this is the first time this technique has
been used in the context of verification of quantum computations, and
it enables a relatively straightforward analysis.