4 ms·

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 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 https://www.nature.com/articles/414883a [2]: https://www.nature.com/articles/nphoton.2012.259 https://www.nature.com/articles/nphoton.2012.259 [3]: https://arxiv.org/pdf/2103.13855v1.pdf https://arxiv.org/pdf/2103.13855v1.pdf

klabb3 3y ago
> 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.

klabb3 3y ago

> 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.