For anyone who researches or studies quantum information processing the name Isaac Chuang, based at MIT, is well known. His introduction to the subject with Michael Nielson is required reading. Hence, when I saw a paper appear this week in Science (link is to an earlier pre-print version to avoid subscription) to which he had contributed I paid particular attention. The title is something I have discussed on this blog for many years in entries such as this: Realization of a scalable Shor algorithm.
Anyone interested in either quantum computing or cryptanalysis would zero in on "Shor's algorithm".
The work being reported in this paper is not the first successful implementation of Shor's algorithm in a qubit based system, but it is the first time I've seen it done with this degree of confidence in the answer (99%). And, even though the number factored is only 15, most thought it would take 12 qubits (or there abouts) to run the algorithm successfully, but these researchers have squeezed it into 5 qubits. These 5 qubits were only 5 atoms in an ion trap.
Not only have they shown that fewer qubits than previously thought can be used, the architecture suggested by their experiment is scalable. That means that, provided researchers can keep the atoms stable in the ion trap, they could expand the size of the numbers being factored. The team at Innsbruch, who have been building the equipment, have shown particular expertise in achieving just such a scaling of these ion traps.
Now, whilst the technology now looks like it is achievable it is going to be very expensive to implement. However, bearing in mind that the prize is the possibility of factoring the large numbers that lie at the heart of the RSA algorithm I can imagine a few organisations who might be considering it.
Not to mention that researchers will doubtless be looking to see if Shor’s discrete logarithm quantum algorithm for elliptic curves can be used to attack elliptic curve encryption in real world implementations.
Many believe it will take years to achieve but if this is as scalable as it looks then I'm not sure it will be that many years before its operational. It won't be sat on your desk but then what supercomputer does?
Likewise, non-quantum (or more specifically a non-factoring) approaches to breaking RSA will continue to be the subject of research as it may well result in a break through before the engineering is completed. But, suddenly the EU project recently started to look into "post quantum" encryption doesn't look quite as premature as many believed when it was announced.
