Tuesday, 10 December 2013

A particular instance of Grover's search

Here, we will analyze how Grover's search algorithm can be used in the particular cases when the density of marked items is $1/4$ and $1/2$.

Consider a function $f:\{0,1\}^n \to \{0,1\}$, define the sets
\begin{align*} A&=\{x\in\{0,1\}^n : f(x)=1\} \\ B&=\{x\in\{0,1\}^n : f(x)=0\}, \end{align*}
and let $a=|A|$ and $b=|B|$.

The equally weighted superposition of all basis states in a $2^n=N$ dimensional Hilbert space can be expressed as
$\ket{\psi_0}=\frac{1}{\sqrt{N}}\SUM{x\in\{0,1\}^n}{}\ket{x}=\sqrt{\frac{a}{N}}\SUM{f(x)=1}{}\ket{x}+\sqrt{\frac{b}{N}}\SUM{f(x)=0}{}\ket{x}.$
Assuming that $a=|A|$ is known, choose $\theta$ such that $\sin(\theta)=\sqrt{\frac{a}{N}}$. Then the superposition $\ket{\psi_0}$ can be equivalently written as
$\ket{\psi_0}=\sin(\theta)\SUM{f(x)=1}{}\ket{x}+\cos(\theta)\SUM{f(x)=0}{}\ket{x}.$
In Grover's search algorithm, $\ket{\psi_0}$ is prepared as an initial state, and then a sequence of \emph{Grover} iterations are applied, which after $k$ iterations, results in the state
$\ket{\psi_k}=\sin((2k+1)\theta)\SUM{f(x)=1}{}\ket{x}+\cos((2k+1)\theta)\SUM{f(x)=0}{}\ket{x}.$
The objective is to choose the number of iterations $k$ so that $\sin((2k+1)\theta)\approx 1$ so that some state $\ket{x}$ such that $x\in{A}$ is measured with high probability. For this to be the case, it suffices that the following conditions hold:
\begin{align*} \sin((2k+1)\theta)&\approx 1 \\ (2k+1)\theta&\approx \frac{\pi}{2} \\ k&\approx \frac{\pi}{4\theta}-\frac{1}{2} \\ \end{align*}

Consider the case when $a=\frac{1}{4}2^n=\frac{1}{4}N$ so that the initial angle $\theta$ is chosen to satisfy $\sin(\theta)=\sqrt{\frac{a}{N}}=\sqrt{\frac{N}{4N}}=\frac{1}{2}$ implying that $\theta=\frac{\pi}{6}$. In this case, the number of desired iterations that need to be performed is actually given by
$k= \frac{\pi}{4\theta}-\frac{1}{2}=\frac{\pi 6}{4\pi}-\frac{1}{2}=1,$
and thus Grover's algorithm is guaranteed to find an $x$ such that $x\in A$ in just a single iteration.

Now consider the case where $a=\frac{1}{2}2^n=\frac{1}{2}N$ so that the initial angle $\theta$ is chosen to satisfy $\sin(\theta)=\sqrt{\frac{a}{N}}=\sqrt{\frac{N}{2N}}=\frac{1}{\sqrt{2}}$ implying that $\theta=\frac{\pi}{4}$. In this case, the number of desired iterations that need to be performed is approximately
$k\approx \frac{\pi}{4\theta}-\frac{1}{2}=\frac{\pi 4}{4\pi}-\frac{1}{2}=\frac{1/2}.$
However, since $k$ is not an integer and is equally close to the integers $0$ and $1$ it is seen that a state $\ket{x}$ such that $x\in A$ is not guaranteed to be found with certainty if the state $\ket{\psi_k}$ were to be measured. In this instance, Grover's search algorithm provides no benefit, in the sense that the likelihood of observing a state $\ket{x}$ such that $x\in A$ is equally probably if $1$ iteration is performed or if $0$ iterations are performed to the initial state.