Grover's algorithm from scratch, and why only quadratic

Grover's algorithm is the famous one. If you have heard a single concrete claim about quantum computers beyond breaking encryption, it is probably "they can search a database in the square root of the time." It is real, it is buildable from parts you already understand, and it comes with a caveat the headlines almost always blur: the speedup is quadratic, not exponential. Both of those facts matter, and this post is about holding them together: building Grover from scratch, and then being honest about exactly how big its advantage is and is not.

The problem

Grover solves unstructured search. You have a collection of N items, exactly one of which is the one you want, the marked item. And crucially, there is no structure to exploit. The items are not sorted, there is no index, no pattern, no clever shortcut. The only thing you can do is point at an item and ask, is this the one? You want to find the marked item with as few of those questions as possible.

This is the worst case for searching, the case where all your usual tricks fail. No sorting to binary search through, no hash to jump to. Just a pile of indistinguishable items and a way to check one at a time.

What it costs classically

With no structure, classical search has no choice but to try items one by one. You check an item, it is not the one, you check the next. On average you find the marked item after looking at about half of them, and in the worst case you check all N. There is genuinely no better classical strategy for truly unstructured search, because without structure there is nothing to exploit, and every item you have not checked is equally likely to be the one. So the classical cost is on the order of N. Linear in the number of items.

What it costs with Grover

About the square root of N. For a million items, roughly a thousand queries instead of half a million. For a trillion items, about a million queries instead of half a trillion. The marked item is found in around √N steps, a quadratic improvement over the classical N. That is the headline, and it is true.

The pieces

Grover is built from three parts, and you have met the key idea in all of them. Start by putting your qubits into an equal superposition of every possible item with a layer of Hadamards, so every item starts equally likely. Then you repeat two operations together, over and over.

The first is the oracle. Its job is to mark the target by flipping its phase, putting a minus sign on the marked item's amplitude and leaving everything else alone. This is phase kickback again, the same mechanism from the earlier posts, except that here the controlled Z writes the phase straight onto the search qubits, so there is no ancilla in |−⟩ to kick it back from. And notice the catch: because the mark is a phase, it is invisible to a measurement. If you measured right after the oracle, every item would still look equally likely. The mark is there, in the phase, but you cannot yet read it.

The second is the diffusion operator, and it is the clever heart of the algorithm. It reflects every amplitude about the average of all the amplitudes, an operation sometimes called inversion about the mean. The effect is to take the target, whose amplitude the oracle just flipped negative, and pump it up, while pushing the unmarked amplitudes down. Geometrically, the oracle and the diffusion operator together rotate the whole state vector a little bit toward the target. Do that rotation enough times and the state ends up pointing almost exactly at the marked item, so a measurement returns it with high probability.

Inversion about the mean is worth picturing concretely, because it is the part that does the real work and it sounds more mysterious than it is. Imagine all the amplitudes as bars of equal height, since you started in an even superposition. The oracle flips one bar, the target's, to point downward, below zero, leaving the rest unchanged. Now compute the average height of all the bars. Because one bar dropped below zero and the rest are still positive, the average is slightly lower than the positive bars but still positive. Inversion about the mean reflects every bar across that average line. The unmarked bars, sitting just above the average, get reflected to just below it, shrinking a little. The target bar, sitting well below the average because it went negative, gets reflected to well above it, growing a lot. One step, and the target stands taller than everything else. That is the whole trick: flip the target with a phase, then reflect about the average, and the flip turns into height. Repeat, and the target climbs higher each round until it dominates. The phase the oracle wrote, invisible on its own, becomes visible amplitude through the reflection.

Building it

Here is Grover for the smallest interesting case, two qubits, four items, with the target being the item |11⟩. The oracle that flips the phase of |11⟩ is a controlled Z, and the diffusion operator is a tidy sandwich of Hadamards, X gates, and another controlled Z.

from qiskit import QuantumCircuit
from qiskit.primitives import StatevectorSampler

qc = QuantumCircuit(2, 2)
qc.h([0, 1])                 # equal superposition of all four items

# oracle: flip the phase of the target |11>
qc.cz(0, 1)

# diffusion: reflect about the average
qc.h([0, 1]); qc.x([0, 1]); qc.cz(0, 1); qc.x([0, 1]); qc.h([0, 1])

qc.measure([0, 1], [0, 1])
print(StatevectorSampler().run([qc], shots=1000).result()[0].data.c.get_counts())

Run it. The result is 11, every single time. One iteration of oracle plus diffusion, on four items, lands on the target with certainty. For this smallest case a single rotation is exactly enough to point the state straight at the answer, which is a particularly clean thing to watch: you marked |11⟩ with an invisible phase, the diffusion turned that phase into a towering amplitude, and the measurement read it out perfectly.

Why it is √N, and why only quadratic

Now the honest part, the question almost nobody explains. Why exactly the square root, and why is it only quadratic instead of the exponential speedup the hype implies?

Picture the state vector as an arrow, and the target as a direction you are trying to point it. Each Grover iteration, oracle plus diffusion, rotates that arrow by a small fixed angle toward the target. The angle is roughly two over √N. To swing the arrow from its starting position all the way around to the target, you need about (π over 4) times √N of those small rotations.

import numpy as np
for N in [4, 16, 256, 1024, 1_000_000]:
    grover = int((np.pi / 4) * np.sqrt(N))
    print(f"N = {N:>9}   Grover ~ {grover:>4} steps   classical ~ {N // 2} steps")

Run it. The scaling is unmistakable. A million items take around 785 Grover steps against half a million classical ones. The gap is large and real, and it grows with N. But look at the shape of it: Grover takes √N, classical takes N. That is a quadratic speedup, squaring being the relationship between the two. It is not exponential.

Here is why it cannot be more. Each iteration only rotates the arrow by that tiny two over √N angle, so you make steady but strictly bounded progress, and you genuinely have to take about √N steps to get there. You cannot skip ahead, because there is no structure to skip through. And this is provably optimal: it has been shown that no quantum algorithm can search a truly unstructured space in fewer than about √N queries. Grover is the best possible, and the best possible for blind search is quadratic, full stop. The exponential speedups you hear about, the ones in algorithms like Shor's, come from problems that have hidden structure, like periodicity, that a quantum computer can exploit all at once. Unstructured search has no such structure by definition, so there is nothing to exploit exponentially, and √N is the ceiling. Quadratic is not Grover falling short. It is Grover hitting the hard limit of what searching blind can ever achieve.

You can overshoot

The rotation picture has a consequence that surprised me and that most quick summaries skip: you can do too many iterations. If each step rotates the arrow a fixed angle toward the target, then continuing past the right number rotates it straight past the target and out the other side. More is not better. There is a sweet spot, around (π over 4) times √N, and going beyond it makes your answer worse, not better.

def grover(iterations):
    qc = QuantumCircuit(2, 2)
    qc.h([0, 1])
    for _ in range(iterations):
        qc.cz(0, 1)                                              # oracle
        qc.h([0, 1]); qc.x([0, 1]); qc.cz(0, 1); qc.x([0, 1]); qc.h([0, 1])   # diffusion
    qc.measure([0, 1], [0, 1])
    return qc

for k in [1, 2, 3]:
    counts = StatevectorSampler().run([grover(k)], shots=1000).result()[0].data.c.get_counts()
    print(f"{k} iteration(s) -> {counts}")

Run it. One iteration nails the target |11⟩ with certainty, as before. Two iterations scatter the result back to roughly even across all four outcomes, the target no longer special at all. Three iterations stay scattered. For this four item case, one rotation lands exactly on the target, and a second rotation carries the arrow right past it back into the mess. This is why Grover is not a run it as long as you can algorithm. You compute the right number of iterations in advance, from N, and you stop there. Overshooting throws away the answer you had. It is a genuinely counterintuitive property, the rare case where doing more of the right operation undoes your progress, and it falls straight out of the rotation geometry once you see it.

The honest reality

So calibrate your expectations accordingly, the way the NISQ post argued. A quadratic speedup is genuinely valuable. Turning N into √N across the huge range of problems that reduce to unstructured search is a real and meaningful win. But it is not the world remaking exponential leap that "search a database in the square root of the time" tends to conjure when it is repeated without the caveat. For truly enormous problems the quadratic gain helps but does not make the impossible easy.

And there is a hardware reality on top of the theory. Those √N iterations each stack more gates onto the circuit, and as the decoherence post showed, more gates mean more time and more noise. On today's machines, the depth required to search a large space runs straight into the qubits forgetting before the algorithm finishes. So Grover is real, optimal, and genuinely useful in principle, and also currently limited by the same noise that limits everything else. The algorithm is sound. Running it at a scale that beats your laptop is still hard.

Why it still matters

Grover earns its place even with the honest caveat firmly attached, and the quadratic win is only half the reason. The other half is that Grover's central idea, the trick of marking what you want with a phase and then amplifying it with inversion about the mean, has a name of its own, amplitude amplification, and it shows up as a reusable building block inside many other quantum algorithms. It is not just a standalone search routine, it is a subroutine that other algorithms call to boost the probability of a desired outcome. So learning Grover is not learning one trick, it is learning a primitive that recurs throughout the field. The famous database search framing undersells it, in a way: the search is the headline application, but amplitude amplification is the deeper, more widely useful idea hiding inside it, and that idea is exactly the oracle plus diffusion rotation you built above. Master the small version and you have a tool that reappears far beyond search.

A quick test before you move on

Close this and answer in your own words.

What makes a search problem unstructured, and why does that force classical search to take about N steps? If you cannot connect no pattern to exploit to checking items one by one, reread the problem and the classical cost.

What do the oracle and the diffusion operator each do, and why can you not just measure after the oracle? If your answer does not include the oracle marks the target with an invisible phase and diffusion amplifies it, revisit the pieces section.

And why is Grover only a quadratic speedup, not exponential? If because each step rotates by about two over √N and unstructured search has no structure to exploit is not roughly your answer, reread the why it is √N section, because that distinction is the honest heart of this post.

Where I am learning it

Free. Grover is in every quantum algorithms course and in the IBM Quantum learning materials, and the two qubit version above is the right place to start because you can run it and see certainty. The geometric picture, the arrow rotating toward the target a fixed angle each step, is what made the √N scaling finally make sense to me, far more than any formula. As always, the algorithm did not feel real until I built it, watched one iteration nail the target on four items, and then ran the scaling numbers myself to see the quadratic gap open up.

The famous one, honestly

Grover deserves its fame. It is a real quantum algorithm, optimal for what it does, built from phase kickback and a clever reflection, and you can assemble it from parts you already understand and watch it work on four items in a handful of lines. That is worth something, and it is genuinely satisfying to see the target amplitude climb out of an even superposition.

But the fame comes wrapped in a blur, and clearing the blur is the real lesson. The speedup is quadratic, not exponential, because unstructured search has no structure to exploit and √N is provably the best any quantum computer can do. That is not a disappointment once you understand it, it is a precise and beautiful fact about the limits of search itself. Holding the achievement and the limit together, the real speedup and its honest ceiling, is exactly the calibrated way of seeing that this whole series has been trying to build. Grover is the perfect place to practise it.