Most of us have heard something about quantum computing, but many of the popular accounts are misleading, giving the impression that quantum computing is somewhat analogous to parallel computing. The truth is very different and a lot more interesting.
Quantum computing is more fundamental than classical computing. The qubit is a more fundamental object than the bit - anything you can do with bits you can do with qubits, but there are things you can do with qubits that have no classical counterpart. You do need to use mathematics to describe what is going on, but the mathematics is really not difficult to learn and use. Once mastered it opens the way to seeing some beautiful and counter-intuitive ideas. Quantum computing introduces some of the most surprising concepts of quantum mechanics, but in a simple and precise way.
Qubits
The basic unit of classical computing is the bit - it is either zero or one. Bits can be represented by switches that are either in the on or off position. In quantum computing, the basic unit is the qubit. In quantum computing, the basic unit is the qubit. There are two basic qubits that we denote by |0> and by |1>. (Mathematically, these are vectors.)
We can also put qubits in a superposition of states to obtain qubits of the form a|0>+b|1>, where a and b can be any two numbers with the property that the sum of their squares is 1. Qubits can be represented by spins of electrons or by polarizations of photons. Unfortunately, these are not part of our everyday experience, so rather than explain the connection, we will just describe how we work with them.
The first important point is that to get a readout of the result of a computation we must make a measurement of the qubits. When we measure a qubit of the form a|0>+b|1> it changes - it jumps to |0> or to |1> and we extract a bit, not a qubit, of information, i.e. we read off 0 or 1. The probability that the qubit jumps to |0> and we read off 0 is given by the square of a; the probability that we get 1 is the square of b. This, of course, is quite unlike bits where reading off the value of a bit does not affect the bit in any way.
Quantum gates
Two classical gates are the NOT and the AND gate. We input bits and get bits out. Quantum gates are somewhat analogous - we input qubits and get qubits output. One big difference is that quantum gates are invertible, if we are told what the output is, we can calculate the input. For example, the classical NOT gate is invertible - if we get 0 as output, we know that 1 must have been input. But AND is not invertible, if we receive 0 as the output, the input could have been one of three possibilities: 00, 01 or 10. A consequence of requiring invertibility is that a quantum gate must output exactly the same number of qubits as input.
Another important point that needs to be stressed is that when we send qubits through quantum gates no measurements are made. There is no jumping of states.
Earlier we pointed out that a general qubit has the form a|0>+b|1> and that when we measure it we get 0 output with probability the square of a and 1 output with probability the square of b. The numbers a and b do not have to be positive, they can be negative. If a|0>+b|1> is a qubit, then a|0>-b|1> will also be a qubit. If we add these qubits, we will cancel the part that involves |1>. This explanation is a little vague, but it corresponds to the idea of constructive and destructive interference of waves.
Entanglement
Another important quantum gate is the CNOT gate. It takes two qubits as input, and gives two qubits as output. The reason for this gate’s importance is that it enables us to entangle qubits. This is a quantum phenomenon which has no everyday counterpart, so we will examine an example - a pair of entangled qubits in the state a|00>+b|11>. For this example, we have two qubits that could be very far apart. Perhaps I have one and you have the other. The actual objects might be photons and we will each measure the polarization of our photon.
When we make the measurements, we both get exactly the same result - we both get 0 or we both get 1. The probability we get 0 is the square of a and the probability we get 1 is the square of b. What makes entanglement so surprising is that the qubits don’t jump to |0> or to |1> until the first measurement is made. As soon as the first measurement is made both qubits are changed. This is what Einstein famously thought wrong and referred to as ‘spooky action at a distance’. Various experiments have shown that entanglement is real. It also has applications.
One use for entanglement is in for key distribution in encryption. Suppose that you and I want to communicate securely. We want to use an encryption method that uses a key - a large number, or, equivalently, a long string of 0s and 1s. The first thing we need to do is to construct a shared key in such a way that we know has not been intercepted by a third party. Quantum entanglement enables us to do that by sharing and then measuring a large number of entangled qubits. If nobody intercepts our qubits we both end up with exactly the same string of randomly generated bits. If someone intercepts and measures our qubits we won’t end up with the same string.
Consequently, we can compare half of our string of numbers to tell whether or not there is an interloper and, if there is not, use the second half as our key.
Another application is to quantum teleportation. Suppose that you and I have a pair of entangled qubits. Then someone gives you third qubit in an unknown state a|0>+b|1>. Neither of us know the values of a and b. We want to change the state of my qubit to become a|0>+b|1>. This can be done by you sending both the qubits in your possession through a CNOT gate. This entangles all three qubits. You then measure your two qubits obtaining one of four possibilities: 00, 01, 10 or 11.
The mathematics shows that my qubit ends up in one of four possible states: a|0>+b|1>, a|0>-b|1>, b|0>+a|1> or b|0>-a|1>. You send me the results of your measurements. Each of the four cases for your measurements corresponds to one of the four possibilities for my qubit. Once I know which qubit I have, I can send it through a gate that sends it to a|0>+b|1>. The result is that I end up with a qubit in the unknown state. The state has been ‘teleported’ from you to me.
Though this sounds like science fiction this has been performed many times. An amazing example is that of a Chinese team who teleported a qubit from Earth to a satellite in low Earth orbit.
Quantum circuits
Classical circuits consist of gates and wires connecting them. We input bits on the left and read the results on the right. Quantum circuits are similar. They consist of wires and quantum gates. We input qubits on the left. To get information out of the circuit we have to measure the qubits on the right. When we measure a qubit it jumps to a new state and we get a bit output.
We can do everything with a quantum circuit that we can do with a classical circuit, so quantum computations contain all classical ones. Quantum circuits enable us to put qubits into a superposition of states and to entangle them. These are two things that we cannot do with classical bits. So we have more operations available to us, but are these useful?
Quantum algorithms
All quantum gates are invertible. A consequence of this is that up until we make the measurements of qubits, the whole computation is invertible. The entire computation can be represented by one matrix. This matrix can be thought of as giving another way of ‘viewing’ the initial problem - analogous to a change of coordinates. To get quantum speedup there has to be some structure in the initial problem that becomes apparent with one of these quantum viewpoints that is not available using classical ones.
We are far from the description given in many popular accounts where quantum computing is described as being like parallel computing. In many descriptions, it sounds as though all NP problems can be solved in polynomial time on quantum computers. This is far from the case. In fact, it is not initially obvious that there are any problems that can be solved more quickly using a quantum computer. David Deutsch in a landmark paper showed that there is one!
Deutsch, in 1985, showed that a certain problem could be solved more quickly using a quantum algorithm than using any classical one. The problem was highly contrived, designed specifically to show that quantum speedup was real - at least in this one case - it was not meant to be a practically useful algorithm. However, this was the first step in showing that quantum computers might have some advantages over classical ones.
Another major step forward was in 1994 when Peter Shor published his algorithm. This algorithm showed how quantum speedup could be used to factor products of large primes. This has practical consequences. He showed that many of the standard internet encryption techniques (RSA, for example) could be easily broken once quantum computers could be built. This paper spurred interest in both designing an actual quantum computer and in designing new encryption techniques that could withstand attacks from quantum computers.
Peter Shor also showed that you could also correct errors in quantum computations. This has tremendous practical applications. All known ways of physically representing qubits and manipulating them are error prone. Quantum computers are often cooled to extremely low temperatures and shielded from electromagnetic fields, but it is hard to stop errors from creeping in. Shor designed an extremely ingenious method of correcting errors in certain cases. This showed that it might be possible to actually build a physical quantum computer.
The future
Chemistry at its most basic consists of quantum phenomena. Simulating quantum phenomena using quantum computers seems to make a lot of sense and looks as though it has a lot of promise. Secure communication is another area in which there has been substantial progress in recent years. There is talk of the quantum internet. However, the major change that I am most excited about, and is almost here, is in who will have access and understand quantum computing. Up until now it has been the realm of the specialist with graduate degrees. That is going to change.
Quantum computing involves quantum phenomena - superpositions and entanglement - that are not things we experience in our daily lives and so cannot easily describe using words. However, they can be described accurately using mathematics. Many of the pioneers of the subject come from backgrounds in quantum mechanics and are comfortable with sophisticated mathematical ideas. However, the basic mathematics needed for quantum computing is accessible to anyone who is comfortable with high school algebra.
IBM has recently put a quantum computer in the cloud. It has a nice graphical interface and is free to use. It only has five qubits, so it is not going to solve large practical problems, but it is the ideal size to play with. I’ve posted a very short guide to using the IBM Quantum Computer.
It is still early in the history of quantum computing, but we have now reached the point when we can all understand the theory and start to use our first quantum computer.
