A Caltech Library Service

Efficient Certifiable Randomness from a Single Quantum Device

Mahadev, Urmila and Vazirani, Umesh and Vidick, Thomas (2022) Efficient Certifiable Randomness from a Single Quantum Device. . (Unpublished)

[img] PDF - Submitted Version
Creative Commons Attribution.


Use this Persistent URL to link to this item:


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:
URLURL TypeDescription Paper
Vidick, Thomas0000-0002-6405-365X
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
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0495
Simons Foundation828076
Air Force Office of Scientific Research (AFOSR)FA9550-18-1-0161
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Gordon and Betty Moore FoundationGBMF-12500028
Vannever Bush Faculty FellowshipN00014-17-1-3025
Department of Energy (DOE)FP00010905
Record Number:CaltechAUTHORS:20221220-222320267
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:118520
Deposited By: George Porter
Deposited On:21 Dec 2022 19:48
Last Modified:21 Dec 2022 19:48

Repository Staff Only: item control page