Published April 24, 2022
| Submitted
Discussion Paper
Open
Efficient Certifiable Randomness from a Single Quantum Device
- Creators
- Mahadev, Urmila
- Vazirani, Umesh
-
Vidick, Thomas
Chicago
An error occurred while generating the citation.
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.
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.Attached Files
Submitted - 2204.11353.pdf
Files
2204.11353.pdf
Files
(255.1 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:d8da069f3aff7c3bee16d27c1eab31be
|
255.1 kB | Preview Download |
Additional details
- Eprint ID
- 118520
- Resolver ID
- CaltechAUTHORS:20221220-222320267
- Air Force Office of Scientific Research (AFOSR)
- FA9550-16-1-0495
- Simons Foundation
- 828076
- Air Force Office of Scientific Research (AFOSR)
- FA9550-18-1-0161
- NSF
- OMA-2016245
- Institute for Quantum Information and Matter (IQIM)
- NSF
- PHY-1125565
- Gordon and Betty Moore Foundation
- GBMF-12500028
- NSF
- CCF-2048204
- Vannever Bush Faculty Fellowship
- N00014-17-1-3025
- Department of Energy (DOE)
- FP00010905
- Created
-
2022-12-21Created from EPrint's datestamp field
- Updated
-
2023-06-02Created from EPrint's last_modified field
- Caltech groups
- Institute for Quantum Information and Matter