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.
Yet it has been 53 years since we have been able to send a manned mission to the moon . No other program has or likely to come close in the next 13 years including the current US one. By 2038 the moon landings would be closer to Wright brothers than future us.
The curve of progress is only smooth and exponential when you squint hard .
It is a narrow few decades of exponential growth hardly can reasonably be expected to last for 100+ years .
It is for the same reason you cannot keep doubling grains on a chess board just because you did it 10-20 steps quickly.
Fusion power, quantum computing are all always two decades away for a reason despite the money being spent . AI has gone through 3-4 golden ages in living memory and yet too many keep believing this one would last.
Reality is when the conditions are right, I.e. all the ground work has been done for decades or centuries before there can be rapid innovation for a short(few decades at best) time
A near total lack of demand explains that impressive stall.
Even if the shuttle had worked out as well as its designers hoped, was envisioned as a major retreat, while sucking all the dollars out of the room.
And today, the market for lunar landings is still very small.
I think what it shows is that many technologies might have come earlier from a research and development standpoint, if we had enough money to burn. But that was an unusual situation.
It is not like Fusion or Quantum Computing has lacked serious or continuous funding over the last 20-30 years.
Foundational model development is a classic current example. The returns are diminishing significantly, despite the tens of billions each quarter being thrown at the problem.
No other R&D effort in our history has this much resources being allocated to it, perhaps including even the Moon landings.
However the ability to allocate resources has limits. Big tech can spend few hundred billion a year a number that would have been unimaginable even a decade ago, but even they cannot spend few trillion dollars a year.