Click here to Skip to main content
14,923,486 members
Articles / Programming Languages / Java
Posted 2 Oct 2016

Tagged as


7 bookmarked

Grover's Search Algorithm explained

Rate me:
Please Sign up or sign in to vote.
4.95/5 (8 votes)
2 Oct 2016GPL34 min read
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.


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.


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} $

Image 1


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} $

Image 2

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


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
	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
        //generate diffusion matrix
	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);
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:

Image 3

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.


An Introduction to Quantum Algorithms,Emma Strubell,Spring 2011

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


  • Added article
  • Added license GPL3


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


About the Author

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.

Comments and Discussions

QuestionI dont see how this can be usefull Pin
Member 1164031227-Jun-19 0:28
MemberMember 1164031227-Jun-19 0:28 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.