Which problems would a quantum computer solve faster, and by how much?
A quantum computer is not faster at everything. It helps only with problems where a specific quantum algorithm exists, and the gain varies a lot from one problem to another.
| Problem | Best known quantum method | Gain over ordinary computers |
|---|---|---|
| Simulating molecules and materials | Quantum simulation (Feynman, 1981) | Potentially enormous: the original idea |
| Factoring large numbers | Shor's algorithm (1994) | Enormous: would break today's RSA encryption |
| Searching an unsorted list | Grover's algorithm (1996) | Square root: √N steps instead of N |
| Optimisation, machine learning | Several proposals | Uncertain: an active research question |
Grover's search shows what a "square root" gain means. Looking for one item in an unsorted list of N items, an ordinary computer has to check them one by one: on average half of them. Grover's algorithm needs about √N steps.
In a list of one million items, an ordinary computer checks about 500,000 on average. About how many steps does Grover's algorithm need? About (π/4) × √1,000,000 = (π/4) × 1,000 ≈ 785 steps. Big, but far from instant: a quantum computer is not magic.
Shor's algorithm is the reason governments and banks care. A large enough quantum computer could break the RSA encryption used across the internet, so new post-quantum encryption methods, which ordinary computers can run and quantum computers are not known to break, are being rolled out now.
The most likely first useful job, though, is still Feynman's: simulating chemistry and materials.
Grover: about (π/4)√N steps instead of N/2 on average.
Shor: the number of steps grows like a polynomial in the number of digits d of the number, roughly d^3, while the best known ordinary method grows faster than any polynomial. For a number of about 600 digits, the size used in RSA today, published estimates for a large error-corrected quantum computer are hours to days; for the best ordinary computers, far longer than human history.
Quantum computers speed up specific problems, by very different amounts: simulation and factoring the most, search by a square root, many others not at all.