Algorithms and Realistic Advantage

Only some problems have known quantum speed-ups, and each comes with resource requirements. Careful reading of algorithmic claims is a core research skill.

Learning objectives

Separate proven speed-ups from heuristic expectations.
Account for input and output bottlenecks.
Evaluate a claim using resource counts rather than qubit counts.

Known families

Period finding underlies factoring and discrete logarithms with exponential speed-up. Amplitude amplification gives quadratic gains for unstructured search. Simulation of quantum systems is a natural fit.

Data in, data out

Loading large classical datasets into a quantum state can erase the theoretical gain, and extracting a full solution vector may require exponentially many measurements. Both bottlenecks belong in any honest estimate.

How to read a claim

Ask for logical qubit count, circuit depth, required fidelity, total runtime including repetitions, and the classical baseline used for comparison. A claim missing these is not yet assessable.