Mahadev, Urmila and Vazirani, Umesh and Vidick, Thomas (2022) Efficient Certifiable Randomness from a Single Quantum Device. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20221220-222320267
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png) |
PDF
- Submitted Version
Creative Commons Attribution. 255kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20221220-222320267
Abstract
Brakerski et. al [BCM+18] introduced the model of cryptographic testing of a single untrusted quantum device and gave a protocol for certifiable randomness generation. We use the leakage resilience properties of the Learning With Errors problem to address a key issue left open in previous work - the rate of generation of randomness. Our new protocol can certify Ω(n) fresh bits of randomness in constant rounds, where n is a parameter of the protocol and the total communication is O(n), thus achieving a nearly optimal rate. The proof that the output is statistically random is conceptually simple and technically elementary.
| Item Type: | Report or Paper (Discussion Paper) | ||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Related URLs: |
| ||||||||||||||||||||||
| ORCID: |
| ||||||||||||||||||||||
| Additional Information: | Attribution 4.0 International (CC BY 4.0). T.V. is supported by AFOSR YIP award number FA9550-16-1-0495, a grant from the Simons Foundation (828076, TV), MURI Grant FA9550-18-1-0161, the NSF QLCI program through grant number OMA-2016245 and the IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028). U.M. is supported by an NSF CAREER grant (2048204). U.V. is supported by Vannevar Bush faculty fellowship N00014-17-1-3025, MURI Grant FA9550-18-1-0161, and DOE NQISRC Quantum Systems Accelerator grant FP00010905. | ||||||||||||||||||||||
| Group: | Institute for Quantum Information and Matter | ||||||||||||||||||||||
| Funders: |
| ||||||||||||||||||||||
| Record Number: | CaltechAUTHORS:20221220-222320267 | ||||||||||||||||||||||
| Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20221220-222320267 | ||||||||||||||||||||||
| Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||||||||||||
| ID Code: | 118520 | ||||||||||||||||||||||
| Collection: | CaltechAUTHORS | ||||||||||||||||||||||
| Deposited By: | George Porter | ||||||||||||||||||||||
| Deposited On: | 21 Dec 2022 19:48 | ||||||||||||||||||||||
| Last Modified: | 21 Dec 2022 19:48 |
Repository Staff Only: item control page
