Skip to content

Latest commit

 

History

History
126 lines (96 loc) · 5.87 KB

grover.rst

File metadata and controls

126 lines (96 loc) · 5.87 KB

Grover's Search Algorithm and Amplitude Amplification

Overview

This module implements Grover's Search Algorithm, and the more general Amplitude Amplification Algorithm. Grover's Algorithm solves the following problem:

Given a collection of basis states {\ket{y}_i}, and a quantum circuit U_w that performs the following:

U_w: \ket{x}\ket{q} \to \ket{x}\ket{q\oplus f(x)}

where f(x)=1 iff \ket{x}\in\{\ket{y}_i\}, construct a quantum circuit that when given the uniform superposition \ket{s} = \frac{1}{\sqrt{N}}\sum\limits^{N-1}_{i=0}\ket{x_i} as input, produces a state \ket{s'} that, when measured, produces a state \{y_i\} with probability near one.

As an example, take U_w: \ket{x}\ket{q} \to \ket{x}\ket{q\oplus (x\cdot\vec{1})}, where vec{1} is the vector of ones with the same dimension as ket{x}. In this case, f(x)=1 iff x=1, and so starting with the state \ket{s} we hope end up with a state \ket{\psi} such that \braket{\psi}{\vec{1}}\approx1. In this example, \{y_i\}=\{\vec{1}\}.

Algorithm and Details

Grover's Algorithm requires an oracle U_w, that performs the mapping as described above, with f:\{0,1\}^n\to\{0,1\}^n, and \ket{q} a single ancilla qubit. We see that if we prepare the ancilla qubit \ket{q} in the state \ket{-} = \frac{1}{\sqrt{2}}(\ket{0} - \ket{1}) then U_w takes on a particularly useful action on our qubits:

U_w: \ket{x}\ket{-}\to\frac{1}{\sqrt{2}}\ket{x}(\ket{0\oplus f(x)} - \ket{1\oplus f(x)})

If f(x)=0, then the ancilla qubit is left unchanged, however if f(x)=1 we see that the ancilla picks up a phase factor of -1. Thus, when used in conjunction with the ancilla qubit, we may write the action of the oracle circuit on the data qubits \ket{x} as:

U_w: \ket{x}\to(-1)^{f(x)}\ket{x}

The other gate of note in Grover's Algorithm is the Diffusion operator. This operator is defined as:

\mathcal{D} :=
\begin{bmatrix}
\frac{2}{N} - 1 & \frac{2}{N} & \dots &  \frac{2}{N} \\
\frac{2}{N}\\
\vdots          &             & \ddots \\
\frac{2}{N}     &             &       &  \frac{2}{N} - 1
\end{bmatrix}

This operator takes on its name from its similarity to a discretized version of the diffusion equation, which provided motivation for Grover [2]. The diffusion equation is given by \frac{\partial\rho(t)}{\partial t} = \nabla\cdot\nabla\rho(t), where \rho is a density diffusing through space. We can discretize this process, as is described in [2], by considering N vertices on a complete graph, each of which can diffuse to N-1 other vertices in each time step. By considering this process, one arrives at an equation of the form \psi(t + \Delta t) = \mathcal{D}'\psi where \mathcal{D}' has a form similar to \mathcal{D}. One might note that the diffusion equation is the same as the Schruodinger equation, up to a missing i, and in many ways it describes the diffusion of the probability amplitude of a quantum state, but with slightly different properties. From this analogy one might be led to explore how this diffusion process can be taken advantage of in a computational setting.

One property that \mathcal{D} has is that it inverts the amplitudes of an input state about their mean. Thus, one way of viewing Grover's Algorithm is as follows. First, we flip the amplitude of the desired state(s) with U_w, then invert the amplitudes about their mean, which will result in the amplitude of the desired state being slightly larger than all the other amplitudes. Iterating this process will eventually result in the desired state having a significantly larger amplitude. As short example by analogy, consider the vector of all ones, [1, 1, ..., 1]. Suppose we want to apply a transformation that increases the value of the second input, and supresses all other inputs. We can first flip the sign to yield [1, -1, 1, ..., 1] Then, if there are a large number of entries we see that the mean will be rougly one. Thus inverting the entries about the mean will yield, approximately, [-1, 3, -1, ..., -1]. Thus we see that this procedure, after one iteration, significantly increases the amplitude of the desired index with respect to the other indices. See [2] for more.

Given these definitions we can now describe Grover's Algorithm:

Input:
n + 1 qubits
Algorithm:
  1. Initialize them to the state \ket{s}\ket{-}.
  2. Apply the oracle U_w to the qubits, yielding \sum\limits^{N-1}_{0}(-1)^{f(x)}\ket{x}\ket{-}, where N = 2^n
  3. Apply the n-fold Hadamard gate H^{\otimes n} to \ket{x}
  4. Apply \mathcal{D}
  5. Apply H^{\otimes n} to \ket{x}

It can be shown [1] that if this process is iterated for \mathcal{O}(\sqrt{N}) iterations, a measurement of \ket{x} will result in one of \{y_i\} with probability near one.

Source Code Docs

Here you can find documentation for the different submodules in amplification. grove.amplification.amplification

.. automodule:: grove.amplification.amplification
    :members:
    :undoc-members:
    :show-inheritance:

grove.amplification.grover

.. automodule:: grove.amplification.grover
    :members:
    :undoc-members:
    :show-inheritance:
[1]Nielsen, M.A. and Chuang, I.L. Quantum computation and quantum information. Cambridge University Press, 2000. Chapter 6.
[2](1, 2, 3) Lov K. Grover: “A fast quantum mechanical algorithm for database search”, 1996; [http://arxiv.org/abs/quant-ph/9605043 arXiv:quant-ph/9605043].