Computer Science Colloquium-Certified Randomness from Quantum Supremacy

Abstract: We propose an application for near-term quantum devices:

namely, generating cryptographically certified random bits, to use

(for example) in proof-of-stake cryptocurrencies. Our protocol

repurposes the existing "quantum supremacy" experiments, based on

random circuit sampling, that Google and USTC have successfully

carried out starting in 2019. We show that, whenever the outputs of

these experiments pass the now-standard Linear Cross-Entropy Benchmark

(LXEB), under plausible hardness assumptions they necessarily contain

Ω(n) min-entropy, where n is the number of qubits. To achieve a net

gain in randomness, we use a small random seed to produce pseudorandom

challenge circuits. In response to the challenge circuits, the quantum

computer generates output strings that, after verification, can then

be fed into a randomness extractor to produce certified nearly-uniform

bits -- thereby "bootstrapping" from pseudorandomness to genuine

randomness. We prove our protocol sound in two senses: (i) under a

hardness assumption called Long List Quantum Supremacy Verification,

which we justify in the random oracle model, and (ii) unconditionally

in the random oracle model against an eavesdropper who could share

arbitrary entanglement with the device. (Note that our protocol's

output is unpredictable even to a computationally unbounded adversary

who can see the random oracle.) Currently, the central drawback of our

protocol is the exponential cost of verification, which in practice

will limit its implementation to at most n∼60 qubits, a regime where

attacks are expensive but not impossible. Modulo that drawback, our

protocol appears to be the only practical application of quantum

computing that both requires a QC and is physically realizable today.