So how many gates are we talking to factor some "cryptographically useful" number? Is there some pathway that makes quantum computers useful this century?
replies(9):
That is a hard question to answer for two reasons. First, there is no bright line that delineates "cryptographically useful". And second, the exact design of a QC that could do such a calculation is not yet known. It's kind of like trying to estimate how many traditional gates would be needed to build a "semantically useful" neural network back in 1985.
But the answer is almost certainly in the millions.
[UPDATE] There is a third reason this is hard to predict: for quantum error correction, there is a tradeoff between the error rate in the raw qbit and the number of gates needed to build a reliable error-corrected virtual qbit. The lower the error rate in the raw qbit, the fewer gates are needed. And there is no way to know at this point what kind of raw error rates can be achieved.
> Is there some pathway that makes quantum computers useful this century?
This century has 75 years left in it, and that is an eternity in tech-time. 75 years ago the state of the art in classical computers was (I'll be generous here) the Univac [1]. Figuring out how much less powerful it was than a modern computer makes an interesting exercise, especially if you do it in terms of ops/watt. I haven't done the math, but it's many, many, many orders of magnitude. If the same progress can be achieved in quantum computing, then pre-quantum encryption is definitely toast by 2100. And it pretty much took only one breakthrough, the transistor, to achieve the improvement in classical computing that we enjoy today. We still don't have the equivalent of that for QC, but who knows when or if it will happen. Everything seems impossible until someone figures it out for the first time.
---
[1] https://en.wikipedia.org/wiki/UNIVAC_I#Technical_description
> This century has 75 years left in it, and that is an eternity in tech-time.
As a comparison, we went from first heavier than air flight to man walking on the moon in only 66 years.
And that was before Epoch (1969, unix time started in 1970). We went from calculator to AI in 55 years, which is, actually, extremely long. It took exactly the time to miniaturize CPUs enough that you would hold as many gates in a GPU as neurones in a human’s brain. The moment we could give enough transistors to a single program, AI appeared. It’s like it’s just an emergent behavior.
I think it is insanely fast.
Think about it: that planet has been here for billions of years. Modern humanity has been here for 200,000 years, give or take. It took 199700 years and change to get to a working steam engine. 266 years later men were walking on the moon and another 55 years and we had a good facsimile of what an AI looks like in practice. That's insane progress. The next 75 years are going to be very interesting, assuming we don't fuck it all up, the chances of which are right now probably 50/50 or so.