Sampling and Certified Randomness

The famous quantum advantage experiments did not solve a useful problem: they sampled bitstrings from a distribution that is expensive to simulate classically. That capability has one credible near-term product, certified randomness, and this chapter shows with a runnable circuit exactly what sampling from a quantum distribution means.

What did the quantum advantage experiments actually do?

In 2019 a 53-qubit superconducting processor ran the following task, called random circuit sampling: apply a fixed, randomly chosen sequence of gates (the elementary operations of a quantum program) to 53 qubits (quantum bits), measure all of them to get a 53-bit string, and repeat about a million times. The output strings are samples from a probability distribution that the circuit defines, and computing that distribution classically appears to require simulating the full quantum state, at exponential cost.

Read the claim precisely: the machine sampled from a distribution faster than the best known classical simulation of the same sampling. It did not factor a number, optimize a route, or simulate a molecule. The task was chosen because it is what quantum hardware does natively, and because it is classically hard, not because anyone wants its output. The original paper estimated 10,000 years for a classical supercomputer to match the 200-second quantum run; within a few years, improved classical algorithms cut that to days and then further down on large clusters. The demonstration stands as a landmark of hardware control, but its exact classical-vs-quantum margin remains a moving target — a textbook case of filter question 5 from chapter 1. Full claim tracking with sources: quantum advantage reality page.