Quantum Computing, Beyond Qubits – Part 2: Leveraging Nature’s Randomness

1. Overview

In the first part of this series, we went through the basics of quantum computing, mainly from a computer scientist’s perspective.

In the third instalment of this series, we will discuss quantum computers than can solve hard optimization problems through a process known as Quantum Annealing.

We talked about bits versus qubits and classical gates versus quantum gates. We completed the discussion with a simplified description of Deutsch’s quantum algorithm, which, I hope, gave the reader a feel of what quantum computing is about.

In the second part of this series, we would like to approach the subject of randomness in the quantum world.

This will lead us to explore two topics:

Classical vs Quantum Randomness — We will look at nature’s way of creating randomness in the subatomic world and how different that is from our day-to-day experience of random events.
Leveraging Quantum Randomness — Once we have that covered, we will move on to the next topic: how quantum computing leverages randomness to achieve quantum speedups for some problems.

But before we proceed, a word of caution:

Do Not Be Intimidated by the Equations!

We will keep the mathematical equations in this text to an absolute minimum. There will also be many accompanying explanations whenever these are present. They are usually very simple and should not be difficult to comprehend.

3. Leveraging Randomness in Quantum Computing

Given a sample space of all possible outcomes of a certain experiment:

$\Omega = \{A, B, C, \cdots \}$

3.1 Quantum Superposition

We discussed quantum superposition in Part 1 of this series in quite some detail, so we will not attempt to go over that again here.

What we will do, however, is try and see A) what the mathematical formulation of quantum superposition looks like and B) why superposition alone is not enough to achieve any speedups in our quantum computations.

Let’s start with the mathematical formulation.

In the canonical base, the qubit states can be written as follows:

$|0\rangle = \displaystyle{1\choose 0}, \quad |1\rangle = \displaystyle{0\choose 1}$

A superposition of two qubits, both in the zeroth state, can be written as:

$|00\rangle = \begin{pmatrix} 1 \\ 0 \end{pmatrix} \otimes \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \otimes \begin{pmatrix} 1 \\ 0 \end{pmatrix} \\ 0 \otimes \begin{pmatrix} 1 \\ 0 \end{pmatrix} \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}$

Take a second example, this time the state of $|10\rangle$ which we can compute as:

$|10\rangle = \begin{pmatrix} 0 \\ 1 \end{pmatrix} \otimes \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 0 \otimes \begin{pmatrix} 1 \\ 0 \end{pmatrix} \\ 1 \otimes \begin{pmatrix} 1 \\ 0 \end{pmatrix} \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix}$

Hopefully, the above two examples have successfully given you a feel of how:

Qubit superposition can be formed using the tensor product $\otimes$
The dimension of the vector in superposition grows exponentially (by powers of 2) as we add more qubits.

Now that we have the mathematical formulation in place, let’s move on to the next topic, how quantum superposition gets us halfway through achieving quantum computational speedup.

A system of n qubits can be put in a superposition of $2^n$ states. We write that as follows:

$S_n = \displaystyle\sum_{i=0}^{2^n-1} \alpha_i s_i$

Where $s_i$ is a pure quantum state:

$s_i = |\cdots 0010 \cdots \rangle$

And the amplitudes $\alpha_i$ being complex numbers that satisfy the following constraint:

$\displaystyle \sum_{i=0}^{2^n-1} |\alpha_i|^2 = 1$

After we prepare the system, we can perform quantum measurements on it. Every measurement will yield a different result randomly.

We do know, however, that the results are going to comply with two strict rules:

Rule number one says that the result has to be one of the pure quantum states $s_i$
The second rule decrees that the probability of observing $s_i$ is equal to the modulus of the amplitude $\alpha_i$ :

$Pr(s_i) = |\alpha_i|^2$

What Superposition Allows Us to Do?

Exponentially Large Spaces

Quantum superposition allows us to construct systems of qubits whose parameters (the $\alpha_i$ ) can inhabit an exponentially large vector space that scientists call Hilbert space. This is a massive improvement over classical systems that, although theoretically possible, is hopelessly impractical.

Quantum Circuits and Computations

Quantum circuits are composed of quantum gates (in some ways similar to logical Boolean gates) that allow us to apply unitary transformations to qubit systems. The computational speedup comes partially from the fact that those circuits can run simultaneously run computations on all the states that form the qubit system in superposition.

Is That All?

Running measurements on the input qubits as it is will give us a random result, which is not very useful when running quantum computing algorithms. What we need is to increase the amplitude, and therefore the probability, of obtaining the correct answer. To achieve this, we need to use quantum interference.

3.3 Quantum Interference

A typical introduction to quantum interference would be to look at the double-slit experiment.

This experiment has been told and retold many times, so we will skip the basics and go straight to the interesting stuff.

But before we do that, let’s look at a comparison table between classical and quantum randomness regarding the Kolmogorov axioms.

Axiom	Classical	Quantum
1	Probabilities are positive real numbers.	Amplitudes are complex numbers. Probabilities are calculated as modulus of amplitudes.
2	The probability of at least one event happening is 1.	No deviation from classical experience.
3	The probabilities of exclusive events add up.	Probabilities of exclusive events can experience constructive or destructive interference.

Classical vs Quantum Randomness

This table shows that quantum systems can experience constructive or destructive interference because the amplitudes are complex numbers.

Let’s see how that works by looking at the double-slit experiment more closely.

double slit experiment quantum superposition computing — Quantum Interference

To fully appreciate the weirdness of quantum phenomena, particularly interference, we need to keep two things in mind:

Interference can be observed not just with photons but with molecules of decent sizes
Interference will also happen even when we fire particles towards the screen, one at a time

To understand where this phenomenon comes from, let’s look at the quantum state of the particle hitting the screen at position x.

Simply put, we can write this state as a superposition of two states, each representing one path the particle could use to travel from the emitter to the detector:

$\Psi(x) = \Psi_A(x) + \Psi_B(x)$

If this was a classical experiment, we could make the following argument:

The probability that the particle hits the screen at position x = Probability of the particle going through A towards x + Probability of going through B and hitting x as well.

We would have something like this:

$Pr(x) = p_A + p_B = |\Psi_A(x)|^2 + |\Psi_B(x)|^2$

Experiments have confirmed, however, that this model does not make correct predictions.

If we go one step back and look at the wavefunction of the quantum mechanical object and try to calculate the probability from that function, we obtain the following:

$Pr(x) = |\Psi(x)|^2 = |\Psi_A(x) + \Psi_B(x)|^2$

This happens to lead us to the following result:

$Pr(x) = |\Psi_A(x)|^2 + |\Psi_B(x)|^2 + \Psi_A^* \Psi_B + \Psi_A \Psi_B^*$

We can also write the wavefunctions as functions of complex numbers:

$\Psi_A(x) = p_A \cdot e^{i\theta_A}$

And:

$\Psi_B(x) = p_B \cdot e^{i\theta_B}$

Which, after some elementary algebra, would lead us to:

$Pr(x) = p_A + p_B + 2\ p_A\ p_B \cos(\theta_A-\theta_B)$

The term $2\ p_A\ p_B \cos(\theta_A-\theta_B)$ can be positive, negative, or zero and the result could be an increase or a decrease in the overall probability.

In the first case, the interference is said to be constructive as it magnifies the probability amplitude of the particle hitting x.

In the second case, the interference is said to be destructive because it reduces that same probability amplitude.

This interference, constructive or destructive, depends on the phase difference between the two paths or $\cos(\theta_A-\theta_B)$ . This is a crucial point we will revisit over and over during this discussion.

Quantum Circuits Revisited

Now that we understand interference, how do we design a quantum circuit that amplifies the amplitude of obtaining the correct answer so that the chance of observing it is a bit more than 50%? That’s what quantum algorithms are all about.

Is 51% Good Enough?

Yes. The probability of obtaining the correct result in a quantum computing exercise is slightly above 50%. In that case, we can repeat the experiment as much as we like, take a majority vote, and select the winning answer. Naturally, the higher the probability, the fewer trials we need to perform and the sooner we can get an answer.

4. Quantum Algorithms Explained

Indeed, quantum computing will not be available on your PC anytime soon. However, we are lucky enough to live in a day and age where anybody with access to the internet can run a quantum algorithm on a REAL quantum computer.

All you need to do is visit the IBM Quantum Composer website, go through a few basic tutorials, and you are good to go, provided that you understand the basics of quantum computation.

The following subsections will look at different elementary quantum circuits to understand how quantum algorithms can be constructed and run.

4.1 Quantum Circuits and Algorithms

In Part 1 of this series, we introduced the idea of quantum gates by comparing them to their classical counterparts.

In this article, we will look at one example that will help us understand how quantum gates can be assembled in such a way to form a problem-solving, quantum computing machine.

We will show how the resulting quantum circuit leverages randomness to achieve quantum computational speedups.

At its most basic form, a quantum circuit would look like this:

quantum circuit computing deutsch josza — Basic Quantum Circuit

The ultimate purpose of such an algorithm is to query a certain function $f(x)$ for the correct result, say locating its zero.

The function is usually a black-box type referred to as an Oracle. This problem has the nice property of having a solution that is hard to find but easy to verify.

To understand how quantum algorithms can easily solve this problem (find the solution), let’s look at each step and see if we can understand what’s happening.

First, we start with one qubit in state $|0\rangle$ . Easy. This qubit will store our result.

Next, we place the qubit in a superposition state of $|0\rangle$ and $|1\rangle$ . This will allow us to compute the result of the function we are querying for both inputs simultaneously.

The third and most crucial step is the phase query. This is where quantum interference works its magic to magnify the amplitude of the correct result. We will talk about that in detail in the following sections.

We reapply a Hadamard gate in the fourth step to eliminate quantum superposition. At this stage, we should have a higher chance of observing the correct result since its amplitude was magnified in the prior step.

Finally, we measure the result.

Now that we (hopefully!) got the big picture, let’s review some interesting details.

4.2 Superposition and Hadamard Gates

The Hadamard gate is a unitary transformation that applies the following operation to single qubits.

$H = \dfrac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$

It aims to put a pure quantum state in a superposition. When applied to the $|0\rangle$ and $|1\rangle$ states, we obtain the following:

$|-\rangle = H|0\rangle = \dfrac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \dfrac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ 1 \end{pmatrix}$

And:

$|+\rangle = H|1\rangle = \dfrac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix} = \dfrac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ -1 \end{pmatrix}$

Let’s compare a classical vs quantum experiment to appreciate the strange nature of randomness in quantum mechanics.

In the classical world, if you flip a coin once, you have a 50/50 chance of getting heads or tails. If you flip it twice, the odds remain the same, 50% each.

In the quantum world, however, things are quite different. If you start with qubit in state $|0\rangle$ , apply a Hadamard gate and perform a measurement, you get 50% chance of measuring $|0\rangle$ and 50% chance of $|1\rangle$ .

Let’s try that on IBM Quantum Composer:

The result is somewhere around 50% each:

quantum circuit hadamard gate — Experiment Result of Single Hadamard Gate

Now let’s change the experiment slightly by adding another Hadamard gate.

Reasoning in a classical manner, We expect to see a uniform distribution of results between 0 and 1, just like in the first case. But that’s not what happens, have a look:

Applying two gates sequentially has eliminated the randomness to provide a definite outcome!

We can verify this by applying the Hadamard twice on the same input, which results in the identity matrix:

$H \cdot H = I$

That’s not surprising, though, as these properties (unitarity and reversibility) are both requirements for building quantum gates.

4.3 Interference and Phase Query Gates

Phase query gates can be defined by the following function:

$Q_f = (-1)^{f(x)}$

When applied to an input state $|x\rangle$ , we get the following:

$Q_f|x\rangle = (-1)^{f(x)}|x\rangle$

Given that $f(x) \in [0,1]$ , the result is always either $|x\rangle$ or $-|x\rangle$ , with the difference being only in the phase.

Why Is the Difference Only in the Phase?

Remember that $\exp(i\pi) = -1$ . This means that the probability of observing $|x\rangle$ or $-|x\rangle$ are the same since the amplitude of $|-1| = |\exp(i\pi)| = 1$

Now let’s see how that works to amplify one result over another. For this trick to work, the input to the Oracle must be in a superposition of the two pure states, but that’s exactly what we would have done in a prior step by passing the qubit through the Hadamard gate!

The result should now look like this:

$\begin{aligned} Q_fH|0\rangle &= Q_f (\dfrac{1}{\sqrt{2}}(|0\rangle + |1\rangle)) \\ &= \dfrac{1}{\sqrt{2}}((-1)^{f(0)}|0\rangle + (-1)^{f(1)}|1\rangle)) \end{aligned}$

Looking back at the Deutsch-Josza problem, we see that when $f(0) = f(1)$ , the computation would yield:

$Q_fH|0\rangle = \dfrac{(-1)^{f(0)}}{\sqrt{2}}(|0\rangle + |1\rangle))$

After applying another Hadamard gate, will yield $|0\rangle$ .

If, however, $f(0) = \bar{f(1)}$ , the computation would then yield:

$Q_fH|0\rangle = \dfrac{(-1)^{f(0)}}{\sqrt{2}}(|0\rangle - |1\rangle))$

Once more, after applying another Hadamard gate, it will yield $|1\rangle$ .

5. The Current State of Quantum Computing

It is interesting to see how quantum computing radically differs from its classical counterpart.

It would not be an exaggeration to place the current state of quantum computing in a similar position to classical computing in the 1950s.

Scientists are still trying to figure out how to:

Make these “computers” bigger and more stable, and
What sort of algorithms would benefit from performance improvements on quantum computers?

It is fascinating to be living in such a time to witness the birth of new, cutting-edge technology.

6. Further Reading

Richard Feynman. QED: The Strange Theory of Light and Matter (book review)