A Caltech Library Service

Trading Locality for Time: Certifiable Randomness from Low-Depth Circuits

Coudron, Matthew and Stark, Jalex and Vidick, Thomas (2021) Trading Locality for Time: Certifiable Randomness from Low-Depth Circuits. Communications in Mathematical Physics, 382 (1). pp. 49-86. ISSN 0010-3616. doi:10.1007/s00220-021-03963-w.

[img] PDF - Published Version
Creative Commons Attribution.

[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 and more recent proposals for randomness certification based on computational assumptions. Furthermore, 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 362(6412):308–311, 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 results lead to a new proposal for a demonstrated quantum advantage that has some advantages compared to existing proposals. First, 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. Second, 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:Article
Related URLs:
URLURL TypeDescription ReadCube access Paper
Stark, Jalex0000-0002-5205-0849
Vidick, Thomas0000-0002-6405-365X
Additional Information:© The Author(s) 2021. This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit Received 23 January 2019; Accepted 15 January 2021; Published 09 February 2021. 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: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
Issue or Number:1
Record Number:CaltechAUTHORS:20190320-100502117
Persistent URL:
Official Citation:Coudron, M., Stark, J. & Vidick, T. Trading Locality for Time: Certifiable Randomness from Low-Depth Circuits. Commun. Math. Phys. 382, 49–86 (2021).
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:16 Nov 2021 17:02

Repository Staff Only: item control page