Grover's Algorithm

Here is a puzzle. Someone gives you a sealed black box with a single button and a number pad. Among the numbers from $0$ to $N-1$, exactly one is special: type it in and the box lights up green. Every other number gives red. You cannot open the box. All you can do is try numbers.

On an ordinary computer, the best you can do is try numbers one at a time. Sometimes you are lucky, sometimes not, but on average you need about $N/2$ tries. Double the size of the list and the work doubles.

Now suppose the box is wired into a quantum computer. How many tries do you need?

When this question is put to large audiences, the most popular answer is "one": the quantum computer tries every number at once and reads off the right one. ^[16] The second most popular answer is "about $\log N$", an exponential speedup. Both are wrong. The correct answer is about $\sqrt N$. For a million possibilities, that is on the order of a thousand steps instead of half a million. For a trillion, about a million steps.

That answer comes from Grover's algorithm, published by Lov Grover in 1996. ^[1,2] It is one of the few quantum algorithms with a clear, proven advantage, and it is also one of the best tools for correcting the most common misunderstandings about what quantum computers do.

How a Quantum Computer Actually Works

Popular summaries often say that a quantum computer "stores all possible values at once in a superposition and processes them in parallel." That description points at something real, but it leaves out the part that decides everything: you cannot see the superposition, and measuring it gives you only one random result. To understand Grover's algorithm, it helps to replace the analogy with the actual rules. They are strange, but there are only a few.

Readouts are random

A classical computer's memory and what you read from it are the same thing: a string of bits. In a quantum computer they are different. When you read out a quantum computer with $k$ qubits, you get a string of $k$ bits, just like a classical computer. But the result is generally random. A quantum program does not determine one output; it determines a probability distribution over all $2^k$ possible outputs.

You never see that distribution directly. You see one sample from it. And after you read a value, the computer's state changes so that reading again gives the same value. The distribution "collapses" onto whatever you saw.

The state vector

Where does the distribution come from? The state of a $k$-qubit computer is described by a list of $2^k$ numbers called amplitudes, one for each possible bit string. This list is the state vector. The rule connecting amplitudes to what you observe, known as the Born rule, is:

Here $x$ is a particular bit string, $\alpha_x$ is its amplitude, and $P(x)$ is the probability of reading out $x$. If the amplitude for 0011 is $0.5$, you will see 0011 with probability $0.25$.

Because the probabilities must add to 1,

so the state vector always has length 1. Geometrically, it is a unit arrow in a space with $2^k$ perpendicular directions, one for each possible readout. ^[3]

Two details matter a great deal:

• Amplitudes can be negative, and more generally complex numbers with a magnitude and a phase. Flipping the sign of an amplitude does not change its probability, but it produces a genuinely different state that will behave differently later.
• Amplitudes are not probabilities. Probabilities only add. Amplitudes can add or cancel. This is interference, the same effect that produces bright and dark bands when light passes through two slits.

A single qubit

With one qubit there are two possible readouts, 0 and 1, so the state vector is an arrow in a plane:

The notation $|0\rangle$ and $|1\rangle$ (read "ket zero" and "ket one") names the two perpendicular unit directions. An arrow pointing along $|0\rangle$ always reads out 0. An arrow at 45° between them reads out 0 or 1 with equal probability. That is what "superposition" means, and nothing more: the arrow is not along a single readout direction.

A qubit is therefore not a bit that is "secretly both 0 and 1". It is a unit vector with a rule for how it produces random 0s and 1s when measured. Physically, it can be realized by the spin of an electron, the polarization of a photon, the energy levels of a trapped ion, or a tiny superconducting circuit.

Gates are rotations and reflections

Classical computers process bits with logic gates. Quantum computers process the state vector with quantum gates, which always act as rotations or reflections of the arrow. Mathematically they are unitary transformations: they preserve length, so probabilities always still add to 1. ^[3]

A standard example is the Hadamard gate, which turns $|0\rangle$ into the 45° state $(|0\rangle + |1\rangle)/\sqrt2$ and $|1\rangle$ into $(|0\rangle - |1\rangle)/\sqrt2$. Applying a Hadamard gate to each of $k$ qubits starting from all zeros produces an equal superposition of all $2^k$ bit strings.

Entanglement

With several qubits, the state vector has one amplitude per bit string, not one arrow per qubit. Most such states cannot be broken down into separate descriptions of individual qubits. For example, the two-qubit state

always gives matching results when both qubits are measured, even though each result alone is random. This is entanglement. Its correlations are stronger than any classical mechanism with pre-set answers can produce, a prediction confirmed by loophole-free Bell tests. ^[4]

Entanglement is why the state vector of 100 qubits needs $2^{100}$ amplitudes, a number far too large for any classical computer to store. Entanglement is necessary for large quantum speedups in pure-state computation, but it is not sufficient: many heavily entangled computations can still be simulated efficiently on classical machines. ^[5]

The catch

Here is the central point. The state vector can be astronomically large, but it is invisible. A measurement returns one bit string. You can never read out the $2^{100}$ amplitudes; at most you extract $k$ bits of information from $k$ qubits in one run. ^[3]

So the only way a quantum computer helps is if an algorithm can steer the amplitudes, through interference, so that almost all the probability ends up on the answer you want. Designing quantum algorithms is the art of building that interference. Grover's algorithm is one of the clearest examples.

Grover's Algorithm

The setup

Return to the black box. Its formal name is an oracle: a function $f(x)$ that returns 1 for the one special input $w$ (the "marked" item) and 0 for everything else.

This is not as artificial as it sounds. It stands in for any problem where checking a proposed answer is easy, even if finding it is hard: solving a Sudoku, finding a valid schedule, or finding a key that decrypts a message. Such problems make up the large class computer scientists call NP.

Grover's key observation was that any classical checking circuit can be converted into a quantum circuit that, instead of outputting "yes", flips the sign of the amplitude of the input it accepts:

On its own this looks useless, because a sign flip does not change any probability. If you measured right after it, you would see a uniformly random number. The trick is what happens next.

The procedure

1. Start balanced. Apply Hadamard gates to prepare the equal superposition over all $N$ inputs, $|s\rangle = \frac{1}{\sqrt N}\sum_{x=0}^{N-1} |x\rangle$, in which every amplitude equals $1/\sqrt N$.
2. Flip the sign of the marked item using the oracle $O$.
3. Reflect about the balanced state using the diffusion operator $D = 2|s\rangle\langle s| - I$. In plain terms, this takes every amplitude and reflects it through the average of all amplitudes. The marked item, whose amplitude is now negative and below the average, gets pushed well above it. All others shrink slightly.
4. Repeat steps 2 and 3 about $\frac{\pi}{4}\sqrt N$ times.
5. Measure. With high probability, the result is $w$. Check it classically; if it is wrong, run again.

Step 3 is often called inversion about the mean. Each round moves a little probability from all the wrong answers onto the right one.

The geometric picture

The clearest way to see why this works is geometric. Although the state vector lives in $N$ dimensions, throughout the algorithm it stays in a single two-dimensional plane: the plane containing the marked direction $|w\rangle$ and the balanced state $|s\rangle$.

Draw that plane with $|w\rangle$ pointing straight up. Along the horizontal axis put $|s'\rangle$, the equal mix of all the unmarked items. The starting state $|s\rangle$ is almost horizontal, but not quite, because it contains a small piece of $|w\rangle$. Its angle $\theta$ above the horizontal satisfies

For large $N$, the angle is tiny: $\theta \approx 1/\sqrt N$ radians.

Now look at the two operations in this picture:

• The oracle flips the sign of the $|w\rangle$ component. That is a reflection across the horizontal axis.
• The diffusion operator is a reflection across the line through $|s\rangle$.

A basic fact of geometry says that two reflections across lines meeting at angle $\theta$ combine into a rotation by $2\theta$. So each Grover iteration rotates the state vector by $2\theta$ toward the marked direction.

After $r$ iterations, the state sits at angle $(2r+1)\theta$ above the horizontal, and the probability of measuring the marked item is

To reach the top, the state must turn through about $\pi/2$ radians. Dividing by $2\theta$ per step gives the number of iterations:

This is where the square root comes from, and where the unexpected factor of $\pi$ enters: it measures a quarter turn.

A worked example

Take $N = 2^{20} \approx 10^6$, which needs 20 qubits. Then $\frac{\pi}{4}\sqrt N \approx 804$. After 804 iterations, the formula above gives a success probability of about $0.9999998$. A classical search would need on average about 524,000 tries.

For the smallest interesting case, $N = 4$, the starting angle is exactly $30^\circ$, one iteration rotates by $60^\circ$, and the state lands exactly on $|w\rangle$. One query finds the answer with certainty, where a classical search needs up to three.

Too many steps is as bad as too few

Because the state rotates, it can overshoot. Keep iterating past the optimum and the probability of success falls again, rising and falling like a wave. This is unlike any classical search, where more work never hurts.

The computer scientist Scott Aaronson describes the dilemma this creates for a hypothetical hero running Grover's algorithm under siege: measure now with a modest chance of success, or wait for a better chance and risk losing everything. ^[16] It is a scenario, as he notes, that no classical algorithm could produce. Knowing when to stop requires knowing $N$ and the number of solutions. When the number of solutions $M$ is unknown, a variant by Boyer, Brassard, Høyer and Tapp still finds one in about $\sqrt{N/M}$ steps. ^[6]

Where the Speedup Comes From

It is tempting to say that the speedup comes from evaluating the oracle "on all inputs in parallel". But the first oracle call, on its own, reveals nothing. The balanced state after the sign flip gives completely random readouts. The speedup only appears through the slow, repeated interference of the two reflections.

In the quantum description, each classical state is a perpendicular direction. A classical computer can only step from one axis to another. A quantum computer can also move diagonally. Crossing an $N$-dimensional cube along its edges takes $N$ unit steps; going straight across the diagonal takes $\sqrt N$. Grover's algorithm traces a quarter-circle arc from the balanced state to the answer, a path that simply does not exist if you are restricted to the axes.

The analogy should not be taken literally, but the geometry behind it is exact. The same section also admits a simplification used throughout: amplitudes are in general complex numbers, carrying a phase as well as a size. Grover's algorithm happens to need only positive and negative real values, which is why the picture can be drawn with ordinary arrows. Other algorithms, including Shor's, depend essentially on complex phases. It even has a mechanical twin: the physicist Adam Brown showed that Grover's algorithm is step-for-step identical to a classical puzzle in which colliding billiard balls count the digits of $\pi$. ^[7]

Why √N Is the Limit

Grover's algorithm is not merely good. It is provably the best possible.

In a paper circulated in the mid-1990s and published in 1997, Charles Bennett, Ethan Bernstein, Gilles Brassard and Umesh Vazirani proved that no quantum algorithm can search an unstructured list with fewer than on the order of $\sqrt N$ oracle queries. ^[8] Their argument tracks how much a single query can shift the state toward the marked item: each query can change it only a little, so gathering enough change to identify the answer takes about $\sqrt N$ queries. Christof Zalka later showed that Grover's algorithm matches this bound exactly, not just up to a constant. ^[9]

This result has a broad consequence. For problems with no structure to exploit beyond checking answers, quantum computers give at most a quadratic speedup. This is widely regarded as strong evidence that quantum computers cannot solve NP-complete problems efficiently by brute force, although that broader question is not formally settled.

Here $\Theta(\cdot)$ means "grows in proportion to", ignoring constant factors.

Historical Development

The idea that quantum systems might compute differently emerged from a problem in physics. In 1982, Richard Feynman observed that simulating quantum systems on classical computers seemed to require exponentially large resources, and suggested that a computer built from quantum parts might do better. ^[10] In 1985 David Deutsch described a universal quantum computer in formal terms. ^[11]

For about a decade, quantum computing was a theoretical curiosity. That changed in 1994, when Peter Shor found a quantum algorithm that factors large numbers exponentially faster than any known classical method, threatening widely used encryption. ^[12] The natural next question was whether quantum computers could speed up everything. The BBBV lower bound answered no for unstructured search. ^[8] Then, in 1996, Grover showed that the bound could actually be reached. ^[1,2]

The first experimental demonstration came quickly. In 1998 Isaac Chuang, Neil Gershenfeld and Mark Kubinec ran Grover's algorithm on two qubits encoded in the nuclear spins of chloroform molecules. ^[13] In 2017 a trapped-ion group ran a complete three-qubit Grover search. ^[14] These experiments confirmed the mechanism. They did not, and could not, beat a classical computer: searching among 4 or 8 items is trivial for any laptop.

Misconceptions

"A quantum computer tries every answer at once"

False, or at best seriously misleading. A quantum computer can apply an operation to a superposition of many inputs, but measurement returns only one random outcome. If that were the whole story, quantum search would be no better than random guessing. Every useful quantum algorithm works by arranging interference so that wrong answers cancel and right answers reinforce. For unstructured search, that process takes about $\sqrt N$ steps, not one.

"Quantum computers are exponentially faster at everything"

False. Exponential speedups are known only for problems with special mathematical structure, such as factoring (Shor's algorithm) and simulating quantum systems. For generic search, the BBBV theorem limits the speedup to quadratic. ^[8] Many everyday tasks, such as word processing, sorting, or streaming video, have no known meaningful quantum advantage at all. Scott Aaronson's overview for general readers makes the same point: quantum computers would be powerful for certain structured problems, not a universal accelerator. ^[15]

"Quantum computers will break all encryption"

Partly true, and the difference between Shor and Grover is the key.

• Public-key cryptography (RSA, elliptic-curve systems) relies on problems like factoring, which have the special structure Shor's algorithm exploits. A large, error-corrected quantum computer would break these systems outright. ^[12,17] A 2025 estimate suggests that factoring a 2048-bit RSA key might need fewer than a million noisy physical qubits running for about a week, down from 20 million qubits in a 2021 estimate. ^[18,19] NIST has already standardized replacement "post-quantum" algorithms. ^[20]
• Symmetric encryption and hash functions (such as AES and SHA-256) face only Grover's quadratic speedup. A 128-bit key would offer about 64 bits of security against Grover; a 256-bit key would offer about 128 bits. NIST's assessment is that these systems need larger keys or outputs, not replacement. ^[17]

So quantum computers threaten some encryption severely and other encryption only mildly.

"Grover's algorithm searches databases"

Misleading. Grover's original paper was titled as a "database search", but the algorithm needs an oracle that can be queried in superposition. For a real list of stored records, the data would have to be loaded into a quantum-accessible memory, and simply loading $N$ items already costs about $N$ steps, erasing the gain. ^[21] Grover's algorithm is most useful when the oracle is a computation, such as checking whether a candidate key works, not a lookup in stored data.

"Current quantum computers can already do this"

Not in any useful sense. Today's largest machines have from hundreds to a few thousand physical qubits, each prone to errors. John Preskill called this the NISQ era, for "noisy intermediate-scale quantum". ^[22] Running Grover's algorithm on a problem hard enough to matter requires millions or billions of sequential steps without errors, which requires quantum error correction: encoding each reliable logical qubit in many physical qubits and continuously correcting errors. ^[23]

A significant milestone came in 2024, when Google Quantum AI showed that errors in an encoded qubit fell as the error-correcting code was made larger, crossing the threshold where error correction starts to help. ^[24] That was important evidence that scalable error correction is possible. It is still far from the millions of physical qubits needed for large algorithms.

There is also a less obvious problem. Error correction slows every operation down by large factors, and a quadratic speedup is a modest advantage to begin with. An analysis by Babbush and colleagues concluded that quadratic speedups are unlikely to give a practical advantage on early error-corrected machines unless error correction becomes much more efficient. ^[25] Grover's algorithm is therefore better understood as a proof of principle, and a component in other algorithms, than as the first killer application.

Limitations and Open Questions

• Established fact: Grover's algorithm is mathematically proven to find a marked item among $N$ in about $\frac{\pi}{4}\sqrt N$ queries, and no quantum algorithm can do asymptotically better. ^[1,8,9]
• Established experimentally: the algorithm works as predicted on small quantum processors. ^[13,14]
• Not yet demonstrated: any practical advantage from Grover's algorithm over classical computers on a real problem.
• Open engineering question: whether error-corrected machines will be fast and large enough for quadratic speedups to matter. ^[25]
• Open theoretical question: exactly which problems admit large quantum speedups. The black-box argument limits generic search, but problems with hidden structure may still hold surprises.
• Interpretational question: what the state vector "really is", and whether measurement is a genuine physical collapse, is still debated. The algorithm works the same way under all mainstream interpretations. (For the related question of whether nature is fundamentally random, see determinism.)

What the Square Root Reveals

Grover's algorithm matters less for what it will do next year than for what it reveals.

It shows, with complete rigour, that quantum mechanics changes the rules of computation: an unstructured search can be done in $\sqrt N$ steps, something no classical machine can match. It also shows, with the same rigour, how limited that change is: $\sqrt N$ and no better. Quantum computers are not machines that try all answers at once. They are machines that rotate an invisible arrow in an enormous space, and the art lies in finding a rotation that ends at the answer.

The square-root speedup and its limit are proven, and small experiments reproduce the mechanism. That result promises modest but real gains across search and verification and gives cryptographers a precise way to size symmetric keys against quantum attack. Whether hardware can become reliable enough for those gains to outweigh their cost is now the practical question.

References

[1] Grover, L. K. (1996). "A fast quantum mechanical algorithm for database search." Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC '96), 212–219. https://doi.org/10.1145/237814.237866 (Preprint: arXiv:quant-ph/9605043)

[2] Grover, L. K. (1997). "Quantum Mechanics Helps in Searching for a Needle in a Haystack." Physical Review Letters, 79(2), 325–328. https://doi.org/10.1103/PhysRevLett.79.325

[3] Nielsen, M. A., & Chuang, I. L. (2010). Quantum Computation and Quantum Information (10th Anniversary Edition). Cambridge University Press. https://doi.org/10.1017/CBO9780511976667

[4] Hensen, B., Bernien, H., Dréau, A. E., et al. (2015). "Loophole-free Bell inequality violation using electron spins separated by 1.3 kilometres." Nature, 526, 682–686. https://doi.org/10.1038/nature15759

[5] Jozsa, R., & Linden, N. (2003). "On the role of entanglement in quantum-computational speed-up." Proceedings of the Royal Society A, 459(2036), 2011–2032. https://doi.org/10.1098/rspa.2002.1097

[6] Boyer, M., Brassard, G., Høyer, P., & Tapp, A. (1998). "Tight Bounds on Quantum Searching." Fortschritte der Physik, 46(4–5), 493–505. https://doi.org/10.1002/(SICI)1521-3978(199806)46:4/5%3C493::AID-PROP493%3E3.0.CO;2-P (Preprint: arXiv:quant-ph/9605034)

[7] Brown, A. R. (2020). "Playing Pool with |ψ⟩: from Bouncing Billiards to Quantum Search." Quantum, 4, 357. https://doi.org/10.22331/q-2020-11-02-357

[8] Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997). "Strengths and Weaknesses of Quantum Computing." SIAM Journal on Computing, 26(5), 1510–1523. https://doi.org/10.1137/S0097539796300933 (Preprint: arXiv:quant-ph/9701001)

[9] Zalka, C. (1999). "Grover's quantum searching algorithm is optimal." Physical Review A, 60(4), 2746–2751. https://doi.org/10.1103/PhysRevA.60.2746

[10] Feynman, R. P. (1982). "Simulating physics with computers." International Journal of Theoretical Physics, 21(6–7), 467–488. https://doi.org/10.1007/BF02650179

[11] Deutsch, D. (1985). "Quantum theory, the Church–Turing principle and the universal quantum computer." Proceedings of the Royal Society of London A, 400(1818), 97–117. https://doi.org/10.1098/rspa.1985.0070

[12] Shor, P. W. (1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer." SIAM Journal on Computing, 26(5), 1484–1509. https://doi.org/10.1137/S0097539795293172

[13] Chuang, I. L., Gershenfeld, N., & Kubinec, M. (1998). "Experimental Implementation of Fast Quantum Searching." Physical Review Letters, 80(15), 3408–3411. https://doi.org/10.1103/PhysRevLett.80.3408

[14] Figgatt, C., Maslov, D., Landsman, K. A., Linke, N. M., Debnath, S., & Monroe, C. (2017). "Complete 3-Qubit Grover search on a programmable quantum computer." Nature Communications, 8, 1918. https://doi.org/10.1038/s41467-017-01904-7

[15] Aaronson, S. (2008). "The Limits of Quantum Computers." Scientific American, 298(3), 62–69. https://doi.org/10.1038/scientificamerican0308-62

[16] 3Blue1Brown (Sanderson, G.) (2025). "But what is quantum computing? (Grover's Algorithm)." Video, YouTube. Further watching. https://www.youtube.com/watch?v=RQWpF2Gb-gU

[17] Chen, L., Jordan, S., Liu, Y.-K., Moody, D., Peralta, R., Perlner, R., & Smith-Tone, D. (2016). "Report on Post-Quantum Cryptography." NIST Interagency Report NISTIR 8105. https://doi.org/10.6028/NIST.IR.8105

[18] Gidney, C., & Ekerå, M. (2021). "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits." Quantum, 5, 433. https://doi.org/10.22331/q-2021-04-15-433

[19] Gidney, C. (2025). "How to factor 2048 bit RSA integers with less than a million noisy qubits." arXiv preprint 2505.15917. https://arxiv.org/abs/2505.15917

[20] National Institute of Standards and Technology (2024). "Module-Lattice-Based Key-Encapsulation Mechanism Standard." Federal Information Processing Standards Publication FIPS 203. https://doi.org/10.6028/NIST.FIPS.203

[21] Aaronson, S. (2015). "Read the fine print." Nature Physics, 11, 291–293. https://doi.org/10.1038/nphys3272

[22] Preskill, J. (2018). "Quantum Computing in the NISQ era and beyond." Quantum, 2, 79. https://doi.org/10.22331/q-2018-08-06-79

[23] Fowler, A. G., Mariantoni, M., Martinis, J. M., & Cleland, A. N. (2012). "Surface codes: Towards practical large-scale quantum computation." Physical Review A, 86(3), 032324. https://doi.org/10.1103/PhysRevA.86.032324

[24] Google Quantum AI and Collaborators (2025). "Quantum error correction below the surface code threshold." Nature, 638, 920–926. https://doi.org/10.1038/s41586-024-08449-y

[25] Babbush, R., McClean, J. R., Newman, M., Gidney, C., Boixo, S., & Neven, H. (2021). "Focus beyond Quadratic Speedups for Error-Corrected Quantum Advantage." PRX Quantum, 2(1), 010103. https://doi.org/10.1103/PRXQuantum.2.010103