concepts-grovers.md

title	description	author	uid	ms.author	ms.date	ms.service	ms.subservice	ms.topic	no-loc
Theory of Grover's search algorithm	Learn about the theory behind Grover's algorithm.	bradben	microsoft.quantum.concepts.grovers	v-benbra	12/11/2017	azure-quantum	core	conceptual	Q# $$v $$ $$ $ $ $ $$ \cdots bmatrix \ddots \equiv \sum \begin \end \sqrt \otimes { } \text \phi \kappa \psi \alpha \beta \gamma \delta \omega \bra \ket \boldone \\\\ \\ = \frac \text \mapsto \dagger \to \begin{cases} \end{cases} \operatorname \braket \id \expect \defeq \variance \dd & \begin{align} \end{align} \Lambda \lambda \Omega \mathrm \left \right \qquad \times \big \langle \rangle \bigg \Big | \mathbb \vec \in \texttt \ne < > \leq \geq ~~ ~ \begin{bmatrix} \end{bmatrix} \_

Theory of Grover's search algorithm

In this article you'll find a detailed theoretical explanation of the mathematical principles that make Grover's algorithm work.

For a practical implementation of Grover's algorithm to solve mathematical problems you can read our guide to implement Grover's search algorithm.

Statement of the problem

Any search task can be expressed with an abstract function $f(x)$ that accepts search items $x$. If the item $x$ is a solution to the search task, then $f(x)=1$. If the item $x$ isn't a solution, then $f(x)=0$. The search problem consists of finding any item $x_0$ such that $f(x_0)=1$.

The task that Grover's algorithm aims to solve can be expressed as follows: given a classical function $f(x):\{0,1\}^n \rightarrow\{0,1\}$, where $n$ is the bit-size of the search space, find an input $x_0$ for which $f(x_0)=1$. The complexity of the algorithm is measured by the number of uses of the function $f(x)$. Classically, in the worst-case scenario, we have to evaluate $f(x)$ a total of $N-1$ times, where $N=2^n$, trying out all the possibilities. After $N-1$ elements, we know it must be the last element. We will see that Grover's quantum algorithm can solve this problem much faster, providing a quadratic speed up. Quadratic here implies that only about $\sqrt{N}$ evaluations would be required, compared to $N$.

Outline of the algorithm

Suppose we have $N=2^n$ eligible items for the search task and we index them by assigning each item an integer from $0$ to $N-1$. Further, suppose we know that there are $M$ different valid inputs, meaning that there are $M$ inputs for which $f(x)=1$. The steps of the algorithm are then as follows:

1. Start with a register of $n$ qubits initialized in the state $\ket{0}$.
2. Prepare the register into a uniform superposition by applying $H$ to each qubit of the register: $$|\text{register}\rangle=\frac{1}{\sqrt{N}} \sum_{x=0}^{N-1}|x\rangle$$
3. Apply the following operations to the register $N_{\text{optimal}}$ times:
   1. The phase oracle $O_f$ that applies a conditional phase shift of $-1$ for the solution items.
   2. Apply $H$ to each qubit in the register.
   3. A conditional phase shift of $-1$ to every computational basis state except $\ket{0}$. This can be represented by the unitary operation $-O_0$, as $O_0$ represents the conditional phase shift to $\ket{0}$ only.
   4. Apply $H$ to each qubit in the register.
4. Measure the register to obtain the index of a item that's a solution with very high probability.
5. Check if it's a valid solution. If not, start again.

$N_\text{optimal} = \left\lfloor \frac{\pi}{4}\sqrt{\frac{N}{M}}-\frac{1}{2} \right\rfloor$ is the optimal number of iterations that maximizes the likelihood of obtaining the correct item by measuring the register.

Note

The joint application of the steps 3.b, 3.c and 3.d is usually known in the literature as Grover's diffusion operator.

The overall unitary operation applied to the register is:

$$(-H^{\otimes n}O_0H^{\otimes n}O_f)^{N_{\text{optimal}}}H^{\otimes n}$$

Following the register's state step by step

To illustrate the process, let's follow the mathematical transformations of the state of the register for a simple case in which we have only two qubits and the valid element is $\ket{01}.$

1. We start with the register in the state: $$|\text{register}\rangle=|00\rangle$$

2. After applying $H$ to each qubit the register's state transforms to: $$|\text{register}\rangle = \frac{1}{\sqrt{4}} \sum_{i \in \{0,1\}^2}|i\rangle=\frac12(\ket{00}+\ket{01}+\ket{10}+\ket{11})$$

3. Then we apply the phase oracle to get: $$|\text{register}\rangle = \frac12(\ket{00}-\ket{01}+\ket{10}+\ket{11})$$

4. Then $H$ acts on each qubit again to give: $$|\text{register}\rangle = \frac12(\ket{00}+\ket{01}-\ket{10}+\ket{11})$$

5. Now we apply the conditional phase shift on every state except $\ket{00}$: $$|\text{register}\rangle = \frac12(\ket{00}-\ket{01}+\ket{10}-\ket{11})$$

6. Now we end the first Grover iteration by applying $H$ again to get: $$|\text{register}\rangle = \ket{01}$$

   We found the valid item in a single iteration. As we will see later, this is because for N=4 and a single valid item, $N_\text{optimal}=1$.

Geometrical explanation

To see why Grover's algorithm works, let's study the algorithm from a geometrical perspective. Let $\ket{bad}$ be the superposition of all states that aren't a solution to the search problem. Supposing there are $M$ valid solutions, we get:

$$\ket{\text{bad}}=\frac{1}{\sqrt{N-M}}\sum_{x:f(x)=0}\ket{x}$$

We define the state $\ket{good}$ as the superposition of all states that are a solution to the search problem:

$$\ket{\text{good}}=\frac{1}{\sqrt{M}}\sum_{x:f(x)=1}\ket{x}$$

Since good and bad are mutually exclusive sets because an item cannot be valid and not valid, the states $\ket{good}$ and $\ket{bad}$ are orthogonal. Both states form the orthogonal basis of a plane in the vector space. We can use this plane to visualize the algorithm.

Now, suppose $\ket{\psi}$ is an arbitrary state that lives in the plane spanned by $\ket{\text{good}}$ and $\ket{\text{bad}}$. Any state living in that plane can be expressed as:

$$\ket{\psi} = \alpha \ket{\text{good}} + \beta \ket{\text{bad}}$$

where $\alpha$ and $\beta$ are real numbers. Now, let's introduce the reflection operator $R_{\ket{\psi}}$, where $\ket{\psi}$ is any qubit state living in the plane. The operator is defined as:

$$R_{\ket{\psi}}=2\ket{\psi}\bra{\psi}-\mathcal{I}$$

It is called the reflection operator about $\ket{\psi}$ because it can be geometrically interpreted as reflection about the direction of $\ket{\psi}$. To see it, take the orthogonal basis of the plane formed by $\ket{\psi}$ and its orthogonal complement $\ket{\psi^{\perp}}$. Any state $\ket{\xi}$ of the plane can be decomposed in such basis:

$$\ket{\xi}=\mu \ket{\psi} + \nu {\ket{\psi^{\perp}}}$$

If we apply the operator $R_{\ket{\psi}}$ to $\ket{\xi}$ we get:

$$R_{\ket{\psi}}\ket{\xi}=\mu \ket{\psi} - \nu {\ket{\psi^{\perp}}}$$

The operator $R_\ket{\psi}$ inverts the component orthogonal to $\ket{\psi}$ but leaves the $\ket{\psi}$ component unchanged. Therefore, $R_\ket{\psi}$ is a reflection about $\ket{\psi}$.

In Grover's algorithm, after the first application of $H$ to every qubit, we start with an uniform superposition of all states. This can be written as:

$$\ket{\text{all}} = \sqrt{\frac{M}{N}}\ket{\text{good}} + \sqrt{\frac{N-M}{N}}\ket{\text{bad}}$$

And thus the state lives in the plane. Note that the probability of obtaining a correct result when measuring from the equal superposition is just $|\braket{\text{good}|{\text{all}}}|^2=M/N$, that is what we expect from a random guess.

The oracle $O_f$ adds a negative phase to any solution to the search problem. Therefore, it can be written as a reflection about the $\ket{\text{bad}}$ axis:

$$O_f = R_{\ket{\text{bad}}} = 2\ket{\text{bad}}\bra{\text{bad}} - \mathcal{I}$$

Analogously, the conditional phase shift $O_0$ is just an inverted reflection about the state $\ket{0}$:

$$O_0 = R_{\ket{0}}= -2\ket{0}\bra{0} + \mathcal{I}$$

Knowing this fact, it's easy to check that the Grover diffusion operation $-H^{\otimes n} O_0 H^{\otimes n}$ is also a reflection about the state $\ket{all}$. Just do:

$$-H^{\otimes n} O_0 H^{\otimes n}=2H^{\otimes n}\ket{0}\bra{0}H^{\otimes n} -H^{\otimes n}\mathcal{I}H^{\otimes n} = 2\ket{\text{all}}\bra{\text{all}} - \mathcal{I} = R_{\ket{\text{all}}}$$

We just demonstrated that each iteration of Grover's algorithm is a composition of two reflections $R_\ket{\text{bad}}$ and $R_\ket{\text{all}}$.

The combined effect of each Grover iteration is a counterclockwise rotation of an angle $2\theta$. Fortunately, the angle $\theta$ is easy to find. Since $\theta$ is just the angle between $\ket{\text{all}}$ and $\ket{\text{bad}}$, we can use the scalar product to find the angle. We know that $\cos{\theta}=\braket{\text{all}|\text{bad}}$, so we need to calculate $\braket{\text{all}|\text{bad}}$. From the decomposition of $\ket{\text{all}}$ in terms of $\ket{\text{bad}}$ and $\ket{\text{good}}$, we get that:

$$\theta = \arccos{\left(\braket{\text{all}|\text{bad}}\right)}= \arccos{\left(\sqrt{\frac{N-M}{N}}\right)} $$

The angle between the state of the register and the $\ket{\text{good}}$ state will decrease with each iteration, resulting in a higher probability of measuring a valid result. To calculate this probability we just need to calculate $|\braket{\text{good}|\text{register}}|^2$. Denoting the angle between $\ket{\text{good}}$ and $\ket{\text{register}}$ $\gamma (k)$, where $k$ is the iteration count, we get:

$$\gamma (k) = \frac{\pi}{2}-\theta -k2\theta = \frac{\pi}{2} -(2k + 1) \theta $$

Therefore, the probability of success is:

$$P(\text{success}) = \cos^2(\gamma(k)) = \sin^2\left[(2k +1)\arccos \left( \sqrt{\frac{N-M}{N}}\right)\right]$$

Optimal number of iterations

As the probability of success can be written as a function of the number of iterations, we can find the optimal number of iterations $N_{\text{optimal}}$ by computing the smallest positive integer that (approximately) maximizes the success probability function.

We know that $\sin^2{x}$ reaches its first maximum for $x=\frac{\pi}{2}$, so we just need to make:

$$\frac{\pi}{2}=(2k_{\text{optimal}} +1)\arccos \left( \sqrt{\frac{N-M}{N}}\right)$$

This gives us:

$$k_{\text{optimal}} = \frac{\pi}{4\arccos\left(\sqrt{1-M/N}\right)}-1/2 = \frac{\pi}{4}\sqrt{\frac{N}{M}}-\frac{1}{2}-O\left(\sqrt\frac{M}{N}\right)$$

Where in the last step we used the fact that $\arccos \sqrt{1-x} = \sqrt{x} + O(x^{3/2})$.

Therefore we can pick $N_\text{optimal}$ to be $N_\text{optimal} = \left\lfloor \frac{\pi}{4}\sqrt{\frac{N}{M}}-\frac{1}{2} \right\rfloor$.

Complexity analysis

From the previous analysis, we know that we need $O\left(\sqrt{\frac{N}{M}}\right)$ queries of the oracle $O_f$ to find a valid item. However, can the algorithm be implemented efficiently in terms of time complexity? $O_0$ is based on computing Boolean operations on $n$ bits and is known to be implementable using $O(n)$ gates. We also have two layers of $n$ Hadamard gates. Both of these components thus require only $O(n)$ gates per iteration. Because $N=2^n$, we have that $O(n)=O(log(N))$. Therefore, if we need $O\left(\sqrt{\frac{N}{M}}\right)$ iterations and we need $O(log(N))$ gates per iteration, the total time complexity (without taking into account the oracle implementation) is $O\left(\sqrt{\frac{N}{M}}log(N)\right)$.

The overall complexity of the algorithm will ultimately depend on the complexity of the implementation of the oracle $O_f$. If a function evaluation is much more complicated on a quantum computer than on a classical one, the overall algorithm runtime will be longer in the quantum case, even though technically, it will use fewer queries.

References

If you want to continue learning about Grover's algorithm, you can check any of the following sources:

• Original paper by Lov K. Grover
• Quantum search algorithms section of Nielsen, M. A. & Chuang, I. L. (2010). Quantum Computation and Quantum Information.
• Grover's algorithm on Arxiv.org