A brief history of quantum vs classical computational advantage

This review article comprehensively summarizes all experiments claiming quantum computational advantage, critically examines their challenges and refutations, discusses theoretical advantages in specific problems, and highlights recent progress in quantum error correction as a key step toward achieving advantage in Shor's algorithm.

The Gist

The Big Picture: The Great Race

Imagine a race between two runners: Classical Computers (the super-fast, reliable marathon runners we use today) and Quantum Computers (the mysterious, lightning-fast sprinters that operate on the weird rules of quantum physics).

The goal of this paper is to keep a scorecard of every time the Quantum Sprinter claimed, "I can solve this specific puzzle faster than the Classical Runner!" The author, Ryan LaRose, acts like a sports historian, reviewing every race, every protest, and every disqualification to tell us exactly where the race stands today.

The paper defines "advantage" simply: Who finishes the task first? It doesn't matter if the task is useful (like curing a disease) or just a silly puzzle; the only question is speed.

---

Part 1: The "Silly Puzzle" Races (Experimental Advantage)

So far, the Quantum Sprinters have tried to win three specific types of "silly" races. These aren't useful for building bridges or writing emails yet; they are designed specifically to be hard for classical computers but easy for quantum ones.

1. The Random Circuit Sampling Race (The "Coin Flip" Chaos)

• The Task: Imagine a machine that flips 53 coins at once in a completely random, chaotic way. The quantum computer does this and records the pattern of heads and tails. The classical computer has to guess what the pattern would be.
• The First Win (Google, 2019): Google's "Sycamore" computer did this in 200 seconds. They claimed a classical supercomputer would take 10,000 years to do the same math.
• The Counter-Attack: Classical runners didn't give up. They invented new, smarter ways to solve the puzzle.
  • Analogy: Imagine the classical runner realized they didn't need to run the whole track; they could take a shortcut through a tunnel they found.
  • The Result: Over time, classical computers got faster. By 2024, a classical supercomputer managed to do the same task in 86 seconds, beating the quantum computer.
• The Verdict: Google's first win was "refuted." The classical runner caught up and passed them. However, Google tried again with bigger, harder puzzles (more coins, more flips), and those newer races are still unrefuted.

2. The Gaussian Boson Sampling Race (The "Photon Pinball")

• The Task: Instead of coins, this race uses light particles (photons) bouncing through a maze of mirrors. The quantum computer shoots them in, and they land in specific spots. The classical computer has to calculate where they landed.
• The Contenders: Teams from China (USTC) and Canada (Xanadu) built these light-based racers.
• The Counter-Attack: Just like the coin race, classical computers found "loopholes." They realized that if the light particles weren't perfect (which they never are), the math became easier. They built new algorithms to simulate the light maze much faster than expected.
• The Verdict: Most of these claims have been "weakly refuted." This means the classical computers haven't beaten the quantum ones yet on the biggest puzzles, but they are close enough that a slightly better classical computer in the near future probably could.

3. The Quantum Simulation Race (The "Weather Forecast")

• The Task: Simulating how a complex system (like a magnetic material) changes over time.
• The Contenders: IBM and D-Wave.
• The Counter-Attack: IBM claimed they simulated a magnetic system faster than a classical computer. But within two weeks, classical researchers showed they could simulate it on a laptop in a few minutes.
• The Verdict: IBM's claim was quickly "refuted." The classical runner found a much faster route. D-Wave's recent attempt is still being watched, but it's likely to face similar challenges.

---

Part 2: The "Theoretical" Races (The Math Proofs)

Sometimes, mathematicians say, "If we build a perfect quantum computer, it should win this race." But history shows that classical mathematicians are very good at finding new tricks.

• The Recommendation System Race: A quantum algorithm was proposed to recommend movies to you faster than any classical computer.
  • The Twist: A classical mathematician (Ewin Tang) realized, "Hey, if we give the classical computer the same special data structure the quantum one uses, it can solve the problem just as fast!"
  • The Result: The quantum advantage vanished. This is called "dequantization."
• The Optimization Race: Similar stories happened with algorithms designed to solve complex scheduling problems. The quantum advantage was claimed, and then a classical algorithm was found that was just as good.

---

Part 3: The Final Frontier (Error Correction)

Here is the paper's most important conclusion: Quantum computers are fragile.

• The Analogy: Imagine the Quantum Sprinter is a glass runner. They are incredibly fast, but if they trip on a tiny pebble (noise), they shatter. To run a marathon (like factoring large numbers to break encryption), they need to wear a suit of armor.
• The Armor: This armor is called Quantum Error Correction. It uses many physical "glass" qubits to create one sturdy "logical" qubit.
• The Current Status: We are just starting to build this armor.
  • In 2024, Google announced a new chip (Willow) where the "logical" qubit (the armored one) lasted longer than the individual "physical" qubits (the glass ones).
  • This is the "Holy Grail" moment. It proves that adding more parts to fix errors actually makes the system better, not worse.
• The Future: Until we have this armor, we can't run the "useful" races (like breaking codes or simulating new medicines). The paper argues that Error Correction is the final frontier before quantum computers can truly beat classical ones at real-world problems.

Summary: Where Do We Stand?

The paper concludes that the race is a tug-of-war.

1. Quantum computers make a big leap forward.
2. Classical computers get smarter, find shortcuts, and catch up (or pass them).
3. Quantum computers build better hardware and try again.

Right now, we are on the boundary. We have seen quantum computers win on specific, useless puzzles, but classical computers have found ways to beat them on almost all of them. The paper suggests that for quantum computers to win a useful race, they must first master the art of Error Correction. Until then, the lead will keep changing hands.

Technical Summary

Title: A Brief History of Quantum vs Classical Computational Advantage
Authors: Ryan LaRose
Source: Quantum (Accepted 2026-05-14)

Problem Statement

The paper addresses the evolving landscape of "quantum computational advantage" (also termed quantum supremacy or beyond-classical computation). The central problem is defining and tracking the shifting boundary between what is computationally feasible for classical computers versus quantum computers. The authors define computational advantage specifically as a reduction in time-to-solution for a given problem, irrespective of the problem's practical utility. The review aims to catalog all experimental claims of quantum advantage to date, alongside the subsequent classical challenges, refutations, and theoretical developments that have altered the status of these claims.

Methodology

The paper employs a comprehensive review methodology, synthesizing historical data from experimental physics, computer science, and complexity theory.

1. Chronological Cataloging: The authors compile a timeline of all experiments claiming quantum advantage, categorizing them by problem type: Random Circuit Sampling (RCS), Gaussian Boson Sampling (GBS), and Quantum Simulation (QSim).
2. Status Classification: Each experiment is assigned a status based on subsequent literature:
   • Unrefuted: No classical algorithm has yet simulated the experiment faster.
   • Challenged: Classical algorithms have improved simulation times or questioned specific experimental aspects.
   • Weakly Refuted: A classical algorithm exists that could likely simulate the experiment on near-future classical hardware.
   • Refuted: A classical computer has successfully simulated the experiment faster than the quantum device.
3. Theoretical Analysis: The review examines theoretical advantage in specific domains (approximate optimization, recommendation systems, quantum chemistry) to highlight how "dequantization" (the development of classical algorithms inspired by quantum ones) can erode theoretical speedups.
4. Error Correction Review: The paper traces the history of quantum error correction (QEC) experiments, identifying them as the necessary "final frontier" for achieving advantage in algorithms like Shor's, which require fault tolerance.

Key Contributions

• Comprehensive Status Table: The paper provides Table 1, a chronological list of all quantum advantage claims (from Google's 2019 Sycamore to D-Wave's 2024 simulation) and their current standing regarding classical refutation.
• Detailed Narrative of Challenges: It documents the "arms race" between quantum experiments and classical simulation. Notable contributions include the tracking of tensor network contraction optimizations (e.g., "big head" algorithms, hypergraph partitioning) and noise exploitation strategies that have reduced estimated classical runtimes from thousands of years to hours or seconds for specific experiments.
• Clarification of Metrics: The review critically analyzes the Cross-Entropy Benchmark (XEB) fidelity, discussing loopholes where classical algorithms can "spoof" high XEB values without simulating the full circuit, and distinguishing between weak and strong refutations.
• Theoretical Dequantization: The paper details how theoretical advantages in Max-E3LIN2 optimization and recommendation systems were lost when classical algorithms (e.g., by Barak et al. and Ewin Tang) matched or exceeded quantum performance under similar input assumptions.
• QEC Progress: Table 2 and Section 4 summarize the rapid progression of error correction experiments, noting the transition from simple repetition codes to surface codes with distances up to 7, and the recent milestone of Google's 2024 experiment where logical error rates fell below the physical error rate threshold.

Results

• Experimental Volatility: The review finds that almost every major experimental claim of quantum advantage has faced significant challenges.
  • Google's 2019 RCS (53 qubits): Initially claimed a 10,000-year classical runtime. This was challenged by tensor network optimizations and eventually strongly refuted in 2024 (Zhao et al.) using 1,432 GPUs to simulate the experiment in 86.4 seconds.
  • USTC GBS (Jiuzhang 1.0, 2.0, 3.0): Claims of advantage were weakly refuted by Oh et al. (2023), who used tensor networks to simulate these experiments significantly faster than the quantum devices, though the experiments remain unrefuted in the "strong" sense for the largest instances.
  • IBM QSim (2023): A claim of advantage in simulating the transverse-field Ising model was refuted within weeks by multiple classical approaches (tensor networks, belief propagation, Clifford perturbation theory) running on laptops or single GPUs.
  • D-Wave (2024): A recent claim of advantage in quantum simulation remains unrefuted at the time of writing, though the authors note it is likely a target for future classical challenges.
• Theoretical Shifts: The paper demonstrates that theoretical advantage is not static. Algorithms for recommendation systems and approximate optimization (QAOA) have seen their quantum advantages eroded by "dequantized" classical algorithms that utilize similar data structures or approximation techniques.
• Error Correction Milestones: While fault-tolerant quantum computing is not yet realized, the review highlights that logical qubits are now achieving lifetimes longer than their physical components and that error rates are approaching the threshold required for scalable fault tolerance.

Significance and Claims

The paper claims that the history of quantum advantage is a dynamic, shifting target rather than a static achievement.

• Moving Target: The authors emphasize that computational advantage is defined relative to the best-known classical algorithms and hardware at a specific time. As classical algorithms improve (often inspired by quantum insights), the boundary of advantage shifts back to classical computers.
• Verification Crisis: A significant portion of the paper highlights the difficulty of verifying quantum advantage. Many current experiments (like RCS) are classically hard to verify, creating a paradox where the claim of advantage relies on classical computations that are themselves intractable. The paper points to "peaked circuit sampling" and "Hidden Code Sampling" as proposed future directions for efficiently verifiable advantage.
• The Role of Error Correction: The review posits that for algorithms with proven exponential speedups (like Shor's algorithm), the "final frontier" is not just qubit count, but quantum error correction. Without fault tolerance, the overhead of error correction may negate any theoretical speedup.
• Modest Outlook: The authors conclude that while quantum advantage is likely for specific problems, the field is currently on the "boundary" between quantum and classical dominance. They caution against assuming permanent advantage, noting that the status will likely continue to shift as both classical and quantum technologies evolve. The paper serves as a historical record to propel researchers toward new problem formulations that are classically hard, quantumly easy, efficiently verifiable, and scientifically useful.