### Quantum computers: A little bit, better

*After decades languishing in the laboratory, quantum computers are attracting commercial interest*

A COMPUTER proceeds one step at a time. At any particular moment, each of its bits—the binary digits it adds and subtracts to arrive at its conclusions—has a single, definite value: zero or one. At that moment the machine is in just one state, a particular mixture of zeros and ones. It can therefore perform only one calculation next. This puts a limit on its power. To increase that power, you have to make it work faster.

But bits do not exist in the abstract. Each depends for its reality on the physical state of part of the computer’s processor or memory. And physical states, at the quantum level, are not as clear-cut as classical physics pretends. That leaves engineers a bit of wriggle room. By exploiting certain quantum effects they can create bits, known as qubits, that do not have a definite value, thus overcoming classical computing’s limits.

Around the world, small bands of such engineers have been working on this approach for decades. Using two particular quantum phenomena, called superposition and entanglement, they have created qubits and linked them together to make prototype machines that exist in many states simultaneously. Such quantum computers do not require an increase in speed for their power to increase. In principle, this could allow them to become far more powerful than any classical machine—and it now looks as if principle will soon be turned into practice. Big firms, such as Google, Hewlett-Packard, IBM and Microsoft, are looking at how quantum computers might be commercialised. The world of quantum computation is almost here.

#### A Shor thing

As with a classical bit, the term qubit is used, slightly confusingly, to refer both to the mathematical value recorded and the element of the computer doing the recording. Quantum uncertainty means that, until it is examined, the value of a qubit can be described only in terms of probability. Its possible states, zero and one, are, in the jargon, superposed—meaning that to some degree the qubit is in one of these states, and to some degree it is in the other. Those superposed probabilities can, moreover, rise and fall with time.

The other pertinent phenomenon, entanglement, is caused because qubits can, if set up carefully so that energy flows between them unimpeded, mix their probabilities with one another. Achieving this is tricky. The process of entanglement is easily disrupted by such things as heat-induced vibration. As a result, some quantum computers have to work at temperatures close to absolute zero. If entanglement can be achieved, though, the result is a device that, at a given instant, is in all of the possible states permitted by its qubits’ probability mixtures. Entanglement also means that to operate on any one of the entangled qubits is to operate on all of them. It is these two things which give quantum computers their power.

Harnessing that power is, nevertheless, hard. Quantum computers require special algorithms to exploit their special characteristics. Such algorithms break problems into parts that, as they are run through the ensemble of qubits, sum up the various probabilities of each qubit’s value to arrive at the most likely answer.

One example—Shor’s algorithm, invented by Peter Shor of the Massachusetts Institute of Technology—can factorise any non-prime number. Factorising large numbers stumps classical computers and, since most modern cryptography relies on such factorisations being difficult, there are a lot of worried security experts out there. Cryptography, however, is only the beginning. Each of the firms looking at quantum computers has teams of mathematicians searching for other things that lend themselves to quantum analysis, and crafting algorithms to carry them out.

Top of the list is simulating physics accurately at the atomic level. Such simulation could speed up the development of drugs, and also improve important bits of industrial chemistry, such as the energy-greedy Haber process by which ammonia is synthesised for use in much of the world’s fertiliser. Better understanding of atoms might lead, too, to better ways of desalinating seawater or sucking carbon dioxide from the atmosphere in order to curb climate change. It may even result in a better understanding of superconductivity, permitting the invention of a superconductor that works at room temperature. That would allow electricity to be transported without losses.

Quantum computers are not better than classical ones at everything. They will not, for example, download web pages any faster or improve the graphics of computer games. But they would be able to handle problems of image and speech recognition, and real-time language translation. They should also be well suited to the challenges of the big-data era, neatly extracting wisdom from the screeds of messy information generated by sensors, medical records and stockmarkets. For the firm that makes one, riches await.

#### Cue bits

How best to do so is a matter of intense debate. The biggest question is what the qubits themselves should be made from.

A qubit needs a physical system with two opposite quantum states, such as the direction of spin of an electron orbiting an atomic nucleus. Several things which can do the job exist, and each has its fans. Some suggest nitrogen atoms trapped in the crystal lattices of diamonds. Calcium ions held in the grip of magnetic fields are another favourite. So are the photons of which light is composed (in this case the qubit would be stored in the plane of polarisation). And quasiparticles, which are vibrations in matter that behave like real subatomic particles, also have a following.

The leading candidate at the moment, though, is to use a superconductor in which the qubit is either the direction of a circulating current, or the presence or absence of an electric charge. Both Google and IBM are banking on this approach. It has the advantage that superconducting qubits can be arranged on semiconductor chips of the sort used in existing computers. That, the two firms think, should make them easier to commercialise.

Those who back photon qubits argue that their runner will be easy to commercialise, too. As one of their number, Jeremy O’Brien of Bristol University, in England, observes, the computer industry is making more and more use of photons rather than electrons in its conventional products. Quantum computing can take advantage of that—a fact that has not escaped Hewlett-Packard, which is already expert in shuttling data encoded in light between data centres. The firm once had a research programme looking into qubits of the nitrogen-in-diamond variety, but its researchers found bringing the technology to commercial scale tricky. Now Ray Beausoleil, one of HP’s fellows, is working closely with Dr O’Brien and others to see if photonics is the way forward.

For its part, Microsoft is backing a more speculative approach. This is spearheaded by Michael Freedman, a famed mathematician (he is a recipient of the Fields medal, which is regarded by mathematicians with the same awe that a Nobel prize evokes among scientists). Dr Freedman aims to use ideas from topology—a description of how the world is folded up in space and time—to crack the problem. Quasiparticles called anyons, which move in only two dimensions, would act as his qubits. His difficulty is that no usable anyon has yet been confirmed to exist. But laboratory results suggesting one has been spotted have given him hope. And Dr Freedman believes the superconducting approach may be hamstrung by the need to correct errors—errors a topological quantum computer would be inherently immune to, because its qubits are shielded from jostling by the way space is folded up around them.

For non-anyonic approaches, correcting errors is indeed a serious problem. Tapping into a qubit prematurely, to check that all is in order, will destroy the superposition on which the whole system relies. There are, however, ways around this.

In March John Martinis, a renowned quantum physicist whom Google headhunted last year, reported a device of nine qubits that contained four which can be interrogated without disrupting the other five. That is enough to reveal what is going on. The prototype successfully detected bit-flip errors, one of the two kinds of snafu that can scupper a calculation. And in April, a team at IBM reported a four-qubit version that can catch both those and the other sort, phase-flip errors.

Google is also collaborating with D-Wave of Vancouver, Canada, which sells what it calls quantum annealers. The field’s practitioners took much convincing that these devices really do exploit the quantum advantage, and in any case they are limited to a narrower set of problems—such as searching for images similar to a reference image. But such searches are just the type of application of interest to Google. In 2013, in collaboration with NASA and USRA, a research consortium, the firm bought a D-Wave machine in order to put it through its paces. Hartmut Neven, director of engineering at Google Research, is guarded about what his team has found, but he believes D-Wave’s approach is best suited to calculations involving fewer qubits, while Dr Martinis and his colleagues build devices with more.

Which technology will win the race is anybody’s guess. But preparations are already being made for its arrival—particularly in the light of Shor’s algorithm.

#### Spooky action

Documents released by Edward Snowden, a whistleblower, revealed that the Penetrating Hard Targets programme of America’s National Security Agency was actively researching “if, and how, a cryptologically useful quantum computer can be built”. In May IARPA, the American government’s intelligence-research arm, issued a call for partners in its Logical Qubits programme, to make robust, error-free qubits. In April, meanwhile, Tanja Lange and Daniel Bernstein of Eindhoven University of Technology, in the Netherlands, announced PQCRYPTO, a programme to advance and standardise “post-quantum cryptography”. They are concerned that encrypted communications captured now could be subjected to quantum cracking in the future. That means strong pre-emptive encryption is needed immediately.

Quantum-proof cryptomaths does already exist. But it is clunky and so eats up computing power. PQCRYPTO’s objective is to invent forms of encryption that sidestep the maths at which quantum computers excel while retaining that mathematics’ slimmed-down computational elegance.

Ready or not, then, quantum computing is coming. It will start, as classical computing did, with clunky machines run in specialist facilities by teams of trained technicians. Ingenuity being what it is, though, it will surely spread beyond such experts’ grip. Quantum desktops, let alone tablets, are, no doubt, a long way away. But, in a neat circle of cause and effect, if quantum computing really can help create a room-temperature superconductor, such machines may yet come into existence.

From the print edition: Science and technology

Link: http://www.economist.com