Quantum computing rewrites encryption rules

Supercomputers such as IBM’s MareNostrum, launched last year, will be rendered obsolete by quantum computers. Picture / Reuters

When bankers and spies begin to worry about advances in computing, the rest of us would do well to take notice.

What makes them edgy are the advances being made in quantum computing, which is, as might be expected from the name, as confusing a field to understand as the branch of physics on which it is based - quantum mechanics.

But a banker doesn't need to be able to understand quantum physics to know that a computer capable of breaking any of the world's encryption codes as soon as it is turned on could mean serious problems for the bank's financial system.

Systems used to transfer funds around the world every day rely on encryption that takes milliseconds to encode but, in theory, millions of years to crack by even the most powerful computers. And governments routinely use encryption to pass on secret messages.

Quantum computing threatens that, which is why bankers and governments are paying particular attention to a field that barely existed a decade ago.

Although the physicist Richard Feynman put forward the ideas that are the basis of the subject in 1982, the wider interest took off only after a researcher called Peter Shor demonstrated - theoretically - in 1994 that a computer with enough "quantum bits" could effortlessly crack modern encryption.

Interest in the field has now taken hold across the world. Professor Apostol Vourdas, of Bradford University's computing department, has just won a 62,000 ($164,000) grant to co-ordinate a network of universities and companies, including HP and Hitachi, in a quantum computing project. He is working with five PhD students.

"The computing side is just one aspect of the field," he says. "The whole field of quantum technology is growing, taking in communications, computing and cryptography."

The reason for this burgeoning interest is twofold. First, computers as we know them can't keep getting faster. "Moore's Law", which was coined in the 1970s at Intel, predicts that every 18 months the number of transistors (the building blocks of processors and memory) doubles in any given area of integrated circuits, making the machine more powerful.

But eventually physical reality will intervene; at some point between 2010 and 2020, the transistors will no longer be shrinkable, because the electrons that carry the signals will leak out.

Some of that effect is already visible. In the past two years, Intel, IBM and Motorola, the biggest chip-makers, have had problems with the reliability of chips with 65-nanometre parts.

Second, quantum computing and calculation offer a whole new approach to solving problems. That's because quantum computing uses some of the weird aspects of subatomic particles such as electrons and photons to do its calculations.

Both electrons and photos can have a quality called "spin", which is either "up" or "down"; in the quantum computing field these are often used as the "0" and "1" of conventional binary calculation.

What marks out quantum computers is that they don't have to proceed through their calculations step by step. Physicists say that any closed quantum system has a "superposition" of all possible states.

Remember "Schrodinger's Cat"? This is a theoretical experiment about a cat trapped in a soundproof box with a cyanide canister that would be let off if a radioactive particle decayed, of which there is a 50-50 chance.

Clearly, when you open the box, the cat is either alive or dead. But is it alive or dead before you open the box? Arguably, it is both; by opening the box, you "collapse" its alive-and-dead state into one or the other.

A quantum computer takes this idea to the extreme. The "quantum bits" (qubits) are, in theory, in every possible binary configuration, all at the same time. It's as though your computer was simultaneously doing every calculation you'd ever asked it, or ever would, or could.

The problem of getting quantum computers to give the correct answers has stumped researchers in recent years. You can set up lots of "qubits", but getting them to collapse into the answer you want is harder.

The first working quantum computer, which was able to make calculations with two qubits, was demonstrated in 1998.

IBM's Almaden Research Centre then made the running for the next three years, demonstrating a three-qubit machine in 1999, a five-qubit one in 2001, and then a seven-qubit version - using 10 billion billion molecules, each of seven atoms, to show factors of the number 15.

How useful is that, you might wonder? But 15 is special, as the product of two prime numbers. Most modern cryptography encrypts data by wrapping it in a huge, unique number, produced by multiplying two large prime numbers together.

While standard computers are good at multiplying, they are not so good at the reverse, called "factoring".

But quantum computers, directed correctly, are able to produce instant answers to enormous factorisation challenges.

Which is where the banks and governments begin to take fright, and seek newer forms of cryptography to defend against this. Happily, the same technique that cracks the old system produces a newer, more powerful one.

Quantum cryptography has already moved from theory into the real world. Last April, Bank Austria Creditanstalt used quantum cryptography to make a real bank transfer to the city hall of Vienna.

Quantum cryptography really is unbreakable between two points. It uses a peculiar property of quantum particles - if they are generated together, they will be "entangled".

This is rather like identical twins. Look at one, and you know what the other looks like. The result is that you can create two identical cryptographic keys. Send one to your recipient, and be certain of two things: their key really will be the same, and, if someone tries to tap your transmission of the key, they will collapse the system.

Yet some might say quantum computing is not making the progress that was expected of it.

In 2000, Brian Oakley, who chaired a European study group into the possibilities of such machines, said: "I wouldn't be surprised to see applications [of quantum computing] in five years' time." Well, 2005 has dawned, but the machines haven't.

Vourdas, however, is confident their time will come. "In the 1940s, electronic computers were thought to be an intellectual exercise that wouldn't really be made in practice.

"Yet 30 years later, you could buy them in shops. Quantum computing isn't an outgrowth of classical computing, but a revolutionary step forward."

Quantum leap

* HP, Hitachi and a network of universities are engaged on quantum computing research.

* Rather than transistors, quantum computers do calculations using subatomic particles.

* Banks and governments are concerned that quantum computers will be so powerful existing encryption will be easily cracked.

- INDEPENDENT