Physics – Quantum Physics
Scientific paper
2008-10-30
Physics
Quantum Physics
24 pages; reorganization of paper, minor content changes
Scientific paper
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.
Aharonov Dorit
Ben-Or Michael
Eban Elad
No associations
LandOfFree
Interactive Proofs For Quantum Computations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Interactive Proofs For Quantum Computations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Interactive Proofs For Quantum Computations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-278013