  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.
