Notes on Interrogating Random Quantum Circuits

Published

May 29, 2020

Author(s)

Luis Brandao, Rene C. Peralta

Abstract

Consider a quantum circuit that, when fed a constant input, produces a fixed-length random bit- string in each execution. Executing it many times yields a sample of many bit-strings that contain fresh randomness inherent to the quantum evaluation. When the circuit is freshly selected from a special class, the output distribution of strings cannot be simulated in a short amount of time by a classical (non-quantum) computer. This quantum vs. classical gap of computational efficiency enables ways of inferring that an honest sample contains quantumly generated strings, and therefore fresh randomness. This possibility, initially proposed by Aaronson, has been recently validated in a "quantum supremacy" experiment by Google, using circuits with 53 qubits. In these notes, we consider the problem of estimating information entropy (a quantitative measure of randomness), based on the sum of "probability values" (here called QC-values) of strings output by quantum evaluation. We assume that the sample of strings, claimed to have been produced by repeated evaluation of a quantum circuit, was in fact crafted by an adversary intending to induce us into over-estimating entropy. We analyze the case of a "collisional" adversary that can over- sample and possibly take advantage of observed collisions. For diverse false-positive and false-negative rates, we devise parameters for testing the hypothesis that the sample has a certain minimum expected entropy. This enables a client to certify the presence of entropy, after a lengthy computation of the QC-values. We also explore a method for low-budget clients to compute fewer QC-values, at the cost of more computation by a server. We conclude with several questions requiring further exploration.

Citation

ResearchGate

Pub Weblink

https://www.researchgate.net/

Pub Type

Websites

Download Paper

https://doi.org/10.13140/RG.2.2.24562.94400

Local Download

Keywords

certifiable randomness, distinguishability, entropy estimation, gamma distribution, public randomness, quantum randomness

Citation

Brandao, L. and Peralta, R. (2020), Notes on Interrogating Random Quantum Circuits, ResearchGate, [online], https://doi.org/10.13140/RG.2.2.24562.94400, https://www.researchgate.net/ (Accessed November 20, 2024)