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:

\[\begin{split}\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}\end{split}\]

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


Module for amplitude amplification, for use in algorithms such as Grover’s algorithm.

See G. Brassard, P. Hoyer, M. Mosca (2000) Quantum Amplitude Amplification and Estimation for more information.

grove.amplification.amplification.amplification_circuit(algorithm, oracle, qubits, num_iter, decompose_diffusion=False)

Returns a program that does num_iter rounds of amplification, given a measurement-less algorithm, an oracle, and a list of qubits to operate on.

Parameters:
  • algorithm (Program) – A program representing a measurement-less algorithm run on qubits.
  • oracle (Program) – An oracle maps any basis vector |psi> to either +|psi> or -|psi> depending on whether |psi> is in the desirable subspace or the undesirable subspace.
  • qubits (Sequence) – the qubits to operate on
  • num_iter (int) – number of iterations of amplifications to run
  • decompose_diffusion (bool) – If True, decompose the Grover diffusion gate into two qubit gates. If False, use a defgate to define the gate.
Returns:

The amplified algorithm.

Return type:

Program

grove.amplification.amplification.decomposed_diffusion_program(qubits)

Constructs the diffusion operator used in Grover’s Algorithm, acted on both sides by an a Hadamard gate on each qubit. Note that this means that the matrix representation of this operator is diag(1, -1, …, -1). In particular, this decomposes the diffusion operator, which is a \(2**{len(qubits)} imes2**{len(qubits)}\) sparse matrix, into

:math:`mathcal{O}(len(qubits)**2) single and two qubit gates.

See C. Lavor, L.R.U. Manssur, and R. Portugal (2003) Grover’s Algorithm: Quantum Database Search for more information.

Parameters:qubits – A list of ints corresponding to the qubits to operate on. The operator operates on bistrings of the form |qubits[0], ..., qubits[-1]>.
grove.amplification.amplification.diffusion_program(qubits)

grove.amplification.grover

Module for Grover’s algorithm.

class grove.amplification.grover.Grover

Bases: object

This class contains an implementation of Grover’s algorithm using pyQuil. See these notes
by Dave Bacon for more information.
find_bitstring(cxn, bitstring_map)

Runs Grover’s Algorithm to find the bitstring that is designated by bistring_map.

In particular, this will prepare an initial state in the uniform superposition over all bit- strings, an then use Grover’s Algorithm to pick out the desired bitstring.

Parameters:
  • cxn (QVMConnection) – the connection to the Rigetti cloud to run pyQuil programs.
  • bitstring_map (Dict[String, Int]) – a mapping from bitstrings to the phases that the oracle should impart on them. If the oracle should “look” for a bitstring, it should have a -1, otherwise it should have a 1.
Returns:

Returns the bitstring resulting from measurement after Grover’s Algorithm.

Return type:

str

static oracle_grover(oracle, qubits, num_iter=None)

Implementation of Grover’s Algorithm for a given oracle.

Parameters:
  • oracle (Program) – An oracle defined as a Program. It should send \(\ket{x}\) to \((-1)^{f(x)}\ket{x}\), where the range of f is {0, 1}.
  • qubits (list[int or Qubit]) – List of qubits for Grover’s Algorithm.
  • num_iter (int) – The number of iterations to repeat the algorithm for. The default is the integer closest to \(\frac{\pi}{4}\sqrt{N}\), where \(N\) is the size of the domain.
Returns:

A program corresponding to the desired instance of Grover’s Algorithm.

Return type:

Program

[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].