Theory of Computing
-------------------
Title : Interactive Proofs for $\mathsf{BQP}$ via Self-Tested Graph States
Authors : Matthew McKague
Volume : 12
Number : 3
Pages : 1-42
URL : http://www.theoryofcomputing.org/articles/v012a003
Abstract
--------
Using the measurement-based quantum computation model, we construct
interactive proofs with non-communicating quantum provers and a
classical verifier. Our construction gives interactive proofs for
all languages in BQP with a polynomial number of quantum provers,
each of which, in the honest case, performs only a _single
measurement._
In this paper we introduce two main improvements over previous work
in self-testing for graph states. Specifically, we derive new error
bounds which scale polynomially with the size of the graph compared
with exponential dependence on the size of the graph in previous
work. We also extend the self-testing error bounds on measurements
to a very general set which includes the adaptive measurements used
for measurement-based quantum computation as a special case. These
improvements allow us to apply graph state self-testing and
measurement based quantum computation to build interactive proofs
for all languages in BQP.