Name
Abstract | ||
|---|---|---|
The widely held belief that BQP strictly contains BPP raises fundamental questions: Upcoming generations of quantumcomputers might already be too large to be simulated classically. Is it possible to experimentallytest that these systems perform as they should, if we cannot efficiently compute predictions for their behavior? Vazirani has asked (21): If computing predictions for Quantum Mechanics requires exponential resources, is Quantum Mechanics a falsifiable theory? In cryptographic settings, an untrusted future company wants to sell a quantum computer or perform a delegated quantumcomputation. Can the customerbe convincedof correctness without the ability to compare results to predictions? To provide answers to these questions, we define Quantum Prover Interactive Proofs (QPIP). Whereas in standard Interactive Proofs (13) 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" (providing a partial answer to a challenge posted in (1)). 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 Ben-Or, Crepeau, Gottesman, Hassidim, and Smith (8), combined with quantum fault tolerance and secure multiparty quantum computation techniques. A slight modification of our constructions makes the protocol "blind": the quantum computation and input remain unknown to the prover. |
Year | Venue | Keywords |
|---|---|---|
2010 | I4CS | authentication,interactive proofs,fault tolerant,quantum physics,system performance,quantum mechanics,quantum computer |
Field | DocType | Citations |
Quantum complexity theory,Quantum no-deleting theorem,Computer science,Quantum computer,Theoretical computer science,Quantum algorithm,Quantum information,Quantum capacity,BQP,Quantum network | Conference | 8 |
PageRank | References | Authors |
0.90 | 16 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Dorit Aharonov | 1 | 659 | 74.21 |
| Michael Ben-Or | 2 | 2008 | 420.97 |
| Elad Eban | 3 | 29 | 4.86 |