Quantum Supremacy and Quantum Advantage

The frontier is a live tug-of-war between hardware and classical algorithms. Within two years of Sycamore, tensor-network methods that slice and reorder the contraction — culminating in Pan, Chen, and Zhang's 2021–22 spoofing of the exact Sycamore benchmark on GPU clusters — showed the original runtime claim was not the last word, and Google responded with larger, deeper 2023–24 experiments (67–70 qubits) that also mapped a phase transition in how noise defeats classical simulation. On the photonic side USTC's Jiuzhang and Zuchongzhi lines pushed to more modes and more photons, while classical spoofers exploited loss and partial photon distinguishability. The deepest theoretical shift is Aharonov, Gao, Landau, Liu, and Vazirani's 2023 result that noisy random circuit sampling at constant error rate admits a polynomial-time classical algorithm as $n\to\infty$ — so the asymptotic edge belongs to fault tolerance, not to raw NISQ sampling. That has redirected effort toward verifiable quantum advantage: interactive "proofs of quantumness" built on cryptographic trapdoor claw-free functions (Brakerski and coworkers; Kahanamoku-Meyer and coworkers) that a classical verifier can check efficiently, closing the certification gap that linear XEB cannot. The open problem the whole field circles is a demonstration that is simultaneously classically hard, noise-robust, and efficiently checkable.

Hand a device fifty-three quantum coins entangled by a scrambling unitary. Reading the outcome string is trivial for the device — it simply measures. But to predict even the probability of one particular string, a classical computer must sum $2^{53}$ interfering complex amplitudes, an exponentially branching tally with no shortcut for a generic circuit. The device samples from this distribution essentially for free; the classical world has to compute it. The first figure makes that asymmetry concrete: a shallow random circuit, one measurement, a bitstring — against a wall of amplitudes.

The output distribution of a random circuit is not flat. Its probabilities follow the Porter–Thomas law $\Pr[P=p]=Ne^{-Np}$, so some strings are far likelier than others ("speckle"), and the distribution anticoncentrates: no small set of heavy outcomes carries all the weight. Linear cross-entropy benchmarking exploits exactly this. A faithful device preferentially returns the high-probability strings, raising a measurable score; white noise scores zero and a perfect device scores one. The second figure is the object a benchmarker actually reaches for — the density of output probabilities, whose two moments turn a noisy sampler into a fidelity meter.

Why sampling, and not factoring? Factoring needs deep, error-corrected circuits; sampling needs one shallow random circuit and a measurement, well matched to noisy intermediate-scale hardware. The price is verification: you cannot run Shor and check the factors, you must statistically certify that noisy samples come from near the ideal distribution — and that certification is itself classically costly. The whole argument is a race against the polynomial hierarchy. If a classical algorithm could efficiently approximate the sampling, Stockmeyer's theorem would let it approximate $\#\mathrm{P}$ quantities in $\mathrm{BPP}^{\mathrm{NP}}$, forcing $\mathrm{PH}$ to collapse. Believing $\mathrm{PH}$ is infinite is believing the quantum sampler is hard to fake.

The starting object is the ideal output probability of the random circuit — the number the device samples from and the number a classical simulator must compute. For a unitary $U$ compiled from the gate sequence acting on the all-zeros input, the Born rule fixes it.

where: $U$ — the random unitary built from the gate sequence on $n$ qubits; $x \in \{0,1\}^n$ — a computational-basis outcome; $|0^n\rangle$ — the all-zeros input; $P(x)$ — ideal probability of string $x$. Reading: sampling $x$ is one measurement for the device, but writing down $P(x)$ is a sum over $2^n$ amplitudes. For a Haar-random (or deep, chaotic) $U$, the individual probabilities are not equal. Their statistics across strings follow the Porter–Thomas law — the modulus-squared of a complex-Gaussian amplitude — which is the exponential density below.

where: $N=2^n$ — Hilbert-space dimension; $p$ — value of an individual probability. Reading: the mean is $\langle P\rangle=1/N$ and the spread is order $1/N$, so the distribution both anticoncentrates and has heavy speckle — the two features the benchmark needs. The certification tool is the linear cross-entropy benchmark: average the ideal probability over the strings the device actually returned, rescale, and subtract one. On a Porter–Thomas distribution this equals the global fidelity.

where: $x_i$ — strings produced by the device; $P(x_i)$ — ideal probability of each, computed classically; $\langle\cdot\rangle$ — average over the samples. Reading: $\mathrm{XEB}=1$ for a perfect device, $0$ for white noise, and Derivation B shows it equals the fidelity $F$. The hardness of the classical side starts from a proven fact: computing a single $P(x)$ exactly is $\#\mathrm{P}$-hard — as hard as counting the accepting paths of a nondeterministic machine.

where: $\#\mathrm{P}$ — the class of counting problems. Reading: this is unconditional for exact computation; the sampling hardness (below) adds an average-case-approximation conjecture on top. For the photonic route, the amplitude of a Fock-basis outcome after a Haar-random interferometer is a matrix permanent, the same object Valiant proved $\#\mathrm{P}$-hard in 1979.

where: $A$ — an $m\times m$ submatrix of the interferometer's transfer matrix; $S_m$ — permutations of $m$ photons; $\mathrm{Per}(A)$ — the permanent. Reading: identical to the determinant but with all plus signs, which is exactly what removes the fast Gaussian-elimination shortcut. For Gaussian boson sampling — squeezed light rather than single photons — the detection probability is a Hafnian, the permanent's symmetric-matrix cousin.

where: $\mathrm{Haf}$ — the Hafnian; $A_S$ — submatrix selected by the detected pattern $S$; $\sigma_Q$ — covariance matrix of the input Gaussian state. Reading: the Hafnian counts perfect matchings of a graph and is also $\#\mathrm{P}$-hard, so photonics inherits the same complexity backbone. The bridge from "$\#\mathrm{P}$-hard to compute" to "hard to sample" runs through Toda's theorem, which places the entire polynomial hierarchy inside $\mathrm{P}^{\#\mathrm{P}}$.

where: $\mathrm{PH}$ — the polynomial hierarchy; $\mathrm{P}^{\#\mathrm{P}}$ — polynomial time with a $\#\mathrm{P}$ oracle. Reading: an efficient classical sampler would drag all of $\mathrm{PH}$ into its third level, which is believed impossible. Finally, the experimental target for $\mathrm{XEB}$ is a fidelity budget: each imperfect gate multiplies the surviving fidelity, so it decays exponentially in the gate count.

where: $\epsilon_g$ — error probability of gate $g$; $m$ — total gate count; $F$ — global fidelity, the value $\mathrm{XEB}$ reads out. Reading: advantage demands $\sum_g\epsilon_g$ small enough that $F$ stays measurably above zero at the chosen size — the tension that sets the whole engineering problem.

The advantage claim degrades along several physical and algorithmic axes; each defines a frontier where classical methods can re-enter.

1 · The Sycamore fidelity budget (fully worked)

Google's 2019 Sycamore run used $n=53$ qubits and 20 cycles, compiling roughly 1113 single-qubit gates (error $\epsilon_1\approx0.16\%$ each), 430 two-qubit gates ($\epsilon_2\approx0.62\%$), and 53 readouts ($\epsilon_r\approx3.8\%$). Estimate the predicted fidelity from equation (8), and state the classical cost of one ideal probability.

Step 1. Sum the error budget: single-qubit contribution $1113\times0.0016=1.78$, two-qubit $430\times0.0062=2.67$, readout $53\times0.038=2.01$. Total $\sum_g\epsilon_g = 1.78+2.67+2.01 = \mathbf{6.46}$. The two-qubit gates and the readout each cost about as much as the whole single-qubit layer.

Step 2. Apply the fidelity budget $F\approx e^{-\sum_g\epsilon_g}=e^{-6.46}=\mathbf{1.6\times10^{-3}}$. This is of the same order as the measured $\mathrm{XEB}=F\approx 0.002$ that Google reported — small, but by Derivation B it is a genuine global fidelity, not zero.

Step 3. The classical cost of even one ideal $P(x)=|\langle x|U|0^{53}\rangle|^2$ is a sum over the $2^{53}=\mathbf{9.0\times10^{15}}$-dimensional Hilbert space; storing the full state vector alone is petabytes. So the device samples in microseconds from a distribution whose single probabilities sit on a $9\times10^{15}$-amplitude wall, and XEB still certifies $F\approx0.002$.

2 · How many samples certify F ≈ 0.002?

A supremacy run must resolve a fidelity of order $F=0.002$ against statistical noise. Roughly how many samples $M$ are needed for, say, five-standard-deviation confidence?

Step 1. The XEB estimator averages $2^n P(x_i)$ over the samples; on the (near-uniform) device output this quantity has mean $\approx 1$ and per-sample variance of order unity, because $2^n P$ over a random string is an exponential variable with unit mean and unit variance. So the standard error of the estimate after $M$ samples is $\sigma_F\approx 1/\sqrt{M}$.

Step 2. To see $F=0.002$ at five standard deviations we need $\sigma_F \lesssim F/5$, i.e. $1/\sqrt{M}\lesssim 0.002/5 = 4\times10^{-4}$, giving $M \gtrsim (5/0.002)^2 = \mathbf{6.3\times10^{6}}$ samples.

Step 3. Google collected about $3\times10^6$ bitstrings over roughly 200 seconds, landing in exactly this range and reporting multi-sigma confidence in a nonzero $F$. The certificate is real but expensive: each of those millions of samples needs its ideal $P(x_i)$ computed classically, which is why linear XEB cannot scale past the size it is meant to certify.

Quantum supremacy is one of the rare research programs whose founding act was naming it. The concept had drifted through the 1990s and 2000s — Feynman's simulation intuition, the boson-sampling hardness proof — but it acquired a banner, and an agenda, when a complexity-minded physicist gave it a word.

References. Preskill, "Quantum computing and the entanglement frontier" (2012), arXiv:1203.5813 · Aaronson & Arkhipov, "The Computational Complexity of Linear Optics," Theory of Computing 9 (2013) · Arute et al. (Google), "Quantum supremacy using a programmable superconducting processor," Nature 574 (2019) · Zhong et al. (USTC), "Quantum computational advantage using photons," Science 370 (2020) · Bouland, Fefferman, Nirkhe, Vazirani, "On the complexity and verification of quantum random circuit sampling," Nature Physics 15 (2019) · Aharonov, Gao, Landau, Liu, Vazirani, "A polynomial-time classical algorithm for noisy random circuit sampling," STOC (2023) · Nielsen & Chuang, "Quantum Computation and Quantum Information" (2010), Ch. 4–6 · Kitaev, Shen, Vyalyi, "Classical and Quantum Computation" (2002). The key quantitative anchors used throughout this article are: the Porter–Thomas density $Ne^{-Np}$ with moments $\langle P\rangle=1/N$, $\langle P^2\rangle=2/N^2$, hence $\sum_x P^2 = 2/2^n$, arising from complex-Gaussian amplitude statistics; the identity $\mathrm{XEB}=2^n\langle P\rangle_{\text{device}}-1=F$ from the white-noise mixture; Toda's theorem $\mathrm{PH}\subseteq\mathrm{P}^{\#\mathrm{P}}$ and Stockmeyer approximate counting; $\#\mathrm{P}$-hardness of the permanent (Valiant 1979) and the Hafnian; and the experimental anchors — Sycamore $n=53$, error budget $\sum_g\epsilon_g\approx6.5$ giving $F\sim10^{-3}$, reported $\mathrm{XEB}\approx0.002$, about $3\times10^6$ samples; Jiuzhang (2020).

Prerequisites. The Complexity Class BQP · BQP versus P, NP, and PSPACE · BQP is Contained in PP and PSPACE. Leads to. Quantum Query Complexity · The Polynomial Method for Quantum Lower Bounds · BQP versus P, NP, and PSPACE.

Ask the tutor: Ask me to walk through the Stockmeyer-and-Toda collapse step by step, or to show exactly why the Porter–Thomas second moment turns linear XEB into a fidelity meter.