  The widely held belief that BQP strictly contains BPP raises fundamental
questions: Upcoming generations of quantum computers might already be too large
to be simulated classically. Is it possible to experimentally test that these
systems perform as they should, if we cannot efficiently compute predictions
for their behavior? Vazirani has asked: If predicting Quantum Mechanical
systems requires exponential resources, is QM a falsifiable theory? In
cryptographic settings, an untrusted future company wants to sell a quantum
computer or perform a delegated quantum computation. Can the customer be
convinced of correctness without the ability to compare results to predictions?
  To answer 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 few qubits. Our main theorem can be roughly stated as: "Any
language in BQP has a QPIP, and moreover, a fault tolerant one". We provide two
proofs. The simpler one uses a new (possibly of independent interest) quantum
authentication scheme (QAS) based on random Clifford elements. This QPIP
however, is not fault tolerant. Our second protocol uses polynomial codes QAS
due to BCGHS, combined with quantum fault tolerance and multiparty quantum
computation techniques. A slight modification of our constructions makes the
protocol "blind": the quantum computation and input are unknown to the prover.
  After we have derived the results, we have learned that Broadbent at al. have
independently derived "universal blind quantum computation" using completely
different methods. Their construction implicitly implies similar implications.
