9 ms·

> Researchers like Jaime Sevilla and Jess Riedel support this timeline, publishing a report in late 2020 that claimed a 90% confidence of RSA-2048 being factore

by sampo 2y ago

> Researchers like Jaime Sevilla and Jess Riedel support this timeline, publishing a report in late 2020 that claimed a 90% confidence of RSA-2048 being factored before 2060. I am skeptical. 36 years is a long time, but in the past 10 years there hasn't been much progress: year 2001: factorization of 15 (IBM) year 2012: factorization of 21 (University of Bristol) year 2019: factorization of 35 attempt, failed (IBM) https://en.wikipedia.org/wiki/Shor%27s_algorithm#Physical_implementation https://en.wikipedia.org/wiki/Shor%27s_algorithm#Physical_im...

sebzim4500 2y ago
IIRC none of those uses of shor's algorithm were real (well maybe the 2019 one was, but that failed). There's a threshold you need to reach for quantum error correction to work and we are approaching it pretty steadily on a log scale.
- blamestross 2y ago
  lots of functions with horizontal asymptotes look ok on a log scale until they don't.
- JanisErdmanis 2y ago
  Quantum error correction produces logical qubits that have smaller nonzero error rate. Thus it needs to be applied repeatedly to achieve a necessary error rate to produce meaningful results. For Shor algorithm the error rate needs to decrease exponentially with the number of qubits. Thus even though IBM has a hundred qubits QCs they still only have managed to use five qubits to factorize a number 21.
  - sebzim4500 2y ago
    >For Shor algorithm the error rate needs to decrease exponentially with the number of qubits I have never seen a result like that. Do you have a citation?
    - JanisErdmanis 2y ago
      I have forgotten the source where I stumbled on the requirement for a qubit error rate to run the Shor algorithm. I would greatly value it if someone could put a key reference here. A recent result considers a generic error model and a subclass for particular kinds of prime numbers [1]. The important result is $epsilon > cn^{−1/3}$ where epsilon represents qubit error rate and n number of bits in the factorised number. As $n = 2^N$ where N is a number of qubits, the result: error_rate < const/2^{N/3} Therefore, the error rate must decrease exponentially with the number of logical qubits with which the computation is made. [1]: https://arxiv.org/pdf/2306.10072 https://arxiv.org/pdf/2306.10072
- tromp 2y ago
  They were illegitimate instances of Shor according to [1]: > Of course this should not be considered a serious demonstration of Shor’s algorithm. It does, however, illustrate the danger in “compiled” demonstrations of Shor’s algorithm. To varying degrees, all previous factorization experiments have benefited from this artifice. While there is no objection to having a classical compiler help design a quantum circuit (indeed, probably all quantum computers will function in this way), it is not legitimate for a compiler to know the answer to the problem being solved. To even call such a procedure compilation is an abuse of language. [1] https://arxiv.org/pdf/1301.7007 https://arxiv.org/pdf/1301.7007
zeroonetwothree 2y ago
It’s hard to make predictions, especially about the future.
- bee_rider 2y ago
  When a prediction has a probability attached to it, it should be possible to check the math. In some sense it isn’t really a prediction about the future, so much as a statement about current information (which is not complete). Or, possibly, they are using “90% confidence” colloquially as “pretty sure.” If so, that should probably be made more clear. He’s using the fact that the researchers agree as an argument from authority, which is doubly wrong if the apparent authorities here were just giving their hunches.
  - threecheese 2y ago
    It’s a quote, and you are gonna laugh when you find out who said it.
    - bee_rider 2y ago
      Attributed to Yogi Berra, I just don’t think it fits the situation here very well.
- spookie 2y ago
  "When a distinguished but elderly scientist states that something is possible, he is almost certainly right. When he states that something is impossible, he is very probably wrong."
- jessriedel 2y ago
  We are quite clear in the abstract and the paper that the predictions are conditional on the continuation of the smooth progress seen to date. Contrary to the GP's interpretation, these predictions are holding up well.
jessriedel 2y ago
Co-author of the paper here. The “largest integer factored” metric is terrible for several reasons, which is well recognized by researchers and is why people rarely publish those sorts of claims any more. Without net-positive error correction, it’s basically a function of how low your error rate is and how many bits that allows you to compute on with low chance of error, but as soon as the error rate crosses the fault-tolerance threshold then suddenly your storage is limited only by how many qubits you can build. So you can’t use this metric (if people were even publishing it) to predict anything after fault tolerance is achieved. On more meaningful metrics, there has been steady progress.
- wadadadad 2y ago
  Which metrics would be more meaningful?
  - jessriedel 2y ago
    Single most important is probably two-gate error rates, until the fault tolerance threshold is crossed. Then things like connectivity and logical-qubit counts (where logical qubits are roughly proportional to physical qubits, but suppressed by an overhead that improves with lower error rates and implementation-specific factors).
- vlovich123 2y ago
  I thought the error rate has stayed pretty exponential in terms of the number of physical qubits needed to express a logical qubit and it’s not actually known if we’re any closer on that metric vs other more easily achieved metrics. Additionally, I was under the impression that not all QCs being built are able of executing Shor’s algorithm which added additional challenges that aren’t solved. My final impression is that having the QC algorithm run faster than a classical computer doing the same operation has also not necessarily gotten better so we don’t even know if we are actually closer to Quantum supremacy in terms of actually useful more general computation instead of the limited supremacy that Google achieved in 2019 on specific problems, similar to the (still ongoing?) controversy whether DWave built a QC or a quantum annealer capable of accelerating simulations of very specific physical properties. Is this impression outdated and/or misinformed? Would love to update my priors.
bawolff 2y ago
> I am skeptical. 36 years is a long time, but in the past 10 years there hasn't been much progress: 36 years ago we didn't even know shor's algorithm existed, and didn't know quantum computers could non-exponentially factor integers at all. So in a certain sense, we have made infinite progress in the last 36 years. Who knows what could happen in the next 36. More generally, i think making science predictions that far out is basically impossible.
- shagie 2y ago
  https://youtu.be/6qD9XElTpCE https://youtu.be/6qD9XElTpCE > Hear the story of Shor's Algorithm, straight from the source, Peter Shor. Shor's part of the story starts in '81. Though, I generally agree with the it is hard to make predictions that far out. We've got the math to do some higher things, but we still don't have flying cars and fusion power.
  - bawolff 2y ago
    Shor being alive in 1981 is not the same thing as saying shor's algorithm was discovered in 1981.
    - shagie 2y ago
      The seeds of Shor's algorithm was when he went to a lecture on negative probability by Feynman in 1981 as a graduate student. Shor's part of the storm starts in 1981.
DebtDeflation 2y ago
According to Locklin, even factoring 15 requires precompilation where you have to calculate the factors in advance before sending to the QC in order to minimize the number of required gates.

by sampo 2y ago

sebzim4500 2y ago

IIRC none of those uses of shor's algorithm were real (well maybe the 2019 one was, but that failed). There's a threshold you need to reach for quantum error correction to work and we are approaching it pretty steadily on a log scale.

blamestross 2y ago
lots of functions with horizontal asymptotes look ok on a log scale until they don't.
JanisErdmanis 2y ago
Quantum error correction produces logical qubits that have smaller nonzero error rate. Thus it needs to be applied repeatedly to achieve a necessary error rate to produce meaningful results. For Shor algorithm the error rate needs to decrease exponentially with the number of qubits. Thus even though IBM has a hundred qubits QCs they still only have managed to use five qubits to factorize a number 21.
- sebzim4500 2y ago
  >For Shor algorithm the error rate needs to decrease exponentially with the number of qubits I have never seen a result like that. Do you have a citation?
  - JanisErdmanis 2y ago
    I have forgotten the source where I stumbled on the requirement for a qubit error rate to run the Shor algorithm. I would greatly value it if someone could put a key reference here. A recent result considers a generic error model and a subclass for particular kinds of prime numbers [1]. The important result is $epsilon > cn^{−1/3}$ where epsilon represents qubit error rate and n number of bits in the factorised number. As $n = 2^N$ where N is a number of qubits, the result: error_rate < const/2^{N/3} Therefore, the error rate must decrease exponentially with the number of logical qubits with which the computation is made. [1]: https://arxiv.org/pdf/2306.10072 https://arxiv.org/pdf/2306.10072
tromp 2y ago
They were illegitimate instances of Shor according to [1]: > Of course this should not be considered a serious demonstration of Shor’s algorithm. It does, however, illustrate the danger in “compiled” demonstrations of Shor’s algorithm. To varying degrees, all previous factorization experiments have benefited from this artifice. While there is no objection to having a classical compiler help design a quantum circuit (indeed, probably all quantum computers will function in this way), it is not legitimate for a compiler to know the answer to the problem being solved. To even call such a procedure compilation is an abuse of language. [1] https://arxiv.org/pdf/1301.7007 https://arxiv.org/pdf/1301.7007

zeroonetwothree 2y ago

It’s hard to make predictions, especially about the future.

bee_rider 2y ago
When a prediction has a probability attached to it, it should be possible to check the math. In some sense it isn’t really a prediction about the future, so much as a statement about current information (which is not complete). Or, possibly, they are using “90% confidence” colloquially as “pretty sure.” If so, that should probably be made more clear. He’s using the fact that the researchers agree as an argument from authority, which is doubly wrong if the apparent authorities here were just giving their hunches.
- threecheese 2y ago
  It’s a quote, and you are gonna laugh when you find out who said it.
  - bee_rider 2y ago
    Attributed to Yogi Berra, I just don’t think it fits the situation here very well.
spookie 2y ago
"When a distinguished but elderly scientist states that something is possible, he is almost certainly right. When he states that something is impossible, he is very probably wrong."
jessriedel 2y ago
We are quite clear in the abstract and the paper that the predictions are conditional on the continuation of the smooth progress seen to date. Contrary to the GP's interpretation, these predictions are holding up well.

jessriedel 2y ago

Co-author of the paper here. The “largest integer factored” metric is terrible for several reasons, which is well recognized by researchers and is why people rarely publish those sorts of claims any more. Without net-positive error correction, it’s basically a function of how low your error rate is and how many bits that allows you to compute on with low chance of error, but as soon as the error rate crosses the fault-tolerance threshold then suddenly your storage is limited only by how many qubits you can build. So you can’t use this metric (if people were even publishing it) to predict anything after fault tolerance is achieved. On more meaningful metrics, there has been steady progress.

wadadadad 2y ago
Which metrics would be more meaningful?
- jessriedel 2y ago
  Single most important is probably two-gate error rates, until the fault tolerance threshold is crossed. Then things like connectivity and logical-qubit counts (where logical qubits are roughly proportional to physical qubits, but suppressed by an overhead that improves with lower error rates and implementation-specific factors).
vlovich123 2y ago
I thought the error rate has stayed pretty exponential in terms of the number of physical qubits needed to express a logical qubit and it’s not actually known if we’re any closer on that metric vs other more easily achieved metrics. Additionally, I was under the impression that not all QCs being built are able of executing Shor’s algorithm which added additional challenges that aren’t solved. My final impression is that having the QC algorithm run faster than a classical computer doing the same operation has also not necessarily gotten better so we don’t even know if we are actually closer to Quantum supremacy in terms of actually useful more general computation instead of the limited supremacy that Google achieved in 2019 on specific problems, similar to the (still ongoing?) controversy whether DWave built a QC or a quantum annealer capable of accelerating simulations of very specific physical properties. Is this impression outdated and/or misinformed? Would love to update my priors.

bawolff 2y ago

> I am skeptical. 36 years is a long time, but in the past 10 years there hasn't been much progress: 36 years ago we didn't even know shor's algorithm existed, and didn't know quantum computers could non-exponentially factor integers at all. So in a certain sense, we have made infinite progress in the last 36 years. Who knows what could happen in the next 36. More generally, i think making science predictions that far out is basically impossible.

shagie 2y ago
https://youtu.be/6qD9XElTpCE https://youtu.be/6qD9XElTpCE > Hear the story of Shor's Algorithm, straight from the source, Peter Shor. Shor's part of the story starts in '81. Though, I generally agree with the it is hard to make predictions that far out. We've got the math to do some higher things, but we still don't have flying cars and fusion power.
- bawolff 2y ago
  Shor being alive in 1981 is not the same thing as saying shor's algorithm was discovered in 1981.
  - shagie 2y ago
    The seeds of Shor's algorithm was when he went to a lecture on negative probability by Feynman in 1981 as a graduate student. Shor's part of the storm starts in 1981.

DebtDeflation 2y ago

According to Locklin, even factoring 15 requires precompilation where you have to calculate the factors in advance before sending to the QC in order to minimize the number of required gates.