CHIPMAKERS dislike quantum mechanics. Half a century of Moore’s law means their products have shrunk to the point where they are subject to the famous weirdness of the quantum world. That makes designing them difficult. Happily, those same quantum oddities can be turned into features rather than bugs. For many years researchers have been working on computers that would rely on the strange laws of quantum mechanics to do useful calculations. They would do this by using binary digits which, instead of having a value of either “one” or “zero”, had both at the same time. That might allow them to do some calculations much faster than non-quantum, “classical” computers can manage.
Progress has been slow, but steady. And now it may be possible to see how a certain type of quantum computer performs in the real world. On May 15th, at a computing conference in Ischia in Italy, Catherine McGeoch, a computer scientist at Amherst College in Massachusetts, presented a paper describing the performance of a quantum computer manufactured by a Canadian firm called D-Wave
D-Wave has a colourful history. To much fanfare and press attention (including in The Economist), it announced a working quantum computer in 2007. Sporting a superconducting chip cooled to within a fraction of a degree of absolute zero, this certainly sounded high-tech. But the firm provided little concrete information, and given how far ahead it seemed to be compared with academic laboratories working on the same problem, many computer scientists were sceptical of its claim to have created a truly quantum machine. Following the publication of a paper in Nature in 2011, however, it is now generally accepted that the firm has built a working version of a specific type of machine called an adiabatic quantum computer.
Unlike a “standard” quantum computer, which (if one is ever built) could answer the same sorts of question that a classical computer can, an adiabatic computer is limited to a broad category of mathematics known as “discrete optimisation” problems, where many criteria are fighting for attention at the same time and the computer must attempt to meet as many of them as it can. D-Wave’s device does this by encoding the problem in a quantum system and then trying to find its lowest-energy state. That is equivalent to finding the minimum value of the function, a task that mathematically inclined readers may remember from school.
Dr McGeoch and Cong Wang, a graduate student from Simon Fraser university, gave D-Wave’s machine three notoriously tricky mathematical tasks, and then gave the same jobs to conventional algorithms running on standard computer hardware. After the dust had settled they found that the two machines were roughly as good as each other on two tasks. But on the third, a type to which it is ideally suited (quadratic unconstrained binary optimisation, since you ask), D-Wave’s machine dominated, racing through the job around 3,600 times faster than the classical hardware.
Even there, though, there is a catch. Scott Aaronson, a computer scientist at the Massachusetts Institute of Technology, points out that the classical algorithms against which D-Wave’s machine was competing are generalists, not tweaked for the specific problem at hand. Matching them against D-Wave’s machine is, then, a bit like racing a carthorse against a thoroughbred. Dr Aaronson points to another paper, published in April on arXiv, an online repository, by a group led by Matthias Troyer at the Institute for Theoretical Physics, in Zurich, which finds that customised versions of classical algorithms running on standard hardware are even faster than D-Wave’s devices. “There’s currently no problem that the D-Wave machine has been shown to solve faster than a classical computer,” says Dr Aaronson.
That ordinary computers can mostly keep up with D-Wave’s current machines does not mean that quantum computers offer no advantages. Several academic researchers are making progress on universal quantum machines that could tackle a wider range of problems than D-Wave’s device. If such universal computers could be built, they could solve certain problems—simulating chemical reactions, for instance, or breaking many encryption codes, including those used to secure electronic commerce—far faster than anyone knows how to solve them on classical computers. Yet even a universal quantum computer would hardly be the “magic box” of science fiction and hype. For many problems, computer scientists expect that it would provide little or no advantage over today’s classical machines.
Powered by Facebook Comments