Cryptography, qubits and the art of being in two places at once

From Whitehall to the White House, a quantum computer could crack any code. Justin Mullins talks to scientists in the race to build a 'supercomputer'

Two roads diverged in a yellow wood/And sorry I could not travel both/And be one traveller, long I stood/And looked down one as far as I could/To where it bent in the undergrowth/Then took the otherI I shall be telling this with a sigh/Somewhere ages and ages hence: Two roads diverged in a wood, and I - I took the one less travelled by/And that has made all the difference.

Robert Frost's famous poem was intended as a gentle dig at the habit of regret. But what if it were possible for a ghostly traveller to take both roads and decide on his preference at the end of the journey?

This strange and ethereal explorer would never again rue the road not taken and the opportunities it might have offered. Of course, this preposterous idea would never be tolerated by any real poet - only a scientist could propose such an outrage and expect the rest of us to accept it.

But that, in a nutshell, is the inescapable conclusion of 20th-century physics. After the best part of 100 years of theory and experiment, scientists have been forced to concede that, yes, it is possible to be in two places at the same time. The one caveat is that the ghostly traveller must reside in the world of the very small (think sub-atomic) and live by the strange laws of quantum mechanics that govern the universe on this scale.

But it has taken scientists the best part of a century to understand where this magical idea could lead. They have only recently glimpsed the possibility of a new computing revolution that will make today's super computers look like pocket calculators. What frightens many governments is that these computers will make child's play of the codes that protect information and that there will be no way to protect secrets.

When this dual existence was first discovered in the early 20th century, scientists rather miserably failed to see what fun could be had in this magical quantum world. With one or two exceptions, scientists treated the idea of dual existences much as the rest of us think of Paul Daniels pulling a rabbit out of hat: as a neat trick easily explained (if only one knew how) but not one of any practical use.

Then in 1984, David Deutsch, a physicist at the University of Oxford, came up with an idea that was to rock the world of science. What if you could use the idea of dual existences to do something useful: to carry out two calculations when only one had been possible in the past? The idea took a while to sink in. Most scientists believed the quantum world to be so fragile that any interference on their part would destroy the very things they wanted to control. In such circumstances calculations would be impossible.

But Deutsch persevered. He began by thinking about the trip through the yellow wood as a calculation in which each road represented one of two possible answers, say, yes and no - or in the language of logic, 0 and 1. In the conventional world, any journey through the wood would have to be via one road or the other, yielding an answer of either 0 or 1. But in the quantum world, a traveller could try both roads at the same time, allowing the calculation to proceed on both numbers at the same time.

Physicists call an ordinary 0 or 1 a bit of information (short for binary digit) and by the early 1990s they had come up with a name for quantum bits of information: they called them qubits (pronounced queue-bits) and soon realised that these weird packets of dual existence would have a profound effect on their notions of computation.

Being able to carry out two calculations instead of one may not sound very significant, but the idea turns out to be extraordinarily powerful when scaled up. While one qubit allows two existences: 0 or 1, two qubits allow four existences: 00, 11, 01, and 10. So being able to play with two qubits allows you to carry out a calculation on four numbers in parallel. Three qubits allows calculations on eight numbers in parallel. Ten qubits can represent 1,024 numbers and so on. The rise is exponential. With only 300 qubits, it is possible to play with more numbers than there are atoms in the universe. The revolutionary idea that Deutsch put forward is that by exploiting the laws of quantum mechanics, by playing with qubits rather than bits, computers could become vastly more powerful.

But what kind of breakthrough was this? After all, faster computers are what everyone expects. For some time physicists pondered this problem arguing that quantum computers are simply faster versions of ordinary computers. Then in 1993, they proved something else. "There are some problems that quantum computers can solve that ordinary computers cannot," says Artur Ekert, a physicist at the centre for quantum computation at Oxford. "This makes them very exciting."

Mathematicians often class mathematical problems by the time it takes to solve them. So the problem of multiplying two numbers together is very simple. Even when the numbers are very big, the time it takes to calculate an answer depends on the numbers in a very straightforward way. However, the same is not true of the inverse problem: given a number, find the numbers that must be multiplied together to get it. This is known as factoring and is very straightforward for small numbers such as 15 (5 x 3) but becomes progressively much more difficult for larger numbers such as 60 (2 x 2 x 3 x 5) or 2047 (23 x 89). In fact, the difficulty in finding factors increases exponentially with the number of digits in the number, so factoring a number with 200 digits would take an ordinary computer the age of the universe.

Many secret encryption codes are based on this property, which is why factoring is of huge military and commercial importance. Essentially, a message can be encrypted by multiplying two long numbers together and can only be decrypted by somebody who knows the two original numbers or somebody with a powerful enough computer to carry out the necessary factoring. As computers have got more powerful, security experts have always been able stay one step ahead by increasing the number of digits in the numbers they use.

But in the early 1990s, Peter Shor, a mathematician at AT&T's research lab in New Jersey, showed that quantum computers are special, that they would always be able to factor a number regardless of the number of digits it contained. What Shor had proved was that the instant a quantum computer was built, the military, banks and governments could no longer guarantee the secrecy of any of their codes because this single quantum computer could crack them. This was a sobering thought, particularly for the military.

But what the quantum world takes away with one hand it gives back with the other. While the quantum world offers a way to crack existing codes, it also allows an entirely new type of cryptography that can never be cracked, even in principle. The technique uses quantum particles such as photons to send information from one person to another. These photons are so fragile that were any eavesdropper to listen in to the message, he or she would destroy them in a way that the two parties could spot easily and the secrecy of the message would be guaranteed.

Britain, along with the United States, is at the forefront in this field. In the early 1990s, the Defence Evaluation and Research Agency, the UK's military research and development department, pioneered the field of quantum cryptography. And Ekert's group at the University of Oxford is one of the world's leading theory groups. But other governments, particularly in Europe and Australia, have begun to recognise the huge military and commercial importance of quantum computing and have begun research programmes of their own. "The difficulty we have is in finding the salaries to keep talented scientists in this country," Ekert says.

This could be a serious problem in the long term. A number of labs around the world have already demonstrated quantum cryptography and the building blocks of quantum computing are already being built. But no one is expecting to see quantum computers outsmart conventional computers for at least 20 years. Britain is well placed in this race but if it loses its best minds to laboratories abroad, the government could well wish it had taken a different road in developing this technology.