grover's algorithm

• You have a function \(f\) such that \(f(x)=0\) for all \(x\) except at \(M\) values for which \(f(x)=1\). How do we find those values?
• Assume the search space is \(N=2^n\)
• Assume you have an oracle that performs \(\ket{x} \rightarrow (-1)^{f(x)}\ket{x}\)

• Start in the state \(\ket{0}^{\otimes n}\)
• Apply the Hadamard transform (see quantum gates) to obtain:

\[ \ket{\psi} = \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1} \ket{x} \]

Then, we repeatedly apply the Grover iteration:

1. Apply the Oracle
2. Apply the Hadamard transform \(H^{\otimes n}\)
3. Perform a phase shift such that ever \(\ket{x}\) that is not 0 becomes flipped. That is \(\ket{x} \rightarrow -(-1)^{x==0}\ket{x}\)
4. Apply the Hadamard transform \(H^{\otimes n}\)

Note that this iteration can be written: \[ H^{\otimes n}(2\ket{0}\bra{0} - I)H^{\otimes n} = 2\ket{\psi}\bra{\psi} - I \] We get the RHS because \(HIH = I\) and because applying \(H^{\otimes n}\) to \(\ket{0}\) gets you a superposition of all states (see quantum gates)

Then, define: \[ \ket{\alpha} \equiv \frac{1}{\sqrt{N-M}}\sum_{x:f(x)=0} \ket{x} \] and \[ \ket{\beta} \equiv \frac{1}{\sqrt{M}}\sum_{x:f(x)=1} \ket{x} \] where \(\ket{\alpha}\) is a superposition of all non-solutions and \(\ket{\beta}\) is a superposition of all solutions.

We see that the starting state (the superposition of all states) can be written as: \[ \ket{\psi} = \sqrt{\frac{N-M}{N}}\ket{\alpha} + \sqrt{\frac{M}{N}}\ket{\beta} \]

Next, we claim that throughout the algorithm, the state stays within the plane defined by \(\ket{\alpha}\) and \(\ket{\beta}\).

First, we claim that the oracle performs a reflection about \(\ket{\alpha}\) in the plane defined by \(\ket{\alpha}\) and \(\ket{\beta}\). This can be seen because applying the oracle to \(a\ket{\alpha} + b\ket{\beta}\) gives \(a\ket{\alpha} - b\ket{\beta}\).

Next, we claim that \((2\ket{\psi}\bra{\psi} - I)\) also performs a reflection about \(\ket{\psi}\) in the same plane. Why? It's a householder transformation, which can be thought of as an inversion. Why does it stay in the plane? \(I\) keeps the state in the same plane. And \(\ket{\psi}\bra{\psi}\) results in a multiple of \(\ket{\psi}\) which is a linear combination of \(\ket{\alpha}\) and \(\ket{\beta}\).

Each time we run the Grover iteration, the state rotates by \(\theta\). Take a look at the figure in Nielsen and Chuang. Let's say the angle between the state \(\ket{\psi}\) and \(\ket{\alpha}\) is \(\theta/2\). Then, reflecting around \(\ket{\alpha}\) puts the state \(\theta/2\) below \(\ket{\alpha}\) and then reflecting around \(\ket{\psi}\) puts it \(\theta\) above \(\ket{\psi}\), which is \(3\theta/2\) above \(\ket{\alpha}\).

Originally, the state is \(\ket{\psi} = \cos\theta/2 \ket{\alpha} + \sin\theta/2 \ket{\beta}\). And after each iteration, the state rotates by \(\theta\). Then, after \(k\) iterations, the state is at \[ \cos \left(\frac{2k+1}{2} \theta\right) \ket{\alpha} + \sin \left(\frac{2k+1}{2} \theta\right) \ket{\beta}. \]

The initial state is \(\sqrt{(N-M)/N}\ket{\alpha} + \sqrt{M/N}\ket{\beta}\), so the angle between the state and \(\beta\) is \(\arccos\sqrt{M/N}\).

Then, the integer amount of times we need to rotate the state is: \[ CI\left(\frac{\arccos\sqrt{M/N}}{\theta}\right) \] Where \(CI()\) gets the closest integer.

Then, the state is at most \(\theta/2\) angle away from \(\ket{\beta}\). Why? If we were, for instance, \(0.7\theta\) away from \(\beta\), then we should rotate one more time. \(\theta\) is at most \(\pi/2\) (perpindicular), so the angle is at most \(\pi/4\).

Then, measurement of the state gives a solution with probability at least \(1/2\). Why? What is the dot product between \(\ket{\beta}\) and the final state \(\ket{\psi}\)? It is at most \(cos(\pi/4) = 1/\sqrt{2}\). Square this to get the probability, \(1/2\). Lingering question: to do projective measurement like this, don't we have to know \(\ket{\beta}\)? Obviously, we will do the measurement in the computational basis, but then how do we find the probability? Maybe the calculation is: sum the probabilities for all the solution states \(\ket{x}\) and show that these probabilities are at least the squared dot product with \(\ket{\beta}\) using triangle inequality?

Some more thoughts on the above: consider the state \(\ket{\psi}\) at the end. About \(\cos\theta/2\) of the weight is on the \(\ket{\beta}\) component. Among the states in superposition in \(\ket{\beta}\), this weight is shared equally. Each component has weight \(\frac{\cos\theta/2}{\sqrt{M}}\), so the sum of all probabilities is \((\cos\theta/2)^2 = |\braket{\psi}{\beta}|^2\).

Let's take a closer look at the performance bound. Note that it is at most \(\lceil \frac{\pi}{2}/\theta \rceil\). Let's try to lower bound \(\theta\).

Assume that \(M\leq N/2\) (Why?). We have \[ \theta/2 \geq \sin\theta/2 = \sqrt{M/N} \]

so the performance bound is \(\lceil \frac{\pi}{2} \sqrt{N/M} \rceil\)

• Nielsen and Chuang
• helpful explanation