



02762nas a2200169   4500008004100000022001400041245007800055210006900133260001300202300001200215490000800227520222700235100002102462700001702483700001902500856007302519       2021                        eng d  a0010-361600aTrading Locality for Time: Certifiable Randomness from Low-Depth Circuits0 aTrading Locality for Time Certifiable Randomness from LowDepth C  c2/9/2021  a49 - 860 v3823 a<p>The generation of certifiable randomness is the most fundamental informationtheoretic task that meaningfully separates quantum devices from their classical counterparts. We propose a protocol for exponential certified randomness expansion using a&nbsp;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&nbsp;verified classically in linear time, and is guaranteed to contain a polynomial number of&nbsp;certified random bits assuming that the device used to generate the output operated using&nbsp;a (classical or quantum) circuit of sub-logarithmic depth. This assumption contrasts with&nbsp;the locality assumption used for randomness certification based on Bell inequality violation and more recent proposals for randomness certification based on computational&nbsp;assumptions. Furthermore, to demonstrate randomness generation it is sufficient for a&nbsp;device to sample from the ideal output distribution within constant statistical distance.&nbsp;&nbsp;Our procedure is inspired by recent work of Bravyi et al. (Science 362(6412):308&ndash;311,&nbsp;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&nbsp;depth. We develop the discovery of Bravyi et al. into a framework for robust randomness&nbsp;expansion. Our results lead to a new proposal for a demonstrated quantum advantage&nbsp;that has some advantages compared to existing proposals. First, our proposal does not&nbsp;rest on any complexity-theoretic conjectures, but relies on the physical assumption that&nbsp;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&nbsp;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&nbsp;are able to allow a small constant additive error in total variation distance between the&nbsp;sampled and ideal distributions.</p>1 aCoudron, Matthew1 aStark, Jalex1 aVidick, Thomas  uhttps://link.springer.com/content/pdf/10.1007/s00220-021-03963-w.pdf