Coding Grover’s Algorithm in Qiskit
Quantum Approach to Search Algorithms
One of the biggest reasons quantum computing is such a popular technology is due to the way it redesigns our entire understanding of classical computing.
It fundamentally runs on the theories of quantum physics in contrast to the classical approach to modern computing.
This means that quantum computers open the doors to solving complex problems that classical computers could never dream of solving.
By redefining what we know about modern computing methods, we’re redefining the limits for the types of problems that we can solve and the ways in which we can solve them.
Search Algorithms — An Introduction
Famous problems regarding computing include searching through a list or database for a certain item.
This is used in every aspect of the internet — search queries for the web, machine learning pre-processing, web scraping, etc.
Sorted lists have various classical search algorithms such as the Binary Search Algorithm which searches through sorted lists to find a target value in O(log N) time.
Quick Review — The Big ‘O’ Notation
The Big ‘O’ Notation is a way that computer scientists are able to depict the efficiency of an algorithm. It describes the relationship between the time it takes for an algorithm to run based on different factors.
Suppose we’re working with data. I want to send a certain amount of data to my friend who lives 10 minutes away from me. I can either send it to him through the internet, or take a USB stick, physically walk over, and give it to him.
In the first situation where we’re sending it to him through the internet, the more data I have, the more time it’s going to take to send it over. This is a linear relationship and would be described as O(N).
However, in the second example, no matter how much data I have, walking over and giving him a USB stick isn’t going to take more or less time. It will always take 10 minutes, regardless of the amount of data on my USB stick. This would be modelled as O(1).
If you look at this graph, we can see compare different time complexities with the big O notation.
Back to Binary Search
Binary search is logarithmic, meaning that as the number of elements increases, the time complexity increases in a logarithmic fashion. That’s all that O(log(N)) is saying. This is generally really good for a search algorithm.
We’re not going to go too much into what binary search actually is, just know that we have good search algorithms that can be run on classical computers for sorted lists.
What about Unsorted Lists?
Unsorted lists work a little bit differently. There isn’t an efficient algorithm for them on classical computers.
In unsorted lists, classical algorithms go through each element and see if it matches the target element.
For example, if I have the following list of numbers: 1, 5, 6, 3, 6, 7, 8 — suppose I’ve created an algorithm to find the position of the 3 in this list. I would go through each element.
Is the first number ‘1’ = the target number ‘3’? Nope.
Is the second number ‘5’ = the target number ‘3’? Nope.
Is the third number ‘6’ = the target number ‘3’? Nope.
Is the fourth number ‘3’ = the target number ‘3’? Yes.
Ding ding ding! The fourth number in the list is the number ‘3’.
As we can see, this is incredibly inefficient. In our Big ‘O’ Notation, we can represent the algorithmic complexity as O(N) in our worst-case scenario. However, we only have to run our algorithm N/2 times on average since if the target number is found, we don’t need to iterate through the rest of the numbers.
In case you’re interested, this is how we would code an algorithm as such:
For smaller lists like 100 element or 200 element lists, classical computers can do this with ease. However, when you get to larger lists in the 100s of thousands or millions, this becomes a large issue.
If we want to iterate through a list that has 1 000 000 elements, on average we’d have to iterate through 50 000 elements and make a comparison between two values. In the worst-case scenario, we’d have to iterate through EVERY SINGLE ELEMENT!
However, quantum computing introduces an algorithm that drastically changes this. We can reduce O(N) to O(√N), a revolutionary change.
O(N) vs O(√N)
Let’s say we have a list with 100 elements. Classical computers would have to run their algorithm, in the worst-case scenario, 100 times. Quantum computers would have to run their algorithm 10 times in their worst-case scenario. This is a really minuscule difference when it comes to lists this small.
Let’s take this a notch up. Suppose we have a list with 1 000 000 elements. Classical computers would have to run their algorithm, in their worst-case scenario, 1 000 000 times.
Quantum computers would have to run their algorithm 1 000 times in their worst-case scenario.
That’s an INSANE decrease! This can all be done with one of the most popular quantum algorithms out there: Grover’s Algorithm.
Grover’s Algorithm — A Quantum Approach
In 1996, Lov Grover published a paper displaying the utilization of quantum techniques to significantly reduce the complexity of unsorted list searches, more specifically a technique known as Amplitude Amplification.
Before continuing, it’s going to help you to know some of the intuition and mathematics behind quantum computing (what’s a qubit, what’s a statevector, etc.). Check out my article on this here for a quick refresher.
What is an Amplitude?
As we know, qubits are essentially represented as probabilities. A qubit in a superposition has a certain probability of collapsing into either 0 or 1, and is made up of a combination of the two basis vectors |0 ⟩ and |1 ⟩.
This probability is modelled in quantum physics with something known as a wave function.
For the purposes of this article, it isn’t important to know much about this representation. That being said, it is important to know that when I use the word “Amplitude,” I’m referring to the amplitude of this wave function, which refers to probability in the case of quantum mechanics.
Amplitude Amplification — A Genius Application
Amplitude amplication refers to amplifying the probability or “amplitude” of getting a certain result within the wave function.
We can essentially increase the probability of a qubit collapsing into a specific superposition and decrease the probability of it collapsing into all other superpositions through amplitude amplification.
Essentially what we’re doing in Grover’s algorithm is using qubit combinations. For example, if we have two qubits, our possible combinations are: |00 ⟩, |01 ⟩, |10 ⟩, |11 ⟩
Suppose we’re trying to search for the |11 ⟩ state. What our algorithm does is amplify the probability of our qubits collapsing into this state and dramatically decrease the probability of our qubits collapsing into the other three states.
Geometric Interpretation of Grover’s Algorithm
Let’s go into the geometry of Amplitude Amplification and ignore the complicated mathematics that goes into it for now. Understanding what it’s doing is much more important than understanding the derivation of it in the scenario of Grover’s Algorithm.
First, we need to outline a few things. Suppose we have the same 2 qubits before with the four possible combinations |00 ⟩, |01 ⟩, |10 ⟩, |11 ⟩. What we’re attempting to achieve is for our qubits to always collapse on a specific qubit combination.
Step #1: Equal Superposition
Right now, if we were to randomly guess the index of what we’re searching for, all of our guesses have the same probability of being right: 1/4. The first step is to model this into a superposition.
|s ⟩ = 1/2 (|00 ⟩ + |01 ⟩ + |10 ⟩ + |11 ⟩)
This state |s ⟩ is essentially an equal superposition where we can either have |00 ⟩, |01 ⟩, |10 ⟩, |11 ⟩ with equal probabilities of 1/4 each.
Let’s suppose that the state that we want is |11 ⟩. We’re going to use the state |w ⟩ to denote our “winning state” |11 ⟩.
This is the geometric interpretation of the state |w ⟩ and the state |s ⟩.
Note that the state |s’ ⟩ is essentially a state perpendicular to the state |w ⟩. We get this state by taking the state |s ⟩ and removing the possibility of achieving the state |w ⟩ from it.
The way our amplitude amplification works is by applying to functions: an oracle, and a diffuser.
Step #2: Oracle Function
We need a way to mark our winning state |w ⟩. The way we do this is through an oracle function.
This function essentially gives a negative phase to the state that we want to mark. That might seem confusing at first but let’s interpret this geometrically.
Essentially what we’re doing is reflecting our statevector |s ⟩ about |s’ ⟩.
In our case, our oracle function would transform our statevector |s ⟩ into:
|s ⟩ = 1/2 (|00 ⟩ + |01 ⟩ + |10 ⟩ - |11 ⟩)
As we can see, the sign before |11 ⟩ changed to a negative sign. However, the actual amplitudes didn’t change. Utilizing the Born Rule, we know that the probability of measuring a certain state is calculated by taking the square of our amplitude (in this case -1/2) for all non-complex coefficients.
1/2 squared is the same as 1/2 squared — a quarter. This means that our probability still didn’t change. However, our state has been marked.
If we look above, we can see that there is an equal amplitude in the first picture. The second picture marks our state |w ⟩ by performing a phase flip, decreasing the average amplitude.
Step #3: Diffuser Function
Now, we’re going to apply a diffuser function. This is where the real amplification happens. This function essentially reflects are state |w ⟩ to amplify it. The performed reflection is 2|s ⟩⟨ s| - 1. We can geometrically interpret this as the following:
If we take a look here, our amplitude has been drastically amplified. However, it’s hasn’t entirely reached the state |w ⟩. That being said, the probability of collapsing onto the state|w ⟩ has now increased significantly over collapsing onto the state |s’ ⟩ (every state except for w).
We can repeat this process multiple times to continually increase the probability of collapsing onto the state |w ⟩.
If we repeat Steps #2 and #3 around √N times, we can recieve an accurate result, and ultimately succeed in achieving O(√N) unsorted search with Grover’s Algorithm.
Coding out Grover’s Algorithm — 2 Qubits
Now that we understand Grover’s Algorithm intuitively and geometrically, we can code it out! Before starting, feel free to check out the github repository for my code here. To code this out, we’re going to be using the Qiskit quantum computing library.
All we need to do to code out Grover’s Algorithm is:
- Step #1: Put all of our qubits into an equal superposition
- Step #2: Perform a phase flip on the state |w ⟩
- Step #3: Utilize the diffuser function for Amplitude Amplification
Let’s run through what we’re doing here.
We start by creating an oracle function. We want to apply a phase flip to the state |11 ⟩, our |w ⟩ phase. We use the cz or controlled-z gate to do so.
We then create our diffuser function that performs the 2|s ⟩⟨ s| - 1 reflection. For two qubits, we use the h, z, cz, and h gates in that order.
Then, we put everything together and create our circuit. We first apply a hadamard gate on all of our qubits which puts them into an equal superposition. We then apply our oracle function. Lastly, we apply our diffuser function.
After measuring our two qubits to two classical bits, we see that our result is always |11 ⟩, meaning that Grover’s Algorithm has succeeded!
Note that my code simulates the result as if it were running on a quantum computer. We can run our code on a quantum computer but our results would be less accurate due tot he phenomenon of quantum decoherence.
Coding out Grover’s Algorithm — 3 Qubits
Now that we know how to code Grover’s Algorithm on two quits, adding a 3rd qubit isn’t much harder.
Instead of only having 4 states: |00 ⟩, |01 ⟩, |10 ⟩, |11 ⟩ , we have 8 states: |000 ⟩, |001 ⟩, |010 ⟩, |100 ⟩, |011 ⟩, |110 ⟩, |101 ⟩, |111 ⟩.
In this scenario, the two states that we want to be marking are the |101 ⟩ states and the |110 ⟩ states. You can choose a different state, or only a single state. However, this combination is simpler so it’s convenient to show what we’er trying to do.
The process is the exact same. However, we may benefit from creating more generalized functions over specific functions.
In this code, we apply the cz gates twice to apply a phase flip on our two states and create our oracle function.
We also create a diffuser function that’s general and works for any amount of qubits. It looks a lot more complicated but it’s just doing the same intuitive reflection that we learn about before.
At the end, we finish the circuit and put all of our steps together. Our results resemble a close 50/50 split of the states |101 ⟩ and|110 ⟩, exactly what we intended.
If we turn this into a histogram, we get the following:
Remember that quantum mechanics is innately probabilistic, meaning that it won’t be exactly a 50–50 split.
Regardless, we’ve now officially created a circuit that can sort through unstructured lists in O(√N) utilizing Grover’s Algorithm!
If you liked this article, please check out my other articles here, or check out my article on Quantum Teleportation here.
Feel free to check out my other socials: LinkedIn, Twitter
Consider subscribing to my newsletter here! I talk a lot about my progress, experiences, and my struggles. My February issue just came out where I discuss my relationship with momentum, as well as its importance over motivation.
