Implementation of Quantum Algorithm

As it’s time to say goodbye to my journey with PRACE, I would like to talk about my final days here and my experience with quantum algorithms. Quantum algorithms are algorithms that can be used in quantum computers.  We are interested in studying them because they can solve a problem faster than any classical algorithm. Several quantum algorithms have been developed now. Grover’s algorithm is one of them which is used to search in an unsorted list of numbers. Let’s see how it solves the search problem.

How does the algorithm work?

Without introducing any mathematical details, I can simply say that Grover’s algorithm works in two steps. Let’s say, you are looking for a number w, in a list of N numbers. To do so, the algorithm will first flip the phase of the w and then it will amplify the amplitude of the quantum state corresponding to w. The resulting effect would be a higher probability of getting w than the other numbers. More mathematical details are provided here. For now, let’s understand it graphically as in the picture below. As you see, in the second picture below, w has the highest amplitude. 

• 

• 

Now, to execute the algorithm, we need to build a quantum circuit. The two main sections of the circuit are the oracle and the diffuser. Oracle, executes the first step of Grover’s algorithm, and Diffuser, executes the second step.  Let’s see how we did it in our project. 

The final goal of my project

The goal of my project was to implement Grover’s algorithm to search for 13- a 4-bit number. In this case, our ‘full unsorted list’ is all the possible qubit states for 4 qubits, i.e., all the states |0000⟩, |0001⟩, ……, |1111⟩. Therefore, my task had to construct a circuit that implements both the oracle and diffuser in such a way that the state |1101> has the highest probability. After some effort, I was able to construct one.

You may notice the two mysterious boxes labeled as oracle and diffuser. How these are built or what’s inside them isn’t important for now. So, I’ll skip it and would rather turn your focus on something more interesting.  

Can we run a test on a quantum computer?

Current days, IBM is providing free access to several simulators and quantum computers. So, you literally have access to quantum computers! We run several tests with our circuit in the simulator and real quantum computer. The results are usually obtained in the form of a histogram which shows the probability of all possible outcomes. Here is what we obtained with qasm_simulator. 

As you probably can see state |1101> has more than 90% probability and that’s what we expected! While the simulators were working quite fine, the difficult part was the test with real quantum computers. We tried testing with several ones from IBM’s computing cloud and noticed that the results were affected by noise. However, It’s still an issue with today’s quantum computers. But we can surely hope for a better computing cloud in near future. 
 
I believe that you learned something from my blogs. Don’t hesitate to ask questions in the comments if you have any.  

Goodbye HPC!  

Goodbye and thanks to those who followed my posts.