Quantum Computing: Achieving Superspeed Using Grover's Algorithm (with IBM Qiskit)

Modern computing is all about speed and efficiency. Computations and tasks are becoming faster and faster, and any breakthrough in this area can be very profitable with rich applications. At the forefront of this movement is quantum computing - a relatively new technology that can theoretically complete tasks much faster than traditional computers, giving it the potential to completely upheave modern computing. However, it is very much still in development. In this Instructables, we will go over the fundamentals of quantum computing and Grover's Algorithm, then build a simulation ourselves using IBM Qiskit.

Warning: There is some amount of math involved, mostly linear algebra. I'll try to keep the explanations as understandable as possible for everyone, though.

Most images in this Instructables are from Wikimedia Commons.

Install IBM Qiskit and Python on your computer. You will need to install the following libraries:

qiskit

qiskit_algorithms

matplotlib

using the pip install command.

Firstly, how does quantum computing differ from classical computers, and how it is able to achieve tasks much more efficiently? classical computers perform operations on bits, which take values of either 0 or 1. Quantum computers make use of superposition, a property of small particles that allows them to be in some distribution of distinct states at the same time.

This means quantum bits, or "qubits", can theoretically send more information and perform more operations than classical circuits in the same amount of time. The particle and property used can vary - photons and their polarization, electrons and their spin, and ions and their energy states.

Typically, the two states of a qubit are denoted |0> and |1>. (Systems of more qubits can be represented with additional digits, e.g. |0010011>.) A superposition of two states of a single qubit takes the form a|0> + b|1> for some complex numbers a and b with |a|^2 + |b|^2 = 1. (If you don't know what a complex number is, don't worry! We'll stick to real numbers in our examples.)

When measured, qubits collapse into a single state (denoted |0> or |1>). The probability that the qubit collapses into a given state is proportional to the square of the magnitude of the coefficient of that state in the superposition. For example, a qubit in the state 0.6 |0> + 0.8 |1> would collapse into the |0> state with probability 0.6^2 = 36% and into the |1> state with probability 0.8^2 = 64%.

TL;DR: Qubits are like classical bits, but can be partially "0" and partially "1" at the same time. They collapse to one state when measured, depending on the proportion of each state (the 0 state and the 1 state) in the superposition.

Quantum circuits use gates to act on qubits, similar to classical computers. Some gates are analogous to classical gates, such as the Pauli-X (NOT) gate and the controlled NOT (CNOT) gate, while other gates, such as the Pauli-Z (phase flip) and Pauli-Y (bit + phase flip), can only be applied to qubits.

By manipulating the state of a qubit using gates before the qubit is measured, scientists can increase the probability that the qubit will collapse to the desired state. Unlike classical circuits, quantum circuits will almost never have a deterministic results. However, as long as the circuit has an accuracy over 50%, the circuit can be run multiple times to improve accuracy. Plus, most modern qubit gates have accuracies over 99% as well.

TL;DR: Similar to classical computers, quantum circuits use gates to act on qubits.

A common task in computing is searching a list for a desired element. In other words, imagine there is a function F and a list of n elements. If you input the right element into F, you get an output of 1. If you input any other element, you get 0. How many tries does it take to get the correct answer?

Classical computers would have no choice but to try every element one by one. This means it would have a time complexity of O(N) (in other words, roughly proportional to the size of the list). The task would take N/2 steps on average.

TL;DR: It takes classical computers N/2 steps to search a database of N items, on average.

This is where qubits come in handy! Instead of just testing one element at time, we can test a superposition of multiple elements. This does first require us to create a new function U (called an 'oracle') that can transform our qubit.

Consider a simple case, in which we are searching a list of 4 elements. For the oracle, we will represent these 4 elements with the 2-qubit states |00>, |01>, |10>, and |11>. We can construct the oracle such that it multiplies the input by -1 if is correct and leaves it be otherwise. That is,

U|00> = -|00>

U|01> = |01>

U|10> = |10>

U|11> = |11>

However, we can also submit superpositions to this oracle. For example,

U (0.5|00> + 0.5|01> + 0.5|10> + 0.5|11>) = -0.5|00> + 0.5|01> + 0.5|10> + 0.5|11>

In general, if given a list of N items, we will need ceil(log_2(n)) qubits to represent them.

At this point, you might be wondering how this oracle can be constructed without already knowing the target state. After all, if we already know the target state well enough to construct the oracle, what's the point of Grover's algorithm? In fact, it is possible to construct the oracle without actually determining the target state - think of this as constructing a copy of a locked box without determining the shape of the key.

TL;DR: Grover's Algorithm starts by constructing an oracle that can accept superpositions as an input, essentially telling you how close the superposition is to the answer.

Grover's Algorithm begins by submitting an uniform superposition (an equal proportion of all possible states). We repeat the following process some number of times:

1. Apply the oracle function to our current qubit |s> to produce a new qubit U|s>.

2. Apply the "Grover diffusion operator" U_s to the qubit U|s>.

It turns out that it is optimal to apply around pi/4 sqrt(N) iterations.

TL;DR Grover's Algorithm requires you to apply two operations on a starting qubit some number of times, repeating until the superposition gets close to the desired answer.

Admittedly, that wasn't very helpful. However, there is a very nice geometric way to visualize this.

Let our target value (the "right answer") be |w>, and assume we have q qubits. We can interpret |w> as a vector in q-dimensional space. This vector is perpendicular to some (q-1)-dimensional subspace. For example, in 2D space, any given vector is perpendicular to some line (1D subspace) through the origin, and in 3D space, any given vector is perpendicular to some plane (2D subspace) through the origin.

Then, the oracle function can be geometrically interpreted as a reflection across the (q-1)-dimensional subspace. This is because the component perpendicular to the subspace (the |w>-component)) is multiplied by -1, and everything else is preserved. The "Grover diffusion operator" for some |s> can also be geometrically interpreted as a reflection across the vector |s>. That's right - all those scary mathematical names are just another way of saying "a reflection!"

The two-dimensional algorithm is visualized in the image. We start from some vector |s>. The target vector is |w> and the perpendicular space to the target vector is spanned by |s'>. We first apply the oracle function to reflect |s> over |s'>, becoming U_w|s>. Then we apply the Grover diffusion operator to U_w|s> to reflect it across |s>, becoming U_sU_w|s>.

Geometrically, this rotates our original vector towards the target vector U_|w> - and by applying this process the correct number of times, we can get a pretty accurate result!

TL;DR: Geometrically, the superpositions can be represented as vectors (points in N-dimensional space, where N is the number of items in the list). Grover's Algorithm continually rotates the superposition vector towards the desired vector, eventually becoming very close to the desired vector.

Let's see an example of this algorithm in action!

Assume we have to search an 8-item list. For example, the list {red, orange, yellow, green, blue, purple, black, white}. We have a function F that takes in some element of this list and returns 1 if it is the correct color and 0 otherwise.

Firstly, we want to encode color information with some number of qubits. Since each qubit can be in one of two states, we want 2 raised to the power of the number of qubits to be at least 8. This means 3 qubits is the perfect amount. So we can set

red = |000> = (1, 0, 0, 0, 0, 0, 0, 0)*

orange = |001> = (0, 1, 0, 0, 0, 0, 0, 0)

yellow = |010> = (0, 0, 1, 0, 0, 0, 0, 0)

green = |011> = (0, 0, 0, 1, 0, 0, 0, 0)

blue = |100> = (0, 0, 0, 0, 1, 0, 0, 0)

purple = |101> = (0, 0, 0, 0, 0, 1, 0, 0)

black = |110> = (0, 0, 0, 0, 0, 0, 1, 0)

white = |111> = (0, 0, 0, 0, 0, 0, 0, 1)

*these vectors would conventionally be represented as vertical vectors - not horizontal - but it doesn't really matter for this visualization.

We then create an oracle U, which multiplies the correct vector by -1 and leaves all others unchanged. Without loss of generality, assume the correct answer is white, or |111>.

We start by finding the uniform superposition.

|s> = <0.353, 0.353, 0.353, 0.353, 0.353, 0.353, 0.353, 0.353>

We also want to find the optimal number of iterations to apply, which is floor(pi/4 sqrt(N)) = 2.

We apply the oracle to the uniform superposition |s> to get U|s>.

|s> = <0.353, 0.353, 0.353, 0.353, 0.353, 0.353, 0.353, 0.353>

U|s> = <0.353, 0.353, 0.353, 0.353, 0.353, 0.353, 0.353, -0.353>

We then reflect U|s> back over |s> to get our new vector |s_1>.

|s_1> = <0.177, 0.177, 0.177, 0.177, 0.177, 0.177, 0.177, 0.884>

Our first iteration is done! As you can see, the component corresponding to the correct component has increased from 0.353 to 0.884. This means your chance of measuring correctly if you measured right now is 0.884^2 = 78%.

We now do another iteration:

|s_1> = <0.177, 0.177, 0.177, 0.177, 0.177, 0.177, 0.177, 0.884>

U|s_1> = <0.177, 0.177, 0.177, 0.177, 0.177, 0.177, 0.177, -0.884>

|s_2> = <-0.088, -0.088, -0.088, -0.088, -0.088, -0.088, -0.088, 0.972>

At this point, the probability of measuring correctly is 0.972^2 = 94.5%.

The optimal measurement is obtained after floor(pi sqrt(N)/4) steps, at which point the probability of measuring the correct answer is close to 100% for large N. Even in the worst case, the probability of success is greater than 50%.

This represents a quadratic speedup in comparison to traditional computing (in other words, the time needed is proportional to the square root of N rather than N, where N is the size of the list).

IBM Qiskit provides a helpful way to see how Grover's Algorithm works. A sample program is attached. This program requires qiskit, qiskit_algorithms, and matplotlib to be installed via pip.

This program runs Grover's Algorithm on the list 3-qubit states (of which there are 8 possibilities). Running the algorithm multiple times yields the correct result almost 100% of the time! (In the example graph given, the probability is over 95%.)

Sidenote: This program also allows you to search for multiple items at a time. For example, if you search for 2 items, you would expect to get each one 50% of the time.