A Crash Course on Quantum Computers
Nathaniel Zehner
Our modern computers are breath-taking machines consisting of billions of nanoscopic electrical components, able to calculate things at incomprehensible speeds. However, there is a different kind of computer, the quantum computer, which puts even the fastest classical computers to shame. A quantum computer uses phenomena unique to the quantum world, such as the strange idea that something can be in two different states simultaneously. In this article, we’ll start with the smallest unit of quantum computing, the qubit, and work up towards a simple quantum algorithm which can outperform every normal computer. The quantum computer’s ability to tackle previously intractable problems with blistering speed promises to revolutionise the field of computing in the hopefully not-so-distant future.
The fundamental unit of information in a classical computer is the bit, which is either a 0 or a 1. A quantum computer has its own version, known as a qubit (short for quantum bit). In the quantum world things are far more complicated. To describe a qubit, we need to use the mathematical idea of vectors. We can visualise vectors as an arrow from the origin towards a point, where the first entry is the x ordinate, and the second entry is the y ordinate. Let’s start with the simplest states1, \( | 0 \rangle\) and \( | 1 \rangle \), which, in vector form, are \( \left[
\begin{smallmatrix}
1 \\
0
\end{smallmatrix}
\right]\) and \( \left[
\begin{smallmatrix}
0 \\
1
\end{smallmatrix}
\right]\)respectively. In fact, every possible qubit can be represented using a vector \( \left[
\begin{smallmatrix}
a \\
b
\end{smallmatrix}
\right]\), as long as the vector is of length one. When we have a vector \( \left[
\begin{smallmatrix}
a \\
b
\end{smallmatrix}
\right]\), we can split it into \( a \left[
\begin{smallmatrix}
1 \\
0
\end{smallmatrix}
\right] + b \left[
\begin{smallmatrix}
0 \\
1
\end{smallmatrix}
\right]\). We say a qubit in such a state is in a superposition – it is both a \( | 0 \rangle \) and a \( | 1 \rangle \) at the same time.
There is, however, nothing special representing a qubit using a superposition of \( | 0 \rangle \) and \( | 1 \rangle \). Instead, we can split a qubit into a superposition of any two perpendicular vectors. A common pair of vectors is the horizontal \( | + \rangle \) and \( | – \rangle \) pair: \( | + \rangle \) is \( \frac{1}{\sqrt2}| 0 \rangle + \frac{1}{\sqrt2}| 1 \rangle \) and \( | – \rangle \) is \( \frac{1}{\sqrt2}| 0 \rangle – \frac{1}{\sqrt2}| 1 \rangle \). These vectors are both perpendicular and of length one.
A visual depiction of the perpendicular-vector pairs mentioned above.
It’s quite difficult to visualise what a qubit is, and even more so how a qubit can be in two states at the same time. An analogy for a qubit is the spin of an electron. An electron can be either spin-up, \( | 0 \rangle \); or spin-down, \( | 1 \rangle \). When we measure a spin-up electron’s spin in the vertical direction, we unsurprisingly get \( | 0 \rangle \) with certainty. But what happens when we measure in the horizontal direction to see if it is \( | + \rangle \) or \( | – \rangle \)?2 Your intuition might say that since \( | 0 \rangle \) is halfway between \( | + \rangle \) and \( | – \rangle \), the result of our measurement would be \( | + \rangle \) half of the time, and \( | – \rangle \) the other half of the time. Indeed, this is correct. With some more complicated linear algebra, one can show that in general, when we have a qubit \( \left[
\begin{smallmatrix}
a \\
b
\end{smallmatrix}
\right] = a| 0 \rangle +b| 1 \rangle \), the probability to measure \( | 0 \rangle \) is \(a^2\) and the probability to measure \( | 1 \rangle \) is \(b^2\).
What if we measured a qubit \( \left[
\begin{smallmatrix}
a \\
b
\end{smallmatrix}
\right]\) and obtained a result of \( | 0 \rangle \), and then proceed to measure it again? Logically, you might expect to still get \( | 0 \rangle \) with probability \(a^2\) and \( | 1 \rangle \) with probability \(b^2\). If we actually perform the measurements, we’ll instead get only \( | 0 \rangle \). This is due to the Observer Effect: whenever we measure a qubit, its state irrevocably changes to the outcome of the measurement. This can pose a challenge when trying to design a quantum algorithm.
Finally, we’ll introduce the tensor product. All the vectors discussed above only represent one qubit. If we want to represent the states of two qubits, we can use the tensor product, denoted by the symbol \( \otimes \). Thus, we can write the state of two qubits as \( | 1 \rangle \otimes | 0 \rangle \), or using the shorthand: \( | 10 \rangle\). A tensor product is like multiplication, but for vectors. The key difference is that the order matters: \(a \otimes b \neq b \otimes a\). This is because the state where the first qubit is \( | 1 \rangle\) and the second is \( | 0 \rangle\) is not the same as the state where the first qubit is \( | 0 \rangle\) and the second is \( | 1 \rangle\). Let’s see an example of the tensor product with the two qubits \( | 1 \rangle\) and \( | + \rangle\):
$$ | 1 \rangle \otimes \left(\frac{1}{\sqrt{2}} | 0 \rangle + \frac{1}{\sqrt{2}} | 1 \rangle \right) $$
We can then multiply out as usual to get:
$$ \frac{1}{\sqrt{2}} | 10 \rangle + \frac{1}{\sqrt{2}} | 11 \rangle $$
Having understood qubits, let’s see what a quantum computer can do with them. Just like how a classical computer manipulates its bits with many NOT and AND gates, a quantum computer has quantum gates. A quantum gate takes one or more qubits and transforms them into new (but not necessarily different) qubits. For example, the Hadamard gate \((H)\) can take in a \( | 0 \rangle \) or a \( | 1 \rangle \) and transform it into a \( | + \rangle \) or a \( | – \rangle \), respectively. Applying the Hadamard gate again reverses this change, so \( | + \rangle \) goes to \( | 0 \rangle \) and \( | – \rangle \) goes to \( | 1 \rangle \). The Hadamard gate is extremely useful as it takes a normal qubit and puts it into a superposition, which a quantum computer can then take advantage of. There are infinitely many possible quantum gates, but they can all be represented using a mathematical object known as a unitary matrix, depending on how each gate manipulates each qubit. A final point to mention is that a quantum computer can do everything a classical computer can using a series of quantum gates. This might seem trivially obvious, but since a qubit, unlike a bit, cannot be cloned, it is rather tricky to show, so we won’t do that here.
Using superpositions and other quantum phenomena, a quantum computer can solve some problems significantly faster than a classical computer. This was first shown in 1985 by British physicist David Deutsch. The problem is as follows. We have four functions such that:
$$f_0 (x) \text{ sends both } 0 \text{ and } 1 \text{ to } 0\\
f_1 (x) \text{ sends } 0 \text{ to } 0 \text{ and } 1 \text{ to } 1\\
f_2 (x) \text{ sends } 0 \text{ to } 1 \text{ and } 1 \text{ to } 0\\
f_3 (x) \text{ sends both } 0 \text{ and } 1 \text{ to } 1.$$
Since \(f_0\) and \(f_3\) always give the same output, we call it constant. Likewise, since \(f_1\) and \(f_2\) outputs are evenly split between \(0\) and \(1\), we call it balanced. We are given one of these four functions and our task is to determine whether our given function is constant or balanced. Naïvely, we can plug in both \(0\) and \(1\) into our function with a classical computer to get an answer. With a quantum computer, however, we can do better. We’ll use a new quantum gate, \(B_f\), that transforms \(| x \rangle \otimes | y \rangle \) into \(| x \rangle \otimes | y \oplus f(x) \rangle \). The \( \oplus \) symbol denotes the XOR operation, which acts like addition except with the property that \(1 \oplus 1 = 0\).
For example, if we start with \(| 0 \rangle \otimes | 1 \rangle \) and we get \(f_3\), our output would be \(| 0 \rangle \otimes | 1 \oplus f_3(0) \rangle \), which equals \(| 0 \rangle \otimes | 0 \rangle \), since \(1 \oplus 1 = 0\).
We’ll now use the following circuit:
The boxes with an H represent Hadamard gates, and Bf is the new quantum gate we saw above. The circle with a capital M is a measuring apparatus – notice how we only need to measure the first qubit to get our desired results.
We start by putting \(| 0 \rangle \otimes | 1 \rangle\) through two Hadamard gates to get:
$$ | + \rangle \otimes | – \rangle = \left( \frac{1}{\sqrt2} | 0 \rangle + \frac{1}{\sqrt2}| 1 \rangle \right) \otimes \left( \frac{1}{\sqrt2}| 0 \rangle – \frac{1}{\sqrt2}| 1 \rangle \right) = \frac{1}{2}\left(| 00 \rangle – | 01 \rangle + | 10 \rangle -| 11 \rangle \right)\\$$
After applying our quantum gate, we get:
$$ \frac{1}{2} \left( | 0 \rangle | 0 \oplus f(0) \rangle -| 0 \rangle| 1\oplus f(0) \rangle + | 1 \rangle| 0\oplus f(1) \rangle – | 1 \rangle | 1\oplus f(1) \rangle \right) \\
$$
Since \(0 \oplus x \equiv x\), we can simplify and factorise in to:
$$\frac{1}{2} \left( | 0 \rangle \left(| f(0) \rangle – | 1 \oplus f(0) \rangle \right) + | 1 \rangle \left( | f(1) \rangle – | 1\oplus f(1) \rangle \right) \right)\\
$$
Depending on whether \(f(0)\) is \(| 0 \rangle \) or \( | 1 \rangle \), notice how \(| f(0) \rangle – | 1 \oplus f(0) \rangle \) is either \(| 0 \rangle -| 1 \rangle \) or \( | 1 \rangle – |0 \rangle \). The versions differ from each other by a multiple of -1, so we can rewrite it as \((-1)^{f(0)} \left(| 0 \rangle – | 1 \rangle \right) \). With similar logic, we can write \( | f(1) \oplus 0 \rangle – | f(1) \oplus 1 \rangle \) as \( (-1)^{f(1)} \left( | 0 \rangle – | 1 \rangle \right) \).
Thus, we get:
$$
\frac{1}{2} \left( {(-1)}^{f(0)} | 0 \rangle \left( | 0 \rangle – | 1 \rangle \right) +{(-1)}^{f(1)} | 0 \rangle \left( | 0 \rangle-| 1 \rangle \right) \right)
\\$$
Factorising this, we get:
$$
\frac{1}{\sqrt2} \left( {(-1)}^{f(0)} | 0 \rangle +{(-1)}^{f(1)} | 1 \rangle \right) \otimes \frac{1}{\sqrt2} \left( | 0 \rangle – | 1 \rangle \right)
\\$$
We’ve now ingeniously split our transformed qubits into two separate output qubits. Does the form of the first qubit look familiar? Depending on which function \(f\) we get, it’s either \( | + \rangle \), \(| – \rangle \), \( – | – \rangle \), or \( – | + \rangle \). Namely, if \(f\) is constant, we get \( \pm | + \rangle \), and if \(f\) is balanced, we get \( \pm | – \rangle \).
We can now send our first qubit through a Hadamard gate. Continuing from what we’ve seen above, if f is constant, we get \( \pm | 0 \rangle \) and if f is balanced, we get \( \pm | 1 \rangle \). Finally, we can measure the qubit to solve our problem with only one evaluation, rather than two.
This algorithm can be generalised to see whether a function of n bits is constant or balanced. In the worst-case scenario, a classical computer would need to make \(2^{n-1}+1\) evaluations, while a quantum computer still only needs one. With large values of \(n\), this shows how a quantum computer can be significantly faster than a classical computer.
While both Deutsch’s algorithm and its generalisation, the Deutsch-Jozsa algorithm, have almost no practical applications, they show the potential for a quantum algorithm to compute something significantly faster than a classical algorithm. Indeed, the powers of a quantum computer can be harnessed to take on currently infeasible tasks, such as simulating large chemical systems or factorising long numbers. Currently, quantum computers are still in their infancy, with the largest ones having only a paltry 100 or so qubits. Even if quantum machines with qubits don’t end up replacing the billions of transistors that make up our current devices, quantum computers will still have a noticeable effect on our lives by helping find new drugs, or by exponentially speeding up useful calculations. Despite the litany of theoretical discoveries involving quantum computers, we should be excited that their time to truly shine is still ahead of us.
1 The \(|0\rangle\) notation is known as Dirac or bra-ket notation, and is used ubiquitously for quantum computing.
2 If you have a sharp mathematical eye, you might notice that the \(\frac{1}{\sqrt2}\) used for \(|+\rangle\) and \(|-\rangle\) is \(\sin{45}\) and \(\cos{45}\), which seems to only be half of the \(90°\) rotation needed to go from vertical to horizontal. This is because \(|0\rangle\) and \(|1\rangle\) used are only \(90°\) apart, only half of the full 180 degrees between “up” and “down”. Don’t worry, the maths still checks out!
2 If you have a sharp mathematical eye, you might notice that the \(\frac{1}{\sqrt2}\) used for \(|+\rangle\) and \(|-\rangle\) is \(\sin{45}\) and \(\cos{45}\), which seems to only be half of the \(90°\) rotation needed to go from vertical to horizontal. This is because \(|0\rangle\) and \(|1\rangle\) used are only \(90°\) apart, only half of the full 180 degrees between “up” and “down”. Don’t worry, the maths still checks out!
References:
Bernhardt, C. (2020) Quantum Computing for Everyone. Cambridge, MA ; London: The MIT Press.
Wikipedia:
<https://en.wikipedia.org/wiki/Quantum_state>
<https://en.wikipedia.org/wiki/David_Deutsch>
<https://en.wikipedia.org/wiki/List_of_quantum_logic_gates>
<https://en.wikipedia.org/wiki/Bit>
<https://en.wikipedia.org/wiki/Quantum_logic_gate>
<https://en.wikipedia.org/wiki/Quantum_computing>
<https://simple.wikipedia.org/wiki/Quantum_computer>