Quantum Algorithms

Random Circuit Sampling

Running a random quantum circuit and sampling its output, the task behind superconducting quantum advantage demonstrations.

The task

Random circuit sampling (RCS) applies a randomly chosen sequence of one- and two-qubit gates to a register, then measures all qubits, producing a bitstring sample. Repeating gives samples from the circuit's output distribution. For deep enough random circuits on enough qubits, this distribution is believed to be intractable for classical computers to sample from, making RCS a benchmark for quantum advantage.

Why it is hard classically

Kronos motion — behind the sim

A random circuit scrambles amplitudes so that the output distribution has structure but no exploitable shortcut. Simulating it classically requires tracking a state vector of size 2^n or contracting a large tensor network whose cost grows with circuit depth and qubit count. Complexity-theoretic arguments suggest that exactly sampling the distribution efficiently is classically infeasible, under plausible conjectures.

The Porter-Thomas signature

Output probabilities of a random circuit follow the Porter-Thomas distribution, an exponential spread.
High-probability bitstrings appear more often than a uniform sampler would produce.
This speckle pattern is what verification tests look for.

Verification by cross-entropy

Because the true distribution cannot be sampled classically at scale, advantage is argued via cross-entropy benchmarking on smaller verifiable instances and extrapolation. The linear cross-entropy fidelity measures how often the hardware produces high-probability bitstrings, distinguishing a working quantum device from a uniform-noise sampler.

Status and contest

Superconducting processors reported RCS instances estimated to take classical supercomputers impractically long, launching the modern quantum advantage era. The claims are actively contested: improved tensor-network contraction and algorithmic advances have reduced classical runtimes for some instances, and noise limits the fidelity of large circuits. RCS demonstrates advantage on a contrived task, not a useful computation, a distinction central to quantum advantage definitions.