Quantum computer means dark at the end of the tunnel for RSA encryption

A quantum computer has been built that can find prime factors, potentially signalling the beginning of the end for cryptography that relies on the multiplication of large prime numbers, such as RSA encryption.

Dark at the end of the tunnel for RSA encryption - quantum computer Innsbruck-Ritsch

Such computers have existed before, but without scalability – there was no reasonable path to enough quantum bits (qubits) to tackle encryption-scale numbers.

The new computer, designed and built by researchers from MIT and a team at the University of Innsbruck lead by Rainer Blatt, uses lasers to manipulate five qubits implemented as five charged atoms, and has factored the number 15 using Shor’s algorithm.

“In future generations, we foresee it being straightforwardly scalable, once the apparatus can trap more atoms and more laser beams can control the pulses,” said MIT scientist Isaac Chuang. “We see no physical reason why that is not going to be in the cards.”

In 2001, Chuang manipulated a single molecule using nuclear magnetic resonance and used it to factor 15 using Shor’s algorithm, but the implementation was not scalable.

“It was like a big forest, very hard to control one atom from the next one,” said Chuang. “The difficulty is to implement a system that’s sufficiently isolated that it can stay quantum-mechanical for long enough that you have a chance to do the whole algorithm.”

Scroll forward to now, and Chuang’s MIT team together with Innsbruck scientists have developed techniques to efficiently map the algorithm onto qubits, in an extendible way.

Researchers applied an idea from quantum computer researcher Alexei Kitaev to solve the problem using a reasonable number of qubits.

“If you want to factorise the number 15, you would usually require 12 qubits. With our implementation you only need five,” said Innsbruk physicist Thomas Monz, “This reduction is based on recycling one quantum bit along the calculation, and further improved as we make use of a quantum cache-bit to temporally store and later retrieve certain quantum information.”

The five atoms are ionised (electrically charged) to allow them to be held electrostatically within a few microns of each other in an ‘ion trap’.

“That way, we know exactly where that atom is in space,” said MIT’s Chuang. “By having a number of these atoms together, they can still interact with each other, because they’re charged. That interaction lets us perform logic gates – the gates we perform can work on any of these kinds of atoms, no matter how large we make the system.”

An issue with the technique was that photons scattered while reading some information from the qubits threatened to over-heat and degrade information remaining on the qubits. “We had to implement a new cooling method that allows us to re-cool the ion-based quantum register along the computation,” said Monz.

15 is the smallest number that can meaningfully demonstrate Shor’s algorithm, according to MIT, and was factored into three and five with confidence exceeding 99%.

Certain types of encryption use large prime numbers multiplied together. Given the resulting number, on conventional computers it takes months or years to factorise it back into the primes.

“As far as we know, classical computers cannot factorise numbers efficiently because they have to do certain steps one after another,” said Monz. “With a quantum computer, these steps, in some sense, are all running in parallel and thus notably faster.”

Shor’s quantum algorithm for calculating the prime factors of a large numbers was invented by MIT professor Peter Shor in 1994.

“We show that Shor’s algorithm, the most complex quantum algorithm known to date, is realisable in a way where all you have to do is go in the lab, apply more technology, and you should be able to make a bigger quantum computer,” said Chuang. “It might still cost an enormous amount of money to build, and you won’t be building a quantum computer and putting it on your desk any time soon, but now it’s much more an engineering effort and not a basic physics question.”

What should we do?

“Well, one thing is that if you are a nation state, you probably don’t want to publicly store your secrets using encryption that relies on factoring as a hard-to-invert problem, because when these quantum computers start coming out, you’ll be able to go back and un-encrypt all those old secrets,” said Chuang.

Results are published in Science as ‘Realization of a scalable Shor algorithm‘, or here in full, including an introduction to Shor’s algorithm and Kitaev’s approach.

Read more on RSA encryption on Wikipedia.


Leave a Reply

Your email address will not be published. Required fields are marked *