pdf icon
Volume 12 (2016) Article 3 pp. 1-42
Interactive Proofs for $\mathsf{BQP}$ via Self-Tested Graph States
Received: May 3, 2015
Revised: June 1, 2016
Published: June 18, 2016
Download article from ToC site:
[PDF (371K)] [PS (2310K)] [Source ZIP]
Misc.:
[About the Author] [HTML Bibliography] [BibTeX]
Keywords: complexity theory, quantum computing, interactive proofs, BQP
Categories: complexity theory, quantum computing, interactive proofs, BQP
ACM Classification: F.1.3
AMS Classification: 68Q15

Abstract: [Plain Text Version]

$ \newcommand{\cclass}[1]{\mathsf{#1}} $

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 $\cclass{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 $\cclass{BQP}$.