Certified randomness from quantum advantage experiments

Short answer: A 2023 theory paper proposes using the random circuit sampling experiments behind quantum supremacy claims to produce random bits that can be certified as genuinely random. A classical user sends challenge circuits, the quantum computer returns outputs that pass a cross-entropy test, and an extractor turns them into nearly uniform bits. The result is a protocol and security proof under stated hardness assumptions, not a deployed random number service.

The idea

The paper proposes an application for near-term quantum devices: generating cryptographically certified random bits, for example for use in proof-of-stake cryptocurrencies. The protocol repurposes the existing quantum supremacy experiments based on random circuit sampling, which the authors note Google and USTC have carried out since 2019.

How the protocol works

The authors show that whenever the outputs of these experiments pass the standard Linear Cross-Entropy Benchmark, they necessarily contain a min-entropy that grows with the number of qubits, under plausible hardness assumptions. To get a net gain in randomness, a small random seed is used to produce pseudorandom challenge circuits. The quantum computer answers the challenges with output strings. After verification, the strings go into a randomness extractor, producing certified, nearly uniform bits. The authors describe this as bootstrapping from pseudorandomness to genuine randomness.

What is proved and what is assumed

The authors prove the protocol sound in two senses. The first is under a hardness assumption called Long List Quantum Supremacy Verification, which they justify in the random oracle model. The second is unconditionally in the random oracle model against an eavesdropper who could share arbitrary entanglement with the device. These are conditional results, and the strength of the guarantee depends on the hardness assumption and the oracle model.

What it needs in practice

The protocol rests on a quantum computer that can run random circuit sampling at a scale where the cross-entropy test is meaningful, and on classical verification of the outputs. The proposal is for near-term devices, but the paper is a theory proposal, and the abstract does not report a hardware run of the full protocol or a service built on it.

How it differs from a quantum random number generator

An ordinary quantum random number generator trusts its own device to be working as specified. Certified randomness aims to give a user who does not trust the device a reason to believe the bits are random, using the checks built into the protocol. That is the distinguishing goal here, and the reason the proposal builds on a verifiable hardness claim rather than a physical model of one device.

FAQ

What is certified randomness?

Random bits accompanied by a verification that a skeptical user can run, so they do not have to trust the device.

Which experiments does it build on?

Random circuit sampling quantum supremacy experiments, which the paper says Google and USTC have run since 2019.

What test do the outputs pass?

The Linear Cross-Entropy Benchmark.

Is the security proof unconditional?

Only in the random oracle model against an eavesdropper. The other proof relies on the Long List Quantum Supremacy Verification assumption.

Is it available as a service?

The paper proposes a protocol. It does not report one.