Limits of Quantum Speedup
The limits of quantum speedup concern both provable restrictions and the practical erosion of an asymptotic gain. The research question is not whether quantum computers are faster in general, but which task structure survives a fair comparison after all necessary work is counted. Negative results often reveal a better research target or a better classical algorithm.
Required background. Lower bounds and limitations distinguishes oracle, circuit and information-theoretic limits.
Four ways an apparent gain can disappear
Section titled “Four ways an apparent gain can disappear”An oracle may hide expensive data preparation. A quantum output state may require many measurements to produce the desired classical answer. A classical method may exploit low rank, locality or a restricted instance distribution. Finally, fault tolerance can make a modest asymptotic gain irrelevant at accessible sizes.
Write total costs explicitly:
If preprocessing is amortized, specify the number of queries or repeated tasks over which it is shared. Both competitors should receive equivalent reusable data structures when physically appropriate.
Established examples and boundaries
Section titled “Established examples and boundaries”Tang’s recommendation-system algorithm shows that a carefully matched classical sampling interface can eliminate a proposed exponential separation for that task. It does not prove that all quantum learning or all quantum linear algebra is efficiently classical. Montanaro’s overview demonstrates how speedup mechanisms depend on problem structure. Established: some query gains are rigorous and some proposed advantages shrink when the access model is matched. Dequantization example, overview.
Active: identifying useful regimes resistant to known classical methods and proving lower bounds under physically meaningful restrictions. Conjectural: broad claims that a hard-to-simulate state automatically yields a useful classical output, or that failed classical searches establish impossibility.
Productive negative research questions
Section titled “Productive negative research questions”Can a low-entanglement approximation reproduce the target observable without reproducing the state? Does finite precision destroy the promise behind a speedup? Is the difficult quantum subroutine necessary for the final decision? Can randomized sketching exploit the same low-rank structure? Does a lower bound survive advice, preprocessing or parallel access?
These questions connect algorithm design to verification and resource estimation, where an output and a physical budget become concrete.
Graduate project: deconstruct one speedup claim
Section titled “Graduate project: deconstruct one speedup claim”Choose a small linear-algebra or sampling task with an explicit input-access assumption. Implement the stated classical baseline and a structure-aware alternative, then construct a quantum cost ledger without treating data loading as free. Sweep condition number, rank, requested precision and output size. A laptop suffices for initial experiments.
Deliver plots that identify which assumption produces the apparent separation. Failure tests include full-vector output instead of one scalar, a badly conditioned family and a preprocessing budget charged to both sides. If the quantum method loses, retain that result. Research begins with a rigorous restricted-model lower bound, a new classical algorithm, or a sharply defined regime where the earlier objection provably does not apply.
Entry points and review horizon
Section titled “Entry points and review horizon”Begin with one complete cost derivation rather than a survey of claims. Source checks occurred on 11 October 2026; the selected examples are 2016–2019 foundations. Reassess whenever a newer classical algorithm or a cheaper input/output protocol changes the comparison.