Quantum computing gets a bit more real: implications for encryption

March 07, 2016 // By Graham Prophet
Researchers at MIT and the University of Innsbruck (Austria) have built a quantum computer that manipulates the states of just five atoms to solve the find-the-prime-factors-of-a-number problem; while the actual problem solved – factorising the number 15 – appears trivial, the scheme they have devised is in principle scalable and, in time, may begin to erode the basis of prime-factors-based encryption schemes; the key aspect of the announcement lies in scalability.

The prime factors of the ‘minimal case’ of the number 15 are obvious; 3 and 5. A larger number, say, below 100, may take some pen and paper. An even larger number, with hundreds of digits, can take years to factor, using hundreds of classical computers operating in parallel.


The difficulty of finding the prime factors of a large number underpins the key-based, secure encryption in universal use today. It has long been realised that in principle, a quantum computer has the potential to attack the problem. A computer that could manipulate the states of hundreds of atoms simultaneously might quickly factor very large numbers.


In 1994, Peter Shor, the Morss Professor of Applied Mathematics at MIT, came up with a quantum algorithm that calculates the prime factors of a large number, vastly more efficiently than a classical computer. However, the algorithm’s success depends on a computer with a large number of quantum bits. While others have attempted to implement Shor’s algorithm in various quantum systems, none have been able to do so with more than a few quantum bits, in a scalable way.


Now, in a paper published in the journal Science , the researchers report that they have designed and built a quantum computer from five atoms in an ion trap. The computer uses laser pulses to carry out Shor’s algorithm on each atom, to correctly factor the number 15. In slightly more detail they present, “... the realisation of a scalable Shor algorithm, as proposed by Kitaev...[to]... factor the number 15 by effectively employing and controlling seven qubits and four “cache qubits” and by implementing generalised arithmetic operations, known as modular multipliers.” The system is designed in such a way that more atoms and lasers can be added to build a bigger and faster quantum computer, able to factor much larger numbers. The results, they say, represent the first scalable implementation of Shor’s algorithm.