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

Georges Lteif

Georges Lteif

Software Engineer

Last Updated on September 13, 2022.
Subscribe now to stay posted!
About Us
12 min read

1. Overview

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

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 a generous amount of accompanying explanations whenever these are present. In most cases, they are very simple and should not be difficult to comprehend.

2. Table of Contents

Agenda
  1. 1. Overview
  2. 2. Table of Contents
  3. 3. Leveraging Randomness in Quantum Computing
  4. 4. Quantum Algorithms Explained
  5. 5. The Current State of Quantum Computing
  6. 6. Further Reading
  7. 7. Featured Articles

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:

  1. Qubit superposition can be formed using the tensor product \otimes
  2. 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 in a random manner.

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

  1. Rule number one says that result has to be one of the pure quantum states s_i
  2. 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 here and go straight to the interesting stuff.

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

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

This table tells us 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:

  1. Interference can be observed not just with photons but with molecules of decent sizes
  2. 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, be it 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. Suppose 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

It is true that 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.

In the following subsections, we 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 go over some of the 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}

Its purpose is to take a pure quantum state and put 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}

To appreciate the strange nature of randomness in quantum mechanics, let’s compare a classical vs quantum experiment.

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. In fact, 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:

Hadamard Gate
Experiment 1

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.

Two Hadamard Gates
Experiment 2

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:

Experiment Result of Two Hadamard Gates

The application of 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:

  1. Make these “computers” bigger and more stable, and
  2. 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

Back to Articles
Home

Leave a Reply