Coudron Matthew, Stark Jalex, Vidick Thomas
National Institute of Standards and Technology/QuICS, University of Maryland, College Park, USA.
University of California Berkeley, Berkeley, USA.
Commun Math Phys. 2021;382(1):49-86. doi: 10.1007/s00220-021-03963-w. Epub 2021 Feb 9.
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.
可认证随机性的生成是最基本的信息理论任务，它有效地将量子设备与其经典对应物区分开来。我们提出了一种使用单个量子设备进行指数级可认证随机性扩展的协议。该协议要求该设备在二维量子比特晶格上实现一个深度恒定的简单量子电路。该电路的输出可以在经典的线性时间内进行验证，并且假设用于生成输出的设备使用亚对数深度的（经典或量子）电路进行操作，则保证包含多项式数量的可认证随机比特。这一假设与基于贝尔不等式违背的随机性认证所使用的局域性假设以及基于计算假设的随机性认证的最新提议形成对比。此外，对于一个设备来说，要证明随机性的生成，只需在恒定统计距离内从理想输出分布中进行采样即可。我们的过程受到了Bravyi等人（《科学》362(6412):308 - 311, 2018）近期工作的启发，他们引入了一个可以由深度恒定的量子电路解决，但可证明不能由任何亚对数深度的经典电路解决的关系问题。我们将Bravyi等人的发现发展成一个用于稳健随机性扩展的框架。我们的结果为已证明的量子优势提出了一个新的提议，与现有提议相比具有一些优势。首先，我们的提议不依赖于任何复杂性理论猜想，而是依赖于被测试的对抗性设备实现亚对数深度电路这一物理假设。其次，我们任务的成功可以在经典线性时间内轻松验证。最后，我们的任务比大多数其他现有提议更具噪声容忍性，那些提议只能容忍乘法误差，或者需要来自复杂性理论的额外猜想；相比之下，我们能够在采样分布和理想分布之间的总变差距离中允许一个小的恒定加法误差。
