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 random-ness), 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 overestimating 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 at least a certain 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.
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...
See full 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 random-ness), 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 overestimating 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 at least a certain 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.
Hide full abstract
Keywords
certifiable randomness; distinguishability; entropy estimation; gamma distribution; public randomness; quantum randomness
