Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published June 8, 2020 | Published + Submitted
Book Section - Chapter Open

Simpler Proofs of Quantumness

Abstract

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.

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).

Attached Files

Published - LIPIcs-TQC-2020-8.pdf

Submitted - 2005.04826.pdf

Files

2005.04826.pdf
Files (877.6 kB)
Name Size Download all
md5:dc939cd028266d1007930c5f2365d0cd
252.7 kB Preview Download
md5:4ef9984f5dfd7133e12e822ac9b00911
625.0 kB Preview Download

Additional details

Created:
August 19, 2023
Modified:
January 15, 2024