Comment by sweis | Hacker News Reader

Comment by sweis | Hacker News Reader

I think we are many, many years away from a quantum computer being able to break 256-bit ECC:

https://sam-jaques.appspot.com/quantum_landscape

https://www.bsi.bund.de/EN/Topics/Cryptography/QuantumComput...

The current record in factoring with Shor's algorithm is 21. Yes. 3*7. That record has stood for 12 years and arguably is not even running Shor's because it required a priori knowledge of the factors.

Even with "cheating" by using knowledge of the factors, in 20 years we have seen seen a single bit of improvement.

None of the new quantum computers from IonQ, Google, or QuEra with 32-256 qubits are even able to even replicate those early results. D-Wave claims 5000 qubits, but that is for adiabatic QC, which to my knowledge, cannot run Shor's algorithm.

To be a threat, QCs need millions of qubits and orders of magnitude better error correction. I think people make the mistake of looking at the speed of progress of classical computers and thinking it applies to QC. It's just not happening.

Classical silicon chips got to exponential growth because chips were profitable - the profits could be poured back into R&D enabling a natural feedback loop. Profitability wasn't terribly difficult because computers were VERY fast at calculations compared to the next best thing - humans.

For QC to hit natural exponential growth, it would need to be economically feasible compared to the next best thing - classical computers. Is there anything even a tiny QC can do better, faster, and cheaper than a classical computer?

The most sensational, and arguably most valuable, use is breaking hard encryption, so QC has "nation state STEM/security funding" written all over it. Even if it's 1% likely to be used in this way, it makes sense for wealthy nations to spend on it. But yeah, it's not the same story as for the IC boom.

>Is there anything even a tiny QC can do better, faster, and cheaper than a classical computer?

This is a really good question, and I don't know the answer. If I were to try, I'd focus on QC efficient algorithms, and what you can do with that in an application. So, in your system a QC is a magic box that takes an O(n^2) algo and makes it O(n), say. But for ordinary humans, n is very small, so this won't matter. I don't think there is mundane problem, e.g. one dealing with ordinary productivity, that a QC can do better than classical. It's shaping up to be a nation-state funded capital intensive information superweapon against private communication. And you know what? Maybe if you can maintain the infrastructure and staff to build one, you deserve to have it! It's especially untroubling if it's capacity is limited, like being able to read 10 2048-bit RSA encrypted messages per day. That's a superpower, but a very limited and expensive one, which I am fine with.

> The most sensational, and arguably most valuable, use is breaking hard encryption, so QC has "nation state STEM/security funding"

Large-scale electronic computers were first developed for exactly the same purpose, during WWII. The first commercial computers weren't available until a few years after the war, about five years after Colossus.

Indeed, and it's fun to look at the remarkable differences, which are usually more visible in these early stages of development. It gets to the very heart of what "state" is; the beginning of computation really goes back further, to automata and Charles Babbage, where state is encoded into the position of a cog, and decoded by looking at the cog.

For quantum computing, state is written into the wave function of an isolated particle, which is entangled with other isolated particles such that you can perform a read and get something useful out of it. (TBH I'm a little confused about how QC works at the physical level, because it seems like your program could require different patterns of entanglement, but AFAIK the pattern of qubit entanglement is determined by the hardware setup, and cannot be modified at runtime. Maybe there is a generally reusable "shape" that can be interacted with, cleared, setup for a new computation, etc by poking at the particles in some specific order. It's probably a really nice problem for physics folks who feared they'd never get to use their QM classes.)

I thought Turing's Cathedral told the story leading up to that feedback loop quite well. The insignificant size of the grants that enabled the birth of a new industry stand out a bit.

https://www.penguinrandomhouse.com/books/44425/turings-cathe...

I think classical silicon also got exponential because getting better silicon meant better EDA tools.

This is an excellent point.

I wonder if future QC design tools will require a QC to run effectively. Then we could get a similar feedback loop.

> Is there anything even a tiny QC can do better, faster, and cheaper than a classical computer?

That's an area of active research in computational complexity theory. It's not known if the class BQP[1] (bounded-error quantum polynomial time) is equal to P (classical polynomial time). Many people suspect that BQP > P, but it may not be and quantum computers might not have any problems where they're faster than classical computers.

[1] https://en.wikipedia.org/wiki/BQP

This (non-technical) article asserts that statistical analysis of D-Wave (or another quantum annealer) might be used far before Shor's algorithm becomes a factor.

https://www.forbes.com/sites/arthurherman/2021/06/07/q-day-i...

> D-Wave claims 5000 qubits, but that is for adiabatic QC, which to my knowledge, cannot run Shor's algorithm.

https://www.hpcwire.com/2021/10/21/d-wave-embraces-gate-base...

While I have no basis for my judgements, for some reason I think that "real" quantum computers just can't exist in our universe. May be it's not possible to correct enough errors or something like that. By "real" I mean those which can factor numbers that are outside of classical computing capabilities.

And those computers that do exist - they're just glorified analog machines which were known long time ago.

Reply on news.ycombinator.com