[Cryptography] Quantum computers will never overcome noise issues?

[Jon Callas]

I'm a bit late to this party, but I liked the article.

I'm something of a soft quantum skeptic. Kalai is something of a hard quantum skeptic. We probably agree more than we disagree.

I have a number of friends and colleagues working on quantum computers and they think that the theoretical issues are complete and the rest is just an engineering problem. I even agree with that. My soft skepticism could be phrased, "You keep using that word 'just.' I don't think it means what you think it means."

Less squishily, I don't think that someone is going to make a quantum computer by 2050 that would perform at speeds that we predict a classical computer could do if Moore's Law continued until then (which it won't). Even less squishily, I don't think that there will be a quantum computer that can reliably break a generic RSA 4096 key by 2050. If I want to be a hard-ass on what "reliably" means, I'll say that that means that they can break one faster than a classical computer can generate one. If I want to be more generous, I'd back off to say one key per year. If I want to be provocative, I'd say a single generic key at all.

It's really easy to bury a lot in "it's just an engineering problem" and researchers do that a lot. Once you put Sputnik in orbit, cities on the moon are just an engineering problem. Once you have a transistor that you can make a hearing aid out of, mass-producing today's computers is just an engineering problem. That latter just happens to be a seventy-five year engineering problem.

The quantum advocates I know think that in ten to fifteen years, they'll be able to hit somewhere in the Shor brackets I outlined above. The first time I made my small bet was about a decade ago. At present, I'm merely saying that the engineering problem is going to take thirty years rather than fifteen to win. If they're right, I'll be shocked but not surprised. If Kalai's right, I'll also be shocked but not surprised. I'm in the middle of the two extremes, but really agreeing with Kalai. I think the noise, decoherence, and error correction engineering problems are a lot harder than the advocates think, I'm just not quite at thinking they're impossible. Impossible just means that no one's ever done it before. Just.

	Jon