A Caltech Library Service

Trading locality for time: certifiable randomness from low-depth circuits

Coudron, Matthew and Stark, Jalex and Vidick, Thomas (2018) Trading locality for time: certifiable randomness from low-depth circuits. . (Unpublished)

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


The generation of certifiable randomness is the most fundamental information-theoretic task that meaningfully separates quantum devices from their classical counterparts. We propose a protocol for exponential certified randomness expansion using a single quantum device. The protocol calls for the device to implement a simple quantum circuit of constant depth on a 2D lattice of qubits. The output of the circuit can be verified classically in linear time, and is guaranteed to contain a polynomial number of certified random bits assuming that the device used to generate the output operated using a (classical or quantum) circuit of sub-logarithmic depth. This assumption contrasts with the locality assumption used for randomness certification based on Bell inequality violation or computational assumptions. To demonstrate randomness generation it is sufficient for a device to sample from the ideal output distribution within constant statistical distance. Our procedure is inspired by recent work of Bravyi et al. (Science 2018), who introduced a relational problem that can be solved by a constant-depth quantum circuit, but provably cannot be solved by any classical circuit of sub-logarithmic depth. We develop the discovery of Bravyi et al. into a framework for robust randomness expansion. Our proposal does not rest on any complexity-theoretic conjectures, but relies on the physical assumption that the adversarial device being tested implements a circuit of sub-logarithmic depth. Success on our task can be easily verified in classical linear time. Finally, our task is more noise-tolerant than most other existing proposals that can only tolerate multiplicative error, or require additional conjectures from complexity theory; in contrast, we are able to allow a small constant additive error in total variation distance between the sampled and ideal distributions.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:The authors thank Adam Bouland for helpful discussions and members of the Caltech theory reading group (Matthew Weidner, Andrea Coladangelo, Jenish Mehta, Chinmay Nirkhe, Rohit Gurjar, Spencer Gordon) for posing some of the questions answered in this work. We thank Isaac Kim, Jean-Francois Le Gall, and Robin Kothari for useful discussions following the initial announcement of our results. Thomas Vidick is supported by NSF CAREER Grant CCF-1553477, AFOSR YIP award number FA9550-16-1-0495, MURI Grant FA9550-18-1-0161, a CIFAR Azrieli Global Scholar award, and the the Institute for Quantum Information and Matter, an NSF Physics Frontiers Center (NSF Grant PHY-1733907). Jalex Stark is supported by NSF CAREER Grant CCF-1553477, ARO Grant W911NF-12-1-0541, and NSF Grant CCF-1410022. Matthew Coudron is supported by Canada’s NSERC and the Canadian Institute for Advanced Research (CIFAR), and through funding provided to IQC by the Government of Canada and the Province of Ontario.
Group:IQIM, Institute for Quantum Information and Matter
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0495
Air Force Office of Scientific Research (AFOSR)FA9550-18-1-0161
Canadian Institute for Advanced Research (CIFAR)UNSPECIFIED
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Army Research Office (ARO)W911NF-12-1-0541
Natural Sciences and Engineering Research Council of Canada (NSERC)UNSPECIFIED
Government of CanadaUNSPECIFIED
Province of OntarioUNSPECIFIED
Record Number:CaltechAUTHORS:20190320-100502117
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:93982
Deposited By: Tony Diaz
Deposited On:20 Mar 2019 17:22
Last Modified:03 Oct 2019 20:59

Repository Staff Only: item control page