Grover's Algorithm

Overview

Grover's algorithm searches an unsorted collection of N items for one that satisfies a condition, using about the square root of N queries instead of the roughly N a classical computer needs. The speedup is quadratic, and unlike Shor's, it applies to a very broad class of problems: anything where you can check a candidate answer quickly but have no shortcut for finding it.

It is also provably optimal. Bennett, Bernstein, Brassard, and Vazirani showed in 1997 that no quantum algorithm can search an unstructured list in fewer than about the square root of N queries. That makes Grover's algorithm a clean example of how far quantum computing can and cannot go on problems with no structure.

The problem it solves

Finding a specific item in an unsorted list or database without any shortcut like sorting.

History and background

Lov Grover, then at Bell Labs, published the algorithm at the ACM Symposium on Theory of Computing in 1996, two years after Shor's. It was a surprise because many researchers expected that quantum computers would help only with highly structured problems like factoring. Grover showed that even brute-force search benefits.

Boyer, Brassard, Høyer, and Tapp extended it in 1998 to the case where the number of solutions is unknown, and Brassard, Høyer, and Tapp created the related quantum counting algorithm. The method was later generalized by Brassard, Høyer, Mosca, and Tapp into amplitude amplification, which can speed up any classical heuristic that uses randomness. Small versions have been run on all major hardware types, and the first implementations on two and three qubits appeared in the late 1990s and early 2000s.

How it works

Repeatedly applies an oracle that marks the correct answer, then amplifies its probability through reflection operations, concentrating probability onto the right answer.

Imagine the quantum state as an arrow in a two-dimensional plane. One axis represents the marked answer, and the perpendicular axis represents the average of all unmarked items. At the start, an equal superposition over all N items is an arrow almost perpendicular to the answer axis, tilted by a small angle theta, where the sine of theta is the square root of the fraction of marked items.

Each Grover iteration rotates the arrow toward the answer by an angle of 2 theta. The rotation is built from two reflections. First, the oracle flips the sign of the marked item's amplitude, which reflects the arrow about the unmarked axis. Second, the diffusion operator reflects the arrow about the starting equal superposition. Two reflections make a rotation, and after about pi over 4 times the square root of N iterations the arrow lies almost exactly on the answer.

This picture explains two important facts. The algorithm must stop at the right time: if you keep iterating, the arrow rotates past the answer and the success probability falls again. And the speedup is limited to quadratic because each rotation step is a fixed small angle, so the number of steps needed scales with the inverse of that angle.

Step by step

1. Prepare n qubits, where N = 2 to the n, and apply a Hadamard gate to each so that all N basis states have equal amplitude 1 over the square root of N.
2. Apply the oracle, a quantum circuit that flips the sign of the amplitude of any state that satisfies the search condition and leaves the rest unchanged.
3. Apply the diffusion operator: Hadamard on every qubit, a conditional phase flip on the all-zeros state, and Hadamard again. This reflects all amplitudes about their average and thereby amplifies the marked one.
4. Repeat steps 2 and 3 about pi over 4 times the square root of N divided by M times, where M is the number of solutions.
5. Measure all qubits. With probability close to 1, the result is a marked item.
6. Verify the answer with one classical check, since the oracle can be evaluated classically on the candidate. If the check fails, repeat.

A worked example

Consider N = 4 items with one marked, which fits in two qubits. The starting state has amplitude one half on each item, and the angle theta satisfies sine of theta equal to one half, so theta is 30 degrees. One Grover iteration rotates the arrow by 60 degrees to 90 degrees, which points exactly at the marked item, so a single iteration finds it with probability 1. A classical computer would need up to three guesses.

With N = 1,000,000 and one marked item, a classical search takes about 500,000 checks on average, while Grover's algorithm needs about 785 iterations. At N = 2 to the 64, the numbers become 2 to the 63 versus about 2 to the 32 iterations, which is the basis of the claim that Grover's algorithm halves the effective key length of a symmetric cipher.

Complexity and resources

What hardware it needs

• A reliable implementation of the oracle, which is often the most expensive part and can require many ancilla qubits and deep circuits.
• Coherence long enough to run hundreds to millions of iterations without error, so practical large searches need error correction.
• For cryptographic key search, extremely large numbers of sequential iterations that cannot be easily parallelized.

Applications

• Searching databases or solution spaces when only a yes or no check is available, such as satisfiability, constraint solving, and puzzle solving.
• Speeding up other algorithms through amplitude amplification, for example in quantum counting, minimum finding, and collision finding.
• Estimating security margins for symmetric cryptography and hash functions, which is why AES-256 is recommended for long-term security.
• Serving as a standard benchmark and teaching example on real quantum hardware.

Limitations and caveats

• The speedup is only quadratic, so for many problems the overhead of error correction can cancel the gain on realistic hardware.
• Building the oracle may cost more than the search itself, and loading classical data into the oracle is expensive.
• It does not parallelize well: running k machines in parallel gives only a square root of k speedup, so it is worse than classical parallelism.
• Overshooting the optimal number of iterations lowers the success probability.

Common misconceptions

• It does not search a list instantly. It needs about the square root of N steps, which is still large.
• It does not break AES. It effectively halves the key length in the idealized model, which AES-256 and similar ciphers are designed to tolerate.
• It cannot search a real-world database by itself, because loading the data into a quantum state is the bottleneck.

How it compares

• Shor's algorithm has an exponential advantage for a specific structured problem, while Grover's has a smaller but much broader advantage.
• Amplitude amplification generalizes Grover's algorithm to speed up any process that succeeds with some probability.
• Quantum walk search can match the square root scaling on structured graphs and sometimes beats Grover in specific settings.

Real-world impact

Broadly applicable to search and optimization problems; also halves the effective key strength of certain symmetric encryption schemes.

Why it matters

Grover's algorithm shows the limits of quantum computing as much as its power. It proves that for problems without structure, a quantum computer can do no better than a quadratic improvement, which helps people reason about which problems are worth attacking.

It also underlies a great deal of later work. Amplitude amplification, counting, and minimum finding all use the same rotation idea, and many resource estimates for cryptanalysis rely on Grover's algorithm to set key sizes.

Frequently asked questions

Keep learning

• Read the full deep-dive in our Learning Center
• Related algorithm: Quantum Amplitude Amplification
• Related algorithm: Quantum Counting
• Related algorithm: Quantum Minimum Finding
• Related algorithm: Shor's Algorithm

This page is written for educational purposes. Complexity statements describe the best known results at the time of review (September 30, 2026), and research in this area moves quickly, so check recent papers before relying on a specific bound.

← Back to Algorithms Database