Grover's Search Algorithm explained

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\):

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

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.

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

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

And the entire Grover iteration:

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:

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

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:

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

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

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);
}

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

	@Override
	public void init() {
	    //create gate object
	    gateH = gateFactory.getGate(EGateTypes.E_HadamardGate);
		//initialize resultQubit with QubitZero()
        resultQubit = QUBIT_0;
        //create |+> object
		qubitPlus = new QubitPlus();
        //entangle the resultQubit, 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());
		}
        //set the oracle
		setOracle(oracleMatrix);
        //generate diffusion matrix
		generateDiffusionMatrix();
	}

    @Override
	public void run() {
        //calculate the needed number of iterations
		int noOfIterations = (int) Math.sqrt(Math.pow(2, NO_OF_INPUT));
        //apply Hadamard gate
		resultQubit = QuantumOperations.applyGate(resultQubit, gateHn);
        //perform the Grover iterations
		for (int i = 0; i < noOfIterations + 1; i++) {
			resultQubit = QuantumOperations.applyGate(resultQubit, oracleMatrix);
			resultQubit = QuantumOperations.applyGate(resultQubit, diffusionMatrix);
		}
        //test if resulted qubit is valid
		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