## Introduction

In a previous article I talked about a Quantum Computing Library that I wrote and I presented, as an example, the implementation of Deutsch's Algorithm. In this article I will present the Grover's Search algorithm.

The algorithm formulated by Lov Grover in 1996 uses a feature of quantum interference in order to solve an extremely demanding task of searching the value of some parameter, at which a defined function returns certain results, over an unordered set of \(N=2^{n}\). The algorithm performs a search on a quantum computer in only \(O(\sqrt{N})\) operations, while the best classical algorithm for a search over unordered data requires O(N) time.

## Background

Grover's algorithm begins with a quantum register of *n* qubits, where *n* is the number of qubits necessary to represent the search space of \(2^{n}=N\), all initialized to \(|0\rangle\):

$\begin{equation} |0^{\otimes n}\rangle=|0\rangle \end{equation} $

The first step is to put the system into an equal superposition of states, achieved by applying the Hadamard transform \(H^{\otimes n}\):

$ \begin{equation} |\psi\rangle=H^{\otimes n}|0^{\otimes n}\rangle=\frac{1}{\sqrt{2^{n}}}\displaystyle\sum_{x=0}^{2^{n}-1}|x\rangle \end{equation} $

The next series of transformations is often referred to as the *Grover Iteration* and it will be repeated \(\frac{\pi}{4}{\sqrt{2^{n}}}\) times. A call to a quantum oracle *O*, a quantum black-box that can observe and modify the system without collapsing it to a classical state, represents the first step in the Grover iteration.

$ \begin{equation} |x\rangle\xrightarrow{O}(-1)^{f(x)}|x\rangle \end{equation} $

where \(f(x)=1\) if x is the correct state, and 0 otherwise.

The next part of the iteration is referred as the *diffusion transform* which performs *inversion about the average*, transforming the amplitude of each state. The diffusion transform consist of another application of the Hadamard transform \(H^{\otimes n}\), followed by a conditional phase shift that shifts every state except \(|0\rangle\) by -1, follower by another Hadamard transform.

The conditional phase shift can be represented by the unitary operator

$ \begin{equation} 2|0^{\otimes n}\rangle\langle 0^{\otimes n}|-I \end{equation} $

Given the entire diffusion transform, using the notation \(\psi\) from equation 2:

$ \begin{equation} H^{\otimes n}[2|0^{\otimes n}\rangle\langle 0^{\otimes n}|-I]H^{\otimes n}= 2H^{\otimes n}|0^{\otimes n}\rangle\langle 0^{\otimes n}|H^{\otimes n}-I= 2|\psi^{\otimes n}\rangle\langle\psi^{\otimes n}|-I \end{equation} $

And the entire Grover iteration:

$ \begin{equation} [2|\psi^{\otimes n}\rangle\langle\psi^{\otimes n}|-I]O \end{equation} $

### Example

Let's assume that there's a binary function from *n* binary arguments, which accepts the value of 1 at one of them only. It is required to find the value of input arguments for which f(x)=1.

So, let's consider the following task:

$ \begin{equation} f(x_1,x_2,x_3)=x_1\&x_2\&x_3 \end{equation} $

. This function accepts value of 1 only in one of the eight variants of input values, more exactly when

$ \begin{equation} x_1=x_2=x_3=1\Rightarrow f(x_1,x_2,x_3)=1 \end{equation} $

#### Algorithm's Steps

- Initial state \(|0^{\otimes n}\rangle\)
- Apply the Hadamard transform to all qubits:\(H^{\otimes n}|0^{\otimes n}\rangle\)
- Apply the Grover iteration 3 times
- Measure the register

#### Results

The following 8x8 matrix correspond to the table:

$ O= \begin{pmatrix} 1&0&0&0&0&0&0&0 \\ 0&1&0&0&0&0&0&0 \\ 0&0&1&0&0&0&0&0 \\ 0&0&0&1&0&0&0&0 \\ 0&0&0&0&1&0&0&0 \\ 0&0&0&0&0&1&0&0 \\ 0&0&0&0&0&0&1&0 \\ 0&0&0&0&0&0&0&-1 \end{pmatrix} $

Now that we have the oracle, let's calculate the diffusion matrix:

$ D=2|+^{\otimes n}\rangle\langle +^{\otimes n}|-I_n $

Finally, if we will apply the Grover iteration 3 times we will obtain:

$ |\psi\rangle= \begin{bmatrix} -0.309359 \\ -0.309359 \\ -0.309359 \\ -0.309359 \\ -0.309359 \\ -0.309359 \\ -0.309359 \\ 0.574524 \end{bmatrix} $

## Using the code

First of all, before starting implementing the steps from Grover's algorithm, we will define a method for creating the diffusion matrix:

private void generateDiffusionMatrix() {
diffusionMatrix = QuantumOperations.outerProduct(qubitPlus, qubitPlus);
diffusionMatrix = MatrixOperations.multiplyByConstant(diffusionMatrix, 2);
ComplexNumber[][] identityMatrix = MatrixOperations.generateIdentityMatrix(8);
diffusionMatrix = MatrixOperations.subtract(diffusionMatrix, identityMatrix);
}

The implementation will have 3 public methods:

- init()- will create the Hadamard Gate object, Qubit objects and set the initial state;
- run()- will perform the Grover iteration 3 times;
- measure()- will perform the measurement

@Override
public void init() {
gateH = gateFactory.getGate(EGateTypes.E_HadamardGate);
resultQubit = QUBIT_0;
qubitPlus = new QubitPlus();
for (int i = 0; i < NO_OF_INPUT - 1; i++) {
resultQubit = QuantumOperations.entangle(resultQubit, QUBIT_0);
}
for (int i = 0; i < NO_OF_INPUT - 1; i++) {
qubitPlus = QuantumOperations.entangle(qubitPlus, new QubitPlus());
}
gateHn = gateH.getUnitaryMatrix();
for (int i = 0; i < NO_OF_INPUT - 1; i++) {
gateHn = MatrixOperations.tensorProduct(gateHn, gateH.getUnitaryMatrix());
}
setOracle(oracleMatrix);
generateDiffusionMatrix();
}

@Override
public void run() {
int noOfIterations = (int) Math.sqrt(Math.pow(2, NO_OF_INPUT));
resultQubit = QuantumOperations.applyGate(resultQubit, gateHn);
for (int i = 0; i < noOfIterations + 1; i++) {
resultQubit = QuantumOperations.applyGate(resultQubit, oracleMatrix);
resultQubit = QuantumOperations.applyGate(resultQubit, diffusionMatrix);
}
assert (resultQubit.isValid() == true);
}

@Override
public void measure() {
MeasurementPerformer measurementPerformer = new MeasurementPerformer().configure(resultQubit);
resultQubit = measurementPerformer.measure();
}

After running Grover's Algorithm 1 million times, the next chart is obtained:

We can observe that the correct answer |111> was obtained in almost 350000 of 1 million runs.

## Points of Interest

I found interesting to simulate well-known quantum algorithms using my implementation of a Quantum Computing library. In this way I can add more features to it and also find some small bugs. Also, I think is a good way to understand Quantum Algorithms.

## Bibliography

*An Introduction to Quantum Algorithms,*Emma Strubell,Spring 2011

*Qubits, Quantum Mechanics and Computers*, Umesh V. Vazirani, Spring 2005

## History

- Added article
- Added license GPL3

I'm a software engineer and I have 3 years experience in software development. I worked for one year as Java Developer and now I'm working as embedded C software developer in automotive domain. I like a lot embedded software development and I'm passionate about Linux.