The Quantum Investor's Notebook logo The Quantum Investor's Notebook
← Back

Friday, September 18, 2026

Grover’s Algorithm: Turning a Phase Flip into an Answer

Grover’s algorithm searches an unstructured space in roughly √N oracleA quantum operation that recognizes whether a candidate satisfies the required condition, typically by flipping the sign of that candidate. queries instead of N, not by reading every answer at once, but by using interferenceThe addition of quantum amplitudes, which can reinforce or cancel one another depending on their relative phases. to make the right answer increasingly likely to appear.

The problem

Suppose you have one million locked boxes and exactly one contains a prize. There is no useful ordering and no clue telling you where to look; you can only test a box and learn whether it is the right one. Classically, there is not much cleverness available. If the marked box could be anywhere, finding it takes order N tests, and on average it appears about halfway through the search. The Grover algorithmA quantum search method that finds a marked item among N unsorted candidates with about the square root of N checks, instead of about N. changes that scaling from N to √N.1 For one million possibilities √N is only 1,000, and with one marked answer the optimal number of Grover iterations is approximately

(π / 4) √N

so one million candidates require about 785 iterations to make the correct answer appear with probability very close to one.2 The interesting question is how.

Do not read every answer. Change its amplitude.

Begin by placing the quantum computer in an equal superpositionA quantum state that combines multiple basis states, each with its own probability amplitude. of all N candidates. At this point the correct answer is not special: every candidate has amplitudeThe complex number attached to each possible outcome of a quantum state. Its size sets the outcome probability and its angle is the phase. 1/√N, so measuring immediately would give each one probability 1/N. Now we need to distinguish the answer without measuring it. An oracle marks the correct candidate by flipping the sign of its amplitude, so a positive amplitude becomes negative while the others are unchanged.

A flipped sign leaves every candidate’s odds unchanged. For now.

That does not yet make the answer more likely. Probability depends on the squared magnitude of the amplitude, so changing only its sign leaves each candidate’s probability unchanged if we measured in the computational basis at that point. But its phase is now different, and that difference is what the next operation can exploit.

How Grover amplifies the answer, on eight candidates labeled |0⟩ to |7⟩. First, all candidates have equal amplitude, 1 over the square root of N. Second, the oracle applies a phase flip that pushes the |3⟩ bar below zero. Third, the diffusion step reflects every bar about the average, so the |3⟩ bar becomes tall and the others slightly shorter. Fourth, the target |3⟩ is amplified, drawn as a tall red bar. Below: repeat oracle plus diffusion about pi times the square root of N over 4 times in total; phase difference, then interference, then probability.
Figure 1: Grover search on eight candidates. The oracle flips the target’s sign and the diffusion step reflects every amplitude about the average; repeating the pair about π√N/4 times amplifies the target.

Turning phase into probability

Grover’s second operation is the diffusion operatorThe step in Grover search that reflects every amplitude about their average, which shrinks the ordinary candidates and grows the marked one., which in Grover’s own description performs an “inversion about the average” of the amplitudesThe complex number attached to each possible outcome of a quantum state. Its size sets the outcome probability and its angle is the phase..1 Picture the amplitudes as bars of equal height. The oracleA quantum operation that recognizes whether a candidate satisfies the required condition, typically by flipping the sign of that candidate. flips the target bar below zero; the diffusion step then reflects every bar about their average height. The ordinary bars become slightly shorter, and the marked bar becomes much taller. One Grover iteration has therefore not revealed the answer. It has converted a phase difference into a larger probability amplitude, and the algorithm then repeats the same pair of operations: phase flip, diffusion, larger target amplitude.

More Grover iterations are not automatically better.

There is an even cleaner way to see what is happening. For the usual case of one marked answer, the state always remains in a two-dimensional subspace: one direction is the marked state, and the other is the equal superpositionA quantum state that combines multiple basis states, each with its own probability amplitude. of all unmarked states. Each Grover iteration rotates the state through a small angle toward the marked direction, and after roughly π√N/4 iterations it points almost entirely toward the answer, so a measurementA physical process that produces a classical outcome and updates the quantum state. In an ideal projective measurement, the state is left in an eigenstate associated with the observed outcome. is very likely to return it.2 Keep iterating, however, and the rotation continues past the target, so the success probability falls again. More Grover iterations are not automatically better.

Oracle and diffusion as gates

To see the gates, take the smallest interesting case: three qubitsThe basic unit of a quantum computer. Like a 'bit' in a normal computer, but instead of being only 0 or 1 it can be 0, 1, or a blend of both at once., which can label N = 8 candidates from 000 to 111, with the marked answer 101. The circuit starts in |000⟩. A Hadamard gateA one-qubit operation that turns a definite 0 or 1 into a balanced quantum superposition. The standard way to create one. on each of the three qubits turns that into the equal superpositionA quantum state that combines multiple basis states, each with its own probability amplitude. of all eight candidates, each with amplitudeThe complex number attached to each possible outcome of a quantum state. Its size sets the outcome probability and its angle is the phase. 1/√8.3

The oracleA quantum operation that recognizes whether a candidate satisfies the required condition, typically by flipping the sign of that candidate. has to flip the sign of |101⟩ and nothing else, and it does so in three steps. An X gateA single-qubit gate that flips 0 to 1 and 1 to 0, the quantum version of a classical NOT. on the middle qubit turns 101 into 111, shuffling the other labels among themselves. A multi-controlled Z gateA gate that flips the sign of a state only when all of its control qubits are 1. Real hardware builds it from many smaller gates. then flips the sign of |111⟩ alone, since it acts only when all three qubits are 1. A second X gate on the middle qubit undoes the relabeling, so the one state left carrying a minus sign is |101⟩.

The diffusion operatorThe step in Grover search that reflects every amplitude about their average, which shrinks the ordinary candidates and grows the marked one. is another short gate sequence: Hadamards on every qubit, X gates on every qubit, a multi-controlled phase flip, then the X gates and Hadamards again. Together these implement the reflection about the average described earlier, up to an overall sign that no measurementA physical process that produces a classical outcome and updates the quantum state. In an ideal projective measurement, the state is left in an eigenstate associated with the observed outcome. can detect.3 One Grover iteration is the oracle followed by diffusion, repeated roughly π√N/4 times before the qubits are measured. For N = 8 that is about 2.2, so two iterations are run, after which a measurement returns 101 with a probability of about 95 percent.

How Grover looks as a circuit, on three qubits starting in |0⟩. Hadamards on all three prepare the equal superposition. The oracle marks |101⟩: an X on the middle qubit turns 101 into 111, a CCZ flips the phase of |111⟩ only, and a second X undoes the relabeling. The diffusion block applies H, X, CCZ, X, H on all three qubits to reflect about the average. Oracle plus diffusion is one Grover iteration, repeated about pi times the square root of N over 4 times, and measuring then gives |101⟩ with high probability.
Figure 2: Grover’s circuit on three qubits with 101 marked. The oracle and the diffusion block together form one iteration, repeated about π√N/4 times before measuring.

One caveat matters in practice. The famous √N counts oracle queries, not elementary gates. In a real problem the oracle is not handed a label like 101: it must compute the search condition itself, reversibly, inside the circuit, and every multi-controlled gate must be decomposed into many simpler one- and two-qubit gatesA gate that acts on two qubits at once, such as the CNOT. Much harder to perform accurately than a single-qubit gate, and the real test of a machine.. Those costs sit outside the query count.3

Why only a quadratic speedup?

Initially the marked state has amplitude 1/√N. Each Grover iteration rotates the state by an angle of order 1/√N, so reaching an angle of order one takes order √N iterations. That square-root scaling is not merely a limitation of Grover’s particular construction: for unstructured black-box searchA search problem where the input can be accessed only through an oracle, with no additional structure available to exploit. it is optimal, and no quantum algorithm can generally use asymptotically fewer than order √N oracle queries for the same task.4

This is why Grover does not turn exponential search into a polynomial-time problem. If there are N = 2n candidates, exhaustive classical search scales as 2n, while Grover reduces the search part to roughly 2n/2: a huge improvement, but still exponential. There is also an important condition hidden inside the famous √N. The result counts calls to the oracle. A real implementation must still build that oracle, execute it coherently and, for some database-style applications, provide quantum access to the data, and those costs are not captured by the bare query count.

The idea that survived Grover

Grover’s deepest contribution is broader than searching a database. Suppose a procedure produces a useful answer with probability a. Repeating it independently requires order 1/a attempts on average, but the generalization of Grover’s method, called amplitude amplificationThe general form of Grover search: a way to raise the chance that a quantum procedure returns a good answer, using about the square root as many repetitions., can reduce this to order 1/√a coherent uses of the procedure and its inverse.5 That is the reusable idea. Quantum interferenceThe addition of quantum amplitudes, which can reinforce or cancel one another depending on their relative phases. does not magically tell us which answer is correct, but if we can mark good answers coherently, Grover showed how to turn that mark into amplitudeThe complex number attached to each possible outcome of a quantum state. Its size sets the outcome probability and its angle is the phase., and amplitude into a much better chance of measuring the answer.

Sources

  1. Grover, L. K. “A Fast Quantum Mechanical Algorithm for Database Search.” Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC ’96), 212–219 (1996). DOI: 10.1145/237814.237866. Preprint: arXiv:quant-ph/9605043. ↩
  2. Boyer, M., Brassard, G., Høyer, P. & Tapp, A. “Tight Bounds on Quantum Searching.” Fortschritte der Physik 46, 493–505 (1998). DOI: 10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO;2-P. Preprint: arXiv:quant-ph/9605034. ↩
  3. Nielsen, M. A. & Chuang, I. L. Quantum Computation and Quantum Information, 10th Anniversary Edition, Chapter 6 (Cambridge University Press, 2010). DOI: 10.1017/CBO9780511976667. ↩
  4. Zalka, C. “Grover’s Quantum Searching Algorithm Is Optimal.” Physical Review A 60, 2746–2751 (1999). DOI: 10.1103/PhysRevA.60.2746. Preprint: arXiv:quant-ph/9711070. ↩
  5. Brassard, G., Høyer, P., Mosca, M. & Tapp, A. “Quantum Amplitude Amplification and Estimation.” Contemporary Mathematics 305, 53–74 (2002). DOI: 10.1090/conm/305/05215. Preprint: arXiv:quant-ph/0005055. ↩