Quantum Supremacy

"Quantum supremacy" (also called quantum computational advantage) is the milestone of a programmable quantum device performing a well-defined computational task that no classical computer can do in a reasonable time — regardless of whether the task is useful. The cleanest supremacy arguments are based not on solving decision problems but on sampling from probability distributions, where complexity theory gives strong evidence of classical hardness. This lesson explains why sampling, and what the evidence actually shows.

Why sampling, not decision

For decision problems, proving a quantum advantage runs into the wall that $\mathsf{BQP} \ne \mathsf{BPP}$ is not known and would imply long-standing separations. Sampling sidesteps this. A quantum circuit naturally produces a sample from the distribution $p(y) = |\braket{y|C|0}|^2$ over measurement outcomes. The claim is that no efficient classical algorithm can sample from (a close approximation to) this distribution, and this can be argued from complexity assumptions weaker than $\mathsf{BQP}\ne\mathsf{BPP}$ .

The collapse argument

The core technique shows that an efficient classical sampler would collapse the polynomial hierarchy $\mathsf{PH}$ — a consequence considered nearly as implausible as $\mathsf{P}=\mathsf{NP}$ . The logic, in outline:

The output probabilities $p(y) = |\braket{y|C|0}|^2$ of certain quantum circuits encode quantities that are $\#\mathsf{P}$ -hard to compute (e.g. they are related to permanents or to partition functions).
If a classical randomized algorithm could sample from a distribution close to $\{p(y)\}$ , then (via a result of Stockmeyer) one could approximate these probabilities within the polynomial hierarchy.
Approximating a $\#\mathsf{P}$ -hard quantity inside $\mathsf{PH}$ would imply $\mathsf{P}^{\#\mathsf{P}} \subseteq \mathsf{PH}$ , collapsing the hierarchy (by Toda's theorem the third level and below).

So exact classical sampling is essentially ruled out under standard assumptions. The two canonical platforms for this argument are IQP / random-circuit sampling and boson sampling (next lesson).

Two technical pillars: anticoncentration and average-case hardness

Two ingredients are needed to upgrade exact hardness to approximate hardness — which is what a noisy device actually achieves:

Anticoncentration. The output probabilities must be spread out, not dominated by a few outcomes; for random circuits the $p(y)$ behave like an exponential (Porter–Thomas) distribution, $\Pr[p] \approx Ne^{-Np}$ . Anticoncentration ensures that an additive approximation to the distribution still pins down individual probabilities well enough for the Stockmeyer step.
Average-case hardness. The collapse argument needs the probabilities to be hard on average over random circuits, not just in the worst case. This is conjectured (and partially proven) for random circuit families, and is the least settled link in the chain.

Random circuit sampling and verification

The experimental realization (Google's 2019 Sycamore demonstration and successors) runs a random sequence of one- and two-qubit gates on $\sim 50$ – $70$ qubits and samples the output. Verification is the hard part: you cannot check the full distribution (it has $2^n$ outcomes), so one uses the linear cross-entropy benchmark (linear XEB),

\mathcal{F}_{\mathrm{XEB}} = 2^n \big\langle p_{\text{ideal}}(y) \big\rangle_{\,y \sim \text{device}} - 1,

the average ideal probability of the device's observed samples (computed classically for the still-feasible circuit), normalized so that perfect sampling gives $\mathcal{F}=1$ and uniform noise gives $\mathcal{F}=0$ . A device with fidelity $F$ per the noise model is expected to score $\mathcal{F}_{\mathrm{XEB}} \approx F$ . XEB verification is itself classically expensive, which is part of the tension: the very regime that is hard to simulate is also hard to verify.

The moving target

Supremacy is a contest, not a finish line. Each experimental claim has prompted improved classical algorithms — tensor-network contraction exploiting limited circuit depth and connectivity, and clever use of memory — that narrow or temporarily erase the claimed gap, prompting larger or deeper experiments in turn. The honest framing: random-circuit sampling demonstrates a task in the regime where the best known classical methods cost far more than the quantum device, under standard complexity conjectures — a genuine and important milestone, but a conditional and contested one rather than a proof that $\mathsf{BQP}\ne\mathsf{BPP}$ .

Takeaways

Sampling-based supremacy trades usefulness for provability: the tasks are artificial, but their classical hardness follows from believable complexity assumptions (no $\mathsf{PH}$ collapse, average-case hardness) far weaker than separating $\mathsf{BQP}$ from $\mathsf{BPP}$ directly. Anticoncentration and average-case hardness are the technical load-bearing conjectures, and XEB is the practical (if costly) yardstick.