Grover's Search Algorithm

This is a Quantum Computing algorithm that searches a database of items efficiently.

Given $N=2^n$ items encoded as n bit-strings. Given an oracle: a boolean function $f:{\mathbb{B}}^n\to \mathbb{B}$

This provides a quadratic improvement over the classical algorithm, a big improvement.

In fact this is the optimal solution for an unstructured search.

Note that you must know the number of solutions to know how many times to apply the process.

The optimal number of iterations is

$$\frac{\pi \sqrt{N}}{4\sqrt{M}}$$

Idea

Construct $u_f$ quantum function (unitary operator on n bits). Assumre $y$ is the only sequence for which $f$ returns 1.¹

$$u_f|\bar{x}⟩=\{\begin{array}{ll}-|\bar{x}⟩& \text{if }x=y\\ |x⟩& \text{o/w }\end{array}$$

Note that we can’t observe this matrix directly, otherwise we’d already know the answer.

$$|{\varphi }_n⟩=H^{\otimes n}{|\bar{0}⟩}_n=\left[\sum _J{|J⟩}_n\right]$$

Then apply inversion about the mean:

$$S=\{s_J{\}}_J\text{mean: }m=\sum _J\frac{s_j}{N}$$

The mean remainst unchanged by the operation $T$:

$$T=\{t_J=2m-s_J{\}}_J$$

Then we have the density matrix $D=|{\varphi }_n⟩⟨{\varphi }_n|$:

$$U_{{\varphi }_n}=2|{\varphi }_n⟩⟨{\varphi }_n|-1_{2^n}=2^{1-n/2}[1{]}_{J\text{texttimes}K}-1_{2^n}$$

This gives us

$$U_{{\varphi }_n}\left[\begin{array}{c}{a}_0\\ \cdots \\ a_{N-1}\end{array}\right]={\left[\begin{array}{c}2m-a_J\end{array}\right]}_J$$

Idea: Use Grover’s diffusion, this boosts the solution we care about around the mean, but doesn’t change the other solutions.

Footnotes

1. The algorithm still works if there are multiple solutions. Otherwise quantum counting can be used in the case where there are multiple solutions. ↩