A Caltech Library Service

Simpler Proofs of Quantumness

Brakerski, Zvika and Koppula, Venkata and Vazirani, Umesh and Vidick, Thomas (2020) Simpler Proofs of Quantumness. In: 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics. Schloss Dagstuhl – Leibniz-Zentrum für Informatik , Wadern, Germany, Art. No. 8.

[img] PDF - Published Version
Creative Commons Attribution.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


A proof of quantumness is a method for provably demonstrating (to a classical verifier) that a quantum device can perform computational tasks that a classical device with comparable resources cannot. Providing a proof of quantumness is the first step towards constructing a useful quantum computer. There are currently three approaches for exhibiting proofs of quantumness: (i) Inverting a classically-hard one-way function (e.g. using Shor’s algorithm). This seems technologically out of reach. (ii) Sampling from a classically-hard-to-sample distribution (e.g. BosonSampling). This may be within reach of near-term experiments, but for all such tasks known verification requires exponential time. (iii) Interactive protocols based on cryptographic assumptions. The use of a trapdoor scheme allows for efficient verification, and implementation seems to require much less resources than (i), yet still more than (ii). In this work we propose a significant simplification to approach (iii) by employing the random oracle heuristic. (We note that we do not apply the Fiat-Shamir paradigm.) We give a two-message (challenge-response) proof of quantumness based on any trapdoor claw-free function. In contrast to earlier proposals we do not need an adaptive hard-core bit property. This allows the use of smaller security parameters and more diverse computational assumptions (such as Ring Learning with Errors), significantly reducing the quantum computational effort required for a successful demonstration.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2020 Zvika Brakerski, Venkata Koppula, Umesh Vazirani, and Thomas Vidick; licensed under Creative Commons License CC-BY. Date of publication: 08.06.2020. Funding: Zvika Brakerski: Supported by the Binational Science Foundation (Grant No. 2016726), and by the European Union Horizon 2020 Research and Innovation Program via ERC Project REACT (Grant 756482) and via Project PROMETHEUS (Grant 780701). Venkata Koppula: Supported by the Binational Science Foundation (Grant No. 2016726), and by the European Union Horizon 2020 Research and Innovation Program via ERC Project REACT (Grant 756482) and via Project PROMETHEUS (Grant 780701). Umesh Vazirani: Supported in part by ARO Grant W911NF-12-1-0541, NSF Grant CCF1410022, a Vannevar Bush faculty fellowship, and the Miller Institute at U.C. Berkeley through a Miller Professorship. Thomas Vidick: Supported by NSF CAREER Grant CCF-1553477, AFOSR YIP award number FA9550-16-1-0495, a CIFAR Azrieli Global Scholar award, MURI Grant FA9550-18-1-0161, and the IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1125565).
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Binational Science Foundation (USA-Israel)2016726
European Research Council (ERC)756482
European Research Council (ERC)780701
Army Research Office (ARO)W911NF-12-1-0541
Vannevar Bush FellowshipUNSPECIFIED
Miller Institute for Basic Research in ScienceUNSPECIFIED
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0495
Canadian Institute for Advanced Research (CIFAR)UNSPECIFIED
Air Force Office of Scientific Research (AFOSR)FA9550-18-1-0161
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Subject Keywords:Proof of Quantumness, Random Oracle, Learning with Errors
Series Name:Leibniz International Proceedings in Informatics
Classification Code:2012 ACM Subject Classification: Theory of computation; Cryptographic protocols; Theory of Computation; Quantum complexity theory
Record Number:CaltechAUTHORS:20200728-144326318
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:104614
Deposited By: Tony Diaz
Deposited On:28 Jul 2020 22:46
Last Modified:16 Nov 2021 18:33

Repository Staff Only: item control page