Will quantum computing kick off an encryption revolution?
Quantum computing may be on the verge of making current encryption systems obsolete.
Researchers have created a quantum computer out of just five atoms, capable of factoring the number 15, according to a paper, published Friday in the journal Science.
Crucially, and for the first time, this technology is scalable – can be expanded to incorporate more atoms and factor more complex numbers – which is important because many encryption schemes are based upon this “factoring problem.”
“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,” co-author Isaac Chuang, professor of physics and professor of electrical engineering and computer science at the Massachusetts Institute of Technology, explains in a press release.
“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.”
Factoring the number 15, the smallest number that can meaningfully demonstrate Shor’s algorithm, is an easy task, something children learn early in their mathematics curriculum. The prime factors, or multipliers, are three and five.
However, larger numbers prove to be more complex, and when you reach the realm of numbers consisting of hundreds of digits, it takes years and considerable computing power to find the answers.
“Certain algorithms for quantum computers are able to outperform their classical counterparts,” reads the paper’s abstract. “In 1994, Peter Shor came up with a quantum algorithm that calculates the prime factors of a large number vastly more efficiently than a classical computer.”
It is precisely because of the complexity of finding the prime factors of large numbers that encryption schemes are often based on this system.
Because of the speed at which quantum computers promise to solve these mathematical problems, it is likely, if not inevitable, that they will force the development of fresh encryption methods – as well as rendering current encrypted information easily accessible.
“Such pace is possible in part because while in a classical computer a bit of information can be either a 0 or a 1, a quantum computer can store the information as both values simultaneously, so that qubits [quantum bits] can exist in a wide range of 'superpositions' of the two states,” Nature science writer Edwin Cartlidge wrote in 2014.
In this latest research, each qubit was represented by a single calcium atom, five in total, held in what is termed an “ion trap,” by removing an electron from each atom, thereby giving them an ionic charge.
As an electric field held them in place, laser pulses were used to perform “logic gates,” essential components of Shor’s algorithm, on four of the five atoms.
The fifth atom processes the results.
“By having a number of these atoms together, they can still interact with each other, because they’re charged,” said Dr. Chuang.
“That interaction lets us perform logic gates, which allow us to realize the primitives of the Shor factoring algorithm. The gates we perform can work on any of these kinds of atoms, no matter how large we make the system.”
So it is that, while this particular quantum computer can only calculate the prime factors of 15, it promises so much more.
“[Shor’s algorithm] captured the imagination of many researchers who took notice of quantum computing because of its promise of truly remarkable algorithmic acceleration,” said Mark Ritter, senior manager of physical sciences at IBM. “Therefore, to implement Shor's algorithm is comparable to the ‘Hello, World’ of classical computing.”
