“SCIENTISTS FACTOR THE NUMBER 15.”
Hardly a headline to grab the popular imagination. But when it’s done by a quantum computer – and one that’s scalable – it’s time to take notice.
A paper published today in Science describes a five-atom quantum computer that can factor numbers – that is, start with a number and find numbers that, when multiplied, equal that first number. For instance, 15 factors into three times five.
It’s also a striking illustration of how quantum computers will smash today’s internet encryption – when they arrive, that is.
Computerised factoring is not new – quantum computers have factored numbers before (and those much bigger than 15). The key point here, though, is the new design can be upscaled to much more powerful versions simply by adding atoms.
Many of the world’s public key security systems, which encrypt online banking transactions and the like, operate on a simple principle: that it’s easy to multiply two large prime numbers to generate a gigantic number.
But given the gigantic number, it’s next to impossible to work out its factors, even using a computer.
In March 1991 the encryption company RSA set a challenge – they published a list of very large numbers and announced cash awards for whoever could factor them. The prizes went from $1,000 for factoring a 100-digit number, up to $200,000 for a 617-digit number.
A quarter of a century later, most of those numbers remain uncracked.
But with a large enough quantum computer, factoring huge numbers – even those 600 digits long – would be child’s play.
In classical computing, numbers are represented by either 0s or 1s called “bits”, which the computer manipulates in a series of linear, plodding logic operations trying every possible combination until it hits the right one.
Without any prior knowledge of the answers, the system returned the correct factors (15 = 5 x 3), with a confidence of more than 99%.
For example, to factor a 232-digit monster (the largest RSA number broken) took two years with hundreds of classical computers running in parallel – and ended up being solved too late to claim the $50,000 prize.
In contrast, quantum computing relies on atomic-scale units, or “qubits”, that can be 0, 1 or – weirdly – both, in a state known as a superposition. This allows quantum computers to weigh multiple solutions at once, making some computations, such as factoring, far more efficient than on a classical computer.
The problem has been building these qubits into a large-enough assembly to make meaningful calculations. The more atoms, the more they jostle together and the harder it is to control each one.
And as superposition is a very delicate state, a small bump will cause an atom to flip to 0 or 1 easily.
The new design, devised by physicists at the Massachusetts Institute of Technology and constructed at the University of Innsbruck in Austria, uses five calcium ions (atoms stripped of an electron) suspended in mid-air by electric and magnetic fields.
The ions are close enough to one another – about a hundredth the width of a human hair – to still interact. The researchers use laser pulses to flip them between 0, 1 and superposition to perform faster, more efficient logic operations.
Without any prior knowledge of the answers, the system returned the correct factors (15 = 5 x 3), with a confidence of more than 99%. Previous quantum computers achieved the same result with 12 ions.
And this system is “straightforwardly scalable”, according to Isaac Chuang, a physicist at MIT whose team designed the computer.
A truly practical quantum computer would likely require thousands of atoms manipulated by thousands of laser pulses. Meanwhile, other researchers are working on scalable computer systems using more conventional technology such as silicon.
“It might still cost an enormous amount of money to build – you won’t be building a quantum computer and putting it on your desktop anytime soon – but now it’s much more an engineering effort, and not a basic physics question,” says Chuang.
Whatever the cost, the abililty to crack internet security would make a large-scale quantum computer, literally, invaluable.
Read our handy primer on quantum mechanics – Quantum physics for the terminally confused