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
What made computing-at-scale possible wasn't the transistor, it was the precursor technologies that made transistor manufacturing possible - precise control of semiconductor doping, and precision optical lithography.
Without those the transistor would have remained a lab curiosity.
QC has no hint of any equivalent breakthrough tech waiting to kick start a revolution. There are plenty of maybe-perhaps technologies like Diamond Defects and Photonics, but packing density and connectivity are always going to be huge problems, in addition to noise and error rate issues.
Basically you need high densities to do anything truly useful, but error rates have to go down as packing densities go up - which is stretching optimism a little.
Silicon is a very forgiving technology in comparison. As long as your logic levels have a decent headroom over the noise floor, and you allow for switching transients (...the hard part) your circuit will be deterministic and you can keep packing more and more circuitry into smaller and smaller spaces. (Subject to lithography precision.)
Of course it's not that simple, but it is basically just extremely complex and sophisticated plumbing of electron flows.
Current takes on QC are the opposite. There's a lot more noise than signal, and adding more complexity makes the problem worse in non-linear ways.
Indeed, and at the same the breakthroughs are vastly outnumbered by ideas which had plausible sounding counterarguments which turned out to be correct. Which is to say, the burden of proof is on the people making claims that something implausible-sounding is plausible.
I'm not trying to say anything about whether or not a CRQC will ever be built. I'm also not trying to say that pursuing PQC in the short term is a bad idea. But what I am saying is that the burden of proof remains on the believers to show that the engineering challenges are more than theoretically surmountable.