MODULE 3 · LESSON 2
Free — no login requiredSign in to track progress, save quiz attempts and enrol in the full course.
Sign in to track progress / enrolGrover's Search and the Limits of Speedup
Grover's algorithm is the second famous result and the most frequently overstated. It is genuinely important and it does considerably less than advertised.
What it does
Given an unstructured search problem, checking N possibilities to find the one satisfying some condition, a classical computer needs roughly N/2 checks on average and N in the worst case.
Grover's algorithm finds it in roughly the square root of N steps.
For a million possibilities, classical needs around a million checks and Grover needs around a thousand. That is a real and substantial improvement.
The mechanism is the familiar one. The algorithm repeatedly performs an operation that slightly increases the amplitude of the correct answer and slightly decreases the others, a process called amplitude amplification. After about the square root of N repetitions, almost all the amplitude sits on the answer and measuring returns it with high probability.
Note that the number of repetitions matters. Run it too long and the amplitude passes its peak and begins to decrease again. Unlike classical search, more effort is not always better.
Quadratic is not exponential
Here is the essential caveat, and it is the reason careful people are unexcited by Grover's algorithm for large problems.
Taking a square root is a modest operation against exponential growth.
If a problem has 2 to the 100 candidates, Grover reduces the work to 2 to the 50 steps. That number is still around a thousand trillion trillion, which no machine will ever perform. And 2 to the 100 is not a large number by the standards of the optimisation problems people hope to solve.
Worse, adding a small number of variables restores the original difficulty. Doubling the problem size squares the candidate count, and a square root then returns you exactly where you began.
An exponential speedup changes what is possible. A quadratic speedup changes how long something takes. Only the first alters which problems are solvable in principle.
This is why the distinction between the two is the single most useful thing to check in any claim of quantum speedup. Shor's is exponential and genuinely transformative for its problem. Grover's is quadratic and useful at the margin.
It also has a proof attached: Grover's algorithm is optimal for unstructured search. No better quantum algorithm is possible for this case. So the limitation is permanent rather than awaiting improvement.
Why it will not search your database
The popular framing is that Grover's algorithm searches databases quadratically faster. Two problems make this almost never applicable.
Real databases are not unstructured. Grover assumes you must check candidates one by one with no organising principle. Actual databases have indexes, and an indexed lookup is far faster than either classical linear scan or Grover. You would be using a quantum computer to beat a method nobody uses.
Loading the data is the bottleneck. To search N items, they must be accessible to the quantum computer in superposition. Loading N classical items into a quantum state generally takes on the order of N operations. You have spent N to save yourself the square root of N, which is worse than not bothering.
This loading problem, sometimes discussed under the heading of quantum random access memory, recurs throughout proposed applications and is the quiet reason many quantum machine learning proposals do not deliver. The algorithm assumes the data is already in a quantum state, and getting it there costs as much as the classical computation you hoped to avoid.
Where it genuinely helps
Grover's algorithm is most useful when the thing being searched is computed rather than stored.
If candidates can be generated by a function rather than loaded from memory, the loading problem disappears. Cryptographic brute force is the standard example: you are not searching a stored list of keys, you are trying keys generated on the fly.
This is precisely why symmetric encryption needs longer keys. Grover reduces the effective security of a 128 bit key to roughly 64 bits of work, which is uncomfortable. A 256 bit key drops to roughly 128 bits, which remains far out of reach. Hence the standard advice to move to AES-256.
Grover also appears as a subroutine inside larger algorithms, providing a modest improvement to a component. Useful, unglamorous, and a fair summary of the whole result.
Combining this lesson with Module 2 gives a short procedure for evaluating a claim, usable without technical background.
Is the speedup exponential or polynomial? If the announcement does not say, assume polynomial. Exponential results are rare, famous, and always stated explicitly by people who have them.
What is the classical baseline? Compared against a naive method or a well optimised specialist implementation? The Module 1 lesson on Sycamore applies to every claim in the field.
How does the data get in? If the algorithm assumes data is already loaded in a quantum state, ask what loading costs. This alone invalidates many proposals, because loading frequently costs as much as the classical computation being replaced.
How does the answer get out? Some algorithms produce a quantum state encoding the answer, from which extracting what you want requires many repetitions. A result that must be measured a large number of times to be read has that cost hidden in it.
Is the speedup asymptotic or actual? An algorithm that is asymptotically faster may still be slower for every problem size anyone cares about, because of large constant factors. Quantum operations are currently many orders of magnitude slower than classical ones, so an asymptotic advantage can be swamped in practice.
What error rate does it assume? Many published algorithms assume perfect qubits. Their behaviour on real, noisy hardware may be entirely different, which is Module 4's subject.
If a claim survives all six, it is worth taking seriously. Most public claims do not survive the first two.
A vendor says a quantum computer will search a customer database of ten million records quadratically faster using Grover's algorithm. What is the strongest objection?
Grover's algorithm
Click to flipFinds a marked item among N unstructured possibilities in roughly the square root of N steps. Proven optimal for this problem.
Click to flip backGrover's algorithm searches N unstructured possibilities in about the square root of N steps, which is real, proven optimal, and much less than it sounds. A square root does not defeat exponential growth: 2 to the 100 becomes 2 to the 50, still hopeless, and doubling the problem undoes the gain entirely. It will not speed up your database, because real databases are indexed and loading the data costs more than the search saves. It genuinely helps where candidates are computed rather than stored, which is why symmetric keys should be doubled to AES-256.