Quantum computing has the potential to revolutionize technology, science and many other areas of our lives. This primer simplifies a complex subject, and reveals how and why it could be so disruptive. In future reports, we will examine the state of the art and barriers to real implementation.
The 451 Take
Quantum computing is very much a cutting-edge technology, and isn't likely to be in our smartphones anytime soon. But it does have huge disruptive power if it can be developed beyond experimentation and into practical use. Imagine how the internet and our lives would change if the likes of IBM announced that it could crack RSA encryption? Or if mathematical or engineering puzzles once thought unsolvable in our lives could be performed overnight? It is early yet, but it needs to be tracked because it would be a real game-changer. Physicists' skin would crawl at this simple visualization, but traditional computers cycle through options to determine an output; quantum computers allow a chart of all output to be created within the uncertainty of subatomic particles. It is this ability to create all options at once and then examine the certainty of these options happening, as opposed to having to examine all options individually, that gives quantum computing the potential to solve some puzzles faster than ever before.
Consider a thought experiment involving a cat – Schrödinger's cat. The cat is placed a in box, along with a radioactive material. When a sensor detects the radioactive material has radiated a particle, a device releases toxic gas into the box, killing the poor cat. We put the cat into the box alive, close the lid and wait. Is the cat alive or dead?
There is no way of knowing unless we measure the cat's state. We could open the box, acoustically listen for movements or x-ray the box. But these are all measurements, and we genuinely have no way of knowing if the cat is alive or dead unless we penetrate the box using such measurements. We can determine the probability of the cat being alive or dead after a certain time, but we can never be certain. Even if we knew everything about the state of the radioactive element before the cat goes in, we would not be able to know for sure when the fatal radioactive particle is released – in other words, the atomic and subatomic particles that determine when a radioactive particle is released have inherent unpredictability. In essence, until we measure, the cat is both alive and dead, in a state of what is called superimposition.
At the subatomic level, this is actually the case – some particles don't necessarily have an absolute state, which led to Einstein's quote, "God doesn't play dice." He couldn't accept that some things are just inherently unpredictable. Even if we have all the data there is, we cannot determine what will come next. In the vacuum of space, particles can appear out of nowhere and disappear within millionths of a second because of this inherent unpredictability. It is this superimposition of all possibilities due to inherent uncertainty that gives quantum computing its potential.
The Quantum Machine
In computing, binary digits (or bits) are used to represent data: 0 or 1. In quantum computing, qubits are used, and these can represent 0, 1 or a superimposition of 0 and 1. Until the qubit is measured, it is both 0 and 1, just like our cat is both alive and dead. It is this superimposition that gives quantum computing an advantage over traditional computing (or Turing machines, more technically). If we have to store the state of all three bit numbers in a register to be processed, then we need to store and process all successive states: [000,001,010, etc.], which in decimal represents [0,1,2...] in classical computing. But the same situation for three qubits is simply [???], with '?' representing a superimposition of both 0 and 1. If we are trying to hack security keys, for example, rather than having to go through every possible bit combination using a Turing machine, we can just try and determine it once from the superimposed qubits. [???] represents all combinations in a Quantum computer that in a Turing machine would be [000,001,010,011,100,101,110,111].
A qubit is physically a subatomic particle, perhaps a photon (a packet of light) or an electron (the basis of electricity). In the case of an electron, angular momentum, or 'spin,' is used to differentiate between 0 and 1, typically 'up' spin and 'down' spin. In most Turing computers today, five volts represents 1, and 0 volts represents 0; there is no ambiguity between these states. In quantum computing, we don't know if the electron has up or down spin until it is measured, thus it has the ability to be in both states at the same time. This physical basis of quantum computing is less important to understanding its potential than its theoretic basis.
Let's say we are trying to find the factors of a number – what numbers divide leaving no remainder – for example, 10. Using a Turing machine, one way of finding factors is to continually divide the number to see if it divides with no remainders – does nine fit? No. Does eight fit? No.... Does five fit? Yes. So it is a factor...etc. This is a computational challenge because for each number we are evaluating, we have to cycle through a large number of other numbers to process. But using a quantum computer that has been superimposed with all possible states, we can essentially run functions on all possibilities and determine the output all at once. It's akin to working with a row on an Excel spreadsheet compared with a chart of all the outcomes – if you want a quick answer, do you glance at the chart or work through all the rows one-by-one? In a Turing machine, the function rotates through all the rows; in a quantum machine, the function works on a space that can be visualized as almost a chart of all the possibilities at once.
A quantum algorithm can be thought of as a series of logic gates, with each performing operations on this 'chart,' similar to the way an electronic logic gate outputs a single 0 or 1 depending on the state of all the inputs. In reality, each gate is a mathematical function based on imaginary numbers, but the details are unimportant for understanding the basic premise.
Ironically, we can't see this chart directly. The chart is an analogue of all the choices coded into the superimposed state of the subatomic particles. As soon as we try to measure it, just like we measure if the cat is alive or dead, we get a definite output. But of course, at different times, the [???] will be a different value – just like if we measure the state of our cat at the beginning of the experiment, it is more likely to be alive compared with later, when it is more likely to be dead. As such, we must sample the state – we measure it repeatedly, and derive a probability distribution. We might find that during our sample, the answer was  80% of the time and  20% of the time. The answer to our problem is thus , but it is not a probability-based answer – the answer is never definite.
Why the interest in quantum computing? Many encryption algorithms today (such as RSA) rely on a calculation based on the product of two primes. A person who has a key based on these primes can decrypt the data. But it is incredibly difficult to reverse-engineer which two primes derived a specific number, and thus to decrypt the data without the key. It all comes down to determining a number's factors. As we discussed, there is a lot of manual iteration in this process, especially if the number is big. But by using quantum computing, potentially all possible primes can be viewed at once. Rather than having to iterate through all options, our subatomic 'chart' will reveal which primes have been used to encode the key. Think of the surveillance capability that could be released if an unknown agent, potentially a government body, could break communications encryption. Not all tasks can be computed quicker using a quantum approach rather than a traditional one, and it is unlikely to replace the computers we use today, but for some tasks, it may be worth the effort.
Of course, we have highly simplified the complexities of the practical situation for a general audience, but there are some cutting-edge investigations taking place, most notably by IBM and D-Wave. IBM has recently produced a prototype 50-qubit chip. In our next report on quantum computing in the New Year, we will delve into barriers for its implementation, the state of the current market and opportunities for entrants, in addition to covering quantum communications. Once these were R&D projects at the cutting edge, but now their development might have a bearing on the future of IT.