CaltechAUTHORS
  A Caltech Library Service

A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device

Brakerski, Zvika and Christiano, Paul and Mahadev, Urmila and Vazirani, Umesh and Vidick, Thomas (2021) A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device. Journal of the ACM, 68 (5). Art. No. 31. ISSN 0004-5411. doi:10.1145/3441309. https://resolver.caltech.edu/CaltechAUTHORS:20210921-144712064

[img] PDF - Published Version
See Usage Policy.

1MB
[img] PDF (4 May 2021) - Submitted Version
See Usage Policy.

541kB

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

Abstract

We consider a new model for the testing of untrusted quantum devices, consisting of a single polynomial time bounded quantum device interacting with a classical polynomial time verifier. In this model, we propose solutions to two tasks—a protocol for efficient classical verification that the untrusted device is “truly quantum” and a protocol for producing certifiable randomness from a single untrusted quantum device. Our solution relies on the existence of a new cryptographic primitive for constraining the power of an untrusted quantum device: post-quantum secure trapdoor claw-free functions that must satisfy an adaptive hardcore bit property. We show how to construct this primitive based on the hardness of the learning with errors (LWE) problem.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1145/3441309DOIArticle
https://resolver.caltech.edu/CaltechAUTHORS:20190201-143229032Related ItemIEEE Conference Paper
https://arxiv.org/abs/1804.00640arXivDiscussion Paper
ORCID:
AuthorORCID
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2021 Association for Computing Machinery. Received December 2018; accepted November 2020. Published: 12 August 2021.
Subject Keywords:Test of quantumness, certified randomness, quantum interactive proofs
Issue or Number:5
DOI:10.1145/3441309
Record Number:CaltechAUTHORS:20210921-144712064
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20210921-144712064
Official Citation:Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, and Thomas Vidick. 2021. A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device. J. ACM 68, 5, Article 31 (August 2021), 47 pages. https://doi.org/10.1145/3441309
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:110970
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:21 Sep 2021 15:51
Last Modified:05 Oct 2021 20:42

Repository Staff Only: item control page