Background
Introduction
The aim of this document is to introduce the reader to the field of quantum computer science without prior exposure. We spend a little time brushing up on the mathematics which will be required, such as Hilbert spaces and tensor products in section
Once we have understood the mathematical fundamentals, we move on to actual quantum algorithms in section
Afterwards we will spend a little time thinking about other potential applications of quantum computer science. In particular, there is great promise in the field of topological quantum computing covered in section
It would be impossible to cover the entire field of quantum computation in this short document, but it is hoped that the material presented here will imbue the reader with a strong enough foundation to enable further exploration of the topics covered.
Notation
Whenever I say 'circuit' or 'circuit diagram', I am referring to logical circuits and not physical electrical circuits, unless I explicitly state otherwise.
I will not use the conventional equivalence class notation for modular arithmetic, instead using a simple = and reserving the equivalence symbol \(\equiv\) for definitional statements.
For convenience and clarity, I will variously use the tensor product symbol or not. For example, I may write equivalently \(\ket\psi\ket\phi\) or \(\ket\psi\otimes\ket\phi\), and trust that the meaning is clear.
History
In this section I will attempt to give a brief historical overview of the development of the field, so that the reader can have some understanding of its current state. In a single sentence we could say that quantum computation is a well-developed theoretical model which is still struggling to break through into the real world and solve real problems, though large companies such as IBM are actively working toward commercial hardware solutions, and even run a publicly accessible 5-qubit computer [1].
Before we touch on anything relating to quantum information we need to understand where classical computer science came from. The ultimate origins of algorithmic and computational methods are lost to time; the ancient Greeks had several highly sophisticated algorithmic ideas, and the reader will likely have encountered a number of them during the course of his studies in mathematics and physics. Examples include Euclid's algorithm for finding the greatest common divisor of two numbers, and the various prime sieves
Modern computer science as we now know it came into existence virtually all at once in 1936 with the emergence of Alan Turing's ideas on what are now called Turing machines [2]. He showed that any problem which can be solved by algorithmic means can be solved by a Turing machine, and further that any Turing machine can be simulated efficiently by what is now known as a universal Turing machine. The Church-Turing thesis, which we will revisit later, states that any computable problem
Since then progress has been immense, but in a real sense only incremental. There have been few changes in the fundamental methods we employ. We have hit some walls, since some problems prove unsuitable for solution by Turing machines
So we come to the other parent of quantum computer science. The development of quantum mechanics throughout the 20th century is well chronicled, and we are assuming the reader is somewhat familiar with this story. Famously disliked by Einstein, quantum mechanics came about as a result of efforts to solve critical issues in classical physics, most famously the ultraviolet catastrophe, wherein classical physics incorrectly predicts that black bodies will emit infinite amounts of energy. But we don't really need very much from this field; almost the only thing a theoretical quantum computer scientist needs is the concept of quantum superposition. The state of a physical system is not necessarily defined at any given moment - it exists in what is called a superposition of states. A measurement has some probability of finding the system in one state, and some probability of finding the system in another state (possibly very many of them).
mechanics came about as a result of efforts to solve critical issues in classical physics, most famously the ultraviolet catastrophe, wherein classical physics incorrectly predicts that black bodies will emit infinite amounts of energy. But we don't really need very much from this field; almost the only thing a theoretical quantum computer scientist needs is the concept of quantum superposition. The state of a physical system is not necessarily defined at any given moment - it exists in what is called a superposition of states. A measurement has some probability of finding the system in one state, and some probability of finding the system in another state (possibly very many of them).
Perhaps the only other critical ingredient from quantum mechanics is the no-cloning theorem (although this could quite fairly be considered a purely quantum computational/informational result). Roughly, the theorem states that an arbitrary quantum state cannot be copied without destroying the original, and this has strong implications for handling computational tasks and in particular forbids faster-than-light communication. The theorem is remarkably easy to prove once we have the requisite mathematics and we will do so in section
We could debate when exactly it was that the field of quantum computer science came into existence, but the earliest clear indication that I was able to find was the suggestion by Stephen Wiesner in 1969 [5] (though published much later) that quantum information processing could be used as a way to attack cryptological problems. Indeed this is still expected to be one of the areas to which quantum computation will be most applicable, so Wiesner certainly showed good insight. However, credit for the inception of the field is more usually (and perhaps more fairly) given to Richard Feynman, who presented a fairly well developed abstract model showing that a quantum system could be used to perform computational tasks
A short time later in 1985, David Deutsch put the field on a more secure footing by developing usable mathematical techniques to generate algorithms [3]. These techniques, as well the quantum circuit model, are still the leading formalism and he made further contributions in the form of the Deutsch-Josza algorithm in 1992 [7], which showcased a class of (contrived) problems for which a classical computer cannot outperform a quantum computer.
Quantum computation as a mathematical framework was now on firm footing and more or less complete. The field hit another major milestone with the publication of the first paper on the Shor algorithm for factoring [8]. This was not the first quantum algorithm to show supremacy over classical equivalents, but it was one of the first to solve a meaningful problem with practical applications, and so it became and has remained the poster child for quantum computation. Anyone with experience of writing software will know that factoring numbers is a very common elementary problem, and will probably also know that it takes an extremely long time if the numbers involved are large. Shor's algorithm solves this problem efficiently in a probabilistic way, meaning it is quick but there is a certain probability that the proposed solution will be wrong. This isn't a problem in the way one might expect; the solution is potentially incorrect, but checking the correctness of a proposed solution is extremely easy. It turns out that the small amount of extra time taken to check the solution, and run the algorithm again if the solution is wrong, still leaves the quantum approach more efficient than the classical. This is a common theme in quantum computation, and for this reason quantum computers share many features with classical probabilistic computers.
So it seems that the theoretical power of quantum computation is well established. Probabilistic classical computers also exist, but there are no known cases where they can outperform their quantum counterparts. However building physical machines has proven very challenging. Control of individual quantum systems is a relatively recent technological development. There have been attempts to build quantum computers in bulk materials, such as the first nuclear magnetic resonance (NMR) model proposed in 1997 [9] and a 2-qubit version built in 1998. However it was shown by DiVincenzo [10] and others that NMR has serious scaling issues so is unlikely to be a viable candidate in the long term.
Nowadays there are labs all over the world actively involved in the building of quantum computers. It seems clear that the machinery can be built, but the major roadblocks are still reliability and scaling. The largest current computers host somewhat fewer than 20 qubits, but they are several years from widespread commercial viability. IBM, one of the leaders in the field, host a publicly accessible 5-qubit computer, and 45 qubit circuits have been simulated [11]. Other machines like the one produced by the company D-Wave make good headlines. For instance the D-Wave machine claims to host 2000 qubits, but it is not a true quantum computer is the sense we discuss. It can solve certain optimisation problems but is useless for more general tasks. Anyway, according to Patrick Hayden in [12] it is easily outperformed by existing classical machines.
Mathematical preamble
This section will outline the mathematical prerequisites for understanding this material. Although there will be relatively few explicit calculations, it is important that the reader have a reasonable intuition for the mathematical arguments that are presented so that they are able to either trust or check them, as desired.
Modular arithmetic
We're going to need a little bit of modular arithmetic. In both classical and quantum computer science, much of the mathematics is of course concerned with manipulating binary numbers, so in particular we'll need arithmetic modulo 2. For those of you coming from a physics rather than mathematical background, modular arithmetic is likely to be unfamiliar, but the following statement sums up the core concept:
The statement "\(a\bmod n\)" asks "what is the remainder when \(a\) is divided by \(n\)?"
So, for example, we could say 5 mod 4 = 1, or 17 mod 3 = 2. That is to say, the remainder on division of 5 by 4 is equal to 1, and the remainder on division of 17 by 3 is equal to 2. In practice this often boils down to repeated subtractions of the modulus until you cannot subtract any more without reaching negative numbers, and the remainder is the answer. The most common introduction to modular arithmetic is often called clock arithmetic, which is arithmetic modulo 12. We know that 9 a.m. plus four hours gives 1 p.m., and this fact is contained in the statement 9 + 4 mod 12 = 1. Simply evaluate the sum and find the remainder on division by 12. Modular arithmetic just generalises this concept to numbers other than 12.
Since we will be concerned exclusively with binary arithmetic, we will introduce the \(\oplus\) notation, which can be taken to mean mod 2. So
The rub of all this is that any time you see a sum in this notation, the answer can only be either 0 or 1, and we manipulate strings of these numbers. In other sources you may see the notation \(a +_2 b\), again meaning the same thing. Computer scientists will probably be familiar with the use of the % symbol for the modulo operation.
Continued fraction expansion
For the latter classical number theoretic part of Shor's algorithm we'll need to know how to do a continued fraction expansion. This allows us to write a real number in terms of integers as a type of fraction. For rational numbers this fraction will terminate, but it generally won't terminate for non-rationals. We will only encounter rational numbers in our discussion. We illustrate with an example.
- We want to write 31/14 as a continued fraction, so we first break it into its integer and fractional parts, and the inverty the fractional part, like so:
$$ \begin{equation} \frac{31}{14}= 2 + \frac{3}{14} = 2 + \frac{1}{\frac{14}{3}}. \end{equation} $$
- Repeat the integer-fraction split and inversion steps until the final numerator is unity:
$$ \begin{equation} \frac{31}{14} = 2 + \frac{1}{4+\frac{1}{1+\frac{1}{2}}} . \end{equation} $$You will know that the continued fraction has terminated because a further inversion step here will not change anything.
In general we continue until either the fraction terminates or, for non-rational nuymbers, until we have reached an acceptable level of precision. You may see the notation \([a_0;a_1,a_2,\dots] \) to represent fractions of this type, equivalent to
so our example of 31/14 may be represented by [2; 4, 1, 2].
We'll also want to know how to calculate what are call convergents of a continued fraction. These are increasingly accurate rational approximations to a continued fraction, and are given iteratively by the formula
where \(p_0=a_0,\ p_{-1}=1,\ q_0=1,\ q_{-1}=0\). In general, for a continued fraction expansion with \(n\) elements, the \(n\)th convergent will be exact. Let's form the convergents of 31/14 from the representation [2; 4, 1, 2]:
We clearly see the sequence converging on the true value, with the fourth iteration being exact for a four-element continued fraction. The convergent with denominator \(q\) is provably the best approximation possible with a denominator less than or equal to \(q\).
Binary numbers
I think it's safe to assume that all readers of this document are at least vaguely familiar with binary numbers. However, if your background is not in mathematics or computer science it is perhaps unlikely that you have much recent experience converting between base 2 and base 10. A decimal number is represented by a string of the digits from 0 to 9, where the \(n\)th digit from the right, \(d\), has the value \(d\cdot 10^n\) for \(n\in \{0, 1, 2, \dots \}\), and we sum over the digits to get the value of the number. So
Entirely similarly, a binary number is represented by a string of 0s and 1s, where the \(n\)th digit from the right represents the value \(d\cdot 2^n\), and we sum over the digits to get the total. So
For convenience I will represent quantum mechanical state vectors variously by binary or decimal notation, and it is important that you understand how to interpret them.
Hilbert spaces and tensor calculus
We'll need the mathematics of Hilbert spaces, as that's where quantum state vectors live. However, as mentioned earlier it is assumed that the reader has completed at least an introductory level course in some quantum theory, so this section will be brief. For a more detailed review, any introductory text on quantum mechanics will do.
A Hilbert space is a vector space equipped with an inner product. In particular we are concerned with finite-dimensional complex Hilbert spaces. We will try to stick exclusively to Dirac's notation bra-ket notation, where \(\ket x\), \(\ket y\), \(\ket z\), etc. are vectors in a complex Hilbert space \(\mathcal H\). The length of a vector in this space is the usual Euclidean norm, also called the 2-norm, and we will generally assume and insist that vectors are normalised to be of unit length.
A Hilbert space has a number of basis states equal to the number of dimensions of the space. For example, a 3-dimensional complex Hilbert space may have basis states \(\ket{x_0}\), \(\ket{ x_1}\), \(\ket{ x_2}\). A general state is then a linear combination of the basis states, i.e.
where \(\alpha_i\in\mathbb C\). A \(d\)-dimensional Hilbert space is also equipped with operators, which can usually be represented by square matrices of size \(d\times d\). In particular for quantum mechanics we are interested in unitary and normal operators. We define unitary operators \(U\) and normal operators \(N\) respectively as those which satisfy
where \(\mathbb I\) is the identity operator of appropriate size and the asterisk denotes the adjoint (complex conjugate). Clearly then unitary operators are a subclass of normal operators. We will also be using projection operators, defined by
We may sometimes need to to use the matrix representation of operators. Methods for finding this matrix representation, as well as various other theorems and results related to Hilbert spaces and operators, may be introduced as needed. One of the most important properties of unitary operators for our purpose is that they always have an inverse, and we'll want to keep this in mind going forward.
To represent composite quantum systems of multiple potentially correlated subsystems, we use the tensor product; more strictly, this is actually the Kronecker product in the standard basis, which in our field is usually referred to as the computational basis. Taking \(A\) as an \(m\times n\) matrix and \(B\) as a matrix of any size, the most general definition of the tensor product that we will need is given by
where each element \(A_{ij}B\) is itself a matrix with the same dimension as \(B\). I will list the properties of the matrix tensor product as they become necessary. They can all be derived directly from the definition in equation (\(\ref{kronecker_definition}\)).
The tensor product can also be used to combine Hilbert spaces into larger Hilbert spaces. The Hilbert space \(\mathcal H \otimes \mathcal G\) is defined as the space which is spanned by \(\{\ket{h_i}\otimes\ket{g_i}\}\) where \(\{\ket{h_i}\}\) are the basis vectors in \(\mathcal H\) and \(\{\ket{g_i}\}\) are the basis vectors in \(\mathcal G\). Equation (\(\ref{kronecker_definition}\)) has given us all we need to calculate these basis elements: just take the tensor product of each pair according to this definition.
We won't always be using the matrix representation of operators, so we need a basis-free definition of the tensor product to work with. The tensor product of two operators \(A\otimes B\) is defined as the operator which has the following action:
The salient point is that the operator on the left acts only on the state or space on the left, and likewise for right. It is not generally the case that the rightmost operator will even be defined in a way that allows it to act on the leftmost space, and vice versa. For tensor products of more than two spaces or states, the \(n\)th operator acts only on the \(n\)th state or space. Operators that are to act only on one part of a product space may be written as \(A\otimes\mathbb I\otimes\mathbb I\otimes\dots\), or \(\mathbb I\otimes A\otimes\mathbb I\otimes\dots\), etc.
Boolean algebra and logical operators
A Boolean function is one of the form \(f:\{0,1\}^n\rightarrow\{0,1\}\). That is, a function which takes a binary string of length \(n\) as input, and produces a single binary digit as output. The key Boolean operators are the AND, OR and NOT operators:
These operations are easy to understand. The AND oeprator returns 1 if both inputs are 1, and returns 0 otherwise. The OR operator returns 1 if at least one of the inputs are equal to 1, and returns 0 if both inputs are 0. The NOT operator returns 1 if the input is 0, and returns 0 if the input is 1. When we build logical circuits these operations will be encoded in what we'll call logic gates.
Quantum mechanics
Again we're assuming a reasonable knowledge of quantum mechanics, although as mentioned elsewhere we need surprisingly little. My favourite summing up of quantum mechanics is credited to Scott Aaronson, who in Quantum Computing Since Democritus describes it succinctly as "probability with a 2-norm instead of a 1-norm". Admittedly this is unlikely to be very illuminating unless you already have some familiarity with the material. By making some reasonable assumptions about what reality should do and what a bit is, Aaronson argues that quantum mechanics should in principle be discoverable to mathematicians even without experiment to confirm it.
The most important quantum-mechanical concepts for us are the following:
- Superposition: a general quantum system exists in a superposition of all of its basic states. For example an atom exists in a superposition of its ground state and all of its electrically excited states simultaneously, and only upon measurement does the system 'choose' a state to reveal. This is subtly but importantly different to the superposition of classical wave mechanics, because in quantum mechanics the wave function is not an observable. If base states are labelled \(\ket{x_i}\) and probability amplitudes are labelled \(\alpha_i\) then the state \(\ket\psi\) of a general \(N\)-dimensional system is written as$$\begin{equation} \ket\psi=\sum_{i=0}^{N-1}\alpha_i\ket{x_i}. \end{equation}$$
- Entanglement: two (or more) quantum systems can exhibit non-classical correlation, so that the measurement of some property of one system indicates with certainty what a later measurement of a correlated system will give. This is despite the fact that the result of the first measurement was not pre-determined, and pays no respect to the spatial separation of the entangled systems. This is not (by itself) useful for long distance communication as the result of the first measurement is essentially random. Without some other way to communicate, both parties will measure apparently random noise. The famous Bell inequalities [14], which you have certainly encountered if you have studied quantum mechanics, more or less amount to a proof
Once some loopholes have been closed. that quantum mechanics is not compatible with local realismMeaning quantum mechanics is non-local or quantum systems do not have predetermined states. , and this is thanks to entanglement. - No-cloning: it is not possible to create a perfect copy of an arbitrary unknown quantum state without destroying the original. This theorem has profound implications for quantum information processing and is surprisingly easy to prove, so we will do so in section
header-no-cloning-proof .
We're also going to be ever-concerned with the measurement problem. This is the name given to the fact that measurement of a quantum state causes it to collapse to one of the basis states of the measurement, and so in general we cannot access the information contained in a quantum state, which is encoded in the complex probability amplitudes. It is not possible even in principle to discover the exact value of the amplitudes for an arbitrary state, for the same reasons we can never decide if a coin is perfectly fair; it would require an infinite number of trials. The measurement problem will prove to be one of the key obstacles in the pursuit of quantum computation, and much of algorithm design comes down to finding clever ways to bypass it.
Proof of the no-cloning theorem
The no-cloning theorem [15] states that it is not possible to copy an arbitrary quantum state while preserving the original. The proof is surprisingly simple. Let's say we want to write some function \(U_\text{copy}\) which will copy an arbitrary quantum state while preserving the original. The function must have the action \(U_{\text{copy}}:\ket\psi\ket 0\mapsto\ket\psi\ket\psi\) for any state \(\ket\psi\). It can be represented by the circuit shown in
The first line is the copy operation, and the second line follows directly from the linearity property of the tensor product. But this result is in direct conflict with the linearity of quantum-mechanical operators, which requires that
Thus if quantum mechanics is linear (it is), expressions (\(\ref{broken-ucopy}\)) and (\(\ref{true-ucopy}\)) are not equal so it cannot be possible to clone an arbitrary state. Actually, expression (\(\ref{broken-ucopy}\)) was already enough to prevent cloning since unitary transforms are norm-preserving and in general
so the operator \(U_\text{copy}\) cannot be unitary and so is not a valid quantum-mechanical operator.
The Bloch sphere representation of states
I will not belabour this point since again we are assuming quantum mechanics and personally I've never found the Bloch sphere representation to be particularly illuminating. The important facts are that unit norm states lie on the surface of the Bloch sphere, and when we come to quantum gates it might be helpful to realize that all single-qubit gates can be represented as rotations around some axis of the Bloch sphere. In other words, our gates are unitary transformations so preserve the norms of states.
If the Bloch sphere representation of quantum states is completely unfamiliar you can find an exposition in any introductory quantum mechanics text. It is designed to give an easy visualisation of quantum states in a 2-dimensional Hilbert space, i.e. a 2-level quantum system, or qubit. But it does not generalise directly or neatly to higher-dimensional spaces. Since we will almost always be concerned with states of many qubits, the Bloch sphere is of limited usefulness.
Fundamental concepts
Classical computers
The mathematical concept of a Turing machine was first defined by Alan Turing in 1936 [2]. In rough, it is a machine which is able to compute some function which is 'Turing computable'. A Turing machine solves a particular task and consists of some kind of input - in Turing's time a tape - entered into a machine which does some operation on that data, and an output showing the result of some calculation encoded in the action of the machine. It is shown that both the input and operation of the machine can be encoded as a binary string, and so Turing showed that there can exist a machine which is able to simulate any Turing machine, i.e. the universal Turing machine. All modern computers are of the universal Turing machine type - in a very real sense your laptop has the same computational capability as the most powerful supercomputer, except of course most tasks would take very much more time at home.
The most familiar realisation of a universal Turing machine is an everyday binary computer. Inputs and outputs both consist of strings of 0s and 1s, and all higher-level functions simply black-box this fact away and let the hardware take care of it. Anything you do with a computer is translated down through various levels of abstraction until in the end its all just binary computation.
This notion of a universal computer is one that is important to the study of quantum computation. There already exist examples of 'quantum computers' today, but they are of very limited scope. For example the D-Wave machine is one which works on quantum mechanical principles, but it can only perform a specific type of optimisation task. We want a general quantum computer, analogous to the universal Turing machine, which can work on general problems.
Qubits
The first ingredient needed for understanding quantum computation is the qubit, analogous to the classical bit. A bit can takes values either 0 or 1, which will change as the instruction set of some algorithm acts upon them, but any bit will always have one of these values. An input register would be a string of 0s and 1s, i.e. a binary number, which is acted upon by a sequence of instructions with the result of the computation - another, generally different, binary number - being placed in the output register.
The qubit is similarly defined. It can be in states labelled by \(\ket 0\) or \(\ket 1\), which are vectors in a complex Hilbert space, and in a similar way can be acted upon by an instruction set. The difference is that a qubit as a physical quantum system does not need to be, and generally is not, in either of the states \(\ket0\) or \(\ket1\), but can exist in any unit-norm superposition of these two states. In general then a qubit can occupy an infinite number of states \(\ket\psi = \alpha_0\ket0+\alpha_1\ket1\), rather than just the two possible classical states, since there are an infinite supply of pairs \(\left(\alpha_0, \alpha_1\right)\) for which \(\left|\alpha_0\right|^2+\left|\alpha_1\right|^2=1\). For the same reason, a qubit can in principle encode an infinite amount of information, although due to the measurement problem we can never access it.
This is where a great deal of the potential power of quantum computation resides: quantum parallelism. We will see later that thanks to superposition we can compute certain questions for any number of inputs simultaneously, rather than having to do multiple individual calculations as in the classical approach. But it is also the first major pitfall in quantum computation. If we run a classical computer, all we need to do to extract the result is read the output register, which presents no technical or theoretical difficulty. If we attempt to read a quantum output register then we must remember that the measurement result of a quantum system is basis-dependent. This means that if we read with the computational basis, we will lose information due to quantum decoherence if the output was in any state other than the basis states \(\ket0\) or \(\ket1\). We can measure in other bases, such as the Hadamard basis \(\{\ket{+},\ket{-}\}\), where
But again, no superposition of these two states will survive a Hadamard-measurement, the result of which will be probabilistically determined.
How then are we to extract information from a quantum computer? One possibility is to run the computation on a large number of identical machines simultaneously. If we have enough of them then we can build up a picture through numerous measurements of what the full state was. Of course this approach will require an unlimited number of separate quantum computers, if we demand absolute precision and certainty in our results, which is certainly not feasible. Nevertheless, if we are willing to accept an answer which is 'close enough' this may be a tenable solution; for some acceptable probability of error, we would need a particular number of machines. But we could actually just have done the same thing with classical machines, so the advantage of this approach is not obvious. Another way is to employ clever algorithm design which allows us to take advantage of quantum superposition but also allows us to make measurements which produce useful, if not necessarily perfect, information. We will see examples of such algorithms later.
There are a number of physical ways to realize a qubit. Any two-state quantum system will do. The easiest to understand is a simple atom, where the states \(\ket0\) and \(\ket1\) correspond respectively to the ground state and first excited state of the atom. There would be some physical means of switching between the two states
A well isolated qubit conserves information even as it evolves (measurement notwithstanding), because quantum evolution is unitary and therefore reversible. However, now that we've thought about the physical qubit as an atom, the second pitfall of quantum computation begins to become apparent. Quantum superpositions are generally extremely delicate. It is necessary to prevent accidental changes in state, e.g. by thermal photons. The main ways to deal with this problem are
- reduce noise as far as possible,
- use error-correcting codes to detect and correct unintended changes of state.
These are the approaches which will play a large part in the protection of 'conventional' qubits. In particular we will take a brief look at error-correcting codes in section
We may of course work with ensembles of many qubits, and certainly we will need to do so if we want to build a practically useful quantum computer. A 2-qubit system in the computational basis, also called the standard basis, would have basis states \(\{\ket{00},\ket{01},\ket{10},\ket{11} \}\). A 3-qubit system has eight basis states, given by simply writing all the 3-digit combinations of \(\ket 0\) and \(\ket 1\), or perhaps more illuminating, the binary representations of the numbers 0 to 7: \(\ket{000},\ket{001},\ket{010}\), etc. In general, \(n\) qubits have \(2^n\) computational basis states \(\{\ket 0,\ket 1,\ket 2,\ket 3,\dots,\ket{2^n-1}\}\) (or the equivalent binary strings)
In summary then a qubit is the quantum counterpart of the classical bit, with the only important abstract difference being that general quantum systems exist in a superposition of states, while classical bits cannot.
Quantum circuits
In classical computation - that is, the kind of computation used on every device any of us have ever used to solve a problem - we use so called `logic gates' to perform actions on various inputs in order to produce a solution to a particular problem. The inputs will be strings of binary digits which represent some information on which we wish to perform a calculation.
Probably the simplest examples of such calculations are the NOT and AND gates, which act very much as their names suggest. A NOT gate takes a single input, represented by a 0 or a 1, and outputs the (only) other possible digit, respectively 1 or 0. If we define the relation \(a\oplus b=(a+b)\bmod 2\), then the NOT gate is the function \(\texttt{NOT}:a\mapsto a\oplus 1\). In NOT gate.
NOT gate. A wire supplies input from the left the same wire carries output to the right.AND gate. There are two input wires on the left and one output wire on the right.The AND gate has no direct analogue in quantum computation, because a quantum gate must have the same number of inputs and outputs. However it is possible to simulate the AND gate with other quantum gates.
There are a number of other classical logic gates, e.g. XOR, \OR, etc, which perform similarly simple arithmetical operations. However it would not be particularly illuminating to describe them all and it can be shown, somewhat surprisingly, that all of these others can be reproduced using only AND, OR, and NOT gates, so these three together form a universal set of gates for classical computation. By universal I here mean that compositions of only these gates is sufficient to solve any Turing-computable problem. In fact, we can go further and show that all three of these can be simulated by NAND gates, which is exactly an AND gate with a NOT stuck on the end. We will see later than we can find universal sets of quantum gates as well.
Quantum gates are similarly defined. They take some number of qubits as input, and give an output depending on those inputs. Because the output depends on the input, and the input may be a superposition state, quantum gates can be and are used to produce entanglement, as shown in
Before descending too deeply into our explanation of the quantum circuit model it's worth nothing that other computational paradigms do exist. However, the interesting ones can all be shown to be equivalent to this circuit model, and I believe this is the most illuminating one to consider, thanks to its ready comparison with classical circuits. Topological quantum computing requires a fundamentally different physical approach but is mathematically equivalent to what we're doing here. In addition, there are quantum annealers which may have some potential in narrow use cases such as optimisation problems, but are not useful for general computational tasks.
CNOT - depends on the value of the first qubit, so states of the two qubits are correlated after its application. Thus the qubits are entangled. Note that the wires do not have separate states at the output. This is because only the full entangled state is defined, and not the states of its constituent qubits.Wires and gates
The quantum circuit model still in use today was proposed by David Deutsch in 1985 [3]. It's graphical representation is similar to that of classical circuit diagrams composed of gates and wires. In a classical circuit diagram we have wires carrying values 0 and 1, which pass through logic gates, changing their values as the gate dictates.
A quantum circuit consists, unsurprisingly, of wires and gates. However the wires here are a little more abstract, not necessarily representing physical wires as in a classical circuit. Instead they represent other things like the path and value of a qubit through time (left to right), and connections via gates between multiple qubits.
Note that the concept of an output register does not have the same graphical interpretation in the quantum case. In classical computing, the output register is an entirely independent memory location on the right of a diagram where the result of some computation is stored after the calculation has completed. For various reasons, including the no-cloning theorem, this is not generally possible in quantum computing. Instead, what we call the output register is a bank of qubits, normally initialised to the state \(\ket{0^n}\) (that is \(n\) copies of \(\ket0\), which are found on the left of the diagram just like the input register. These output qubits are evolved by the circuit and we may read them later on. Importantly we can also read the input register, which is itself generally altered by the computation. You might be thinking that the distinction is quite vague, but we will often have a collection of qubits whose only purpose is to store a calculation result, and for this reason it is sensible to think of them as an output register. For a visualisation of this see
The gates themselves represent some unitary transformation on the state of some number of qubits, except for the measurement gate which is non-unitary. The actual machinery of how these unitary transformations are achieved will not concern us much. A simple quantum circuit might look like
The input is from the left, where the wires are labelled with the states of the qubits. Depicted here we see two gates - one acts on a single qubit, and one acts on multiple qubits. Gates acting on multiple qubits will almost always produce entanglement. The wires continue to the right where their state now depends on the prior actions of the circuit. We should be careful not to refer to the right-hand wires as an output register in conflict with our prior definition, unless we are careful to make the meaning clear. It is better to refer to them as the post state or posterior state.
Single-qubit gates
In the computational basis the Pauli-\(X\), -\(Y\) and -\(Z\) gates have the matrix representations
You can easily check that these are all unitary according to definition (\(\ref{unitary-definition}\)). In circuit diagrams they are represented simply by a box containing their label \(X\), \(Y\) or \(Z\). In the computational basis it can easily be shown that the \(X\)-gate has exactly the same action as the classical NOT gate, i.e. it maps \(\ket0\mapsto\ket1\) and \(\ket1\mapsto\ket0\). The \(Y\)-gate is most easily visualized as a rotation of \(\pi\) radians around the \(y\)-axis of the Bloch sphere, sending \(\ket0\mapsto i\ket1\) and \(\ket1\mapsto -i\ket0\). The \(Z\) gate is often called the phase-flip gate because it leaves \(\ket0\) unaltered and sends \(\ket1\mapsto-\ket1\). Unlike the \(X\) and \(Y\) gates it does not alter measurement probabilities because \(\left|\alpha\right|^2=\left|-\alpha\right|^2\) for all \(\alpha\in\mathbb C\). A quantum NOT circuit is shown in
The next crucially important gate is called the Hadamard gate, and owing to its utility in producing balanced superposition you will rarely encounter a quantum circuit which does not contain it. In particular it is so fundamental to state preparation that is often omitted altogether and the state it would produce is assumed from the outset. In the computational basis it has matrix representation
As stated, the Hadamard gate produces balanced superposition if it is fed a basis state, sending \(\ket0\mapsto\left(\ket0+\ket1\right)/\sqrt 2\) and \(\ket1\mapsto\left(\ket0-\ket1\right)/\sqrt 2\). In circuit diagrams it is represented by the letter \(H\).
Finally we have the phase-shift gate, which could be considered a general case of the phase-flip \(Z\)-gate. It has matrix representation
The state \(\ket0\) is unaffected and \(\ket1\mapsto e^{i\phi}\ket1\). Like the \(Z\) gate, the phase-shift gate does not affect the probability of measuring either basis state, since \(\left|e^{i\phi}\right|^2=1\) for all \(\phi\in[0, 2\pi]\).
Other named single-qubit gates exist and they will be introduced as needed. An unitary operator is a valid quantum gate so they won't all have names.
Multi-qubit gates
Composite systems, comprising potentially very many particles, also evolve unitarily so we can define quantum gates for multi-qubit systems as well. The quantum CNOT gate, which has exactly the same definition as the classical CNOT, is a 2-qubit gate with the following action:
As you can see this gate always leaves the first qubit unchanged, and acts an \(X\) (NOT) gate on the second qubit only if the first qubit is in state \(\ket{1}\). Hence the name controlled-NOT. The subscript indicates that the first qubit is the control, and the second qubit is the target. This can be reversed, but I will usually omit this notation and you should assume this ordering unless otherwise specifiedCNOT is only that quantum states are generally in superposition. This is a very important gate as it will produce a maximally entangled state if the first qubit is in a superposition, sending \(\ket{00}+\ket{10}\) to \(\ket{00}+\ket{11}\), etc.
CNOT circuit component.We also have the SWAP gate, which allows us to swap the positions of two qubits. In fact it is just a particular arrangement of CNOT gates, as shown in SWAP gate achieves the switch without the need for additional qubits. It's worth checking that it actually works, since at first glance it might be surprising. If we feed in the qubits \(\ket x=\alpha_0\ket 0+\alpha_1\ket1\) and \(\ket y=\beta_0\ket0+\beta_1\ket1\) then we have
Lines 2, 3 and 4 correspond respectively to using the first, second, and first qubit as controls. Note that the values in each vector have swapped places between the first and last lines.
SWAP gate, represented as a sequence of CNOT gates.Two further gates of particular interest are the Toffoli and Fredkin gates, shown in CSWAP since it has the action of swapping the second and third bits if the first bit has value 1, and no action otherwise. The Toffoli gate, sometimes called the CCNOT, is a double-controlled NOT gate, and is universal for quantum computation when supplemented with single-qubit gates.
Universal quantum gates
Can we have really universal gate sets for quantum computation, as we did for classical computation? Since any quantum operation is unitary (with the exception of measurement), then we can certainly have a universal set if we can construct all unitaries. But this isn't really practical; we'd like a reasonably small set of gates, rather than one for every member of the infinite set of unitaries.
There are a few different notions of universality when it comes to quantum gates and circuits. Here I will focus on the most intuitive of those senses: can we build, exactly or approximately, an arbitrary unitary transformation using only a small set of quantum gates, each of which acts only on a small set of qubits? Yaoyun Shi offers one of many proofs [16] that the CNOT gate in combination with almost any single-qubit gate \(T\) constitutes a universal set in a particular sense [17]: we can reproduce any element in \(U(2^n)\) (i.e. a unitary action on \(n\) qubits) to arbitrary precision using only a finite collection of these gates.
It can be shown that any unitary can be decomposed as a product of 2-level unitary matrices, where we define an \(n\)-level matrix as one which has non-trivial entries on only 2 rows and columns. The full matrix may have any size, but will look elsewhere like the identity. For example
is a 2-level matrix even though its dimension is 4. We call it 2-level because it only has non-trivial action on a 2-dimensional subspace of a higher-dimensional space. We already have the means of producing any \(2\times 2\) unitary in the form of the \(X\), \(Y\), \(Z\) gates - remember, these are a basis for size 2 unitaries - so if we can prove that this decomposition is possible we can produce a unitary of any dimension. This is proven in general in [18], and Nielsen and Chuang give a \(3\times 3\) example on page 190 of [19]. So we can write any \(d\)-dimensional unitary as a product
where \(U_d\) is a \(d\)-dimensinal unitary and \(U_i\) are 2-level, \(d\)-dimensional unitaries.
This seems pretty good. We can build any unitary matrix exactly! The trouble is that we haven't yet said anything about efficiency. Recall that the dimension \(d\) of the space is exponential in the number of qubits, or equivalently in the size of the input \(n\), so if we need \(d\) unitaries to do this decomposition, we're looking at a number of gates which is exponential in \(n\). It's nice that we can theoretically build exact unitaries but for practical reasons we'd like to be more conservative in our gate usage.
We can be more efficient if we accept approximations to our unitary operations, rather than demanding exact implementations. Before we do that we'll need to formalize the 'closeness' of two unitaries. The difference between two unitaries will be defined by
\(\mathcal{E}\) is a real number, and the maximum is taken over all the states \(\ket\psi\). Clearly if \(\tilde U\) and \(U\) map \(\ket\psi\) to very similar vectors, their difference will be near the zero vector and this norm will be small. If they are very dissimilar vectors then their difference will be far from the zero vector and the error will be large.
Using this definition it is shown in [19] that we can approximate any unitary using only gates from the following set
Algorithms and oracles
When we embark properly on our study of quantum algorithms and circuits, we will encounter oracles as abstract circuit components used to study various problems. Oracles appear in circuit diagrams as a black box which is able to compute some function, but crucially we make no assumptions about the nature of this machine. It isn't necessarily a Turing machine or any other familiar type of device. We assume only that it gives a solution to the particular problem it is presented with.
Making these assumptions about oracles and including them in our circuits allows us to worry about other aspects of circuit design, continuing our theoretical development without getting bogged down. In the same way, mathematicians often assume the truth of some conjecture in order to explore its consequences and develop surrounding theory. If we were forced to wait for a proof of every conjecture we probably wouldn't have advanced past basic arithmetic. Nevertheless, for many problems we will study we have good reason to believe, and in some cases we know for sure, that our functions can in fact be computed by physical systems. As such we are justified in encoding them as oracles. This is exactly the kind of abstraction that makes computer science so powerful.
Oracles can be presented as solving either decision or functional problems. It is worth noting that function problems can often be re-expressed as decision problems, but we won't generally concern ourselves with this level of abstraction. We will normally assume that the oracle simply computes the numerical value of some function which is crucial to the problem we are solving. The particular kind of an oracle we will usually concern ourselves with in quantum computation is of the following form:
The circuit representation is given in
We should also attempt to define what we mean by algorithm. An easy first account given by many authors is to define a computable function as 'one which can be solved by algorithmic means'. This is obviously not very satisfying, since we're now left with defining the word algorithm, but giving a more precise definition is actually quite challenging. We will consider a quantum algorithm to be simply a procedure with a finite number of steps, each of which can be executed by a quantum computer.
The word finite is key here, and alludes to the famous halting problem. The halting problem, which is another of the topics discussed in Turing's paper [2], is a representative of a class of functions which is classically undecidable, i.e. an answer cannot be produced by existing models of computation. In particular, the halting problem asks 'given a particular algorithm, will the algorithm ever halt?' It is somewhat surprising that it is not possible to look at a general algorithmic procedure and know or compute the fact of whether it will halt for all inputs, but proofs of the halting problem do exist, and in general they prove it by forming contradictions by invoking some kind of checker.
Let's say we have a program Halt.exe, which takes another program Check.exe as input and loops if that program returns a 1, and halts if it returns a zero. Now feed an identical halting program, Halt2.exe, into Check.exe. If Halt2.exe can halt, Check.exe returns 1 and Halt.exe loops, while if Halt2.exe cannot halt, Check.exe returns a 0 zero and Halt.exe stops. This is a contradiction, since the second case implies that Halt.exe both can and cannot haltCheck.exe cannot exist, i.e. the halting problem is undecidable.
Undecidable problems are outside the realm of both classical and quantum computational theory, and may require fundamentally different models of computation to resolve, if they can be resolved at all.
So an algorithm is a sequence of instructions which computes the answer to a decidable problem. In particular, a quantum algorithm is one which employs some fundamentally quantum means, such as superposition, to compute a function. Quantum simulations of classical algorithms would not usually be considered true quantum algorithms. We will make the implicit assumption that all of our algorithms are decidable, and that all of their individual steps are implementable.
Computational complexity
The field of computational complexity (and quantum computational complexity) is key to understanding many results in computer science, and in particular it gives us a notion of the cost of a computation, which is of great interest to physicists, computer scientists, computer engineers, and others.
To be of general use we need to be able to express this cost in a way that is independent of any actual machine. The cost of a computation may be expressed in terms of the amount of physical resources used to compute it - we most commonly consider time-complexity, but also space-, energy-, etc. For example, we might consider how many time steps a computation will take. This is an obvious area of interest since no matter how clever an algorithm is, it is of no real use if it takes decades to complete or requires infinite amounts of memory. On the other hand, the memory capacity of modern computers is effectively unlimited, and this is one of the reasons we usually consider time as the resource to be spent.
We can break problems into two very broad complexity categories: those which are called tractable, and those which are called intractable [20]. Roughly, a tractable problem is one which can be solved using only 'polynomial time'. What we mean by this is that, if the input data for a calculation has size \(n\), then the time taken to complete will be a polynomial function in \(n\). An intractable problem is one which takes exponential time, defined in a similar way. Of course an exponential time problem may be solved more quickly than a polynomial time problem for certain sizes of input, but as \(n\) becomes large any exponential function is larger than any polynomial function.
We can greatly reduce the cost of some computations if we are willing to accept a probably-correct solution, and do not demand a definitely-correct solution. This is particularly important in quantum computation as many of our algorithms will use probabilistic methods. This may sound unusual to those who are used to thinking of computers as deterministic machines, but the probability of an incorrect answer can be made exceedingly small while still allowing a considerable increase in speed. Also, some classes of problems are difficult to compute, but easy to verify once a solution is proposed. If we can use a probabilistic method to quickly get proposed solutions and then easily check them, it may still be possible to increase efficiency. One example of a probabilistic classical algorithm is the Miller-Rabin primality test [21], which decides whether a given number is prime or composite with some (exceedingly high) probability of correctness.
A particular class of problems to which it is hoped quantum computation may be applied are the so-called NP problems: those which are classically intractable but which can be verified in polynomial time given a proposed solution. A quantum computer may quickly generate a proposed solution, which can be checked quickly, perhaps even by a classical computer. Contrast this with P problems, which may be solved by a deterministic classical computer in polynomial time.
However it is not actually known that we even need a quantum computer to accomplish this task in the first place. It is possible that we are simply yet to discover a classical algorithm which will render all NP problems classically tractable, though this is generally considered highly unlikely. Proving that P = NP or P \(\neq\) NP is probably the most famous and one of the most important open questions in computer science. This is because the class of NP problems is such that finding a polynomial-time solution to one member also gives a polynomial-time solution to a wide range of related problems, and there are some which are very important for commerce, data security, etc.
Let's think in a little more detail about what we mean by polynomial time: assume we have a problem with an input of size \(n\). Then we can for example say that an algorithm can solve this problem in polynomial time. By this we would mean that, in the worst case scenario, the time taken to complete the calculation would be a polynomial function in \(n\). Of course there are an infinite class of polynomial functions, so this doesn't give a precise number of seconds or even steps for the calculation, but it does tell us that for large \(n\), it will complete before a calculation that is exponential in \(n\), since any exponential function is asymptotically larger than any polynomial function. There are also examples of problems solved in logarithmic time, constant time, etc, and these are ranked in efficiency according to their asymptotic behaviour.
You might say that a problem which is solved in time which is a function of \({n^{10}}^{150}\), which is polynomial, is always going to take longer than a problem with exponential time cost for any reasonably-sized input \(n\). This may be true, but as it turns out, natural problems don't seem to have this property. If a problem has polynomial cost, it tends to be a relatively small power of \(n\) such as \(n^2\), \(n^3\), etc. For that reason we consider it justifiable to treat all exponential-cost problems as harder than all polynomial-cost problems.
Note that in practice a function call can complete in much less time than its complexity class would suggest; a database searching algorithm may get very lucky and find the result it wants on the first attempt. The complexity class generally gives the time taken in the worst case scenario, e.g. the search algorithm may find the desired result on the last attempt, or not at all, meaning it has had to check every single database entry.
The set of all complexity classes is large and messy, and for that reason the phrase 'complexity zoo' is often uttered in reference to the particle zoo of particle physics. We aren't going to try to learn them all. Of particular interest to us are the classes BPP and BQP. BPP stands for bounded-error probabilistic polynomial, and it is roughly the class of problems that can be solved in polynomial time by a probabilistic classical computer. BQP is the class of problems which are polynomial for a probabilistic quantum computer. One of the key aims of the section on quantum algorithms will be to show that these classes are not identical; that is, we hope to see that there is a non-zero set of problems which can be solved efficiently by a quantum computer but not a classical computer. In the language of complexity theory we would say that we have found a separation of these two complexity classes and demonstrated quantum supremacy.
There is much more to be said about complexity theory, but this much will be sufficient for our purposes. For the reader who wishes to go into more depth on classical or quantum computation, an understanding of complexity theory is a must.
Making computation reversible
There is a particular feature which is bound to be present in quantum computation which is not present in the usual classical computation. This feature is reversibility. We know that general quantum computations will be reversible, since any gate will be a unitary operation and unitary operations are guaranteed to be invertible. Before moving onto quantum computation, it might be useful to explain how classical computation can be made reversible, and what advantage this gives.
The inspiration for seeking reversible computation comes firstly from Landauer's principle. This principle holds that it is in fact the erasure of information which carries an unavoidable energy cost (\(kT \ln 2\) where \(T\) is the ambient temperature), and if we can avoid erasing bits then we can avoid this energy cost. Of course there are other energy costs associated with computation which dwarf that required to erase bits, so at present this isn't a huge concern. However it is possible and perhaps likely that computer engineering will eventually advance to the point that Landauer's energy cost will be a non-negligible contribution to the total, and then we would like to know how to avoid it. In addition, any energy saving we can make will reduce the heat dissipated by our computer and make cooling easier.
The answer to avoiding erasure is to make our programs reversible. If we have an initialized input register, then after running our program we will have an output register which will need to be erased or reset after being read (assuming we want to use that memory location again). We can either reset by erasing everything in the output register and reinitializing our input state, incurring Landauer's energy cost, or by running the entire computation backwards so that the input register is restored without ever erasing a single bit.
It should be immediately obvious that not all of the familiar classical logic gates can be reversed, since some of them erase information. In particular the AND gate has three input states which give the same output state:
Clearly then it is impossible to reliably recover the input state if the output state is 0, and so some number of bits must be erased. The OR gate faces a similar issue. We'll need alternatives for both which don't suffer from this problem.
To replace the AND gate we can introduce the Toffoli gate which is a 3-bit gate defined by the action
The notation \(\Lambda^2\) means there are two control bits. This gate will be represented in a circuit as shown in NOT of \(z\) if \(x = y = 1\). However, you should be able to convince yourself that we can also use the Toffoli gate to simulate an AND gate if we force \(z = 0\); the third bit then takes the value \(xy\).
So we proposed a reversible NOT gateNOT gate is actually reversible anyway.AND gate for free! We can also use Toffoli gates to build an OR gate since
What we see here is that the OR operation can be expressed in terms of only NOT and AND operations, both of which can be reproduced by the Toffoli gate. Recalling that the set {AND, OR, NOT} is universal for classical computation as mentioned on page 25, we have just made classical computation fully reversible using a single 3-bit universal gate.
You might wonder whether we needed 3-bit gates at all. It turns out that we really do need them, and Preskill [17] gives an argument showing that the reversible 2-bit gates are not enough - they only allow us to compute linear functions, but there are plenty of functions on \(n\) bits which are not linear. As a matter of convenience we will still generally allow the usage of fewer-bit gates, since while the Toffoli is enough in principle, it will often be easier to use alternatives. In particular we can use normal NOT gates to alter the input and output value of the control bits for the Toffoli gate.
The principle of deferred measurement
I stated at the beginning of the last section that quantum computation is obviously reversible, but there is a caveat to be made. Clearly measurement of a quantum state is not a unitary operation, and as you will see that throughout our coming discussion on quantum algorithms, we will often use measurement gates at intermediate steps in circuits. We can do this thanks to the principle of deferred measurement, which states that
"Measurement can always be moved from an intermediate stage of a quantum circuit to the end of the circuit; if the measurement results are used at any stage of the circuit then the classically controlled operations can be replaced by conditional quantum operations." -Nielsen and Chuang [19], page 186.
What this means is that we can build our physical circuits to measure anywhere, normally at the end of a computation, but still present our diagrams with measurements at convenient intermediate steps without altering the probability distribution of the result. The reason we would like to do this is mostly pedagogical, as it often has the effect of dramatically reducing the number of base states in any given superposition and thus simplifying the description.
But what about measurement in general? It is not unitary so presumably not reversible, so how can we ever measure anything? One solution to this problem is to just accept that this step isn't reversible and simply pay Landauer's price, which is quite small after all, but there are more elegant workarounds. Surprisingly, we can do measurementless computation. By entangling our working qubits with additional qubits, called ancilla or environment qubits, we can work out the state of the qubits of interest without directly measuring them. The state of the ancillary qubits encodes the state of the working qubits. One such procedure is detailed in [22].
There are also models of quantum computation which consist exclusively of measurement; that is, the qubits are massaged into new states by intelligently collapsing them to what we need them to be.
Quantum algorithms
In the sections that follow I will attempt to give detailed accounts of a few well-known quantum algorithms. The selection is intended to showcase a few of the fundamental techniques in quantum algorithm design. We will start with the quantum Fourier transform as it isn't really an algorithm in its own right, but is still worthy of study and informs our analysis of Shor's algorithm. We will end with Shor's algorithm for factoring integers, as it inherits many features of the others and so follows naturally from them. Otherwise the algorithms presented here appear in no particular order.
Quantum Fourier transform
Most accounts of the quantum Fourier transform seem to follow the very logical pattern
discrete transform \(\rightarrow\) fast transform \(\rightarrow\) quantum transform \(\rightarrow\) applications
Very sensible, but I think our purposes are be better served by first explaining what it is that the quantum Fourier transform actually gets us, so that we know why we should care about how it works. Basically it allows us to go from an unstructured but periodic set of values (of amplitudes, in particular), to a set of values which are zero on all entries except those whose index corresponds in some calculable way to the period. This is depicted in
The usual, non-quantum Fourier transforms are likely familiar to many readers. The discrete Fourier transform (DFT) has applications in signal processing and the continuous Fourier transform appears in quantum mechanics and quantum field theory as a means of switching between position and momentum representations. In quantum computation we are unsurprisingly most interested in the discrete transform. The quantum Fourier transform is so fundamentally crucial to various quantum algorithms that it's worth a little study in its own right.
The discrete Fouriter transform
The discrete Fourier transform takes a vector \(f\) of complex numbers and returns another vector of complex numbers. For \(f_k\in f\) the discrete Fourier transform and its inverse are respectively given by
where \(N\) is the number of elements of the vector and \(\omega=e^{2\pi i/N}\). Note that the position of the negative sign in the exponent of the inverse transform is arbitrary, and they could equally well have been defined the other way around. Keep this in mind when referencing other material. It's worth quickly verifying that this inverse is correct:
where \(\delta_{m,j}\) is the Dirac delta function. The discrete Fourier transform runs in roughly O(\(N^2\)) time [19], since it requires \(N^2\) complex multiplications and \(N(N − 1)\) complex additions. This is already pretty good, but actually it is possible to do a little better by exploiting some symmetries and patterns in the discrete Fourier transform. We find the fast Fourier transform runs in approximately O(\(N \log N\)) time, which is a significant improvement across all values of \(N\). We won't delve into the fast Fourier transform too much here, since it's really only about doing the multiplication in a more clever way, reaching the same goal, and as such not very illuminating for our purposes. It's usage is nevertheless important for improving the speed of circuits.
The quantum Fourier transform
But we're interested in the quantum Fourier transform, which is really just a quantum realization of the discrete Fourier transform (or fast Fourier transform). In the computational basis the quantum Fourier transform has matrix representation
\(N\) is the dimension of the Hilbert space under study, so \(N = 2n\) where \(n\) is the number of qubits in the system. \(\omega\) is an \(N\)th root of unity, i.e. one of the \(N\) complex solutions to \(\omega^N = 1\). In particular it is the first other than 1 when moving counter-clockwise in the complex plane. Generally we can just take \(\omega=e^{2\pi i/N}\). \(\text{QFT}_N\) is represented as an \(N\times N\) matrix. The factor \(1/ \sqrt N\) is just the usual normalisation to ensure that the matrix is a unitary operator.
The vector on which the quantum Fourier transform acts is the collection of amplitudes on the bases of some state, including any zero amplitudes. For example, the vector \(f\) for a state \(\ket\psi\) might be described by
So rather than transforming some known values into new known values, the quantum Fourier transform acts on the invisible information stored in a quantum state, and transforms it without allowing free experimental access, and thus without disturbing the unitarity of the system or causing any decoherence.
It's worth confirming that the quantum Fourier transform is indeed unitary, since it's not immediately obvious, and we really do need it to be if we're going to use it as a quantum operator. Starting from our definition in equation (\(\ref{qft-definition}\)),
Here we use the fact that \(\braket{x|x'}=\delta_{x,x'}\), so the sum of \(x'\) yields unity:
We can resolve the sum over \(x\) by introducing a Dirac delta by the identity
We end up with
The last equality follows as each instance of \(\ket y\otimes \bra y\) puts a 1 on exactly one diagonal position in the matrix, and thus their sum gives \(\mathbb I\). so the quantum Fourier transform is indeed unitary. This not only means that it is a valid quantum operator, but also that we are able to implement it as a circuit, since we discovered earlier that we can implement any unitary with as much precision as we'd like. Nielsen and Chuang [19] give a general method of realising a quantum Fourier transform circuit, and give the particular example of the 3-qubit case, reproduced in
The quantum Fourier transform is of tremendous utility in a variety of quantum algorithms, and in particular it is the key step in the Shor algorithm for factoring. The circuits for Shor's and Simon's algorithms look very much alike, except that one features the quantum Fourier transform where the other features (an ensemble of) the Hadamard gate. Is there some hidden meaning here?
There is. Let's get a feel for how the quantum Fourier transform works by acting it on the amplitudes of some single qubit state, so that the length of our vector is \(N = 2\) and then \(\omega=e^{2\pi i/2}=-1\). The general single-qubit state is
Then we can calculate our transformed amplitudes \(\tilde\alpha_0\) and \(\tilde\alpha_1\) most easily using definition (\(\ref{qft-definition}\)), and we find
So our state is sent to
Do we know of anything else that would perform the same action? In fact we do - the now familiar single-qubit Hadamard transform has exactly the same effect, so we naturally consider the quantum Fourier transform as a generalisation of the Hadamard to higher numbers of qubits: \(\text{QFT}_2 = H\).
Let's run through another illustrative, non-proof example to see the suppression of off-period amplitudes. We'll use a 2-qubit state so that our Hilbert space has dimension \(N = 4\). Take \(\ket\psi=(a,b,a,b)\) in the computational basis, so clearly our period is \(r = 2\). Since \(N = 4\) we have \(\omega=e^{i\pi/2}\). Then
We see that the only non-zero amplitudes are those corresponding to basis states \(\ket0\) and \(\ket2\), so if we were to perform a measurement at this point we would be certain to find one of these states. These correspond, via the convergents of a continued fraction expansion, to multiples of the period \(r = 2\), and in general multiple runs of this experiment would allow us to calculate this \(r\) with high probability.
This is probably all we need to know about the quantum Fourier transform for now. We know how to use it to transform the amplitudes of a state, and we know why we might use it.
The Deutsch-Josza algorithm
The Deutsch-Josza algorithm was expounded in 1992 by David Deutsch and Richard Josza [7]. Though it is widely acknowledged that the algorithm fills no real use cases, it is nevertheless regarded as one of the earliest demonstrations that a quantum system can in principle compute at least a non-zero set of decision problems in a way that is more efficient then any conceivable classical method. In the terminology of complexity theory, we would say that it provides a separation between the classes P and EQP. I won't go into detail about EQP, but the point is that this is not as powerful as the separation we would like, between BPP and BQP, because there are probabilistic classical algorithms that can solve this problem efficiently. However the quantum solution is deterministic, rather than probabilistic, so it is still a significant discovery.
In this section we will describe the Deutsch-Josza problem, and think about the resource costs of both the quantum and classical methods of solving it. We will see that no classical method can match the proposed quantum solution, even in principle. Since this is the first algorithm we will study, we will attempt to tell the story with a reasonable level of mathematical rigour. This rigour may be relaxed either when I deem that it provides no meaningful insight, or in later sections once the reader is able to trust the kinds of steps taken.
Statement of the problem
The Deutsch-Josza circuit is an example of an oracle discussed in section
- the function \(f\) is constant, meaning all \(f(x)\) are equal, or
- the function \(f\) is balanced, meaning \(f\) has value 0 for exactly half of the inputs \(x\), and \(f\) has values 1 for the other half of inputs \(x\).
Note that we know we can look at exactly half of the inputs since there are \(2^n\) elements in \(\{0, 1\}^n\), and \(2n\) is even. The quantum function \(U_f\) is described by the quantum circuit of the type shown earlier in
For the case \(n=1\)
I claim that the circuit presented in
- The input state is $$\begin{equation} \ket{\psi_0}=\ket0\otimes\frac{1}{\sqrt 2}(\ket0-\ket1). \end{equation}$$
- After the Hadamard gate on the first qubit we have state $$\begin{equation} \ket{\psi_1}=\frac{1}{\sqrt 2}(\ket0+\ket1)\otimes\frac{1}{\sqrt 2}(\ket0-\ket1)=\frac{1}{2}(\ket{0,0}-\ket{0,1}+\ket{1,0}-\ket{1,1}). \end{equation}$$The commas are present only to aid readability. We will stop writing them later.
- Next we apply our quantum Boolean function through \(U_f\), recalling that it has the action \(U_f:\ket{a,b}\mapsto\ket{a,b\oplus f(a)}\). Our state becomes $$\begin{equation} \ket{\psi_2}=\frac{1}{2}\left(\ket{0, f(0)}-\ket{0,1\oplus f(0)}+\ket{1,f(1)}-\ket{1,1\oplus f(1)}\right). \end{equation}$$
- Applying the second Hadamard gate to the first qubit produces $$\begin{align}\nonumber \ket{\psi_3}=\frac{1}{2}( &\ket{0,f(0)}+\ket{1,f(0)}-\ket{0,1\oplus f(0)}-\ket{1,1\oplus f(0)} \\[1em] &+\ket{0,f(1)}-\ket{1,f(1)}-\ket{0,1\oplus f(1)}+\ket{1,1\oplus f(1)} ). \end{align}$$
- Now if \(f\) is constant, that is if \(f(0)=f(1)=a\), then we have the following state:$$\begin{align}\nonumber \ket{\psi_4}&=\frac{1}{2}( \ket{0,a}+\ket{1,a}-\ket{0,1\oplus a}-\ket{1,1\oplus a} +\ket{0,a}-\ket{1,a}-\ket{0,1\oplus a}+\ket{1,1\oplus a} )\\[1em] &=\frac{1}{\sqrt 2}(\ket{0,1\oplus a}-\ket{0,a}). \end{align}$$
- While if \(f\) is balanced so \(f(0)\neq f(1)\), our state becomes $$\begin{equation} \ket{\psi_4'}=\frac{1}{\sqrt 2}\left(\ket{1,f(0)}-\ket{1,f(1)}\right). \end{equation}$$
We're done. The striking thing to notice in steps 5. and 6. is that if \(f(0) = f(1) = a\), we are certain to measure \(\ket0\) for the first qubit, and if \(f(0) \neq f(1)\) then we are certain to measure \(\ket1\) for the first qubit. Thus we have solved in exactly one step what classically would take exactly two steps. The advantage comes from the parallelism provided by quantum superposition, enabling us to effectively check both inputs at once. Although a lot of the results of complexity theory rest on unproven assumptions, it seems all but certain that this algorithm proves the supremacy of quantum computing. After all, it relies on quantum superposition which no classical algorithm, no matter how clever, can hope to exploit. Even a probabilistic algorithm couldn't solve this with probability greater than 1/2, since there are only two input cases.
For the general case \(n>1\)
Of course we'd like to see that this algorithm works in general. For greater values of \(n\) we use the circuit in
We begin by applying Hadamard gates to the input register of \(\ket0\)s, and this produces an evenly weighted superposition over all the binary input strings,
This can be seen by thinking about a tensorial form of the binomial expansion where we preserve the order of the multiplicands:
These are the binary representations of \(\ket0\), \(\ket1\), \(\ket2\), ..., \(\ket{2^n-2}\), \(\ket{2^n-1}\), and this trend continues for all values in between. This is a very common step in quantum algorithms and we will use it again many times. Now we apply the unitary \(U_f\) and we get
For any individual \(x\) in this sum it must be the case that \(f(x) = 0\) or \(f(x) = 1\). If \(f(x) = 0\) then the second qubit will remain \(\left(\ket0-\ket1\right)/\sqrt 2\), and if \(f(x) = 1\) the second qubit will become \(\left(\ket1-\ket0\right)/\sqrt 2\). This is effectively just a sign change dependent on the value of \(f(x)\), and the way we write it in general is \((−1)^{f(x)}\). So if \(f(x) = 0\) nothing changes and if \(f(x) = 1\) we have a sign change. We can therefore rewrite our state as
This is called a phase kickback - we have encoded the result of a function call in the phase of our quantum state. Notice that the 'bottom' qubit has retained the state it started with, and we have only changed the phase for those basis states for which \(f(x) = 1\), and associated that phase with our input register rather than the output register which is its source.
This is also an important quantum computational technique called a phase inversion, and we will see it again later, used for another purpose. This phase inversion is the reason we prepared the bottom qubit in the state \(\ket{-}\). It has allowed us to turn an evenly weighted superposition into one which has been distinguished into two classes. However it is only the amplitudes that have been distinguished, and each state still has equal probability of a measurement. To compute the result of the next second column of Hadamard gates we'll use the formula
This result is actually thanks to the quantum Fourier transform, of which the single-qubit Hadamard is a special case (where \(N = 2\)). From now on I will only consider the state of the input register since our workspace qubits \(\ket{-}\) doesn't do anything more. The resulting state is
We have lost the square root in the denominator because the second Hadamard brings another power of \(1/\sqrt{2^n}\). We can now measure the input register. Each distinct state \(\ket y\) of the input register has amplitude
Since \(x\in\{0,1\}^n\), we note that exactly half of the values of \(x\) are odd and exactly half are even. Now consider the two cases in question, each with two subcases:
- If \(f\) is constant
- then the amplitude for state \(\ket{y=0}\) becomes \(\sum_x(-1)^{f(x)}/2^n=\pm 1\), having lost the \(y\)-dependent phase contribution, with the sign depending on the constant \(f(x)\), so we measure \(\ket{y=0}\) with certainty,
- and the amplitudes for any states \(\ket{y\neq 0}\) comprise an equal number of positive and negative unit contributions (corresponding to even and odd \(x\)) for a total of zero, so the total amplitude of these states is zero.
- If \(f\) is balanced
- then the amplitude for measuring state \(\ket{y=0}\) becomes \(\sum_x(-1)^{f(x)}/2^n=0\) since exactly half if \(f(x)=0\) and half of \(f(x)=1\),
- and the amplitude for at least one state \(\ket{y\neq 0}\) must be non-zero, since we've just discovered that we can't measure \(\ket{y=0}\).
What we have just found is that if \(f\) is constant we must measure \(\ket{y=0}\), and if \(f\) is balanced we must measure some other \(\ket{y\neq 0}\). This is precisely thanks to the superposition principle of quantum wave functions; our problem was set up so that the phases of 'wrong' measurements exactly destructively interfere, while phases of the correct measurement constructively interfere.
Thus in a single run of our quantum function we have discovered a global property of \(f\), a function with an arbitrarily large domain. So we see that the Deutsch-Josza algorithm runs in constant time for any size of input. In contrast, the best classical algorithm will have to individually evaluate \(f(x)\) for at least \(2^n/2+1\) values of \(x\) to be certain of correctly discerning the constant or balanced nature of \(f\). Checking half of the possibilities is not enough - it may be the case that the function is constant, or it may be the case that the first \(2^n/2\) evaluations just happened to be identical and the function is in fact balanced.
Summary of the Deutsch-Josza algorithm
As this is our first algorithm and I went into some depth, I will summarize the last few pages to help you digest them:
- Prepare the state \(\ket{0^n}\ket{-}\).
- Apply Hadamard gates to produce an equally-weighted superposition over all basis states \(\ket x\). Our full state is now \(\sum_x\ket x\ket{-}/\sqrt N\).
- Apply our unitary function to cause a phase inversion, which produces a separation between those bases \(\ket x\) for which \(f(x)=0\) and those for which \(f(x)=1\). Our full state is now \(\sum_x(-1)^{f(x)}\ket x\ket{-}/\sqrt N\).
- Apply the second ensemble of Hadamard gates to get a \(y\)-dependent phase.
- Measure the input register as \(\ket{y=0}\) with certainty if \(f\) is constant, and \(\ket{y\neq 0}\) with certainty if \(f\) is balanced.
Grover's algorithm
Of the algorithms we will study, Grover's is in my opinion the easiest to understand intuitively. What difficulty there is lies in showing that the procedures we want to carry out can be achieved unitarily, i.e. they can be performed by valid quantum operators.
Grover's algorithm is a function inversion algorithm. That is, given an output, Grover's algorithm uses quantum methods to calculate the input that would give this output, with a high probability of success. For obvious reasons it is often also considered a database searching algorithm; we can ask a database whether it contains some element, and if so what is the index of that element. It roughly follows the recipe
prepare state \(\rightarrow\) (phase inversion \(\rightarrow\) inversion about mean)\({}^m\) \(\rightarrow\) measure
The phase inversion step has the effect of negating the phase on some base state of interest. This is followed by the inversion about the mean step which has the effect of amplifying the amplitude of that state and suppressing all others. We run these two steps as many times as we like (\(m\) times, say), each time suppressing and amplifying the relevant amplitudes until we are happy with the level of precision we have bought. We then measure and, with high probability, find the state we were seeking. Note that Grover's algorithm works in almost exactly the same way if there is more than one such special state, but for ease of explanation we only consider the case where that state is unique.
The state preparation we want is easy enough to achieve, and we will see in the following sections that the other two key steps are indeed unitary, so we should be able to build them with physical systems.
The recipe
For Grover's problem, we take an unsorted database with \(N\) entries. Equivalently, consider an unstructured function \( f : \{0, 1\}^n \rightarrow \{0, 1\}\) whose domain has size has size \(N\) and codomain has size 2. For exactly one element \(x_1 \in \{0, 1\}^n\), we have \(f(x_1) = 1\), and for all other \(x \in \{0, 1\}^n\), \(f(x) = 0\). We need an \(N\)-dimensional Hilbert space to compute in, so we'll need as least \(n\) qubits where \(N = 2n\). We want to find the value \(x_1\) such that \(f(x1) = 1\). The definition of the function promises that there is only one such \(x_1\).
We encode the function \(f\) in an oracle \(U\) with the action
This might look a little different to some of the others we work with, and doesn't explicitly call for a separate output register. However we're really just repeating the phase inversion step that we did for the Deutsch-Josza algorithm, so in fact we have a single-qubit workspace register in the state \(\ket-\). This is not written here as it does not feature in our calculations beyond enabling the phase inversion. We saw in section
- Initialize the state \(\ket{\psi_1}=\ket{0^n}\) where \(n\) is the number of qubits, and \(N = 2^n\) is the size of the database (or the size of the domain of \(f\)). Apply Hadamards to produce the state \(\ket{\psi_2}=\sum_{x=0}^{N-1}\ket x/\sqrt N\), just as we did in section
header-deutsch-josza-algorithm . The mean amplitude of this state is just \(\mu_2=1/\sqrt N\). - Apply our black box to compute the function \(f\), or said another way, apply the phase inversion to the basis state \(\ket x\) for which \(f(x)=1\). This produces the state
$$ \begin{equation} \ket{\psi_3}=\frac{1}{\sqrt N}\sum_{x=0}^{N-1}(-1)^{f(x)}\ket x=\frac{1}{\sqrt N}\left(-\ket{x_1}+\sum_{x:x\neq x_1}\ket x\right), \end{equation} $$the second equality following provided there is a unique \(x_1:f(x_1)=1\), which is guaranteed by construction. This procedure is shown schematically by the cahrts in
figure-phase-inversion-chart . The mean amplitude of this superposition is now \(\mu_3=(N-2)/N\sqrt N\), which is strictly less than \(\mu_2=1/\sqrt N\). - Execute an inversion about the mean. This is effectively just a reflection over the dotted line in
figure-mean-inversion-chart , so basis states which have original amplitude greater than the mean will have decreased amplitude, and basis states with original amplitude less than the mean will have increased amplitude. This is shown schematically infigure-mean-inversion-chart . To achieve this inversion, we calculate the new amplitudes by doubling \(\mu_2\) and subtracting the amplitudes in state \(\ket{\psi_3}\). The result is$$ \begin{equation}\label{grover-inversion-result} \ket{\psi_4}=\left(2\mu_2+\frac{1}{\sqrt N}\right)\ket{x_1}+\left(2\mu_2-\frac{1}{\sqrt N}\right)\sum_{x:x\neq x_1}\ket x. \end{equation} $$On this first iteration, \(\mu_2\) is only slightly smaler than \(1/\sqrt N\) so the amplitude of \(\ket{x_1}\) is roughly tripled, while all other amplitudes are only slightly reduced. - At this stage, the probability of measuring the state of interest, though increased, is still very much less than the summed probabilities of all other states, so measurement at this point is likely to discover a wrong answer. Grover himself shows in [23] that after about \(\sqrt N\) iterations, the amplitude of \(\ket{x_1}\) is about \(1/\sqrt 2\). But the amplitude of each other state is now very much smaller.
- Perform a measurement and read a string \(\ket x\). Since the amplitude of \(\ket{x_1}\) is around \(1/\sqrt 2\), and all other amplitudes are very much smaller, we measure \(\ket{x_1}\) with probability \(\sim1/2\). Since all other measurements/ are very unlikely, repeating the experiment a few times and reading the same answer more than once gives a high level of surety in our solution.
This all seems wonderful. There are no complex algorithmic ideas here. Provided we can execute the two key steps unitarily, we have solved this problem. We actually saw in detail how we can achieve the phase inversion in our discussion on Deutsch's algorithm. We'll need a single extra qubit as workspace, in the state \(\ket-\). This has been omitted from my exposition so far, but we saw that this allows us to do the operation
which is what we need. So that's no problem. But what about inversion over the mean?
Unitary inversion about the mean
I claim that inversion about the mean can be achieved by the alarmingly simple matrix
where \([2/N]_N\) is the \(N\times N\) matrix with all elements equal to \(2/N\), and \(\mathbb I_N\) is the \(N\)-square identity matrix. It is easy to check that this is unitary:
But even if it is unitary, why does this matrix achieve an inversion about the mean? Let's se how it acts on a generic quantum state \(\ket\psi=(\alpha_0,\alpha_1,\dots,\alpha_N)\) of dimension \(N\).
But \(\sum_x\alpha_x/N\) is simply the mean amplitude, so each element of this state vector is just two times the mean, minus the original amplitude of that basis vector. This is the same thing we saw in equation (\(\ref{grover-inversion-result}\)), so the matrix really has achieved an inversion about the mean.
In terms of quantum gates, this transformation can by done by the circuit in figure
Resource cost
Finally, we will say something about the quantum vs. classical resource costs of searching an unsorted database. It is clear that a classical algorithm cannot solve this problem deterministically without making O(\(N\)) calls to a database of size \(N\). This is because in the worst case, the element we're trying to find is in the last cell of the database.
In contrast, a quantum computer only requires O(\(\sqrt N\)) runs of our quantum algorithm. For large \(N\), this represents a large saving. For example, if our database has size \(N = 10^6\), we can repeat our quantum experiment 100 times, far more than necessary for any reasonable level of certainty, and still only use 10% of the calls that the classical algorithm made: \(100\sqrt{10^6} = 10^5\).
Simon's problem
Simon's problem [25] is an important milestone on the road to Shor's algorithm, and shares many features with it. The problem it solves - order finding - is certainly more useful than the Deutsch-Josza solution. The problem can be phrased as:
Let \(f:\{0,1\}^n\rightarrow\{0,1\}^n\) be a function which is promised to have the property that for some \(s\in\{0,1\}^n\), for all \(x,y\in\{0,1\}^n\), \(f(x)=f(y)\iff x=y\) or \(x\oplus y=s\). Calculate \(s\).
In simple English this is saying that \(f\) is a periodic function, and the problem is to find the period \(s\) which is an \(n\)-digit binary number, where \(n\) is known. Crucially, the problem statement guarantees no structure on the function \(f\) other than periodicity, so we don't have much to work with. As is usually the case with problems in quantum computation, we assume that the function \(f\) is implemented by some black box with the action \(U(\ket x\ket y)=\ket x\ket{y\oplus f(x)}\).
We begin by preparing an input state of \(\ket{0^{2n}}\), i.e. \(2n\) copies of a qubit in the state \(\ket0\), with the first \(n\) qubits to act as the input register and the second \(n\) qubits to act as the output register. We perform a Hadamard transform on the first \(n\) qubits, just as we have done for our previous algorithms, to produce an equally weighted superposition of all the basis states of the input register. We have
Now, acting \(U_f\) on state (\(\ref{simon-input}\)) places all the values of \(f(x)\) in the output register, as in
What would happen if we measure the output register at this time? Well, we'd get some random value \(f(x_0)\), encoded in the binary string formed by the ensemble of output qubits. But we would also have a collapse of the entangled input register. If the function has period \(s = 0^n\) (i.e. it's not periodic on our domain) then we just get \(\ket{x_0}\) and learn very little. If however the state is periodic so \(s \neq 0^n\), the input register is now in a superposition of the two basis states \(\ket x\) for which \(f(x) = f(x_0)\). This looks like
Unfortunately this doesn't really do us any good since our measurement of \(f(x_0)\) was random and so our measurements on the input register will give random strings as well. Let's not measure the input register just yet. Instead let's leave it in this collapsed state and apply Hadamards to it. The input register is now
To reach this state we use equation (\(\ref{simon-needs-it}\)), introduced in section
This still looks a bit of a mess, but we have achieved something noteworthy. The amplitude of each distinct state \(\ket y\) is now \((−1)^{x_0y} (1 + (−1)^{sy})\), which is zero for any \(y\) with \(sy \bmod 2\neq 0\). This means we must measure some state of the input register for which \(sy \bmod 2 = 0\). After a few such measurements we will end up with a system of equations
This is just a system of linear equations. which is easily solved
Resource cost
But how many such \(y\)-measurements will we need to ensure an acceptable likelihood of calculating \(s\) correctly? It's hard to say because measurements of \(y\) are random, and so we may get the same result twice. It turns out that once we do enough measurements to get \(n−1\) distinct \(y\) values, then we have enough information to calculate \(s\) with certainty.
So we ask how many runs of this experiment we will need to measure \(n − 1\) distinct \(y\) values with reasonable probability. According to [26], the probability that we will fail to get a linearly independent set in any given run is less than 3/4, so running the experiment 20 times gives a failure probability of less than 1/100,000. So we can solve the problem with arbitrarily small error probability \(\varepsilon\) by running only O(\(n\)) times
By contrast, any classical algorithm is at best O(\(2^n\)). THis is because you only have two options for an unstructured function: you can either check cases systematically, or you can check them randomly. If you check them randomly you will need to make of order \(\sqrt N=\sqrt{2^n}\) attempts before you are likely to find a match. Checking systematically is no better, since in that case you might need to check order \(2^n/2\) elements before finding a match. In this case the quantum advantage is purely in the parallelism provided by superposition.
Unlike Deutsch-Josza, this algorithm provides a true separation between BPP and BQP, so it provides stronger evidence for quantum supremacy.
Shor's algorithm for factoring
First appearing in his 1994 paper [8], Peter Shor's algorithm for factoring uses quantum methods to break a large integer into a product of primes. Since the most ready application of factoring large integers is the breaking of RSA encryption, most accounts take the integer to have form \(N = pq\), both for pedagogical reasons and since this is the form of the integer of interest in the RSA scheme.
Shor's algorithm has already been proven effective in a physical proof of concept. In 2001 IBM famously used Shor's technique to show \(15 = 3 \times 5\), and more recently in 2012 the factorisation of \(21 = 3 \times 7\) was achieved [27]. Considerably larger numbers have been factored, but those were achieved by purpose-built machines not capable of general computation.
Since Shor's algorithm requires a little more number theory that those covered so far, we will make another brief mathematical diversion before embarking on the algorithm itself.
More mathematical preliminaries
The factoring problem is difficult for a classical computer, but it has some structure that renders it vulnerable to quantum attack. It shares many properties with Simon's problem, just discussed in section
This sequence eventually repeats, and as shown by Euler in the 1760s it does so in a predictable fashion for general \(x\) and \(N\). The number of iterations before a repetition is naturally called the period of this sequence. Euler showed us that if \(x \nmid p\) and \(x \nmid q\), then the period will be some integer which is a factor of \((p − 1)(q − 1)\).
Aaronson gives the example of \(N = 15,\ p = 3,\ q = 5\), which gives \((p − 1)(q − 1) = 8\). Then the powers of (e.g.) 2 modulo 15 are
so the period of the sequence is 4, which divides 8, as Euler would have predicted.
What good has this done? Well, so far all we've been able to learn is a divisor of \((p − 1)(q − 1)\), which doesn't seem very useful. But if we do this repeatedly by varying \(x\), we can learn several factors of \((p − 1)(q − 1)\) - potentially all of them. Though we could never be certain we really have all the factors we can now calculate \((p − 1)(q − 1)\) with a high probability of success.
The first major roadblock appears because we have no reason to expect to be so lucky that the period r will be small; in principle \(r\) may be of the same order as \(N\). We may need to calculate an awful lot of terms in the sequence \(x^a \bmod N\), each of which takes polynomial time. This is why the problem is difficult on classical architecture. However, if we bring our new quantum computational methodologies to bear we may be able to again take advantage of the parallelism provided by quantum superposition. We can build a quantum state that is a superposition of all of our \(x \bmod N\)s, and hopefully we can find some way to extract information about the period, which is a global property of the state (since it's a global property of the sequence).
To calculate all these terms we will take advantage of a method called repeated squaring. Since our \(N\) is large, we may need to calculate arbitrarily large powers of \(x\) before we even reach \(N\), let alone find a repeating pattern. You might wonder if calculating something like 7259 mod 34 is something we can do in a reasonable amount of time. After all, you'd expect multiplying \(x\) by itself 259 times or more to take quite a while no matter what kind of computer you're using. Luckily we don't need to, thanks to two facts.
- The powers of 2 grow very large very quickly, and
- We can modulo the calculation at intermediate steps, and the answer will still end up correct.
What I mean by point 2 is the following: say I want to calculate \(3^8\bmod 5\), these numbers chosen arbitrarily for the sake of example. I could calculate \(3^8\) by writing
but calculating this will take several steps, involve quite large numbers, and at the end I still need an efficient way to take the modulus by 5. If instead I write
which is a standard result from number theory, we could calculate like so:
At no point did we have to deal with any large numbers, and each step was an easy calcaultion. So by repeatedly squaring and taking modulo 5 at each step, we quickly reached an answer. Of course in this simple example the advantage is not necessarily significant, but the technique is readily applied to much larger powers where the advantage is more striking. Computers can compute this way very efficiently. The extreme example I gave earlier can be written as
so let's calculate all \(7^{2^x}\) up to \(2^x=256\):
I know all the calculations I skipped have result 1 because \(1^2=1\bmod 35\). We find
I'm not going ti ask you to do any more of these, but the ablilty to do this is key to Shor's algorithm so it's worth being aware of. The string link between algorithm design and number theory is inescapable.
Recipe
But assuming all of this is doable (it is), we still need some way to extract information about the period out of a state in a very complicated superposition. We can't just perform a raw measurement, since to get any useful information that way we'd need to very cleverly choose the right basis, which we can only do if we know the answer ahead of time. The problem will be solved by the quantum Fourier transform.
The problem can be stated thus: Given an odd
- We must be sure that \(N\) is itself not prime, or the algorithm will fail to find any factors. This is easy to check thanks to the existence of various primality checking algorithms, mentioned earlier, the details of which are not important for our purposes.
- We must be sure that \(N\) does not have the form \(N = p^x\) for some prime \(p\) and non-negative integer \(x\). Again, this is easy to check by by ensuring that \(N^{1/k}\) is not an integer for all \(k \leq \log_2 N\). This is a relatively small number even when \(N\) is large so does not take much time.
So luckily the failure modes of Shor's algorithm correspond to cases where the problem is easily solved anyway. As long as neither of these failure modes are in effect, it is guaranteed that \(N\) is the product of two distinct coprimes greater than unity, so we know that \(k\) exists. Now I claim that we can factor a number \(N\) using the following procedure:
- Choose a number \(N\) to factor.
- Choose a random number \(a\) which is less than \(N\).
- If \(\gcd(a,N)\neq 1\), which is easily checking by the Euclidean algorithm for greatest common divisor, then \(a\) is a factor and we are done.
- Else, perform a magic spell to find the period \(r\) of the function \(f(x)=a^x\bmod N\).
- If \(r\) is odd or if \(a^{r/2}\bmod N\equiv 1\) or -1, return to step 2 and choose another \(a\).
- Otherwise, \(\gcd(a^{r/2}\pm 1, N)\) are both factors of \(N\) and we are finished.
- (If none of the results of step 6 are non-prime, adopt that number as a new \(N\) and return to step 1 to factor it.)
These steps have reduced the problem of factoring to one of period finding, which we are able to solve efficiently on a quantum computer. Nielsen and Chuang [19] have an appendix which explains in more detail why this reduction works. Several of these steps will likely require explanation, but one in particular probably feels a little off. The magic spell I refer to in step 4 is of course where we exploit the full quantum Fourier transform. The large majority of this section will be dedicated to the details of step 4, and we won't worry too much about the number theory.
Magic spell
First I'll write down the incantation in step form, and then will explain some important steps in a little more detail. We have our number \(N\) to be factored, we have our random integer \(a\), and we have \(f(x) = a^x \bmod N\). Next:
- Choose a number \(q: N^2 \leq 2^q \lt 2N^2\), and define \(Q \equiv 2^q\). This guarantees that more than one period is passed in the range \(\{0,\dots , Q\}\), since the period in principle can be roughly as large as \(N\). This implies that \(Q/r\lt N\), recalling that \(r\) is the period we're searching for.
- Initialize the state
$$ \begin{equation} \frac{1}{\sqrt Q}\sum_{x=0}^{Q-1}\ket x\ket{0^q}. \end{equation} $$That is, \(2q\) qubits forming an input register \(\sum^{Q−1}_{x=0}\ket x\) and an output register \(\ket{0^q}\). We've seen how to do this a few times now; it's just a load of Hadamard gates on the input register.
- Use a provided black box to compute \(f(x) = a^x \bmod N\) (probably by repeated squaring) to produce the state
$$ \begin{equation} \frac{1}{\sqrt Q}\sum_{x=0}^{Q-1}\ket x\ket{f(x)}. \end{equation} $$Again, this was explained and defined in section
header-algorithms-and-oracles . The input and output registers are now entangled. - Now the key step: do a quantum Fourier transform of the input register to get the state
$$ \begin{equation} \frac1Q\sum_{x=0}^{Q-1}\sum_{y=0}^{Q-1}\omega^{xy}\ket y\ket{f(x)}. \end{equation} $$The extra factor of \(1/\sqrt Q\) comes from the quantum Fourier transform, and \(\omega\) is the first \(Q\)th root of unity, all as discussed in section
header-quantum-fourier-transform o the quantum Fourier transform. - Measure the output register to obtain some random value \(z\), encoded as usual as a binary string on the qubit ensemble. Since the input and output registers are entangled, the input register is now in a superposition of only those basis states for which \(f(x)=z\), so our state is now
$$ \begin{equation} \frac1Q\sum_{y=0}^{Q-1}\sum_{x:f(x)=z}\omega^{xy}\ket y\ket z. \end{equation} $$Thus, for any particular \(y\), the amplitude of the state \(\ket y \ket z\) is$$\begin{equation} \frac1Q\sum_{x:f(x)=z}\omega^{xy}. \end{equation}$$Recall that \(\omega = \exp(2\pi i/Q)\). This means that for any \(\ket y\) for which \(y\) is a multiple of \(Q/r\), the complex amplitudes for that state will interfere construtively leading to a relatively high probability of measurement, while all others interfere destructively. More on this later. Thus if we measure the input register at this stage we have a high probability of measuring one of the states \(\ket y\) for which \(y = kQ/r\) for \(k \in \mathbb Z\). Collecting enough such \(y\) values enables calculation of \(Q/r\) with high confidence.
- Use the method of convergents of continued fractions, or another method, to calculate \(r\) from \(Q/r\).
Shor's algorithm example
Since all of this abstract mathematics is a little hard to parse, let's work through an example. Since Shor's algorithm was famously used to factor the number 15, we might as well choose \(N = 15\). Before we start I might as well tell you that the period is going to be \(r = 4\), so you can keep an eye out for it and follow the calculations a little better. Most steps are easily checked for small numbers like this.
- Let \(N = 15\), and then we randomly select \(a = 7\). Now \(N^2 = 225\) and \(2N^2 = 550\), and we want our \(Q = 2^q\) to be a power of 2 between these two values. Therefore choose \(Q = 2^q = 256 = 2^8\).
- Prepare the state
$$ \begin{equation} \ket{\psi_0}= \frac{1}{\sqrt{256}}\left(\ket{0,0}+\ket{1,0}+\ket{2,0}+\dots+\ket{255,0}\right). \end{equation} $$Hopefully by now we understand that this is acheived by applying the Hadamard transform to a collection of qubites in state \(\ket0\).
- Apply the unitary black box, which applies the function \(f(x)=a^x\bmod N=7^x\bmod15\). Our state is transformed to
$$ \begin{align} \ket{\psi_1} &=\frac{1}{\sqrt{256}}\left(\ket{0,7^0\bmod 15}+\ket{1,7^1\bmod 15}+\ket{2,7^2\bmod 15}+\dots+\ket{255,7^{255}\bmod 15}\right) \\[1em] &= \frac{1}{\sqrt{256}}\left(\ket{0,1}+\ket{1,7}+\ket{2,4}+\dots+\ket{255,13}\right). \end{align} $$
- Apply a quantum Fourier transform to the input register. The full state becomes
$$ \begin{equation} \ket{\psi_2}= \frac{1}{256}\left( \sum_{y=0}^{255}\ket{y,1} + \sum_{y=0}^{255}\omega^{y}\ket{y,7} + \sum_{y=0}^{255}\omega^{2y}\ket{y,4} + \dots + \sum_{y=0}^{255}\omega^{255y}\ket{y,13} \right). \end{equation} $$
- Measure the output register. We're guaranteed to get one of the values 1, 4, 7, 13, since they are the only remainders of 7 mod 15. Let's say we measure 7; our state is now
$$ \begin{equation} \ket{\psi_3} =\frac{1}{\sqrt{64}}\frac{1}{\sqrt{256}}\left( \sum\omega^{y}\ket{y,7} +\sum\omega^{5y}\ket{y,7} +\sum\omega^{9y}\ket{y,7} +\dots +\sum\omega^{253y}\ket{y,7} \right). \end{equation} $$The new normalisation constant emerges because the measurement removes three quarters of the possible output register states. The amplitude for any distinct input register state \(\ket y\) is now \(\sum_{c=0}^{63}\omega^{(4c+1)y}/\sqrt{64}\). If \(y\) is anything other than a multiple of \(Q/r\) then these complex vectors will orbit the complex plane and in this case will fully cancel out - generally the cancellation is not necessarily total. If \(y\) is a multiple of \(Q/r\), then the amplitude is amplified. The reason for this is that \(\omega^{64n\cdot 4c}=e^{2\pi inc}=1\), while for any \(y\neq 64\) or a multiple thereof, the numbers \(\omega^{y\cdot 4c}\) are vectors pointing in a variety of directions in the complex plane.
- So, with certainty we measure some \(y\) which is a multiple of \(Q/r\). How then do we calculate \(r\) itself? For this, we would generally use the continued fraction expansion method, taking the final convergent for which the denominator is less than \(N\), and using this denominator as a candidate for \(r\). However in this case it just so happens that \(r\) is a power of 2 so it exactly divides \(Q\), and emerges quite easily because we know \(Q\) and can calculate \(Q/r \in\mathbb Z\).
- Return this \(r\) to the classical part of the algorithm.
$$ \begin{equation} \gcd(7^{4/2}+1,15)=5,\quad \gcd(7^{4/2}-1,15)=3. \end{equation} $$So the prime factors of 15 are 3 and 5.
Other avenues
The following sections are intended to serve as a brief sample of other areas of study. As such the mathematics will not necessarily be as rigorous as in previous sections and I will be more liberal in my assumptions.
Quantum error correction
Numerous times throughout this document we have made reference to the fact that quantum systems are inherently delicate, and that this delicacy must be managed if we are to build useful quantum computers. How is this to be done? Leaving aside for now the natural fault-tolerance of topological quantum computers, which still face numerous questions (not least of which is whether the requisite particles actually exist!), this section will discuss various error-correcting codes which can be used to protect quantum information. Different codes exist for different types of errors. We will not consider them all. We'll start with simple repetition codes in section
Repetition codes and syndrome measurements
These may be familiar to some readers, but we will discuss them briefly since they are the easiest quantum error-correcting codes to explain and understand. They rely upon encoding a physical qubit in the state \(\ket{0}\) or \(\ket{1}\) into a logical qubit \(\ket{0_L}\) or \(\ket{1_L}\). This really is done in the simple way you might naively expect, where
You see that a single physical qubit is represented by any number of additional physical qubits which together represent a logical qubit. This is actually very easy to achieve theoretically, and it's worth showing how since the no-cloning theorem might make you suspicious. The general circuit is shown in
The idea here is that if some error occurs to change the value of one of the qubits we use to encode, we can still recover the original information by something like a majority vote. Of course we can't just read the values of all of the encoding qubits since that would destroy the information contained in the state, but we can do what is called a syndrome measurement. This is a type of measurement that reveals exactly zero information about the state, thus causing no collapse, while still allowing us to know whether a bit flip has occurred. Nielsen and Chuang [19] give the example of the syndrome measurement for an encoding using three physical qubits. We have the state \(a\ket{000}+b\ket{111}\), and the four (including identity) possible bit flip errors would produce one of
assuming only a single qubit was affected. Notice that any measurement of any single qubit fails to tell us what the state is, e.g. if we measure \(\ket0\) for the second qubit, we learn nothing since any of these states contains some probability of that measurement. More generally we can define a notion of distance \(d\), which tells us how many qubits we can measure without disturbing the state. In this example \(d = 1\).
But how does this tell us which error has occurred, if any? We define the projection measures \(P_0, P_1, P_2, P_3\), where \(P_0\) is the projection operator corresponding to no error so \(P_0 = \ket{000}\bra{000} + \ket{111}\bra{111}\), and \(P_1\) corresponds to an error in the first qubit, etc., so we have the following matrices:
These are orthogonal operators producing orthogonal states, meaning they are distinguishable by measurement. It is not hard to check that
so the projection measure will be equal to zero in all bases except that where the error has occurred. Note that we have only learned what the basis states of our full state are, and still have no information about the amplitudes \(a\) or \(b\), so the state is intact but we know which qubit has flipped (again assuming only a single error). It is then a simple matter to apply an \(X\) gate to the appropriate physical qubit and undo the error, recovering the original logical qubit. If more than one qubit has erred, then this procedure will fail.
Note that all of this is easily generalizable to any number of encoding qubits per our original definition in equation (\(\ref{logical-qubits}\)). However it all rests upon the assumption that the probability of an error is small enough that we may assume at most one error has occurred. This is only realistic if we can make our channels reasonably clean in the first place. Great progress is being made towards producing low-noise gates and channels, so this is no longer the unreasonable assumption it may once have appeared.
It is also possible to correct phase flip errors this way. A phase flip error is the accidental application of a \(Z\) transform, by which \(\ket{0}\mapsto\ket{0}\) and \(\ket{1}\mapsto-\ket{1}\). We can use the same code we've just described because
which is to be considered as the NOT operation in the Hadamard basis. Effectively then we just apply Hadamard gates to each qubit in
It is interesting to note that the bit flip code is inspired by a simple instance of a classical error-correcting code, and with only those modifications which were strictly necessary to make it work in the quantum case we discover a way to correct an error that has no counterpart in the classical world, the phase flip.
We have corrected \(X\) and \(Z\) codes, but what about \(Y\)? According to Preskill [17] and others it is true that we can correct against \(Y\) errors thanks to the fact that \(Y\sim XZ\). I will assume but not prove this. And further, we can show that protecting against all three of these errors in principle allows us to correct against an arbitrary combination of them, provided only a single qubit is affected. This is thanks to the linearity of quantum mechanical operators.
Let \(C\) be an error-correcting operator, which can correct against any \(X\), \(Y\) , or \(Z\) error on a single qubit. We define \(X_n\) to be the \(X\) error acting on qubit \(n\), and so on. We have
So \(C\) corrects all three error types and leaves the no-error state alone. The \(\ket j\) qubits are junk present to serve as workspace, and they are transformed into \(\ket{j'}\) by the correction procedure. It would be impossible to have a unitary operator with the desired action without work qubits, and this should be clear with a little thought. The state of the junk qubits is presumably corrupted by the error-correcting process, but we don't care about their state. If we now introduce a unitary error \(\tilde U\), defined by
it should be clear that our procedure \(C\) corrects this error, thanks only to the linearity of operators:
In the final equality the phase constants \(\varepsilon_i\) have been associated with the junk qubits, which I have suppressed here for clarity. Any additional phases introduced by the error correction procedure are also kicked back to the junk qubits.
So if we can correct against \(X\), \(Y\) and \(Z\) errors we can correct against arbitrary errors, but I've said nothing so far about what kind of code would achieve this. We'll see one such code now.
The Shor error-correcting code
What happens if we experience a bit-flip and a phase-flip error? Although the bit-flip (equivalently phase-flip) code above can correct either, it cannot correct both. Shor proposed a more general error-correcting code in 1995 [28], shortly after his famous algorithms.
To implement the Shor code, we must encode our state in some larger number of physical qubits just as before. We will assume the use of three qubits at each encoding step, for ease of explanation. Again, this code generalizes easily and naturally to allow more redundancy. We first encode our physical qubits according to
where \(\{\ket{+},\ket{-}\}\) is the usual Hadamard basis. We then encode each of these according to the bit flip code discussed in the previous section so
All in all then we use nine qubits to encode a single physical qubit, and this time our logical \(\ket0\) and logical \(\ket1\) are
The circuit for this error-correction technique, in
What about \(Z\) transforms? It is not a priori obvious that we can execute both levels of this code independently. So far we have only corrected a bit flip. But the bit flip code is insensitive to phase changes, easily checkable, so if a \(Z\) error has occurred, it is still intact. If we now decode from nine to three qubits, so move onto the basis \(\{\ket{+++},\ket{---}\}\), and apply the phase error correction procedure, a \(Z\) transform will be detected and repaired.
Recall we are assuming that correcting X and Z errors amounts to correcting a \(XZ \sim Y\) error, so the Shor code can protect against any error.
Something might have been nagging at you throughout our discussion of these codes, and that's our use of phrases like 'if an error occurs'. Is this a reasonable phrase to utter when discussing quantum mechanical systems? Not really. Just as in any other quantum system, the full state exists in a superposition \(\alpha_0\ket{\psi^\text{clean}}+\sum_i\alpha_i\ket{\psi_i^\text{error}}\). The state after transmission through a channel has some amplitude of being the clean state and some amplitude(s) of being an error state. Then our syndrome measurement is not actually certain to find the error at all. Nevertheless, this procedure offers a non-zero chance of detecting and correcting an error, so it is certainly an improvement on transmitting unencoded/unprotected qubits.
Threshold theorem
In 1996, Shor made yet another major contribution to the field by showing that we can build arbitrarily large circuits, provided the accuracy of individual components can be made sufficiently high.
The threshold theorem states that a physical quantum computer can accurately simulate an ideal quantum computer provided the noise level is below a certain threshold. By simulate, we mean encode the noisy physical qubits as logical qubits which then form the basis of our ideal quantum computer. The exact value of this threshold is not known but bounds have been placed on it. It is normally taken to be approximately one failure in 1000 gate operations, or 99.9% reliable.
Topological quantum computation
A fundamentally different approach to the 'conventional' qubits we normally think about, topological quantum computation hypothetically allows naturally fault-tolerant computation. That is, the stability of the qubits is guaranteed directly by the physics, rather than enforced by experimental care and active error correction.
First proposed by Alexei Kitaev in 1997 [29], topological quantum computing attempts to construct a naturally fault-tolerant computer by encoding information in non-local properties of a material, i.e. topological invariants. The easiest example of a topological invariant is probably the genus (number of holes) of a manifold. It's easy to see that a doughnut retains the same genus even when subjected to quite serious deformations - you would need to cut the manifold to change the genus - so the genus number is a topological invariant. The hope is that these non-locally encoded qubits will be virtually immune to local disturbances that would cause conventional qubits to decohere. If we could encode our \(\ket0\) in a doughnut, and our \(\ket1\) in a football, it is easy to see that they would be insensitive to minor deformations. Of course we'll need to be a little more sophisticated than that!
Topological quantum computing proposes to achieve this encoding by manipulating particles known as anyons. Anyons are excitations of a 2-dimensional medium, so are considered elementary quasi-particles in contrast to things like elections, which are excitations of a 3-dimensional vacuum and are true elementary particles. Of course we don't live in a 2-dimensional universe, but modern materials science is able to produce what are essentially planar materials
The name anyon - pronounced 'any-on' - is owed to the fact that particle exchange can introduce an arbitrary (any) phase on the state of a system. You probably remember from you first course in quantum mechanics that exchanging the spatial position of two particles in a wave function introduces either unit or negative unit phase, depending on whether they are bosons or fermions. You might also be aware of the connection with the spin-statistics theorem. Wilzcek showed that the Fermi and Bose statistics we are accustomed to are actually extreme ends of a continuum, and that anyons obey statistics interpolating these two. The particles have the properties outlined in table 1. Importantly, all acquirable phases square to the identity, so there is no difference to the physics upon exchanging identical particles.
These phases arise due to the fact that in three spatial dimensions, all exchange paths are isotopic - any path can be deformed into any other. This is not true in two spatial dimensions. Here, two paths may not be isotopic, in particular because one path \(A\) may entirely enclose another path \(B\), so is not in the same homotopy class as a path \(A'\) which does not enclose \(B\). This implies that the path taken to execute an exchange is physically meaningful.
To construct the topological invariants we need, we braid the world lines of these anyons. A braid is a mathematical object related to a knot, and one of the reasons we wish to work in three (2 + 1) dimensions is that we can create non-trivial braids of zerodimensional objects with 1-dimensional world lines, but this is not possible in four (3 + 1) dimensions, where any braid of 1-dimensional strands is trivial in the sense that they are all equivalent to the identity, i,e. they can all be unwound without cutting or moving ends.
A braid really is the simple object you might imagine, and examples are shown in
- Initialize the computer by encoding qubits on the anyons, arranged on a 2-dimensional lattice.
- Apply quantum gates by braiding the word lines of the anyons.
- Read the final state of the anyons, again stored in a regular 2-dimensional lattice, by fusing them.
The initialization takes a set of different types of anyons and arranges them to encode data. It's not hard to imagine, at least in principle, how we could compute by braiding. A particular operation might correspond to particular pair-twist of the type shown in
So far we haven't spoken much about the physics of anyons. We do so in the next section.
Majorana fermions
Majorana fermions are one proposed physical realization of anyons. A Majorana fermion is a quasi-particle related to the Dirac fermion. These quasi-particles were first proposed by Italian physicist Ettore Majorana in 1937. They are not fundamental particles like electrons, but rather an emergent behaviour of ensembles of other particles that can behave in ways reminiscent of fundamental particles. In this way they are not dissimilar to holes in solid state physics, which are simply the absence of electrons but can behave like fundamental particles with positive charge. A bound pair of Majorana fermions comprises a non-Abelian anyon. The term non-Abelian here refers to the particular statistics obeyed by the anyons, and these are the type of interest for topological quantum computers.
Majorana fermions are distinguished from the usual Dirac fermions in that they are solutions to the Majorana equation, a real variant of the Dirac wave equation. Here when we say real we mean that the solutions to the equation are strictly real-valued, rather than complex as in the Dirac equation. This is the source of some unusual behaviour, for example the fact that real numbers are self-conjugate leads to Majorana particles being their own antiparticles, which is a property we need in anyons. Furthermore, because Majorana particles are their own antiparticles they must have zero electric charge so that charge can be conserved in annihilation events. This is reminiscent of neutrinos, and indeed neutrinos are the only standard model fermion which has not been ruled out as a candidate Majorana fermion.
Bound pairs of Majorana fermions are in general spatially disparate and it is this property that allows us to encode information in a topological way. As they are non-local excitations, they are naturally resistant to local noise sources such as thermal photons. This may sound like an exotic state of matter, but actually these topological degrees of freedom have already been observed in things like the quantum Hall effect, wherein a semi-conductor state in a strong magnetic field is insensitive to local disturbances.
Topological quantum computation is mathematically equivalent to the circuit model we have just learned about in some depth, but is fundamentally more resistant to decoherence. For this reason it is thought by many that topological quantum computing is a good candidate for development into naturally fault-tolerant universal quantum computation. Though it cannot protect against all sources of error, it may provide us with a more stable foundation to work from.
Conclusions
What we have discovered is a variety of quantum algorithms which almost undeniably show supremacy over any classical counterparts. I say almost because much of complexity theory is unproven, and as mathematicians we should always be wary of unproven conjectures, however trusted they are and however obvious they may seem. In many of our results it seems impossible to imagine how a classical algorithm could match our quantum approach, but we should acknowledge that this may simply be failure of imagination.
Some quantum speed-ups are more significant that others. In the case of Grover's algorithm, we only managed to achieve a quadratic improvement in speed - O(\(2^n\)) in the classical case, and O(\(\sqrt{2^n}\)) in the quantum case. Relatively small speed ups like this are only useful on the condition that our quantum computers are comprised of components with a similar speed to modern classical components. This is still a long way off, and will probably require several more decades of research and engineering.
However in the case of Shor's algorithm we gain a much more dramatic exponential improvement, which means that quantum computer components don't necessarily have to work very quickly to provide an advantage. For problems like Deutsch-Jozsa in section
The results of topological quantum computing and quantum error correction provide hope that effective quantum computers can be built despite the the fact that we normally consider the quantum realm to be inherently delicate. It seems that the current theoretical and future practical supremacy of quantum computation over classical computation is all but assured.
References
- IBM Q. Online quantum computer. [Accessed August 2017: http://researchweb.watson.ibm.com/ibm-q/].
- A Turing. On computable numbers, with an application to the entscheidungsproblem. in, m. davis (ed.) the undecidable (pp. 116-151), 1937.
- David Deutsch. Quantum theory, the church-turing principle and the universal quantum computer. In Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, volume 400, pages 97–117. The Royal Society, 1985.
- B Wells. A universal turing machine can run on a cluster of colossi. In Abstracts Amer. Math. Soc, volume 25, page 441, 2004.
- Stephen Wiesner. Conjugate coding. ACM Sigact News, 15(1):78–88, 1983.
- Richard P Feynman. Simulating physics with computers. International journal of theoretical physics, 21(6):467–488, 1982.
- David Deutsch and Richard Jozsa. Rapid solution of problems by quantum computation. In Proceedings of the Royal Society of London A: Mathematical, Physical and Engineering Sciences, volume 439, pages 553–558. The Royal Society, 1992.
- Peter W Shor. Algorithms for quantum computation: Discrete logarithms and factoring. In Foundations of Computer Science, 1994 Proceedings., 35th Annual Symposium on, pages 124–134. Ieee, 1994.
- David G Cory, Amr F Fahmy, and Timothy F Havel. Ensemble quantum computing by nmr spectroscopy. Proceedings of the National Academy of Sciences, 94(5):1634–1639, 1997.
- ] David P DiVincenzo et al. The physical implementation of quantum computation. arXiv preprint quant-ph/0002077, 2000.
- Thomas H¨aner and Damian S Steiger. 0.5 petabyte simulation of a 45-qubit quantum circuit. arXiv preprint arXiv:1704.01127, 2017.
- Patrick Hayden. The quantum computational universe. [Accessed July 2017: https://www.youtube.com/watch?v=AqWuyeh0SxQ].
- Scott Aaronson. Quantum computing since Democritus. Cambridge University Press, 2013.
- John S Bell. On the einstein podolsky rosen paradox. 1964.
- DGBJ Dieks. Communication by epr devices. Physics Letters A, 92(6):271–272, 1982.
- Yaoyun Shi. Both toffoli and controlled-not need little help to do universal quantum computation. arXiv preprint quant-ph/0205115, 2002.
- John Preskill. Lecture notes for physics 229: Quantum information and computation. California Institute of Technology, 16, 1998.
- Chi-Kwong Li, Rebecca Roberts, and Xiaoyan Yin. Decomposition of unitary matrices and quantum gates. International Journal of Quantum Information, 11(01):1350015, 2013.
- Michael A Nielsen and Isaac Chuang. Quantum computation and quantum information, 2002.
- Amit Hagar and Michael Cuffaro. Quantum computing. In The Stanford Encyclopedia of Philosophy. Metaphysics Research Lab, Stanford University, spring 2017 edition, 2017. [https://plato.stanford.edu/archives/ spr2017/entries/qt-quantcomp/ accessed July 2017].
- Michael O Rabin. Probabilistic algorithm for testing primality. Journal of number theory, 12(1):128–138, 1980.
- JP Leaao. Reversibility and measurement in quantum computing. Superlattices and microstructures, 23(3-4):433–444, 1998.
- Lov K Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219. ACM, 1996.
- Umesh Vazirani. Quantum mechanics and quantum computation. edX, 2013. [Online; accessed 5-August-2017].
- DR Simon. On the power of quantum computation. In Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pages 116–123. IEEE Computer Society, 1994.
- John Watrous. Introduction to quantum computing, 2006. [Accessed July 2017: https://cs.uwaterloo.ca/ watrous/LectureNotes.html].
- Enrique Martin-Lopez, Anthony Laing, Thomas Lawson, Roberto Alvarez, Xiao-Qi Zhou, and Jeremy L O'brien. Experimental realization of shor's quantum factoring algorithm using qubit recycling. Nature Photonics, 6(11):773–776, 2012.
- Peter W Shor. Scheme for reducing decoherence in quantum computer memory. Physical review A, 52(4):R2493, 1995.
- A Yu Kitaev. Fault-tolerant quantum computation by anyons. Annals of Physics, 303(1):2–30, 2003.