Quantum Computing Gets a Performance Boost — Is It Enough to Break RSA?
Researchers at the Massachusetts Institute of Technology (MIT) and the University of Innsbruck in Austria have developed a way to solve a scalability problem that affects current implementations of quantum computers.
The Number 15 and Quantum Computing
The experts made a proof-of-concept machine that could factor the number 15 in five qubits instead of the 15 qubits normally used by quantum computing. A qubit is the basic computational unit of a quantum computer. The fewer the number of qubits it takes to solve a problem, the faster that quantum computer will be.
In a paper titled “Realization of a Scalable Shor Algorithm,” researchers described the new process they uncovered for quantum computing.
“Here we present the realization of a scalable Shor algorithm, as proposed by Kitaev,” they wrote. “We factor the number 15 by effectively employing and controlling seven qubits and four ‘cache qubits’ and by implementing generalized arithmetic operations, known as modular multipliers.”
The number 15 is important here because 15 qubits is the lowest number of qubits for which the algorithm can be used.
Building a New Computing Environment
But what the researchers are really saying goes beyond just this particular computer. They demonstrated how a different architecture of quantum computers could be constructed to enable the scaling of Schor’s algorithm.
That algorithm is important for calculating the prime factors of a large number. With this new architecture, it can be used to get much better efficiency than what’s possible with a traditional computer. “This algorithm has been realized scalably within an ion-trap quantum computer and returns the correct factors with a confidence level exceeding 99 percent,” the researchers explained.
Isaac Chuang, professor of physics and professor of electrical engineering and computer science at MIT and one of the paper’s authors, discussed what this meant to him when speaking to PCWorld.
“We show that Shor’s algorithm, the most complex quantum algorithm known to date, is realizable in a way where, yes, all you have to do is go in the lab, apply more technology, and you should be able to make a bigger quantum computer,” he told the source.
New Technology Threatens Encryption
RSA methods of encryption are heavily dependent on the long time and intense effort it would take for someone to do the mathematical defactorialization of two prime numbers. RSA assumes in its core design that it would be very, very time-consuming to do this because of the computational complexity involved in the defactorialization. Any method that increases that speed will lessen the security of this common encryption method.
While the machines that could speed up Shor are not ready right now, this work shows that they will get there someday. Enterprises must prepare for that moment.
Two months ago, the National Security Agency (NSA) advised all U.S. government agencies to not use RSA-style encryption. It recommended other techniques since “symmetric key algorithms are believed to be secure [from quantum computer-based attacks] provided a sufficiently large key size is used.”
There’s a good chance the NSA knew that this research was on the horizon before making those recommendations. Regardless, all users should take heed of the warnings and take extra steps to protect data.