“I think I can safely say that nobody understands quantum mechanics” — Richard Feynman
Quantum Computing has always been an enticing topic amongst tech writers and journalists. Its promises to the world of computing — and its difficulty — have enabled the area of research to gain an almost mystical reputation. All too often, articles and infographics surrounding the subject give high praise to its apparent potential while skimming over how such a system works in practice. This tends to misinform all but the most avid of readers.
Pop-science explanations will commonly skip over the intricacies of quantum systems, with statements such as:
While a traditional bit can be a ‘1’ or ‘0’, a quantum bit can be both a ‘1’ and ‘0’ at the same time.
Or, if you’re more lucky (but still unsure):
A quantum bit exists in a superposition of ‘1’ and ‘0’.
The reason that none of these explanations seem to ring true is that we are trying model quantum phenomena in a language that was developed in a very classical world. To explain quantum computing adequately, we need to adopt a new language, the language of mathematics.
In this guide, I will introduce the mathematics needed to model and understand quantum computing systems, how to represent and run quantum logic and demonstrate an example of a quantum algorithm, and show how it outperforms a traditional computer.
I’ll try to explain the topics to the best of my ability, but it would help for anyone reading this to understand the basics of linear algebra and digital logic. (You can learn about linear algebra here, and digital logic here).
Lets start with a quick recap of digital logic. Digital logic is based around the manipulation of electricity in circuits to make calculations. For the sake of abstraction, we simplify the state of a wire carrying electricity with a state of ‘1’ or ‘0’, representing ‘on’ or ‘off’. By arranging transistors in specific patterns, we can create ‘Logic gates’, which take one or more inputs, and produce an output depending on a specific set of boolean logic.
Common logic gates and their corresponding truth tables.
By chaining these basic gates together, we can create more complicated gates, and by chaining more complicated gates together, we can eventually end up with a CPU through enough abstraction.
As stated previously, we’re going to need a way of representing digital logic mathematically, and we’ll start by describing traditional logic as such. With linear algebra, you can represent the classical bits ‘1’ and ‘0’ as 2x1 column vectors as
With the figure on the left being the dirac notation of the vector. By representing our bits as such, we can model logical operations on a bit by using vector transformations. Note that while there are many operations you can do on two bits with logic gates (AND, NOT, XOR etc…), there are only four operations you can do on a single bit: identity, negation, constant 0 and constant 1. Identity leaves the bit unchanged, negation flips the bit (sets 0 to 1 or 1 to 0), and constant-1 and 0 set the bit to 1 or zero regardless of what it was originally.
Given our new representation of a bit, you can see that it’s now quite simple to perform operations on this bit by performing vector transformations on it.
Before moving on, we’ll need to cover a topic known as reversible computing. This simply means that for an operation or logic gate to be reversible, you must be able to determine the set of inputs used, given the output and the name of the operation used. From this, you can probably tell that the Identity and Negation operations are reversible, while the constant-1 and 0 operations are not. Owing to the unitarity property of quantum mechanics, quantum computers only ever use reversible operations, and so we will solely focus on these. Later on, we will be converting non-reversible gates to reversible ones to make them possible to use in a quantum computer.
You can represent multiple bits at a time by using the tensor product of each bit together.
Now that we’ve got most of the maths we need, we’ll introduce our first quantum logic gate. This operator is called a CNOT, or controlled NOT gate and is very important to reversible and quantum computing. A CNOT gate works on a pair of bits and returns a pair of bits. The first bit is designated the ‘control’ bit, and the other the ‘target’ bit. If the control bit is 1, the target bit is flipped, and if the control bit is 0, the target bit is left unchanged.
This operator can be represented with the following transformation vector:
To demonstrate what we’ve covered so far, this is how we would use a CNOT gate on multiple bits:
To summarise everything up until this point, in the first example we expand |10⟩ into its tensor product, apply the CNOT matrix to get a new resulting product state, then we factor it out to get a result of |11⟩, as we would expect from the CNOT table that was shown before.
Now that we’ve covered all the maths needed to understand traditional computing and bits, we can start to discuss actual quantum computing and quantum bits.
If you’ve gotten this far, you’ll be suprised to know that qbits are actually very easy to express mathematically. Essentially, while a cbit (classical bit) is either a |1⟩ or |0⟩, a qbit simply exists in a superposition of both |0⟩ and |1⟩ before it is measured. After it is measured, it collapses to either a |0⟩ or |1⟩. More formally, a qbit is represented as a linear combination of both |0⟩ and |1⟩ with the following definition:
a₀ and a₁ are the amplitudes of |0⟩ and |1⟩ respectively. These can be thought of as “quantum probabilities” that represent the chance that a qbit will collapse into either state when it is measured because in quantum mechanics an object in superposition will collapse into a into a single state when it is observed. We can expand this expression and express it as such:
For the sake of simplicity we will be using this notation for the duration of this article.
For this qbit, when it is measured, its chance of collapsing with a value of a₀ is |a₀|², and its chance of collapsing to a value of a₁ is |a₁|². For example, the following qbit:
has a chance of |1/ √2|² , or 1/2 chance of collapsing into a 1, making it a 50/50 chance.
As the probabilities of a classical system must sum to 1 in order to form a complete probability distribution, it follows that the squares of the absolute values of the amplitudes of |0⟩ and |1⟩ must also add up to 1. From this, we can form the following equation:
Those adept at trigonometry will realise that as this follows Pythagoras’ theorem (a²+b²=c²), and so we can graphically represent the possible states of a qbit as a point on the unit circle as such:
Logical operators and gates on qbits work exactly the same as with cbits, through matrix transformations. All of the reversible matrix operators we’ve covered up until this point such as CNOT also work on qbits. These matrix operators have the effect of manipulating each of the amplitudes of a qbit without measuring and collapsing it. For example, here is a negation operator on a qbit:
Before we move on, it’s worth noting that the values of the amplitudes of a₀ and a₁ are really complex numbers, and so the state of a qbit can be more accurately represented as a 3d unit sphere, also known as a bloch sphere:
However for the sake of simplicity, we will be sticking to real numbers in this guide.
Now, we can start discussing some logical gates that only make sense in a quantum context.
One of the most important operators is the ‘Hadamard gate’. A Hadamard gate takes a bit in a 0 or 1 state, and puts it into an exactly equal superposition, with a 50% chance of collapsing into a 1 or 0 when measured.
Note that the bottom-right cell of the Hadamard operator is negated. This is so that the output of the operator is different depending on whether the input was a |1⟩ or a |0⟩, making the calculation reversible.
One other important aspect of a Hadamard gate is that is reversible, so it can take a qbit in an exactly equal superposition and transform it into a |0⟩ or |1⟩.
This is incredibly important, as it allows us to transition out of a quantum state without measuring — and collapsing — the state of a qbit. This allows for us to structure quantum computations deterministically, rather than probabilistically.
Quantum operators containing only real numbers are their own inverse, and so we can represent an operator’s effect on a qbit as a transformation around the unit circle as a state machine as depicted:
Which means that for a qbit with a state shown in the diagram above, after performing a Hadamard operation on it, it will be transformed to the state pointed to by its corresponding arrow. Similarly, we can construct another state-machine to represent the transformations done on a qbit by a negation operator which was shown previously (also known as a Pauli-X gate, or bit-flip) as follows:
To perform more complicated operations on our qbit, we can chain multiple operators together, or use gates multiple times. We can represent an example of a series of transformations using Quantum circuit notation as follows:
This means that if we start with a |0⟩ bit, apply a bit-flip, followed by a Hadamard gate, another bit-flip, another Hadamard gate, and a final bit-flip, you end up with the resulting vector on the right of the circuit. By overlaying each state machine atop of each other, you can start at |0⟩ and follow the coloured arrows corresponding to each transformation to see how this works.
As we’ve gotten this far, we can now look at the subset of a quantum algorithm known as the Deutsch-Jozsa algorithm and demonstrate how it can clearly outperform a classical computer. One interesting note about the Deutsch-Jozsa algorithm is that it is completely deterministic, meaning that it will return the right answer 100% of the time, as opposed to many other quantum algorithms that rely on probabilistic measurements of qbits.
Imagine that you were given a black box that contains a function/operator on one bit (Remember the four possible operators on a bit: Identity, negation, constant-0 and constant-1). You don’t know which function is inside the box. However, you can try as many inputs as you’d like and see the corresponding outputs.
How many inputs and outputs would you have to run through the black box to figure out which function is being used? Try to consider this for a second.
On a classical computer, it will take two queries to figure out which function is being applied. For example, if an input of ‘1’ returns ‘0’, you know that it’s either a constant-0 function, or a negation function, and so you’ll have to run an input of ‘0’ as well to see if the output changes.
On a quantum computer, this will also take two queries to determine. This is because you still need two different outputs to determine precisely which function is being applied to the input. However, if you were to rephrase the question slightly, quantum computers will have a significant advantage. If you instead only want to know whether the function is constant or variable, then quantum computers have the upper hand.
The function in the box is variable if different inputs produce different outputs (i.e, Identity and bit-flip), and it is constant if the output is fixed, regardless of the input (i.e, Constant-1 and Constant-0).
By using a quantum algorithm, you will be able to figure out whether the function in the black box is constant or variable by only using one query. But before we can dive into how this works, we need a way to define how each of these functions would be structured on a quantum computer. Owing to how all quantum operators must be reversible, we run into an immediate problem with the constant-1 and 0 functions as they are not reversible.
In quantum computing, the commonly used solution for this is to add an additional output qbit that returns whatever input was given to the function.
From this, we can can determine the inputs just from knowing the outputs, making the function reversible. Because of the structure of quantum circuits, we also need an additional input bit. For the purposes of the design of our operators, we will assume that this additional input qbit will always be |0⟩.
Using the same Quantum circuit notation that was introduced earlier, lets go through how we would design each of the four gates (identity, negation, constant-0 and constant-1) with quantum operators.
Here is how you would design the constant-0 function:
We don’t need to use any operators at all. The first input qbit (which we assume is always |0⟩) is returned, and the second input returns itself, as always.
The constant-1 function is slightly different:
Because we assume the first input qbit to always be set to |0⟩, using a bit-flip operator on it will make it always return 1. And as always, the second qbit returns itself.
Constructing an identity operator gets a little bit more complicated, but can be done as follows:
The symbol here is a CNOT gate, where the top line is the target bit, and the bottom line is the control bit. Recall that with a CNOT operator, the target bit is flipped if the control bit is |1⟩, and the target bit is left unchanged if the control bit is |0⟩. Because we assume that the top line is always set to |0⟩, this this means that the top line will always be set to the bottom line.
The Negation operator is very similar:
We simply flip the bit at the end of the output line.
Now that we’ve got the preliminary notation out of the way, we can dive into how a quantum computer can beat a classical computer at determining whether our black box contains a constant or variable function in only one query.
The trick to solving this problem with quantum computing in one query is to transform the input qbits to a superposition before they are passed to the function as follows:
Another Hadamard gate is applied to the outputs of the function to take the qbits out of superposition, making the algorithm deterministic. We initialise the system with state |00⟩ and for reasons I will now explain, if the black-box function is constant the system will return |11⟩. Otherwise if the black-box function is variable, the system will return |01⟩ after measurement.
For the rest of this article, refer to this image which was introduced earlier:
By applying a bit-flip operator followed by a Hadamard gate to both our inputs of |0⟩, they are both transformed into an equal superposition of |0⟩ and |1⟩ as follows:
From this value being passed into the black-box function, it’s quite simple to demonstrate how both of the constant value functions will return |11⟩.
Similarly, we can see that the Constant-1 function will also return |11⟩ as follows:
Note that both of the outputs will still measure as |1⟩, as -1² = 1.
With the same method, we can also prove that we will always get |01⟩ from both of the variable functions using the same method, although this is a tad more complicated.
Because CNOT is a 2 qbit operator, it cannot be represented as a simple state machine, and so finding the 2 outputs must be done by using the tensor product of both input qbits and multiplying by the CNOT matrix as we covered earlier:
By using the same method, we can also show that we return a value of |01⟩ if the black-box contains a negation operator:
And so, we have now demonstrated a situation in which a quantum computer can clearly outperform a classical computer.
Where to from here?
That’s about it for this article, good work on making it this far. If you’ve understood everything up until this point, you should have a decent understanding of the basics of quantum computing, understand quantum logic notation and understand how quantum algorithms may beat classical computers in certain situations.
This is far from a comprehensive guide on quantum computing and algorithms, but rather a quick introduction to the mathematics and notations involved to enable readers to not be confused by pop-science-esque explanations and metaphors of the subject that still leave many confused. There are a number of important topics that I didn’t have time to cover in this article such as quantum entanglement of qbits, how the amplitudes of |0⟩ and |1⟩ are complex numbers and how different quantum logic gates function by transforming the Bloch sphere.
If you’d like to learn about quantum computers more formally and structured, I highly recommend reading ‘An Introduction to Quantum Algorithms’ by Emma Strubell, which is quite maths dense but explains quantum algorithms in much more depth