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
![]() |
PDF
- Published Version
Creative Commons Attribution. 1MB |
![]() |
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: |
| ||||||||||||
ORCID: |
| ||||||||||||
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