4 ms·

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 r

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.
- cwillu 2y ago
  A QC that can't run Shor's algorithm is not a QC, as much as D-Wave screams and stamps their feet that it's not fair.
  - jessriedel 2y ago
    In principle it can be a QC, just not a general purpose (“Q-Turing complete”) QC. There were useful classical computing machines before there were general purpose Turing-complete classical computers. In practice, the first useful QCs will probably be Q-Turing complete.
  - NickC25 2y ago
    I'm a complete layman when it comes to Quantum Computing, but I thought Shor's algorithm is effectively the most basic usecase example of Quantum Computers? I'm confused here.
    - dumbo-octopus 2y ago
      Yes, but it doesn't work on modern hardware. Too much noise. Everyone in the industry is basically fully occupied with coming up with a mechanism for active error correction. But based on what I've heard from the folks on the front lines, it's still 10+ years away at minimum.
    - jessriedel 2y ago
      There are extant non-general purpose quantum computers that solve super esoteric useless math problems specially designed to be easy on these primitive quantum computers but infeasible on any classical computer. (This is “quantum supremacy” aka “quantum advantage”.) Furthermore, we expect to develop slightly less primitive quantum computers in the medium-term that can solve maybe-interesting quantum simulation questions without having the capability to run Shor’s algorithm (at least on an interestingly large integers). So no, Shor’s algorithm is not the most basic use case. It’s just one of the cleanest to understand.
      - 2y ago
tedunangst 2y ago
Predictions as to the first coprime factored after it has been achieved? Will they publish just rsa-1024, or drop a whole load of factors all at once, eliminate the whole field?
- jessriedel 2y ago
  My non-confident impression is that when fault tolerance is first achieved it will still be somewhat expensive to add qubits, so the size of the largest integers that are factorizable will grow roughly like “quantum Moore’s law”. Like maybe they double qubit count every year or two, and I think the length (in digits) of the largest factorizable integer will scale like that, modulo a root or square. I could be confused though.

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.

cwillu 2y ago
A QC that can't run Shor's algorithm is not a QC, as much as D-Wave screams and stamps their feet that it's not fair.
- jessriedel 2y ago
  In principle it can be a QC, just not a general purpose (“Q-Turing complete”) QC. There were useful classical computing machines before there were general purpose Turing-complete classical computers. In practice, the first useful QCs will probably be Q-Turing complete.
- NickC25 2y ago
  I'm a complete layman when it comes to Quantum Computing, but I thought Shor's algorithm is effectively the most basic usecase example of Quantum Computers? I'm confused here.
  - dumbo-octopus 2y ago
    Yes, but it doesn't work on modern hardware. Too much noise. Everyone in the industry is basically fully occupied with coming up with a mechanism for active error correction. But based on what I've heard from the folks on the front lines, it's still 10+ years away at minimum.
  - jessriedel 2y ago
    There are extant non-general purpose quantum computers that solve super esoteric useless math problems specially designed to be easy on these primitive quantum computers but infeasible on any classical computer. (This is “quantum supremacy” aka “quantum advantage”.) Furthermore, we expect to develop slightly less primitive quantum computers in the medium-term that can solve maybe-interesting quantum simulation questions without having the capability to run Shor’s algorithm (at least on an interestingly large integers). So no, Shor’s algorithm is not the most basic use case. It’s just one of the cleanest to understand.
    - 2y ago

tedunangst 2y ago

Predictions as to the first coprime factored after it has been achieved? Will they publish just rsa-1024, or drop a whole load of factors all at once, eliminate the whole field?

jessriedel 2y ago
My non-confident impression is that when fault tolerance is first achieved it will still be somewhat expensive to add qubits, so the size of the largest integers that are factorizable will grow roughly like “quantum Moore’s law”. Like maybe they double qubit count every year or two, and I think the length (in digits) of the largest factorizable integer will scale like that, modulo a root or square. I could be confused though.