Hacker News Reader

It is! Taking into account that only the Schor algorithm is proven to be exponentially faster in factorising numbers and looking into current progress on using it, the threat for RSA 2048 will become real in ridiculous 2^2048 years. This can be estimated by taking three events in factorisation:

2002: factorisation of 15 [1]

2012: factorisation of 21 [2]

2022: factorisation of 35 by IBM (although the article is about number 21, but let’s give them credit) [3]

In a plot, the tendency is somewhat linear, with the factorised number increasing by one every year.

A sceptic immediately replies to this thread, saying we already have 100-1000 qubit quantum computers and are on the path to getting a million qubits in the foreseeable future. That may as well be true. The issue is that the Schoor algorithm requires that the error rate of the qubit operations scale exponentially with the number of qubits. This is why IBM only uses five qubits in [3], although they already had a hundred qubit QCs at that time. It just produces meaningless results when used with more qubits.

This is also why the line for factorisation is about to be linear. If the error rate of the qubit operations decreases by 20% every year and we have exponential progress, the usefulness of the Schor algorithm taken on a log scale would be linear.

The error correction is not a panacea either. It does not reduce errors to zero for logical qubits but rather reduces them after the error threshold is reached. It would require repeated application to get the necessary error threshold to run the Schor algorithm for a desired number, which would require an unreasonable number of qubits.

[1]: https://www.nature.com/articles/414883a

[2]: https://www.nature.com/articles/nphoton.2012.259

[3]: https://arxiv.org/pdf/2103.13855v1.pdf

> The issue is that the Schoor algorithm requires that the error rate of the qubit operations scale exponentially with the number of qubits.

So… traditional silicon computing scales exponentially in time, but QC computes in constant time(!) with the minor detail that it scales exponentially in error.

> If the error rate of the qubit operations decreases by 20% every year and we have exponential progress, the usefulness of the Schor algorithm taken on a log scale would be linear.

Right, which is exactly the type of leeway you need, no? 1-2 qubits per year will take many decades to break ECC or RSA. It’s the same Moores law-style assumptions baked into traditional computing getting faster.

> This is why IBM only uses five qubits in [3], although they already had a hundred qubit QCs at that time. It just produces meaningless results when used with more qubits.

So IBM has this really cool gf, but she’s at a different school so you won’t know her. Half joking, but putting error propagation in the footnotes seems very off to me as a complete layman. Like thinking we can accurately predict the weather 5 months out with a bit more compute.

I don’t expect commercially viable fusion, room temperature superconductors, or useful quantum computers in my lifetime.

The jury is still out on real self driving cars, but I’m less optimistic than I was five years ago.

A friend of mine uses a self-driving taxi service in SF all of the time.

How come you and all your other friends and family don’t? When do you think the rest of you will?

I'd say in half the amount of time it took for us to go from the first internal combustion engine to the Model T? Or if you think that's a bad comparison: The Model T to the honda civic?

If that’s my odds are pretty good of living to see it. I hope you’re right.

Because I don't live in SF. So ask the companies when they'll deploy elsewhere.

> First, do we even have high confidence that QC is the thing that will break current algorithms?

If it doesn't it means our physics theories are fundamentally wrong.

Not necessarily. It could be that ECDLP (Elliptic Curve Discrete Log Problem) is not as hard as we thought.

It's not inconceivable that it's in P (Polynomial time).

In fact, if we were to see current algorithms being broken right now, I think it's more likely to be due to a classical algorithm breakthrough than by quantum algorithms running on an actual large scale quantum computer with hundreds or thousands of logical (i.e. practically error-free) qubits.

We don’t have any mainstream physical theory that describes the process of quantum decoherence aka wave function collapse. We know it happens, but don’t know when exactly or how quickly. So if QCs fail, Quantum Mechanics won’t be proven wrong, but rather we’ll have more data on wave function collapse which has been an open question for more than a century.

I personally like Penrose Objective Collapse theory, because it also connects gravity and QM in an unusual way.

QM predicts that QCs will work. If QCs don't work, QM has a big problem.

Wave collapse interpretation is an orthogonal topic.

Not being able to build something, is not the same as proofing it is impossible. (Unless one has a very high ego.)

It might as well require some unknown tech, or material or rather a real understanding of the domain.

Sure, but parent was saying what if we manage to build QC as we envision them and then they don't work.

QM doesn’t say anything about how long a system can stay in quantum entangled state, so it doesn’t say what is the limit to computations that can be performed on a quantum computer. Some computations were successfully performed, as QM predicts, but now it seems that researchers are hitting a limit.

QM says QC as we envision them will work.

QM says a quantum entangled state will remain like that until disturbed/measured. If there is some limit as you suggest, that means QM is at least partially broken.

That’s right, but it doesn’t specify what exactly is disturbance/measurement. We know from observation that interaction with a macroscopic system causes wave function collapse seemingly instantly. But we don’t know much about in-between behavior, like what happens when interacting with another microscopic system and does wave function of a microscopic quantum system collapse on it’s own given enough time.

> QM predicts that QCs will work.

Although that is true, QC isn't ruled in or out by other current observations, despite the extreme accuracy with which quantum physics theories match a very wide range of observations. If QCs can't work, QM will need to be amended but very subtly.

It's even possible that useful QC can't work for such a subtle reason that there's no way to be sure.

According to current physics and computability theories, it is thought you need a useful QC to calculate the behaviour of any physical system that has the properties required by a useful QC. Where "useful" means large enough to be out of reach of classical computers, and "calculate" means to sufficient accuracy to test if calculated behaviours match observation.

This means, the universe might deviate from the appealing math of quantum physics just enough to prevent a highly-entangled QC from ever working, at the same time as agreeing with everything we can calculate from what we have observed so far.

Examples of things we can measure but not calculate accurately: Chemical behaviours, material properties and phase transitions (at least some of them) depend on highly-entangled quantum effects, even higher than any QC is aiming for.

You might think, if we know the basic physics, and we can accurately measure temperature, energy, reaction rates and other properties, those measurements surely gives us a good idea if quantum physics theory matches the universe.

But where there is high entanglement, we can't do the calculations accurately enough to say for sure. They are limited by computational complexity on conventional computers. We have good approximations that are very useful, but they aren't precise enough to rule QC feasibility one way or the other.

QM is quite simple.

But then we also have QFT. The difficult things you were talking about fall more on the QFT side of things.

In my view QM predicts QC will work just like math predicts Turing machines will work.

But the practical realization of an advanced Turing machine can indeed be a very complicated thing - in fact we need quantum physics to understand how modern transistors work.

So if practical useful QC don't work, wouldn't that be more of a QFT engineering problem?

I fully agree that we might not be able to build a working QC, just like we are struggling with fusion power for over 50 years now despite theory predicting it should work, and in theory it being a simpler problem than QCs.

Maybe I'm being pedantic with the distinction between QM/QFT...

> First, do we even have high confidence that QC is the thing that will break current algorithms?

Yes?

I mean nothing is certain, but it is the most viable known threat by a wide margin.

> Secondly, how much time from “the writing is on the wall” until bad actors can deploy them for financial gain? Unless it’s short, why not wait and migrate later?

Nobody knows, but its difficult to coordinate changes, and it is difficult to know which quantum algs actually work. It can take decades to have confidence a new crypto promitive actually works.

As far as actually changing things, look how long it took to change out md5. People started warning it was insecure in 1996, it was totally broken in 2005, and in 2012 the flame malware used it to hack computers.