Quantum Advantage and Supremacy Experiments

A quantum advantage experiment tries to do something absurd on purpose: run a task on a real, noisy quantum device that no classical computer on Earth could reproduce in feasible time — and choose the task so carefully that the classical hardness can be argued from complexity theory, not merely observed. The task is never "factor a number" or "solve a problem someone wants solved." It is sampling: the device prepares a state $|\psi\rangle$ and emits bitstrings drawn from $p(x)=|\langle x|\psi\rangle|^2$ . Sampling is chosen for two reasons. First, it is what a quantum measurement already does — no error correction, no universal gate set, no useful output required. Second, the hardness arguments for sampling reach all the way down to the conjectured non-collapse of the polynomial hierarchy. John Preskill coined "quantum supremacy" in 2012 for exactly this regime, where a quantum device decisively outruns classical computation on some task, useful or not. Two blueprints have been realized: random circuit sampling on superconducting qubits (Google's 53-qubit Sycamore, 2019) and Gaussian boson sampling on photonic networks (USTC's Jiuzhang, 2020–21). Both are firmly NISQ — shallow, uncorrected, and successful because the task tolerates the device's native noise instead of demanding fault tolerance. The intellectual spine is complexity theory: for an ideal random circuit the output probabilities are permanent- or Hafnian-like quantities whose exact evaluation is $\#\mathsf{P}$ -hard, and Stockmeyer's counting theorem turns an efficient approximate classical sampler into a collapse of the polynomial hierarchy. That bridge needs two conjectures — anti-concentration and average-case hardness — and it is there, and in the gap between ideal and noisy circuits, that every specific advantage claim stays provisional and contested.

Key takeaways

A quantum advantage experiment runs a well-defined sampling task on a programmable device whose output distribution is believed to need superpolynomial classical resources to reproduce, even approximately.
The two flagship paradigms are random circuit sampling (RCS) on superconducting qubits and Gaussian boson sampling (GBS) on photonic networks — both sample, neither solves a decision problem.
Hardness is complexity-theoretic: exact output probabilities are $\#\mathsf{P}$ -hard, and under anti-concentration plus average-case conjectures even approximate sampling collapses the polynomial hierarchy via Stockmeyer counting.
The benchmark is the linear cross-entropy fidelity $F_{\mathrm{XEB}}$ , which estimates the overlap of the noisy device distribution with the ideal one without full tomography; Sycamore reported $F_{\mathrm{XEB}}\approx 2\times10^{-3}$ .
Claims are perpetually contested: better tensor-network and Feynman-path simulators repeatedly shrink or overturn specific runtime advantages, and photon loss weakens GBS claims — the frontier moves.
These are NISQ demonstrations of raw computational power, not useful algorithms and not fault-tolerant computation — the task itself has no known application.
Key idea: pick a sampling task whose exact output probabilities are $\#\mathsf{P}$ -hard and whose distribution anti-concentrates; then a classical algorithm that even approximately samples it would, via Stockmeyer counting, place a $\#\mathsf{P}$ quantity at the third level of the polynomial hierarchy and collapse it — so under standard conjectures no efficient classical sampler exists, while a quantum device samples it natively in linear depth.

The core insight

Pick a sampling task whose exact output probabilities are $\#\mathsf{P}$ -hard and whose distribution anti-concentrates; then a classical algorithm that even approximately samples it would, via Stockmeyer counting, place a $\#\mathsf{P}$ quantity at the third level of the polynomial hierarchy and collapse it — so under standard complexity conjectures no efficient classical sampler can exist, while a quantum device samples it natively in linear depth.

Where this lives today

The field is a live contest between quantum hardware and classical algorithms. On the hardware side, superconducting devices have pushed past Sycamore's 53 qubits — larger Zuchongzhi and improved Google processors run more qubits and deeper circuits to rebuild margin — while photonic GBS experiments detect ever more photons through larger interferometers. On the classical side the counterattack has been relentless: secondary-storage Schrödinger–Feynman hybrids, tensor-network contraction exploiting low treewidth and circuit light cones, "frugal" GPU samplers that target only $F_{\mathrm{XEB}}$ rather than the full distribution, and Pauli-path simulators have each shrunk claimed classical runtimes for specific experiments from millennia to days or hours, and loss-exploiting algorithms have eroded some GBS claims. The durable legacy is quieter than any headline: cross-entropy benchmarking is now a standard holistic diagnostic for many-qubit processors, probing correlated fidelity across a whole circuit as component-level randomized benchmarking cannot — and the exchange has sharpened the realistic map of when a quantum device actually helps, the groundwork for advantage that is not just large but useful, which is the job of fault-tolerant quantum computing.

The physical picture

A circuit of $\mathrm{poly}(n)$ gates prepares an amplitude vector in a $2^n$ -dimensional space, and a single measurement draws one bitstring from $p(x)=|\psi_x|^2$ . A classical computer that wants to imitate this must account for the interference among exponentially many computational paths, and the tasks are engineered so that no shortcut — no low rank, no low entanglement, no sparsity, no small treewidth — compresses that sum. The first figure fixes the contract: the device samples natively where the classical simulator faces an exponential wall.

Figure

The sampling task: a random circuit U on n qubits prepares a state and one measurement draws a bitstring x from its output distribution p(x) — Sycamore (n = 53, depth 20) samples in ≈200 s, while a faithful classical simulator must track 2⁵³ ≈ 9.0×10¹⁵ complex amplitudes

Why is that sum incompressible? Because a deep random circuit makes the amplitudes look like independent complex Gaussians. Their squared magnitudes then follow the Porter–Thomas law $P(p)=Ne^{-Np}$ : no handful of outcomes dominates, the distribution anti-concentrates, and estimating any single probability becomes as hard as a generic $\#\mathsf{P}$ count. This statistical signature is both the source of hardness and the thing the experiment measures. The second figure is that law, drawn from the relation itself.

Figure

Porter–Thomas statistics of a deep random circuit: the outcome probabilities follow P(p) = N·e^(−Np) with N = 2ⁿ, so the mean is ⟨p⟩ = 1/N and the collision probability Σ p² = 2/(N+1) ≈ 2/N — the anti-concentration that makes single-probability estimation as hard as a generic #P count

Noise is the silent protagonist. A per-gate error $\epsilon$ over $m$ gates degrades the global fidelity as $F\approx(1-\epsilon)^m\approx e^{-\epsilon m}$ ; push the circuit deeper and the output decays toward the uniform distribution, which is trivially samplable. The experiment lives on a knife edge between "too noisy to be hard" and "too deep to run faithfully." And verification is in tension with the claim: cross-entropy benchmarking correlates measured bitstrings against classically computed ideal probabilities, so certifying the advantage requires the very computation said to be infeasible — at full scale you can only spot-check.

The core equations

The founding object is the ideal sampling distribution: the probability the device should emit each bitstring. Everything downstream is a statement about this distribution or about how faithfully a noisy device reproduces it.

p(x)=|\langle x|U|0^n\rangle|^2 \qquad (1)

where: $U$ — the (random) quantum circuit, a product of $\mathrm{poly}(n)$ gates; $x\in\{0,1\}^n$ — an $n$ -bit measurement outcome; $|0^n\rangle$ — the all-zeros initial state; $p(x)$ — the ideal probability of outcome $x$ . Read it as: prepare $U|0^n\rangle$ , measure in the computational basis, and $p(x)$ is what you sample from. For a deep random circuit the amplitudes are effectively Haar-random, and the outcome probabilities follow the Porter–Thomas law — an exponential distribution whose exponential tail is anti-concentration.

P(p)\,\mathrm{d}p = N e^{-N p}\,\mathrm{d}p,\qquad N=2^n \qquad (2)

where: $p$ — a single outcome probability; $N=2^n$ — Hilbert-space dimension; $P(p)$ — the distribution of probabilities over outcomes for a Haar-random state. The mean is $\langle p\rangle=1/N$ and the second moment is $\langle p^2\rangle=2/N^2$ ; the ratio of two encodes anti-concentration. The experimental figure of merit is the linear cross-entropy benchmark, which estimates the device fidelity from the ideal probabilities of the measured strings — no tomography, just a classical lookup of $p(x_i)$ for each sampled $x_i$ .

F_{\mathrm{XEB}} = \frac{2^n}{S}\sum_{i=1}^{S} p(x_i) - 1 \qquad (3)

where: $x_i$ — the $i$ -th bitstring emitted by the device; $S$ — number of experimental samples; $p(x_i)$ — ideal probability of $x_i$ , computed classically; $F_{\mathrm{XEB}}$ — estimated fidelity, $0$ for uniform sampling and $1$ for ideal sampling. Reading: a device that favors high- $p$ strings scores above the uniform baseline in proportion to how much ideal weight survives the noise. Photonic experiments target a different but structurally identical hardness: their outcome probabilities are matrix permanents (lossless Fock-state boson sampling) or Hafnians (Gaussian boson sampling), both $\#\mathsf{P}$ -hard to evaluate exactly.

\Pr[x]=\frac{|\mathrm{Per}(A_S)|^2}{\prod_i s_i!},\qquad \Pr[S]=\frac{\mathrm{Haf}(A_S)}{\sqrt{|\det \sigma_Q|}\,\prod_i s_i!} \qquad (4)

where: $\mathrm{Per},\mathrm{Haf}$ — the permanent and its generalization the Hafnian, both $\#\mathsf{P}$ -hard; $A_S$ — the submatrix of the interferometer selected by the detected photon pattern $S$ ; $\sigma_Q$ — covariance data of the Gaussian state; $s_i!$ — normalization for repeated occupations. Reading: the interferometer computes a hard matrix function in light, and detection samples from it. Because the device is uncorrected, the last essential relation is not about hardness but about survival: the digital error model that predicts the fidelity from the gate-error budget.

F \approx \prod_{\text{gates}}(1-\epsilon_g)\approx \exp\!\Big(-\!\sum_g \epsilon_g\Big)=e^{-\epsilon_1 g_1-\epsilon_2 g_2-\epsilon_r n} \qquad (5)

where: $\epsilon_1,\epsilon_2,\epsilon_r$ — single-qubit, two-qubit, and readout error rates; $g_1,g_2$ — counts of single- and two-qubit gates; $n$ — qubit count. Reading: independent errors multiply their survival probabilities, so the log-infidelity is just the summed error budget. Underneath all of it sits the complexity backbone: the identities that make exact amplitudes a $\#\mathsf{P}$ -hard quantity, and the graph parameter that actually governs classical simulation cost.

\mathsf{PostBQP}=\mathsf{PP},\qquad \#\mathsf{P}\subseteq\mathsf{P}^{\mathsf{PP}},\qquad T_{\mathrm{TN}}\sim e^{\,O(\text{treewidth})} \qquad (6)

where: $\mathsf{PostBQP}$ — bounded-error quantum poly-time with postselection; $\mathsf{PP}$ — probabilistic poly-time (majority of paths); $\#\mathsf{P}$ — the counting class where exact amplitudes and permanents live; $T_{\mathrm{TN}}$ — tensor-network contraction time, set by the circuit graph's treewidth. Reading: exact amplitudes are as hard as counting, and the practical classical cost is exponential in treewidth, not in $n$ directly.

Derivation AApproximate sampling hardness via Stockmeyer counting

The goal is the central theorem behind every advantage claim: that an efficient classical algorithm which merely approximately samples an anti-concentrated, $\#\mathsf{P}$ -hard distribution would collapse the polynomial hierarchy, a consequence complexity theorists overwhelmingly believe is false. We argue contrapositively — assume a poly-time randomized classical sampler that is close in total-variation distance to the ideal $p(x)=|\langle x|U|0^n\rangle|^2$ , and drive the assumption into a collapse, flagging the two conjectural ingredients (anti-concentration and average-case hardness) as we use them.

Step 1. A classical sampler is a poly-size randomized circuit $C(r)$ that outputs a string $x$ from internal random bits $r$ . The probability it emits a fixed $x_0$ is $\Pr[C(r)=x_0]=2^{-|r|}\,\#\{r:C(r)=x_0\}$ — a $\#\mathsf{P}$ -type count over the random bits. Why: the sampler's own output probability is already a counting quantity, which is exactly the kind of object Stockmeyer's theorem can estimate.

Step 2. Stockmeyer's approximate counting places a multiplicative-precision estimate $\hat q$ of $q(x_0)=\Pr[C(r)=x_0]$ inside $\mathsf{BPP}^{\mathsf{NP}}\subseteq\Sigma_3^p$ , the third level of the polynomial hierarchy. Why: approximate counting of a $\#\mathsf{P}$ quantity does not require the full counting power — it lives low in $\mathsf{PH}$ , and that gap is what the whole argument exploits.

Step 3. If the sampler is $\delta$ -close in total variation to the ideal $p$ , then for most $x_0$ we have $q(x_0)\approx p(x_0)$ . Here anti-concentration is load-bearing: because typical $p(x_0)\sim 1/N$ is not exponentially smaller than the additive error budget, a multiplicative estimate of $q$ transfers to a multiplicative estimate of $p(x_0)$ . Why: without anti-concentration a concentrated distribution could match total-variation distance while badly mis-estimating individual probabilities, breaking the transfer.

Step 4. Invoke average-case hardness: estimating $p(x_0)=|\langle x_0|U|0^n\rangle|^2$ to multiplicative precision for a random $U$ is conjectured to be $\#\mathsf{P}$ -hard (proven for exact permanents by Valiant; conjectured for the approximate average case). Why: worst-case $\#\mathsf{P}$ -hardness is not enough — the experiment runs a random circuit, so hardness must hold for typical instances, and this is the argument's most fragile link.

Step 5. Combine. We have produced a $\#\mathsf{P}$ -hard estimate sitting inside $\Sigma_3^p$ ; by Toda's theorem $\mathsf{PH}\subseteq\mathsf{P}^{\#\mathsf{P}}$ , so $\#\mathsf{P}\subseteq\mathsf{P}^{\#\mathsf{P}}\subseteq\Sigma_3^p$ forces $\mathsf{PH}=\Sigma_3^p$ — a collapse to the third level. Why: a hard-to-compute quantity trapped in a low level of the hierarchy pulls the whole tower down, contradicting the standard conjecture that $\mathsf{PH}$ is infinite.

Go deeper · Derivation B · 1 minThe linear cross-entropy benchmark estimates the fidelity

Derivation BThe linear cross-entropy benchmark estimates the fidelity

The goal is to show why the simple empirical average in equation (3) actually measures the circuit fidelity, and to expose the two ingredients it secretly relies on — a depolarizing-style noise model and the Porter–Thomas second moment. We model the noisy device as a weighted mixture of the ideal distribution and uniform noise, push the linear-XEB estimator through that model, and read off that the empirical score minus one equals the fidelity weight.

Step 1. Model the noisy output as $q(x)=F\,p(x)+(1-F)\,2^{-n}$ : with probability $F$ the device samples the ideal distribution, otherwise it emits a uniformly random string. Why: a global depolarizing channel on an anti-concentrated circuit scatters errors into an effectively uniform background, so this two-component mixture is the right leading model.

Step 2. The estimator averages $2^n p(x)$ over device samples, so compute its expectation under $q$ : $\mathbb{E}_{x\sim q}[2^n p(x)] = 2^n\sum_x q(x)\,p(x)$ . Insert the mixture and use $\sum_x p(x)=1$ together with the Porter–Thomas collision sum $\sum_x p(x)^2\approx 2/2^n$ . Why: the collision sum is exactly where anti-concentration enters the benchmark — a concentrated distribution would give a different constant and spoil the calibration.

Step 3. Evaluate: $2^n\big[F\cdot \tfrac{2}{2^n}+(1-F)\cdot 2^{-n}\big]=2F+(1-F)=1+F$ . Subtracting the uniform baseline of $1$ isolates $F$ , so $F_{\mathrm{XEB}}=\tfrac{2^n}{S}\sum_i p(x_i)-1$ is an unbiased estimator of the fidelity weight. Why: the factor-of-two from the collision sum is precisely what makes the ideal component score $2$ while uniform scores $1$ , and their difference reports $F$ .

Go deeper · Derivation C · 1 minAnti-concentration from the Haar second moment

Derivation CAnti-concentration from the Haar second moment

The goal is to compute the collision probability of a random-circuit distribution from first principles and show that it is $\Theta(1/N)$ , not exponentially smaller — the quantitative statement of anti-concentration that both previous derivations quietly used. We take the second moment of a Haar-random pure state via the symmetric-subspace (Weingarten) average, sum it over outcomes, and interpret the result as "a constant fraction of the probability mass lives on outcomes of size about $1/N$ ."

Step 1. For a Haar-random state on dimension $N$ , the second moment of a single outcome probability is $\mathbb{E}[p(x)^2]=\tfrac{2}{N(N+1)}$ , the standard symmetric-subspace result. Why: averaging $|\langle x|\psi\rangle|^4$ over the Haar measure is a moment computation on the symmetric subspace of two copies, whose dimension gives the factor $2/(N(N+1))$ .

Step 2. Sum over all $N$ outcomes to get the collision probability: $\sum_x p(x)^2 = N\cdot\tfrac{2}{N(N+1)}=\tfrac{2}{N+1}\xrightarrow{N\gg1}\tfrac{2}{N}$ . Why: the collision probability is the single number that says how spread out the distribution is; $2/N$ is only twice the uniform value $1/N$ , so no small set of outcomes hoards the mass.

Step 3. Translate to a statement about outcomes: by Porter–Thomas, $\Pr_x[p(x)\ge \alpha/N]$ is $\Theta(1)$ for constant $\alpha$ , so a constant fraction of the mass sits on outcomes of probability $\sim 1/N$ . Why: this is exactly what lets total-variation closeness of a classical sampler become multiplicative closeness on typical probabilities — the load-bearing step of the Stockmeyer argument.

Step 4. Note the failure mode: if the distribution were concentrated, with a few outcomes carrying most of the mass, a classical sampler could match total-variation distance while mis-estimating those large probabilities, and the hardness reduction would collapse. Why: anti-concentration is therefore not cosmetic but a genuine hypothesis of the theorem, which is why circuit families are chosen to guarantee it.

Limiting cases

The advantage exists only in a narrow window of system size, depth, and noise; step outside it and the task becomes either classically easy or experimentally impossible.

Case	Result	Meaning
Noiseless, deep, anti-concentrated	$F_{\mathrm{XEB}}\to 1,\ P(p)\to Ne^{-Np}$	The ideal regime where the hardness arguments apply: Porter–Thomas statistics, $\#\mathsf{P}$ -hard amplitudes, no known classical shortcut.
High noise / many gates	$F\approx e^{-\epsilon m}\to 0\Rightarrow p(x)\to 2^{-n}$	The output collapses to (near-)uniform and is trivially samplable, so deeper is not better — advantage needs $\epsilon m\lesssim O(1)$ .
Shallow / low-entanglement	$\chi\le\chi_{\max},\ \text{cost}\sim\mathrm{poly}(n)\,\chi^2$	If bond dimension (treewidth) stays bounded, tensor-network contraction is efficient and there is no advantage.
Photon loss in GBS	$\eta^k,\ \eta=\text{transmission}$	Losing $k$ photons suppresses high-order terms exponentially, and classical algorithms exploit this to approximate the lossy distribution.
Concentrated distribution	anti-concentration fails	A sampler can match total-variation distance while mis-estimating large probabilities — the Stockmeyer reduction breaks, so hardness is lost.

Common trap"Cannot be simulated quickly" means "computes something useful."

It does not. Advantage experiments solve a contrived sampling task with no known application — the point is the separation, not the output. They are also not fault tolerant, and this cuts two ways at once: the noise makes the device sample a corrupted distribution, and that same corruption (photon loss, depolarization, light-cone truncation, low effective treewidth) is precisely the handle improved classical algorithms use to spoof the benchmark. Quoting an ideal-circuit runtime separation while the device runs a noisy circuit is a category error, and it is why nearly every headline separation has since been narrowed. Treat "it ran on quantum hardware" as a claim to be validated against the best current classical simulator, not as a proof of hardness.

Worked examples

1 · Reconstructing the Sycamore fidelity from the error budget (fully worked)

A 53-qubit, depth-20 random circuit has single-qubit error $\epsilon_1\approx1.5\times10^{-3}$ , two-qubit error $\epsilon_2\approx6\times10^{-3}$ , and readout error $\epsilon_r\approx3.8\times10^{-2}$ per qubit. Predict $F_{\mathrm{XEB}}$ from the digital error model, and say whether it is measurable.

Step 1. Count the operations. At $n=53$ and depth $m=20$ , single-qubit gates number $g_1\sim n\,m\approx \mathbf{1060}$ , and two-qubit gates (each cycle pairs roughly a fraction of the qubits under the actual coupling pattern) number $g_2\approx \mathbf{430}$ ; readout acts once on each of the $n=53$ qubits.

Step 2. Sum the log-infidelity term by term: $\epsilon_1 g_1 = 1.5\times10^{-3}\times1060 \approx \mathbf{1.6}$ ; $\epsilon_2 g_2 = 6\times10^{-3}\times430 \approx \mathbf{2.6}$ ; $\epsilon_r n = 3.8\times10^{-2}\times53 \approx \mathbf{2.0}$ . The two-qubit and readout terms dominate the budget.

Step 3. Total log-infidelity $\approx 1.6+2.6+2.0 = 6.2$ , so $F\approx e^{-6.2}\approx \mathbf{2\times10^{-3}}$ , matching the reported $F_{\mathrm{XEB}}\approx0.2\%$ .

Step 4. Is $0.2\%$ measurable? Yes — because the standard error of the estimate falls as $1/\sqrt{S}$ , millions of samples resolve a $10^{-3}$ signal cleanly (see Example 2). The device retains a $\sim10^{-3}$ ideal component, and the claim is that even spoofing this small fidelity is classically hard — not that the device samples the ideal distribution faithfully.

2 · How many samples certify $F_{\mathrm{XEB}}\approx 2\times10^{-3}$ ? (fully worked)

The linear-XEB estimator is $\hat F=\tfrac{1}{S}\sum_i y_i$ with $y_i = 2^n p(x_i)-1$ and $\mathbb{E}[y_i]=F$ . Estimate how many samples resolve a fidelity of $F\approx2\times10^{-3}$ with signal-to-noise of order one.

Step 1. Find the per-sample variance. Under ideal Porter–Thomas sampling, $2^n p(x)$ has mean $2$ (from $2^n\sum_x p(x)^2 = 2^n\cdot2/2^n$ ) and second moment $2^{2n}\sum_x p(x)^3 = 2^{2n}\cdot 6/N^2 = 6$ , so $\mathrm{Var}(2^n p)=6-2^2=\mathbf{2}$ . Thus $\mathrm{Var}(y_i)\approx 2$ .

Step 2. The estimator's standard error is $\mathrm{SE}=\sqrt{\mathrm{Var}(y_i)/S}=\sqrt{2/S}$ . Demanding $\mathrm{SE}\lesssim F$ to resolve the signal gives $S\gtrsim 2/F^2 = 2/(2\times10^{-3})^2 = \mathbf{5\times10^{5}}$ samples.

Step 3. Check against the experiment. Google collected $\approx3\times10^{6}$ samples, giving signal-to-noise $F/\sqrt{2/S}=2\times10^{-3}/\sqrt{2/3\times10^{6}}\approx \mathbf{2.4}$ . A fidelity of $10^{-3}$ is tiny but statistically solid — the sample budget, not the fidelity, is what makes the benchmark trustworthy, and it grows as $1/F^2$ so that halving the fidelity quadruples the samples needed.

Physics of the portrait

Quantum advantage began as a complexity-theory bet before it was an experiment. Its sharpest theorist turned a piece of photonics into a hardness argument that still frames every claim in the field.

Origins · 1 minScott Aaronson and how this was discovered

Scott Aaronson

b. 1981 · complexity theory of quantum advantage

Scott Aaronson is the complexity theorist who gave quantum advantage its rigorous backbone. In 2004, still a graduate student, he proved $\mathsf{PostBQP}=\mathsf{PP}$ — that a quantum computer allowed to postselect on rare measurement outcomes exactly captures the classical counting class $\mathsf{PP}$ — an identity that turns quantum amplitudes into $\#\mathsf{P}$ -hard quantities in one line and reproves Toda's theorem as a corollary. In 2011, with his student Alex Arkhipov, he introduced boson sampling: send indistinguishable photons through a random linear-optical network and sample where they emerge, and the output probabilities are permanents of the network's submatrices — $\#\mathsf{P}$ -hard by Valiant's theorem. Their key move was to argue that even an approximate classical sampler would, via Stockmeyer's counting theorem, collapse the polynomial hierarchy, provided two conjectures (anti-concentration and average-case permanent hardness) hold. That template — a natively quantum sampling task, a $\#\mathsf{P}$ -hard output, and a Stockmeyer-plus-conjectures collapse — is exactly the logic later carried over to random circuit sampling and Gaussian boson sampling. Aaronson has been as vigorous in policing the claims as in seeding them, treating the moving frontier of classical simulation not as an embarrassment but as the honest heart of the subject. The word "supremacy" is Preskill's; the theorem that makes it more than a stunt is largely Aaronson's.

History

2004

— Aaronson proves PostBQP = PP, the complexity backbone

2011

— Aaronson and Arkhipov introduce boson sampling and its hardness argument

2012

— Preskill coins the term "quantum supremacy"

2016

— Bremner, Montanaro and Shepherd extend hardness to commuting (IQP) circuits

2019

— Google's Sycamore reports a random circuit sampling advantage

2020

— USTC's Jiuzhang reports a Gaussian boson sampling advantage

Going further

Texts and papers. Preskill, "Quantum computing and the entanglement frontier" (2012) · Aaronson & Arkhipov, "The computational complexity of linear optics," Theory of Computing 9 (2013) · Bremner, Montanaro & Shepherd, "Average-case complexity versus approximate simulation of commuting quantum computations," PRL 117 (2016) · 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) · Hangleiter & Eisert, "Computational advantage of quantum random sampling," Rev. Mod. Phys. 95 (2023) · Nielsen & Chuang, Quantum Computation and Quantum Information (2010) · Watrous, The Theory of Quantum Information (2018). The key results underlying this article are: the Porter–Thomas density $P(p)=Ne^{-Np}$ and Haar second moment $\sum_x p(x)^2=2/(N+1)$ from symmetric-subspace/Weingarten calculus; the $F_{\mathrm{XEB}}=2^n\langle p\rangle-1$ derivation under the depolarizing-mixture model, using $\sum_x p(x)^2\approx2/2^n$ and $\sum_x p(x)^3=6/N^2$ ; the order-of-magnitude Sycamore fidelity $F\approx e^{-6.2}\approx2\times10^{-3}$ from representative benchmarked error rates (exact published values are instance-dependent and quoted as representative); and the sample estimate $S\gtrsim 2/F^2\approx5\times10^5$ from $\mathrm{Var}(2^np)=2$ . Permanent/Hafnian $\#\mathsf{P}$ -hardness is Valiant's theorem; $\mathsf{PostBQP}=\mathsf{PP}$ (Aaronson) and Toda's theorem $\mathsf{PH}\subseteq\mathsf{P}^{\#\mathsf{P}}$ are textbook results.

Prerequisites. Polynomial Hierarchy and #P · Permanents and the Permanent–Determinant gap · Stochastic Noise Channels (depolarizing, loss) · Measurement-Based Quantum Computation. Leads to. Magic State Distillation · Topological Quantum Computation · Measurement-Based Quantum Computation.

Ask the tutor: Ask me to walk through the Stockmeyer collapse step by step, reconstruct the Sycamore fidelity or sample budget from scratch, or explain why a specific classical simulator (tensor-network, Pauli-path, loss-exploiting) narrowed a particular advantage claim.

What is the difference between "quantum advantage" and "quantum supremacy"?

They name the same technical milestone — a quantum device outperforming the best classical computation on some well-defined task — but differ in framing and connotation. "Quantum supremacy" is Preskill's original 2012 term for the threshold where a quantum device decisively beats classical computation on any task, useful or not. "Quantum advantage" is the now-preferred phrase, partly to avoid the loaded word "supremacy" and partly to emphasize that the goal is a genuine computational edge. Some authors reserve "advantage" for a useful speedup and "supremacy" for the bare separation on a contrived task, but usage is not standardized. In this article they refer to the same sampling demonstrations.

Why permanents and Hafnians, and why are they so hard?

When indistinguishable photons pass through a linear-optical network, their amplitudes interfere according to a matrix permanent — the determinant's cousin without the alternating signs. Valiant proved in 1979 that computing the permanent of a 0/1 matrix is $\#\mathsf{P}$ -hard, as hard as counting the solutions to any NP problem, even though the superficially similar determinant is easy. Gaussian boson sampling replaces single photons with squeezed light, and its outcome probabilities become Hafnians, which count perfect matchings of a graph and are also $\#\mathsf{P}$ -hard. The absence of the cancellation that makes determinants tractable is exactly why no efficient algorithm is known — and why sampling from these distributions is believed to be classically infeasible.

If the device is so noisy, how can it demonstrate anything?

Because the chosen task tolerates noise instead of demanding fault tolerance. A depth-20 random circuit with $F_{\mathrm{XEB}}\approx10^{-3}$ samples the ideal distribution only about $0.1\%$ of the time and emits near-uniform noise otherwise — but the claim is not that the device reproduces the ideal distribution. The claim is that even matching this small fidelity, spoofing a $10^{-3}$ correlation with the ideal probabilities, is classically hard. Millions of samples resolve that tiny signal statistically. This is a deliberate feature of sampling-based supremacy: it works in the NISQ regime precisely because it never asks the hardware to be nearly perfect, only to be hard to imitate.

How do you verify a claim that requires the very computation said to be infeasible?

This is the central tension, and honestly it is only partly resolved. Cross-entropy benchmarking needs the ideal probabilities $p(x_i)$ , computed classically — which is feasible at the exact system size where the experiment is meant to be classically hard only because verification uses the full circuit knowledge and enormous supercomputer time for a spot-check, not a real-time simulation. At full scale you cannot compute $p(x)$ for enough strings, so you validate at smaller sizes and extrapolate the error model, cross-check simplified circuits, and trust the digital error model. This gap — provable hardness at exactly the scale where you can no longer verify — is a genuine open problem, and efficiently verifiable advantage schemes are an active research direction.

What killed or weakened the early advantage claims?

Better classical algorithms, exploiting the fact that the device samples a noisy distribution. Google's 2019 "10,000 years" estimate assumed a particular Schrödinger–Feynman method; within months, tensor-network contraction that exploits the circuit's low treewidth and finite light cones, plus algorithms that target only the $F_{\mathrm{XEB}}$ score rather than the full distribution, cut equivalent classical runtimes to days and then hours. For Gaussian boson sampling, algorithms that exploit photon loss and partial distinguishability approximate the lossy distribution efficiently. None of this disproves the underlying complexity conjectures — it attacks the specific noisy instances actually run, which is exactly why claims must always be stated against the current best classical simulator.

Is there any useful computation hiding in these experiments?

Not directly — the sampling tasks were chosen for hardness, not utility, and no one wants the samples for their own sake. But the byproducts are genuinely useful. Cross-entropy benchmarking became a standard holistic diagnostic for many-qubit processors, catching crosstalk and correlated errors that gate-level metrics miss. The competition drove real advances in classical simulation (tensor-network methods, Pauli-path simulators) that feed back into error mitigation and NISQ algorithm design. And Gaussian boson sampling has been proposed for restricted applications like estimating molecular vibronic spectra and graph problems tied to the Hafnian. The honest summary: these experiments demonstrate raw computational power and sharpen the tools, but useful, scalable advantage is the separate goal of fault-tolerant quantum computing.

Quantum Advantage and Supremacy Experiments

Where this lives today

The physical picture

The core equations

Limiting cases

Worked examples

1 · Reconstructing the Sycamore fidelity from the error budget (fully worked)

2 · How many samples certify $F_{\mathrm{XEB}}\approx 2\times10^{-3}$ ? (fully worked)

Physics of the portrait

Going further

Before this

Where this leads

Quantum Advantage and Supremacy Experiments

Where this lives today

The physical picture

The core equations

Limiting cases

Worked examples

1 · Reconstructing the Sycamore fidelity from the error budget (fully worked)

2 · How many samples certify FXEB≈2×10−3F_{\mathrm{XEB}}\approx 2\times10^{-3}FXEB​≈2×10−3? (fully worked)

Physics of the portrait

Going further

Before this

Where this leads

2 · How many samples certify $F_{\mathrm{XEB}}\approx 2\times10^{-3}$ ? (fully worked)