Quantum supremacy is often envisioned as a fixed finish line: a single milestone where a quantum computer performs a calculation so complex that no classical supercomputer could ever replicate it. In reality, this boundary is highly dynamic. It represents a continuous "arms race" between scaling quantum processors and rapidly evolving classical simulation techniques, a framing established early on by Aaronson et al. in their complexity-theoretic analysis. Whenever a quantum device achieves a new milestone, classical algorithms are optimized, parallelized, and redesigned to close the gap.
The Mechanics of Classical Catch-Up: Tensor Networks
To understand why the boundary shifts, we must look at how classical computers simulate quantum states without explicitly storing an exponentially large state vector. The primary vehicle for this is the Tensor Network (TN).
As explained in a comprehensive review by Berezutskii et al., tensor networks break down a massive quantum state into a web of smaller, interconnected tensors. The computational cost of simulating the circuit then boils down to finding an efficient contraction path—the order in which these tensors are multiplied together.
Finding the absolute best contraction path is an incredibly difficult optimization problem. However, classical methods are becoming remarkably adept at solving it. For example, the authors of a recent benchmark study developed a reinforcement learning framework that treats contraction path discovery as an optimization game. Their approach achieved a 5.40x speedup, reducing the estimated classical simulation time of Google's landmark Sycamore circuit from weeks to less than four days.
Hardware Optimization and Algorithmic Refinements
Beyond tensor networks, classical simulation succeeds by tailoring mathematical shortcuts to specific hardware architectures.
Consider Random Circuit Sampling (RCS). Early on, Li et al. demonstrated that a dynamic programming-based partitioning scheme could push the Sunway TaihuLight supercomputer to calculate full state-vectors for 49-qubit circuits at unprecedented depths, as detailed in their 2018 paper. More recently, classical engineering has outright overtaken early hardware milestones. By harnessing a massive cluster of 1,432 GPUs and introducing novel post-processing techniques, Zhao et al. simulated random circuit sampling seven times faster than the Sycamore processor's physical execution time, effectively resetting the baseline for what constitutes a true quantum advantage in their 2024 work.
A similar pattern occurs in Gaussian Boson Sampling (GBS), a quantum paradigm based on photon interference. The classical hardness of GBS relies on the difficulty of computing complex matrix functions known as Hafnians or Torontonians. However, Wu et al. showed that these complex functions can be broken down into smaller, manageable components, significantly increasing the number of photons a classical computer can simulate in their algorithmic speedup paper. To prove this capability at scale, Li et al. successfully simulated a 50-photon GBS task on the Sunway TaihuLight supercomputer in just 20 hours, establishing a formidable new benchmark for photonic quantum devices in their 2020 study.
The Quantum Response: Scaling and Phase Transitions
Because classical simulation techniques continuously erode the quantum-classical performance gap, quantum hardware must scale both in size and complexity to maintain a definitive lead.
This pressure has driven the development of increasingly powerful superconducting processors. The Zuchongzhi series represents this rapid scaling: Wu et al. first widened the gap using a 66-qubit processor in their 2021 experiments, which was quickly followed by Zhu et al. executing a 60-qubit, 24-cycle random circuit sampling task in their subsequent work. To stay ahead of advancing classical supercomputers like Frontier, Gao et al. scaled this architecture to the 105-qubit Zuchongzhi 3.0, achieving a multi-billion-year performance gap over classical methods in their 2024 demonstration.
However, simply adding qubits is insufficient if the circuit's behavior can be easily approximated. Quantum hardware must operate in specific physical regimes where classical emulation becomes mathematically intractable. In their study on random circuit sampling, Morvan et al. experimentally identified distinct phase transitions that separate "classical-ish" behavior from true quantum complexity. By keeping error rates low enough to operate within a stable, computationally complex phase, the authors demonstrated a computation on a 67-qubit Sycamore processor that resists even the most advanced classical tensor network strategies.
The Necessity of Evolving Baselines
The continuous catch-up of classical methods highlights why rigid, static benchmarks fail. As Aaronson et al. argued in their analysis of Linear Cross-Entropy Benchmarking, establishing that a statistical test is hard to spoof does not protect it from being overtaken by algorithmic improvements over time. This competitive dynamic spans across quantum paradigms; even in optimization tasks, Yang et al. noted that classical simulated annealing algorithms can still outperform physical quantum annealers on specific quadratic unconstrained binary optimization (QUBO) subproblems in their 2024 study.
Ultimately, quantum supremacy is not a single historical event, but a moving frontier. True quantum advantage can only be claimed and verified by continuously measuring quantum hardware against a classical baseline that is itself rapidly evolving.
Key Foundational Work
Complexity-Theoretic Foundations of Quantum Supremacy Experiments (2016) — contributed 2 concept elements to this direction.
Quantum Supremacy Circuit Simulation on Sunway TaihuLight (2018) — contributed 1 concept elements to this direction.