Algorithms
Quantum Speedup
An advantage in running time, queries, or resources that a quantum algorithm has over the best classical algorithm for the same problem.
Definition
A quantum speedup means that a quantum computer can solve a problem using fewer steps than any classical computer. Speedups come in different sizes: exponential, such as Shor's algorithm for factoring, quadratic, such as Grover's search, and none for many problems. The size matters because a quadratic speedup can be wiped out by the overhead of error correction, while an exponential one can survive it.
In depth
Not all speedups are equally valuable. Quadratic speedups, such as those from Grover search, amplitude estimation, and many quantum walk algorithms, are broad but modest. Babbush, McClean, Newman, and coauthors showed in 2021 that, once the overhead of error-corrected hardware is included, a quadratic speedup needs very large problem sizes and fast logical gates to pay off, so the focus should be on larger speedups. Super-polynomial speedups are known for factoring, discrete logarithms, simulating quantum systems, and some problems in the oracle model.
A fair statement of a speedup should specify four things: the problem, the classical baseline, the cost model, and the input and output assumptions. A speedup claim in terms of queries to an oracle does not automatically carry over to a real problem where the oracle must be built. An algorithm that is exponentially faster in terms of the number of qubits may need exponentially large data to be loaded, which erases the gain. The history of dequantization shows how classical algorithms can catch up when assumptions are made explicit.
The distinction between theoretical speedup and practical advantage is important. Practical advantage involves wall-clock time and cost on real hardware compared with the best classical hardware and software available. Even a provable speedup might not reach practical advantage if constants are large, and a heuristic method without a proof might still win on specific instances.
Technical Definition
A quantum speedup is a separation between the complexity of the best known quantum algorithm and the best known (or provably best) classical algorithm for a task, measured in query, gate, or time complexity. Provable speedups exist in the query model, such as Grover's quadratic and Simon's exponential, while speedups in gate complexity for end-to-end problems, such as factoring, rely on unproven assumptions about classical hardness.
Visual Explanation: An Analogy
Compare two ways of finding a name in a phone book. One reads every entry, and the other cleverly narrows down the possibilities. The second is faster, and whether it is quadratically or exponentially faster determines whether it stays useful when the clever method needs a much slower machine.
Key facts
| Item | Detail |
|---|---|
| Exponential | Shor's factoring, Simon's problem, and simulation of quantum dynamics |
| Quadratic | Grover search, amplitude estimation, minimum finding |
| None proven | NP-complete problems in general, and most of machine learning on classical data |
| Overhead warning | Quadratic speedups are hard to realize on error-corrected hardware (Babbush et al., 2021) |
| Dequantization | Classical algorithms that match claimed quantum speedups under the same assumptions |
Where the idea comes from
The first speedup was Deutsch and Jozsa's in 1992, followed by Simon's exponential separation in 1994, Shor's algorithm the same year, and Grover's in 1996. Later work refined the picture, including the 2018 dequantization results and the 2021 analysis of overheads.
Real-World Use Cases
- Judging whether a proposed quantum application is likely to be worth its cost.
- Comparing algorithms in resource estimates.
- Interpreting advantage claims in the news.
- Directing research toward problems with large, robust speedups.
How it differs from related ideas
- A theoretical speedup is a statement about algorithms, while quantum advantage is a statement about real devices solving real tasks.
- Query speedups are proven, and gate-complexity speedups often rest on conjectures.
- A speedup over a naive classical method is not a speedup over the best one.
Common Misconceptions
- Quantum computers are not faster at everything. For many tasks there is no known speedup.
- A speedup in theory does not guarantee a practical benefit.
- Doubling qubits does not double speed. The relationship depends on the algorithm.
Frequently asked questions
What is a quantum speedup?
A reduction in the resources needed to solve a problem with a quantum algorithm compared with the best classical algorithm.
Which problems have an exponential speedup?
Factoring and discrete logarithms through Shor's algorithm, and simulation of quantum systems. For many other problems the speedup is smaller or unproven.
Why can a quadratic speedup fail in practice?
Because error correction and logical gate speeds add large overheads that can cancel a square-root gain unless the problem is very large.
Related Terms
Keep exploring
- Algorithm: Shor's Algorithm
- Algorithm: Grover's Algorithm
- Algorithm: Quantum Amplitude Estimation
- Hardware: Google Willow