In theoretical computer science, a quadratic speedup—such as Grover’s algorithm reducing an unstructured search from $O(N)$ to $O(\sqrt{N})$ operations—is celebrated as a major victory. However, in the physical world of wall-clock time, an asymptotic advantage does not automatically guarantee a practical one.
To understand why a quantum algorithm succeeds or fails in practice, we must look at the crossover point: the specific problem size at which a quantum computer actually finishes a task faster than a state-of-the-art classical computer. Recent rigorous analyses show that for a wide class of problems, a quadratic speedup is simply too weak to overcome the massive engineering advantages of modern classical hardware.
The Constant-Factor Performance Gap
Why does a theoretically superior algorithm lose in the real world? It comes down to the massive disparity in operational speed between classical transistors and quantum gates. Modern classical chips (CPUs, GPUs, and ASICs) benefit from decades of optimization, operating at gigahertz frequencies and boasting immense parallel throughput. In contrast, early fault-tolerant quantum processors are projected to operate at much lower logical clock frequencies.
As noted by Herman et al., this hardware speed gap means that a quantum algorithm must provide a massive degree of algorithmic efficiency just to achieve a faster wall-clock execution time than its classical counterparts.
To build intuition, let us look at the numbers. Hoefler et al. calculated that modern classical hardware maintains a throughput advantage of approximately ten orders of magnitude over optimistic projections for future fault-tolerant quantum computers.
Consider how this affects a real-world application like financial derivative pricing. Chakrabarti et al. demonstrated that for quantum derivative pricing to provide practical value over classical methods, the quantum hardware must achieve a logical clock rate of approximately 10 MHz to complete simulations within a reasonable window. However, early-generation hardware projections hover around 10 kHz. This thousand-fold performance gap means that the constant-factor overhead completely swallows the modest gains of a quadratic speedup.
The Hidden Cost of Fault Tolerance
The problem worsens when we account for the physical realities of quantum error correction. A quantum computer cannot run "raw" gates indefinitely; it must group thousands of noisy physical qubits into a single protected "logical" qubit.
This error-correction layer introduces massive constant-factor overheads in both time and hardware. Babbush et al. illustrated this dynamic in the context of chemistry simulations. They found that while quantum simulation of exact electron dynamics scales better asymptotically than classical mean-field methods, the high constant factors associated with quantum gate operations create a significant practical barrier. Consequently, the crossover point where quantum hardware outperforms classical supercomputers is pushed out to extremely large system sizes.
As Hoefler et al. argue, theoretical papers frequently ignore these fault-tolerant overheads. This creates a "practicality gap" where a quantum advantage is only realized at problem sizes or execution times that exceed realistic operational constraints (such as an algorithm requiring months of continuous runtime to beat a GPU simulation that takes seconds).
The Moving Target of Classical Parallelism
A quadratic speedup also struggles because classical computing is a moving target. Classical baselines are rarely single-threaded; they leverage massive parallelism across clusters of GPUs or specialized hardware.
This parallelism acts as a multiplier on classical performance, effectively raising the breakeven point for quantum advantage. Babbush et al. emphasize that classical parallelism substantially accelerates classical algorithms, making it significantly harder for quantum computers with only quadratic speedups to compete effectively on highly parallelizable problems.
Classical Time: T_c = (C * N) / P (where P is classical parallelism)
Quantum Time: T_q = Q * sqrt(N) (where Q is quantum gate overhead)
If classical parallelism $P$ is large, and the quantum overhead $Q$ is also large, the problem size $N$ required for $T_q < T_c$ becomes astronomically high.
This challenge is not unique to fault-tolerant digital quantum computers; it has also plagued analog quantum systems. When benchmarking early 100+ qubit analog quantum annealers, Boixo et al. noted that proving the existence of quantum mechanisms (like tunneling) within a processor does not automatically imply a speedup over classical solvers at low qubit counts.
Furthermore, Rønnow et al. discovered that when evaluating these processors, researchers must carefully account for the intrinsic hardware parallelism of analog systems. Failing to normalize for this linear parallel advantage can lead to misleading conclusions where hardware-level concurrency is mistaken for true quantum-mechanical acceleration.
Finding the True Crossover Point
If low-degree polynomial speedups are insufficient, where does quantum advantage become practical? Empirical benchmarking helps pin down these exact boundaries.
For certain specialized tasks like quantum Hamiltonian simulations, the crossover point can occur at relatively modest scales. Chatterjee et al. identified a clear performance crossover between 24 and 30 qubits, where the time required for classical simulation begins to surpass the execution time of quantum hardware.
[10-20 Qubits] ----------------> [24-30 Qubits] ---------------> [Fault-Tolerant Scale]
Current QML Models Hamiltonian Simulation Required for Real-World
(Beaten by Classical) Crossover Point Quadratic Advantage
However, for broader applications like Quantum Machine Learning (QML), the threshold is higher. Wu et al. demonstrated that while QML models can successfully identify rare particle signals, current models are constrained by low qubit counts (10 to 20 qubits), preventing them from surpassing classical performance. The authors estimate that a minimum threshold of approximately 30 qubits is required just to begin demonstrating a clear advantage over classical algorithms in complex classification tasks.
The Mandate for Super-Quadratic Speedups
The mathematical reality of the crossover point forces a shift in how we design quantum algorithms. If a quantum computer has a $10^{10}$ throughput disadvantage, a quadratic speedup ($N$ vs $\sqrt{N}$) requires the problem size $N$ to be larger than $(10^{10})^2 = 10^{20}$ before the quantum computer wins. For most applications, executing $10^{20}$ operations would take decades on both classical and quantum machines.
Therefore, the quantum computing community must focus its efforts on algorithms that offer higher-order polynomial or exponential speedups. As Babbush et al. argue, algorithms providing only quadratic speedups are unlikely to yield a practical quantum advantage on early fault-tolerant quantum computers. Instead, researchers must prioritize algorithms with cubic, quartic, or exponential advantages to successfully compensate for the slower operational speeds of quantum hardware.
This principle echoes early insights from Agaian et al., who noted that for quantum computing to be a viable alternative to classical methods, algorithms must demonstrate a substantial, often exponential, speedup. To achieve real-world utility, we cannot rely on the theoretical elegance of a quadratic speedup; we must look for problems where the quantum advantage is overwhelmingly non-linear.
Key Foundational Work
Quantum computing and a unified approach to fast unitary transforms (2002) — contributed 1 concept elements to this direction.
Evidence for quantum annealing with more than one hundred qubits (2014) — contributed 1 concept elements to this direction.
Defining and detecting quantum speedup (2014) — contributed 1 concept elements to this direction.