Grover Search

Grover search makes a marked input likely to appear when we measure a quantum register. Its mechanism is geometric: one reflection changes the signs of marked amplitudes, and a second reflection converts that phase difference into increased marked probability. Repeating the pair rotates the state toward the marked subspace.

For an unstructured predicate with $M$ marked inputs among $N$, the quantum query complexity for success probability at least $2/3$ is $\Theta(\sqrt{N/M})$ when $1\le M\le N/2$, compared with $\Theta(N/M)$ classically. These bounds assume the same Boolean oracle problem. They count calls to a supplied coherent oracle, not the gates or memory needed to implement it.

Helpful background. Phase kickback explains how a Boolean answer becomes a phase. Projectors supplies the geometry of the two reflections. Query complexity explains bounded-error oracle comparisons.

Marked inputs and Boolean oracle access

Let $f:\{0,\ldots,N-1\}\to\{0,1\}$, with exactly $M$ inputs satisfying $f(x)=1$. The task is to output any such input. If $M=0$, no valid output exists; if $M=N$, every label works. Apart from querying $f$, assume the labels reveal no exploitable structure about which inputs are marked.

The supplied bit oracle acts on an address and a target qubit:

$$U_f\lvert x\rangle\lvert y\rangle =\lvert x\rangle\lvert y\mathbin\oplus f(x)\rangle.$$

With the target in $\lvert-\rangle=(\lvert0\rangle-\lvert1\rangle)/\sqrt2$, one call applies the search-register phase oracle and returns the target unchanged:

$$O_f\lvert x\rangle=(-1)^{f(x)}\lvert x\rangle, \qquad O_f=I-2\Pi_G,$$

where $\Pi_G$ projects onto marked basis states. With a target in $\lvert0\rangle$, a bit-oracle call instead checks a measured candidate.

These two uses explain why the access assumption matters. A supplied uncontrolled phase oracle alone cannot distinguish $f$ from $1-f$: their operators differ only by a global minus sign. In particular, for a half-marked set and its complement, no common output distribution can succeed above one half on both. The full bit oracle removes this ambiguity and supports verification. See quantum oracles for the distinction between access types.

Classically, $q$ independent uniform trials fail with probability $(1-M/N)^q$. Avoiding repeated addresses improves constants but leaves the $\Theta(N/M)$ scale for the stated success target. Grover search improves this scale quadratically. It does not replace binary search on a sorted list, which uses additional structure.

The marked–unmarked plane

Start in the uniform superposition

$$\lvert s\rangle = \frac1{\sqrt N} \sum_{x=0}^{N-1}\lvert x\rangle.$$

For $0<M<N$, define normalized states in the marked and unmarked subspaces:

$$\begin{aligned} \lvert G\rangle &= \frac1{\sqrt M} \sum_{f(x)=1}\lvert x\rangle, \\ \lvert B\rangle &= \frac1{\sqrt{N-M}} \sum_{f(x)=0}\lvert x\rangle. \end{aligned}$$

They are orthonormal. Introduce an angle $\theta\in(0,\pi/2)$ by

$$\sin^2\theta=\frac MN.$$

The initial state becomes

$$\lvert s\rangle = \sin\theta\,\lvert G\rangle + \cos\theta\,\lvert B\rangle.$$

Both the phase oracle and the diffusion operation preserve the plane spanned by $\lvert G\rangle$ and $\lvert B\rangle$. The full $N$-dimensional calculation therefore collapses to a planar rotation. Equal amplitudes within each class remain equal throughout the ideal algorithm.

The oracle reflects $\lvert s\rangle$ across the unmarked axis. Reflection about $\lvert s\rangle$ then produces $Q\lvert s\rangle$, advancing the state toward $\lvert G\rangle$ by $2\theta$.

For $N=2^n$, Hadamards prepare $\lvert s\rangle$ from $\lvert0^n\rangle$. For other $N$, the derivation assumes preparation of the uniform state on exactly the $N$ valid labels and a reflection about it. Padding to a larger power of two is also possible, but then the initial marked fraction and iteration count must use the padded size.

Two reflections and their rotation

The diffusion operator is

$$D=2\lvert s\rangle\langle s\rvert-I.$$

It fixes $\lvert s\rangle$ and reverses every vector orthogonal to $\lvert s\rangle$, so it is reflection about the initial-state axis. One Grover iterate is

$$Q=DO_f.$$

In the ordered basis $\{\lvert G\rangle,\lvert B\rangle\}$,

$$\begin{aligned} O_f &= \begin{pmatrix} -1&0\\ 0&1 \end{pmatrix}, \\[4pt] D &= \begin{pmatrix} -\cos2\theta&\sin2\theta\\ \sin2\theta&\cos2\theta \end{pmatrix}, \\[4pt] Q &= \begin{pmatrix} \cos2\theta&\sin2\theta\\ -\sin2\theta&\cos2\theta \end{pmatrix}. \end{aligned}$$

Although the last matrix depends on the chosen coordinate ordering, its action is unambiguous. Write

$$\begin{aligned} \lvert\psi(\phi)\rangle &= \sin\phi\,\lvert G\rangle + \cos\phi\,\lvert B\rangle,\\ Q\lvert\psi(\phi)\rangle &= \lvert\psi(\phi+2\theta)\rangle. \end{aligned}$$

Each iterate advances the state-angle parameter by $2\theta$ toward the marked axis.

Inversion about the mean

For $N=2^n$, the diffusion operator can be written

$$D = H^{\otimes n} \left( 2\lvert0^n\rangle\langle0^n\rvert-I \right) H^{\otimes n}.$$

If a state has computational-basis amplitudes $\alpha_x$ and mean amplitude

$$\overline{\alpha} = \frac1N\sum_x\alpha_x,$$

then $D$ maps

$$\alpha_x\longmapsto2\overline{\alpha}-\alpha_x.$$

This explains the traditional name inversion about the mean. It is the same reflection as $2\lvert s\rangle\langle s\rvert-I$, expressed component by component. Multiplying a reflection by an overall phase leaves this uncontrolled search experiment unchanged. In a controlled Grover operation, however, that phase becomes relative to the inactive control branch and must be tracked; this matters for amplitude estimation.

Success probability and when to stop

The initial state has angle $\theta$ in the good–bad plane. After $r$ Grover iterations,

$$Q^r\lvert s\rangle = \sin\!\left((2r+1)\theta\right) \lvert G\rangle + \cos\!\left((2r+1)\theta\right) \lvert B\rangle.$$

Measuring in the computational basis therefore returns a marked input with probability

$$P_r = \sin^2\!\left((2r+1)\theta\right).$$

Conditioned on success, each of the $M$ marked labels is equally likely in the symmetric version of the algorithm.

Choosing the stopping time

The first probability maximum occurs when

$$(2r+1)\theta\approx\frac\pi2.$$

Choose the nonnegative integer nearest to

$$r_\star = \frac{\pi}{4\theta}-\frac12.$$

Rounding changes the final angle by at most $\theta$, giving

$$P_r\geq\cos^2\theta = 1-\frac MN$$

for $0<M<N$. In particular, for $M\le N/2$ the success probability is at least one half. Two independent runs, each followed by a bit-oracle check of the measured candidate, succeed with probability at least $3/4$. Thus the stated $2/3$ target requires only a constant number of runs. Each verification costs one additional query; an exactly successful promised instance needs no verification. For a sparse marked set,

$$\theta = \arcsin\sqrt{\frac MN} \approx \sqrt{\frac MN},$$

so

$$r \approx \frac\pi4\sqrt{\frac NM}.$$

The probability is oscillatory. Continuing past the optimum rotates amplitude away from the marked subspace. More iterations are not automatically better.

Four-item and eight-item examples

One marked item among four

For $N=4$ and $M=1$,

$$\sin\theta=\frac12, \qquad \theta=\frac\pi6.$$

One iteration gives

$$P_1 = \sin^2(3\theta) = \sin^2\frac\pi2 = 1.$$

This is the smallest familiar example in which the standard $\pi$-phase reflections land exactly on the marked axis.

One marked item among eight

For $N=8$ and $M=1$,

$$\theta=\arcsin\frac1{\sqrt8} \approx0.3614.$$

The nearest stopping time is $r=2$, and

$$P_2 = \sin^2(5\theta) \approx0.9453.$$

A third iteration would overshoot:

$$P_3 = \sin^2(7\theta) \approx0.3301.$$

The comparison makes the coherent rotation, and the need to stop deliberately, concrete.

There is also an instructive boundary case: if $M=N/2$, then $\theta=\pi/4$ and $P_r=1/2$ for every integer $r$. Standard $\pi$ reflections never improve the initial probability. Independent sampling and verification already take only constant expected cost. For $M>N/2$, this simple strategy is likewise sufficient.

Searching when the marked fraction is unknown

A stopping time chosen for one solution can overshoot when there are several. The randomized method of Boyer, Brassard, Høyer and Tapp avoids needing $M$ in advance. One convenient version starts with $m=1$ and repeats:

1. Test a uniformly sampled label, stopping if it is marked.
2. Choose an integer $j$ uniformly from $0\le j<m$; prepare a fresh $\lvert s\rangle$, apply $j$ Grover iterations, measure and verify.
3. After failure, replace $m$ by $\min(6m/5,\sqrt N)$.

The first test handles dense marked sets cheaply. For $M>0$, the expected total query cost is $O(\sqrt{N/M})$, including verification. This is an expected stopping time, not a deterministic cap. If $M=0$ is allowed, impose a finite budget and specify the probability of incorrectly reporting no solution. Repeated failure alone is not a proof of emptiness.

Other useful variants solve different problems:

• Amplitude estimation estimates the marked fraction using the eigenphases of a controlled Grover operation.
• Given a positive lower bound $a_{\min}\le M/N$, optimal fixed-point constructions choose phase shifts so that the completed sequence has failure at most $\epsilon$, using $O(\log(1/\epsilon)/\sqrt{a_{\min}})$ queries for $0<\epsilon<1/2$. This is a uniform guarantee over allowed marked fractions, not a claim that every intermediate step increases success. The response can have small oscillations within its guaranteed error band.
• When $M$ is known, suitable phase adjustments can produce exact success. These are modified reflections; their probabilities need not follow the standard $P_r$ above.

Amplitude amplification develops these phase schedules and replaces uniform preparation by an arbitrary reversible state preparation.

Query optimality and implementation cost

The hybrid argument of Bennett, Bernstein, Brassard and Vazirani gives an $\Omega(\sqrt N)$ bound for finding a single marked item with bounded error. Boyer and collaborators analyze multiple solutions and unknown $M$; Zalka establishes the optimal leading behavior for near-certain single-solution search, $\pi\sqrt N/4$. More generally, the fixed-error bound is $\Theta(\sqrt{N/M})$ for $1\le M\le N/2$. It applies to the unstructured oracle problem, not every structured problem that can be encoded as search.

For a single marked item and $1\le p\le N$ parallel oracle calls per round, the optimal round count is $\Theta(\sqrt{N/p})$. Splitting the candidates into $p$ groups achieves this scale. Using all $p$ calls each round gives total work of order $\sqrt{Np}$, so reducing depth by parallel hardware does not reduce total queries by the same factor.

A direct circuit implementation has several separate costs:

Operation	Cost in one run	Physical meaning
Initial preparation	$C_{\rm prep}$	Make the intended distribution over valid labels.
Phase predicate	$rC_f$	Evaluate the predicate reversibly, apply its phase, and restore workspace.
Diffusion reflection	$rC_D$	Reflect about the prepared state.
Candidate check	$C_{\rm verify}$ when used	Read whether the measured label is marked.

Thus this implementation uses roughly $C_{\rm prep}+r(C_f+C_D)+C_{\rm verify}$ gates before repetitions, synthesis and error-correction overhead. This is a circuit estimate, not a universal gate lower bound. Reversible computation explains workspace restoration, and universal gate sets explains decomposing the reflections into available gates.

A classical database does not automatically provide coherent predicate access. Loading arbitrary data, accessing it reversibly and comparing entries may dominate the search. Conversely, a compact arithmetic predicate can often be implemented without loading a list. The physical implementation determines whether a query advantage becomes a runtime advantage.

What applications can and cannot gain

For $n$ binary variables with one satisfying assignment, $N=2^n$ and the Grover query count is $\Theta(2^{n/2})$. This is still exponential in $n$. It improves naive exhaustive enumeration, while classical pruning or other quantum algorithms may exploit structure unavailable to the black-box model.

The same qualification applies to key or preimage search: reversible checking gives an ideal square-root query reduction, but the number of targets, oracle gates, depth, parallelism and fault tolerance determine concrete cost. Grover search returns one candidate; it does not reveal all function values or list every solution at once.

The Dürr–Høyer minimum-finding algorithm uses repeated searches below a changing threshold to find an unstructured list minimum in $O(\sqrt N)$ value queries with bounded error. Its threshold updates are essential additional steps. Quantum algorithms for optimization compares this approach with methods that exploit more structure.

Exercises

1. Invariant two-dimensional subspace

Show that $O_f$ and $D$ map every vector in

$$\operatorname{span}\{\lvert G\rangle,\lvert B\rangle\}$$

back into the same span. Explain why this is sufficient to analyze the uniform-start algorithm in two dimensions.

Solution

The oracle acts as

$$O_f\lvert G\rangle=-\lvert G\rangle, \qquad O_f\lvert B\rangle=\lvert B\rangle,$$

so it preserves the span. Since $\lvert s\rangle$ lies in the span, for any vector $\lvert v\rangle$ in it,

$$D\lvert v\rangle = 2\lvert s\rangle\langle s\vert v\rangle -\lvert v\rangle$$

is also a linear combination of $\lvert G\rangle$ and $\lvert B\rangle$. The initial state lies in this invariant plane, so every later state does as well.

2. Exact four-item search

For $N=4$ and one marked item, calculate the marked amplitude before and after one Grover iteration.

Solution

Initially,

$$\sin\theta=\frac12, \qquad \theta=\frac\pi6.$$

The marked amplitude in the normalized good direction is $1/2$. One iterate changes the angle from $\theta$ to $3\theta=\pi/2$, so the marked amplitude becomes

$$\sin\frac\pi2=1.$$

There is only one marked basis state, hence measurement returns it with certainty.

3. Stopping-time guarantee

Let $r$ be the integer nearest to $\pi/(4\theta)-1/2$. Prove that the final success probability is at least $\cos^2\theta$.

Solution

Nearest-integer rounding gives

$$\left| r-\left(\frac{\pi}{4\theta}-\frac12\right) \right| \leq\frac12.$$

Multiplying by $2\theta$ yields

$$\left| (2r+1)\theta-\frac\pi2 \right| \leq\theta.$$

Write the final angle as $\pi/2+\delta$, where $\lvert\delta\rvert\leq\theta$. Then

$$P_r = \sin^2\left(\frac\pi2+\delta\right) = \cos^2\delta \geq \cos^2\theta.$$

Using $\sin^2\theta=M/N$ gives $P_r\geq1-M/N$.

4. Several marked inputs

Suppose $N=1024$ and $M=16$. Estimate $\theta$, the optimal number of standard iterations, and the classical and quantum query scales.

Solution

Here

$$\begin{aligned} \sin\theta &= \sqrt{\frac{16}{1024}} = \frac18, \\ \theta &= \arcsin\frac18 \approx0.1253. \end{aligned}$$

The real-valued optimum is

$$\frac{\pi}{4\theta}-\frac12 \approx5.77,$$

so choose $r=6$. Classical sampling takes order

$$\frac NM=64$$

queries, whereas Grover search takes order

$$\sqrt{\frac NM}=8$$

queries, with the leading constant setting the particular stopping time.

5. Over-rotation

For $N=8$ and $M=1$, compare the success probabilities after two and three iterations. Why does this rule out a stopping policy of “continue until success is certain” without knowledge of $\theta$?

Solution

With $\theta=\arcsin(1/\sqrt8)$,

$$P_2=\sin^2(5\theta)\approx0.9453,$$

whereas

$$P_3=\sin^2(7\theta)\approx0.3301.$$

The unitary evolution rotates rather than relaxes toward the target. It contains no internal signal announcing that the probability has peaked. A stopping rule must use knowledge of $M$, estimation, randomized schedules, or a fixed-point design.

6. Phase oracle and uncomputation

Assume the clean phase oracle $O_f\lvert x\rangle=(-1)^{f(x)}\lvert x\rangle$. Show that $O_f=I-2\Pi_G$. Then consider $N=4$ with one marked input. Suppose a faulty implementation leaves an orthogonal workspace label $\lvert x\rangle$ for each address. What happens if the workspace is discarded before applying $D$?

Solution

The projector $\Pi_G$ has eigenvalue $1$ on marked basis states and $0$ on unmarked basis states. Therefore $I-2\Pi_G$ has eigenvalue $-1$ when $f(x)=1$ and $+1$ when $f(x)=0$, exactly matching $O_f$.

If evaluating the predicate instead produces

$$\lvert x\rangle\lvert0\rangle \longmapsto \lvert x\rangle\lvert w_x\rangle,$$

then different $x$ values remain correlated with different workspace states. The input register no longer undergoes the intended clean reflection $O_f$. In the stated four-item example, tracing out the orthogonal workspace gives $\rho=I/4$. Since $D\rho D^\dagger=I/4$, the marked probability stays $1/4$, instead of becoming one. To implement the clean phase oracle on the search register, the workspace must finish in a common state independent of $x$. Compute–phase–uncompute is the usual way to achieve this; merely discarding correlated workspace is not.

7. Quadratic is still exponential

An unstructured constraint problem has $n$ binary variables and one satisfying assignment. Express the classical and Grover query counts in terms of $n$. What claim is justified?

Solution

There are $N=2^n$ assignments. Exhaustive classical search requires

$$\Theta(2^n)$$

predicate queries, while Grover search requires

$$\Theta(\sqrt{2^n}) = \Theta(2^{n/2}).$$

The justified claim is a quadratic improvement in $N$, or a halving of the exponent in this black-box enumeration model. It is not a polynomial-time algorithm in $n$, and it does not establish an efficient algorithm for arbitrary structured instances.

References

• C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, “Strengths and weaknesses of quantum computing,” SIAM Journal on Computing 26, 1510–1523, 1997, doi:10.1137/S0097539796300933.
• M. Boyer, G. Brassard, P. Høyer, and A. Tapp, “Tight bounds on quantum searching,” Fortschritte der Physik 46, 493–505, 1998, arXiv:quant-ph/9605034.
• G. Brassard, P. Høyer, M. Mosca, and A. Tapp, “Quantum amplitude amplification and estimation,” Contemporary Mathematics 305, 53–74, 2002, arXiv:quant-ph/0005055.
• C. Dürr and P. Høyer, “A quantum algorithm for finding the minimum,” 1996, arXiv:quant-ph/9607014.
• L. K. Grover, “A fast quantum mechanical algorithm for database search,” in Proceedings of the 28th Annual ACM Symposium on Theory of Computing, 212–219, 1996, doi:10.1145/237814.237866.
• M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, 10th anniversary ed., Cambridge University Press, 2010, doi:10.1017/CBO9780511976667.
• T. J. Yoder, G. H. Low, and I. L. Chuang, “Fixed-point quantum search with an optimal number of queries,” Physical Review Letters 113, 210501, 2014, doi:10.1103/PhysRevLett.113.210501.
• C. Zalka, “Grover’s quantum searching algorithm is optimal,” Physical Review A 60, 2746–2751, 1999, doi:10.1103/PhysRevA.60.2746.