Interactive Proofs for Quantum Computations

The widely held belief that BQP strictly contains BPP raises fundamental questions: if we cannot efficiently compute predictions for the behavior of quantum systems, how can we test their behavior? In other words, is quantum mechanics falsifiable? In cryptographic settings, how can a customer of a future untrusted quantum computing company be convinced of the correctness of its quantum computations? To provide answers to these questions, we define Quantum Prover Interactive Proofs (QPIP). Whereas in standard interactive proofs the prover is computationally unbounded, here our prover is in BQP, representing a quantum computer. The verifier models our current computational capabilities: it is a BPP machine, with access to only a few qubits. Our main theorem states, roughly: 'Any language in BQP has a QPIP, which also hides the computation from the prover'. We provide two proofs, one based on a quantum authentication scheme (QAS) relying on random Clifford rotations and the other based on a QAS which uses polynomial codes (BOCG+ 06), combined with secure multiparty computation methods. This is the journal version of work reported in 2008 (ABOE08) and presented in ICS 2010; here we have completed the details and made the proofs rigorous. Some of the proofs required major modifications and corrections. Notably, the claim that the polynomial QPIP is fault tolerant was removed. Similar results (with different protocols) were reported independently around the same time of the original version in BFK08. The initial independent works (ABOE08, BFK08) ignited a long line of research of blind verifiable quantum computation, which we survey here, along with connections to various cryptographic problems. Importantly, the problems of making the results fault tolerant as well as removing the need for quantum communication altogether remain open.