QUANTUM mechanics and computers traditionally don't mix. The strange fuzziness of the quantum world is a big obstacle for chip designers, who work with components so small that quantum effects make the electrons flowing through them unruly and unpredictable. But it is possible to design a computer in which that quantum fuzziness is a feature, not a bug. Researchers have been working on so-called quantum computers since the early 1980s, when the idea was first proposed. Recently, a Canadian firm called D-Wave has been in the news, for its device—a special kind of quantum computer designed to solve one particular problem—has, for the first time, been raced against a classical, non-quantum computer to see which is faster. D-Wave's machine is designed to solve only a specific kind of problem, but scientists around the world are working on general-purpose quantum machines that could attack any kind of problem that a standard computer could tackle. But what exactly is a quantum computer?
Classical computers—like the one on which you are reading this article—work by performing a series of simple tasks (such as adding two numbers) extremely quickly. But the circuits in a classical computer abide by the rather boring laws of classical physics, which stipulate that they can only be in a single state at a given time. Quantum computers use the racier laws governing quantum mechanics to skirt around that limitation. The fundamental unit of quantum computation is the "qubit", the quantum analogue of the ordinary "bit" in a standard machine. Like ordinary bits, qubits can take the value of 1 or 0. Unlike ordinary bits, their quantum nature also lets them exist in a strange mixture—a "superposition", in the jargon—of both states at once, much like Erwin Schrödinger'sfamous cat.
That means that a quantum computer can be in many states simultaneously, which in turn means that it can, in some sense, perform many different calculations at the same time. To be precise, a quantum computer with four qubits could be in 2^4 (ie, 16) different states at a time. As you add qubits, the number of possible states rises exponentially. A 16-bit quantum machine can be in 2^16, or 65,536, states at once, while a 128-qubit device could occupy 3.4 x 10^38 different configurations, a colossal number which, if written out in longhand, would have 39 digits. Having been put into a delicate quantum state, a quantum computer can thus examine billions of possible answers simultaneously. (One way of thinking about this is that the machine has co-operated with versions of itself in parallel universes.)
With great power, alas, come irritating limitations. The answers that a quantum machine gives to questions are probabilistic. In other words, they might be wrong and must be checked. If a given solution is wrong, the calculation must be repeated until the correct answer emerges, a flaw that removes the speed advantage quantum computers offer over classical devices. Clever programming can exploit another quantum phenomenon called interference to significantly improve the odds of getting a correct result, restoring some of the speed-up. But boffins have figured out how to do that only for a small number of problems, which limits the probable utility of quantum computing. Most famously, by running something called Shor's algorithm, a quantum computer could rapidly find the prime factors of very large numbers, a computatonal feat whose difficulty for ordinary computers forms the basis of many of the cryptographic systems used on the Internet. That would certainly be useful. But for many tasks, ordinary computers will probably be just as fast as their quantum counterparts.