NSA is cautious about quantum computers

The well-known cryptology author Bruce Schneier writes:

NSA Plans for a Post-Quantum World

The NSA is worried enough about advances in the technology to start transitioning away from algorithms that are vulnerable to a quantum computer. Does this mean that the agency is close to a working prototype in their own classified labs? Unlikely. Does this mean that they envision practical quantum computers sooner than my 30-to-40-year estimate? Certainly.

It is tricky to interpret comments from a govt spy agency. Some people assume that it has vast security knowledge far beyond the general public, while others assume that it is tricking us into using insecure products so it can spy on us.

Here the National Security Agency is pretty clearly saying that it is worthwhile to spend money to re-engineer cryptographic systems to protect against a quantum computer running Shor's algorithm to crack RSA.

This seems crazy to me. Maybe the NSA wants to sabotage confidence in RSA. Maybe it wants to justify spending on new systems. Maybe it is just spreading FUD - fear, uncertainty, and doubt.

Proponents of quantum computing are always bragging about how they have factored 15, 21, or even 143. I just noticed that a paper last year claimed Quantum factorization of 56153 with only 4 qubits:

The largest number factored on a quantum device reported until now was 143. That quantum computation, which used only 4 qubits at 300K, actually also factored much larger numbers such as 3599, 11663, and 56153, without the awareness of the authors of that work. Furthermore, unlike the implementations of Shor's algorithm performed thus far, these 4-qubit factorizations do not need to use prior knowledge of the answer. However, because they only use 4 qubits, these factorizations can also be performed trivially on classical computers. We discover a class of numbers for which the power of quantum information actually comes into play. We then demonstrate a 3-qubit factorization of 175, which would be the first quantum factorization of a triprime.

So someone factored 56153 = 233 x 241 without realizing it!

I am not sure that this clever trickery has much to do with quantum computing power. You want to look for someone claiming to achieve some sort of quantum speedup, where the quantum computer is somehow doing something more efficiently than a classical computer. That has not been achieved. The above paper also says that no number has ever even been truly factored with Shor's algorithm, as the published successes took shortcuts that assumed the answer in advance.

So no one has ever made a true qubit, and no one has truly used quantum computing to factor anything.

Bruce Schneier has some discussion of cryptographic consequences. He was predicting that there would be no significant quantum computers in his lifetime, but then he backed off and deferred to others. I say that quantum computers will not break commercial crypto for 1000 lifetimes.

Quantum complexity expert Scott Aaronson posts this reaction to the latest quantum computer:

A bunch of people have asked me to comment on D-Wave’s release of its 1000-qubit processor, ...

More importantly, I’d say it remains unclear whether any of the machine’s performance on the instances tested here can be attributed to quantum tunneling effects. ...

But, I dunno, I’m just not feeling the urge to analyze this in more detail. Part of the reason is that I think the press might be getting less hyper-excitable these days, thereby reducing the need for a Chief D-Wave Skeptic. ...

The realization has set in, I think, that both D-Wave and the others are in this for the long haul, with D-Wave currently having lots of qubits, but with very short coherence times and unclear prospects for any quantum speedup, and Martinis and some others having qubits of far higher quality, but not yet able to couple enough of them.

This could continue for 20 years. Lots of serious research, but no useful results.