CaltechAUTHORS
  A Caltech Library Service

Interactive Proofs for Quantum Computations

Aharonov, Dorit and Ben-Or, Michael and Eban, Elad and Mahadev, Urmila (2017) Interactive Proofs for Quantum Computations. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20200805-141909801

[img] PDF - Submitted Version
See Usage Policy.

1078Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20200805-141909801

Abstract

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.


Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription
http://arxiv.org/abs/1704.04487arXivDiscussion Paper
Additional Information:D.A. thanks Oded Goldreich, Madhu sudan and Guy Rothblum for exciting and inspiring conversations that eventually led to this work. E.E. thanks Avinatan Hassidim for stimulating and refining ideas, particularly about fault tolerance. We also thank Gil Kalai, David DiVincenzo and Ari Mizel, for stimulating questions and clarifications, and Daniel Gottesman for many helpful ideas and remarks, and in particular, for his help in proving Theorem 1.4.
Record Number:CaltechAUTHORS:20200805-141909801
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20200805-141909801
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:104763
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:05 Aug 2020 21:39
Last Modified:05 Aug 2020 21:39

Repository Staff Only: item control page