



@article {2775,
	title = {Trading Locality for Time: Certifiable Randomness from Low-Depth Circuits},
	journal = {Communications in Mathematical Physics},
	volume = {382},
	year = {2021},
	month = {2/9/2021},
	pages = {49 - 86},
	abstract = {<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>},
	issn = {0010-3616},
	doi = {10.1007/s00220-021-03963-w},
	url = {https://link.springer.com/content/pdf/10.1007/s00220-021-03963-w.pdf},
	author = {Matthew Coudron and Stark, Jalex and Vidick, Thomas}
}
