Click here to Skip to main content
13,795,352 members
Click here to Skip to main content
Add your own
alternative version

Tagged as

Stats

12.8K views
7 bookmarked
Posted 2 Oct 2016
Licenced GPL3

Grover's Search Algorithm explained

, 2 Oct 2016
Rate this:
Please Sign up or sign in to vote.
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.

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

License

This article, along with any associated source code and files, is licensed under The GNU General Public License (GPLv3)

Share

About the Author

23ars
Engineer
Romania Romania
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.

You may also be interested in...

Comments and Discussions

 
-- There are no messages in this forum --
Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web06 | 2.8.181207.3 | Last Updated 2 Oct 2016
Article Copyright 2016 by 23ars
Everything else Copyright © CodeProject, 1999-2018
Layout: fixed | fluid