In 1996, Peter Shor published his paper on Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. At that instant, the topic of quantum computing suddenly rose to a whole new level.
The paper received a lot of interest from the community as prime factorization of large numbers was considered extremely difficult, and was therefore used as the basis for RSA cryptography.
At that time, however, there were no quantum computers in existence, at least not in the sense that we are familiar with.
It wasn’t until 1998 that a physical quantum computing machine could actually be demonstrated.
That system was a 2-qubit quantum computer and it was successfully used to demonstrate the Deutsch-Jozsa algorithm in action.
The Deutsch-Jozsa problem had very little practical use; its sole purpose is to provide an example of a problem that is easy to solve on a quantum computer but difficult to solve on a classical one.
Today, Google and IBM race towards quantum supremacy, a term coined by John Preskill, and which refers to achieving practical computational capabilities not possible on classical computers.
The below text is from IBM’s Q System One website; it shows how far quantum computing has traveled in the last couple of years:
Quantum Computing for Everyone
In 2016 we were the first company to put quantum computing on the cloud, and into the hands of hundreds of thousands of users. Today, anyone can access an expanded selection of quantum cloud services based on IBM Quantum System One technology, to conduct research and explore new problems on our systems.
But what is quantum computing? Can we put a number on how fast it is compared to classical machines?
In this article, we will use David Deutsch’s algorithm as our background to try and answer the following questions:
- How quantum computing works
- How quantum computers differ from their classical counterparts
- How a difficult problem can be solved efficiently using quantum computing
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
- 1. Overview
- 2. Table of Contents
- 3. How Quantum Computing Works
- 4. Quantum Solution to Deutsch’s Problem
- 5. Further Reading
- 6. Featured Articles
3. How Quantum Computing Works
3.1 Bits vs Qubits
One of the first results in the mathematics of computation […] was the distinction between computable and non-computable functions[…]. Central to this result is Church’s thesis, which says that all computing devices can be simulated by a Turing machine. This thesis greatly simplifies the study of computation, since it reduces the potential field of study from any of an infinite number of potential computing devices to Turing machines.
As you probably may know, a classical computer manipulates “bits” of data.
A bit is a discrete unit of information that allows you to answer a single question with a Yes or a No. A series of n bits allows you to answer n such questions.
A sequence of bits looks like this:
Or, using a generic notation:
A string of bits can represent any number as long as it has finite precision.
Quantum computers, on the other hand, use quantum bits (or qubits for short).
To understand the difference between a quantum bit and a classical bit, we will use the analogy of an electric switch.
In classical systems, the switch can be either ON or OFF. “Looking” at the switch any number of times does not alter its state.
Alternatively, in a quantum system, we need to think of the switch as residing in a closed box.
The box and its accompanying switch, at the time of creation, can be in one of the following three scenarios:
|Scenario||Switch State||Measurement Outcome|
|1||Pure ON||ON with Probability 1|
|2||Pure OFF||OFF with Probability 1|
|3||Superposition of ON and OFF||ON or OFF with probabilities p |
and (1 – p)
You probably noticed that Scenarios 1 and 2 are somehow trivial. Scenario 3, however, is particularly interesting.
In fact, in scenario 3, and before the box is opened, the switch is in a superposition of two states: both ON and OFF.
If we “look” inside the box, we will be performing a measurement. The measurement will instantly yield either ON or OFF in all three cases.
When we make a measurement, we are altering the state of the quantum system forever. The switch will now remain in the “pure” state, which is either ON or OFF.
This is a very subtle point.
You might wonder whether we model the quantum system in this way (as being in two states at the same time) because of our lack of knowledge of what’s inside the box. That is not true.
To understand why this is not the case, consider the following scenario.
If we create many identical quantum boxes, we would expect that if one of them is ON, the others will be the same. What happens though with quantum systems is quite different.
Every time we open one of those boxes, we will find the switch to be ON with probability p or OFF with probability (1 – p).
This leads us to conclude that the switch was, in fact, in a superposition of two states, ON and OFF, until the time of measurement.
We can now denote a single qubit as follows:
The probability of obtaining an OFF state is whereas we can observe an ON state with probability .
3.2 Quantum Computing with Multi-Qubit Systems
Now let us consider the case where we have two switches inside the box instead of one. Opening the box will give us one of the following states:
|State||Switch 1||Switch 2|
We can now denote that system as follows:
Again, the coefficients satisfy the following constraint so that the total probability does not exceed 1:
What this tells us is that a system of n classical bits can be fully described by n numbers whereas a quantum system requires .
The fact that a quantum computer can hold exponentially more information is one of the reasons why it is so powerful.
Simulating a Quantum Computer
On classical memory, a double floating-point number can be represented on 8 bytes. A 50 qubit system requires bytes or 1 Petabytes. To give you some context, a supercomputer at NASA can have 2,016 nodes with each node running 128GB of RAM for a total of 252TB, a quarter of what’s required to run a 50 qubit simulator!
That by itself however does not explain the power of quantum computing. The truth is: an analog bit that can take any value from 0 to 1 can be said to represent a superposition of the two states.
So what makes quantum computers and qubits so special?
We can observe three major differences at least between a classical analog bit and a qubit: superposition, measurement, and entanglement.
3.3 Quantum Superposition
The first major difference between a qubit and a classical analog bit with a value of 0.5 is that the latter is just that. No matter how many times you measure the analog bit, it will always show 0.5.
Now, consider a qubit in the following state:
Each time we measure , we have a 50% chance of observing 0 or 1. In fact, we will never observe 0.5.
Taking Advantage of Superposition
The power of quantum computing lies in its ability to take advantage of superposition. If we use a qubit in a superposition of two states as input into our quantum computer and perform a single computation on it, we will be processing both states in a single shot.
On a classical machine, each input will have to be processed separately.
This may not seem like much for one qubit but performance will scale significantly, although perhaps not exponentially for practical reasons which we will discuss in subsequent articles.
Is That All?
Superposition by itself does not tell the whole story. If you think about it, you will notice that running a measurement on a superposition of states will yield a random result for each measurement with probabilities defined by the amplitudes of each state. This is not very helpful. In fact, we need the system to produce the correct value. For this to happen, we need to make use of constructive interference, something we will discuss in greater detail in Part 2.
3.4 Quantum Measurements and Computation
The second difference between classical bits and qubits has to do with the measurement exercise.
Thus, looking at the machine during the computation will invalidate the rest of the computation.
Whenever we measure the value of a quantum system, we invalidate it. Scientists refer to a collapse of the wavefunction.
Going back to our analogy with the box and switch, we can state the following:
- Before we open the box for the first time, the switch can be either ON, OFF, or both OF and OFF
- Once the box is opened, the switch state will “collapse” to either an ON or an OFF state and will remain in that state forever
With classical bits, there is no distinction between the state of a bit before or after the measurement.
Using the box and switch analogy, consider the following experiment.
- Firstly, we make an identical set of boxes with one switch inside each.
- Secondly, we move those boxes far apart so that they cannot influence each other by the time they are opened, even if they exchange photons running at the speed of light.
- Finally, we run a measurement on each box.
The result is as follows: The two boxes (or quantum systems) are said to be entangled if the outcome of the measurements is perfectly correlated.
For example, if we measure the first qubit and find it to be ON, we will notice that the second qubit will always yield OFF.
Einstein was not happy with this phenomenon and referred to it as “spooky action on a distance“ since it seems to violate the Special Theory of Relativity, but experiments have now unequivocally confirmed it.
3.5 Classical Gates
Inputs and outputs from classical computers are typically strings of bits which are then grouped into bytes to make up the different data types that a computer can process.
The way these bits are manipulated is as follows.
Classical computers pass these bytes, 2 bits at a time, into a sequence of logical, also known as Boolean, gates. Each gate will perform a single Boolean operation such as AND, OR, XOR, or NOT.
Universality of Logical Gates
Computer science tells us that these gates are universal. What this means is that a whole sequence of such gates, applied in a specific order, would allow us to compute any function that we desire, such as addition, subtraction, or multiplication of two numbers.
For practical reasons though, we only use a Negative AND or NAND gate. A combination of NAND gates allows us to emulate all the other logical gates which, in turn, allows the implementation of every other function.
3.6 Computing with Quantum Gates
Quantum gates follow a similar logic. We have unitary gates that apply transformations to single qubits and binary gates that apply transformations to two bits at a time.
An example of a unitary gate is the Hadamard gate. It takes a or a , both of which are pure (or eigen-) states, and transforms them into a superposition of the two states.
This is crucial as it gives us the ability to design a multi-state, and therefore multi-input, qubit system that can be used to feed a quantum computer.
An equally important gate is the binary CNOT gate which allows us (in conjunction with the Hadamard gate) to entangle and disentangle two qubits.
The CNOT gate takes two inputs and and spits out two others. The first output is unchanged: .
The second qubit will be the result of XORing the two input qubits: .
3.7 Quantum Annealing
Another way that principles of quantum mechanics can be used to run quantum computations that can outperform classical computers is through quantum annealers.
These are different types of quantum computers that may not be as universal as those that use gates and that are the focus of this article.
Quantum annealers are designed to solve combinatorial optimization problems, the most popular of which is the Travelling Salesman Problem.
4. Quantum Solution to Deutsch’s Problem
Let’s put some of these concepts into practice and see what we get.
4.1 Problem Position
The best example for understanding how quantum computing works is probably Deutsch’s algorithm.
The Deutsch–Jozsa algorithm is a deterministic quantum algorithm proposed by David Deutsch and Richard Jozsa in 1992 with improvements by Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca in 1998. Although of little current practical use, it is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm.
The problem that Deutsch proposed was as follows: with a single evaluation, determine whether a unitary function is constant or balanced.
By definition, a constant function always returns a 0 or a 1, regardless of the value of x. The only two examples of constant functions that we know of are and .
Also by definition, a balanced function will return a value. The only two examples we can find are the Identity and the Negation functions.
Typically, you need to evaluate at least twice to find the solution. On quantum computers though, the Deutsch algorithm allows us to do that with a single evaluation.
4.2 Deutsch-Josza Algorithm
The following diagram describes Deutsch’s algorithm applied on a quantum computer.
We have already encountered the Hadamard gate (H), the measurement gate, and the CNOT gate but we have not talked about the f-CNOT gate.
In fact, the f-CNOT gate is just a modified version of the CNOT gate where x is replaced with f(x) before the XOR operation takes place.
It’s nothing more than applying f(x) to the input before applying CNOT.
4.2.1 Step 1: Preparing the Inputs
The first step is fairly simple. In it, we prepare two qubits in the ON state.
4.2.2 Step 2: Creating Quantum Superposition
In step two, we apply a Hadamard gate on each qubit to transform its state into a superposition of ON and OFF. This allows us to obtain an input variable with all four possible combinations of qubit states:
This is where the magic happens. The system in this state of superposition will allow us to perform all four evaluations at the same time.
4.2.3 Step 3: Evaluating f(x)
In this step, we look at the outcome of the operation that f-CNOT will perform on the input from Step 2. The result is as follows:
Let’s have a closer look at the first term . This, in fact, is the outcome of the transformation of .
Because the first qubit is 0, the CNOT gate will not flip the other one. Notice how that is not the case in the second term. Indeed the 0 has been flipped to 1.
To understand how this will help us solve our problem, we need to consider two cases. First is when is constant, the other is when is balanced.
With a little bit of elementary algebra, we can arrive at the two situations:
- If is constant, we obtain:
- On the other hand, if is balanced, we get:
But how does that help us determine the nature of ? The key to solving this problem lies in the first factor of both equations:
4.2.4 Step 4: Finding the Result
Taking a closer look at these two equations, you will probably recognize them as the outcomes of the Hadamard gate for inputs and although differing by a factor of .
We know that the Hadamard gate, if applied to the two inputs in superposition, will allow us to recover the original inputs and . And this is exactly what we will do.
If the outcome is , the function is balanced, otherwise it’s constant.
4.3 What Does Deutsch’s Algorithm Tell Us About Quantum Computing
We can look at Deutsch’s problem and its solution as an example of those problems which are exponentially more difficult to solve on classical computers but take only a few steps to resolve on quantum computers.
It also tells us that there is some effort that needs to be made to reformulate the problem in such a way that will allow us to take advantage of superposition or any other quantum phenomenon.
5. Further Reading
- Richard Feynman. QED: The Strange Theory of Light and Matter (book review)