Skip to main content
U.S. flag

An official website of the United States government

Official websites use .gov
A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS
A lock ( ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Notes on Interrogating Random Quantum Circuits

Published

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

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 March 28, 2024)
Created May 28, 2020, Updated August 10, 2020