Simple Algorithm
Quantum Computing · Excited State · 20 min

Quantum Advantage & the Road Ahead

Milestones, claims, counter-claims and the path to useful machines.

In 2019 Google reported that its 53-qubit Sycamore processor sampled from a random circuit in about 200 seconds, a task it estimated would take a leading supercomputer about 10,000 years. IBM promptly argued for about 2.5 days, and by 2022 tensor-network methods produced comparable samples in hours. Nobody was simply wrong. Understanding why tells you what quantum advantage is, and what it is not.

What you’ll learn

  • Distinguish computational (beyond-classical) advantage from useful advantage, and state what a credible claim needs.
  • Explain random circuit sampling and derive why the linear cross-entropy benchmark tracks circuit fidelity.
  • Describe boson sampling and Gaussian boson sampling, including the 2020 Jiuzhang experiment.
  • Explain how classical responses (tensor networks, exploiting low fidelity and noise) changed the estimates.
  • Outline the road to fault tolerance and the resources useful algorithms need.

What counts as quantum advantage?

Preskill (2012) coined "quantum supremacy" for the moment a quantum device does something no classical computer can do in any reasonable time; most people now say quantum advantage. A credible claim has four parts: a well-defined computational task, a quantum device that performs it, evidence that no classical algorithm can do it efficiently, and a way to check that the device really did it.

AspectComputational (beyond-classical) advantageUseful advantage
Taskany well-defined task, often sampling, chosen for its hardnessa problem someone needs solved, such as a molecular energy or a material property
Evidencecomplexity theory plus the best known classical algorithmsbeating the best classical methods in cost, time or accuracy
Status (mid-2020s)claimed for random circuit sampling and boson sampling, with continuing classical counter-claimsno widely accepted demonstration yet
Check your understanding

Which additional fact would turn a computational advantage into a useful one?

  1. The device used more qubits than any previous experiment
  2. The output has value beyond the demonstration, and no classical method obtains it faster or more cheaply
  3. Computing the output distribution exactly is #P-hard
  4. The result was published in a major journal
Show the answer

B. The output has value beyond the demonstration, and no classical method obtains it faster or more cheaply

Usefulness is about the problem, not the machine: the answer must matter to someone, and the quantum route must beat the best classical route to the same answer.

Random circuit sampling on Sycamore (2019)

Arute et al. (2019) ran random circuits on 53 working superconducting qubits: 20 cycles, each a layer of randomly chosen single-qubit gates followed by a pattern of two-qubit gates. The output distribution of a random circuit is a speckle pattern: most bitstrings are rare and a few are several times more likely than average. Reproducing the speckle is believed classically hard; checking it is hard too, so the experiment scored its samples with the linear cross-entropy benchmark (XEB).

Predict before you look

For a large random circuit, Np(x)Np(x) (with N=2nN=2^n) is approximately exponentially distributed with mean 1: the Porter–Thomas distribution. What percentage of bitstrings have probability more than twice the uniform value 1/N1/N?

Show the answer

13.5 %

Pr⁡[Np>2]=e−2≈13.5%\Pr[Np>2]=e^{-2}\approx13.5\%. In the toy circuit, 2 of the 16 bitstrings are that heavy. A sampler that favors heavy bitstrings scores well on XEB, as you will now derive.

DerivationWhy XEB measures fidelity
  1. FXEB=N Ex∼device[pC(x)]−1F_{\text{XEB}}=N\,\mathbb E_{x\sim\text{device}}\big[p_C(x)\big]-1

    Average the ideal probability pC(x)p_C(x) (computed classically) over the bitstrings the device actually produced.

  2. ideal device:Ex∼pC[pC(x)]=∑xpC(x)2=N E[p2]=N⋅2N2=2N ⇒ FXEB=1\text{ideal device:}\quad\mathbb E_{x\sim p_C}[p_C(x)]=\sum_xp_C(x)^2=N\,\mathbb E[p^2]=N\cdot\frac{2}{N^2}=\frac2N\ \Rightarrow\ F_{\text{XEB}}=1

    For Porter–Thomas, E[p2]=2/N2\mathbb E[p^2]=2/N^2: the second moment of an exponential with mean 1/N1/N.

  3. uniform guessing:Ex∼U[pC(x)]=1N ⇒ FXEB=0\text{uniform guessing:}\quad\mathbb E_{x\sim U}[p_C(x)]=\frac1N\ \Rightarrow\ F_{\text{XEB}}=0

    Random bitstrings score zero.

  4. ρ=F ∣ψC⟩ ⁣⟨ψC∣+(1−F)IN ⇒ FXEB=F⋅1+(1−F)⋅0=F\rho=F\,\dyad{\psi_C}+(1-F)\frac{\id}{N}\ \Rightarrow\ F_{\text{XEB}}=F\cdot1+(1-F)\cdot0=F

    For a device modeled as global depolarizing noise, the score equals the circuit fidelity. Sycamore reported FXEB≈0.2%F_{\text{XEB}}\approx0.2\%: small, but resolvable with millions of samples.

Boson sampling on Jiuzhang (2020)

Aaronson and Arkhipov (2011) proposed a task for linear optics: send nn identical photons into an mm-mode interferometer described by a random unitary UU, and record where they exit. For an outcome SS with at most one photon per mode, the probability is ∣Per⁡(US)∣2\abs{\operatorname{Per}(U_S)}^2, where USU_S is the n×nn\times n submatrix picked out by the input and output modes and the permanent is the determinant without the minus signs:

Per⁡(A)=∑σ∈Sn∏i=1nAi,σ(i)\operatorname{Per}(A)=\sum_{\sigma\in S_n}\prod_{i=1}^{n}A_{i,\sigma(i)}
Computing permanents exactly is #P-hard (Valiant 1979), and the best classical algorithms take time exponential in nn. Photons do not compute permanents; their interference simply produces outcomes with these probabilities.
DerivationTwo photons, one beam splitter
  1. U=12(111−1),Pr⁡[one photon in each output]=∣Per⁡U∣2U=\frac{1}{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix},\qquad\Pr[\text{one photon in each output}]=\abs{\operatorname{Per}U}^2

    One photon enters each input port of a 50:50 beam splitter.

  2. Per⁡U=12(1⋅(−1)+1⋅1)=0\operatorname{Per}U=\tfrac12\big(1\cdot(-1)+1\cdot1\big)=0

    The two ways of getting one photon per output cancel: the photons always leave together. This is the Hong–Ou–Mandel effect.

  3. distinguishable particles:Pr⁡=Per⁡(∣Uij∣2)=14+14=12\text{distinguishable particles:}\quad\Pr=\operatorname{Per}\big(\abs{U_{ij}}^2\big)=\tfrac14+\tfrac14=\tfrac12

    Classical particles add probabilities, not amplitudes. Boson sampling scales this interference up to dozens of photons.

Gaussian boson sampling (Hamilton et al. 2017) replaces single photons, which are hard to produce on demand, with squeezed light; the probabilities become hafnians, a matrix function that generalizes the permanent. Zhong et al. (2020) built Jiuzhang: 50 single-mode squeezed states sent into a 100-mode interferometer, with up to 76 detected photon clicks, and estimated a sampling rate about 101410^{14} times faster than classical simulation.

ExperimentPlatformTaskScale
Sycamore (Google, 2019)superconductingrandom circuit sampling53 qubits, 20 cycles
Jiuzhang (USTC, 2020)photonicGaussian boson sampling100 modes, up to 76 clicks
Zuchongzhi 2.0 (USTC, 2021)superconductingrandom circuit sampling56 qubits, 20 cycles
Borealis (Xanadu, 2022)photonic, time-multiplexedGaussian boson sampling216 squeezed modes
Landmark beyond-classical sampling experiments. Each was followed by classical simulation efforts targeting it.

The classical response

Classical simulation fought back on three fronts.

  • Better algorithms. Tensor-network contraction treats the circuit as a network of small tensors. Its cost depends on how the network can be cut and contracted, not just on the qubit count, and optimized contraction orders slashed the estimates: Pan, Chen and Zhang (2022) produced a million samples for the Sycamore circuits, at a higher estimated fidelity than the experiment's, in about 15 hours on 512 GPUs.
  • Exploiting low fidelity. The experiment's samples were about 99.8% noise. A classical algorithm need only match F≈0.002F\approx0.002, and for many methods a fidelity-FF simulation costs about FF times an exact one.
  • Exploiting noise asymptotically. Aharonov, Gao, Landau, Liu and Vazirani (2023) gave a classical algorithm that samples from noisy random circuits in polynomial time for any constant noise rate per gate. It does not directly spoof the 2019 experiment, but it shows that uncorrected random circuit sampling cannot give an advantage that grows without bound.
Predict before you look

A 53-qubit, 20-cycle circuit contains roughly 430 two-qubit gates. If each fails with probability 0.6% and everything else were perfect, what circuit fidelity would you expect?

Show the answer

7.5 %

(1−0.006)430≈e−2.6≈7.5%(1-0.006)^{430}\approx e^{-2.6}\approx7.5\%. Add about 1,100 single-qubit gates and 53 imperfect measurements and you reach the reported ∼0.2%\sim0.2\%. Fidelity decays exponentially with circuit size, so the experimental window is narrow, and the low fidelity is exactly what classical spoofers exploit.

The road to fault tolerance

Useful algorithms, such as Shor's factoring or chemistry by phase estimation, need circuits with billions of gates and logical error rates far below anything physical. That requires quantum error correction: encode each logical qubit in many physical qubits and keep the physical error rate below the code's threshold, so that a larger code yields a smaller logical error rate.

Milestones as of the mid-2020s: superconducting experiments showed the logical error rate falling as the surface-code distance grew from 3 to 5 to 7, the first clear operation below threshold; neutral-atom and trapped-ion experiments ran small algorithms on up to a few dozen logical qubits with error detection or correction. Estimates for useful tasks still call for roughly a million or more physical qubits: factoring RSA-2048 was estimated at about 20 million noisy qubits running for hours (Gidney & Ekerå 2019), revised in 2025 to under a million running for about a week, and FeMoco-class chemistry needs a few million.

AspectBeyond-classical samplingUseful fault-tolerant algorithms
Qubits50 to a few hundred physicalthousands of logical, about 10610^6 physical
Error correctionnoneessential
Gatesthousands10910^9 or more non-Clifford gates
Checking the answerXEB, classically feasible only at small sizesoften easy (factors) or physically meaningful
Orders of magnitude only.

Key takeaways

  • Computational advantage means a hard, well-defined task done faster than any known classical method; useful advantage also requires the answer to matter. As of the mid-2020s only the former has been claimed.
  • Random circuit sampling on Sycamore (53 qubits, 2019) was scored by linear XEB, which equals the circuit fidelity under depolarizing noise; it was about 0.2%.
  • Boson sampling probabilities are squared permanents and Gaussian boson sampling uses hafnians; Jiuzhang (2020) detected up to 76 photon clicks in 100 modes.
  • Classical responses (tensor networks, low-fidelity shortcuts, noise-exploiting algorithms) cut the estimated classical costs dramatically; uncorrected sampling advantage is fragile.
  • Useful applications need fault tolerance: below-threshold codes and roughly a million or more physical qubits.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

A "spoofer" outputs uniformly random bitstrings. What linear XEB score does it get on average?

  1. 11
  2. 0.50.5
  3. 00
  4. −1-1
Show the answer

C. 00

Uniform samples have average ideal probability exactly 1/N1/N, so FXEB=N⋅1N−1=0F_{\text{XEB}}=N\cdot\tfrac1N-1=0.

Question 2

Which statement about the 2019 Sycamore experiment is accurate?

  1. It solved a commercially useful optimization problem
  2. It sampled from random circuits, a task with complexity-theoretic evidence of hardness, and later classical algorithms cut the estimated classical cost from millennia to hours
  3. It factored a large integer
  4. It proved that BQP is strictly larger than BPP
Show the answer

B. It sampled from random circuits, a task with complexity-theoretic evidence of hardness, and later classical algorithms cut the estimated classical cost from millennia to hours

It was a beyond-classical sampling demonstration scored by XEB. Its 10,000-year estimate was later undercut by tensor-network simulations taking hours on GPU clusters.

Question 3

In boson sampling with single photons, outcome probabilities are squared permanents. In Gaussian boson sampling with squeezed light, they are given by…

  1. determinants, which are classically easy
  2. Pfaffians
  3. eigenvalues of the interferometer
  4. hafnians
Show the answer

D. hafnians

For squeezed inputs, probabilities are squared hafnians of submatrices built from the interferometer and the squeezing; hafnians generalize permanents and are #P-hard to compute in general.

Question 4

Why can't uncorrected random circuit sampling give an advantage that keeps growing with system size?

  1. Fidelity decays exponentially with the number of gates, and for a constant noise rate per gate there are polynomial-time classical algorithms for noisy random circuit sampling
  2. Because random circuit sampling is in P
  3. Because larger circuits cannot be built
  4. Because XEB cannot be computed at any size
Show the answer

A. Fidelity decays exponentially with the number of gates, and for a constant noise rate per gate there are polynomial-time classical algorithms for noisy random circuit sampling

Without error correction, F≈e−ϵGF\approx e^{-\epsilon G} for GG gates with error ϵ\epsilon, and Aharonov et al. (2023) showed noisy random circuits at constant noise rate can be sampled classically in polynomial time.

Question 5

Below the threshold, what happens to the logical error rate of a surface code as its distance grows?

  1. It increases, because more qubits mean more errors
  2. It stays the same
  3. It decreases exponentially in the distance
  4. It decreases only linearly in the distance
Show the answer

C. It decreases exponentially in the distance

A logical error needs a chain of about d/2d/2 or more faults, so pL∼(p/pth)(d+1)/2p_L\sim(p/p_{\text{th}})^{(d+1)/2}: exponential suppression in dd when p<pthp<p_{\text{th}}. Above threshold, the opposite happens.

Go deeper

Further reading

  • F. Arute et al., "Quantum supremacy using a programmable superconducting processor", Nature 574, 505 (2019).
  • H.-S. Zhong et al., "Quantum computational advantage using photons", Science 370, 1460 (2020).
  • A. W. Harrow & A. Montanaro, "Quantum computational supremacy", Nature 549, 203 (2017).
  • J. Preskill, "Quantum computing in the NISQ era and beyond", Quantum 2, 79 (2018).