# 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 solvingcomplex problemsthat classical computers could neverdreamof 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 algorithm1 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 anaccurate result, and ultimately succeed in achievingO(√N)unsorted search withGrover’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 codesimulates the resultas if it were running on aquantum computer. We can run our code on a quantum computer but our results would be less accurate due tot he phenomenon ofquantum 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.