5 ms·

We can expect a quantum computer with 20 million noisy qubits to break RSA 2048 [1] I can't speak to coherence time or circuit depth concerns, but qubit counts

We can expect a quantum computer with 20 million noisy qubits to break RSA 2048 [1] I can't speak to coherence time or circuit depth concerns, but qubit counts are doubling roughly every year. Current chips have thousands of qubits, so the exponential scaling implies we'd have 20 million qubits by 2035-2040. edit: And from the paper, the required quantum volume ("megaqubitdays") scales bewteen O(n^3) and O(n^4) with RSA key length. So a few years after breaking RSA 2048, you'd have a computer five times larger that could break RSA 3072. [1] https://quantum-journal.org/papers/q-2021-04-15-433/ https://quantum-journal.org/papers/q-2021-04-15-433/

tptacek 3y ago
More detail on progress towards quantum factoring of RSA (among other things): https://sam-jaques.appspot.com/quantum_landscape https://sam-jaques.appspot.com/quantum_landscape I'm not super concerned. Cynically: one big driver of research into PQ cryptography is that it's a full employment program for academic cryptographers. Not that there's anything wrong with that! I like a Richelot isogeny as much as the next guy, or I would if I understood what they were.
mirekrusin 3y ago
> Current chips have thousands of qubits, really? I thought we have 70 max?
- cwillu 3y ago
  I suspect d-wave nonsense was involved in the confusion.
- MattPalmer1086 3y ago
  IBM released a processor with 433 qubits last year, and they say they are on track to deliver a 1121 qubit processor this year. https://www.ibm.com/quantum/roadmap https://www.ibm.com/quantum/roadmap
  - mirekrusin 3y ago
    Do you have links to some results for this 433 processor? The only results I've seen is this [0] from April which is 70 qbit and it's all about fighting with noise. It looks like overcoming noise is exponentially harder with more qubits and this whole quantum thing may never work for practical problems after all? [0] https://arxiv.org/pdf/2304.11119.pdf https://arxiv.org/pdf/2304.11119.pdf
sweis 3y ago
The record quantum computers can factor is 21 -- and that is by cheating by already knowing the factors are 3 and 7. There are other results that use special form composites which don't count. So a QC can factor a 5 bit number with Shor's algorithm in 2023 (with some cheating). That record has not changed for 10+ years. I publicly bet 8 years ago that nobody would factor the number 35 by 2030. I hope I'm proved wrong.
fsh 3y ago
Google's "quantum supremacy" paper was about a 53 qubit chip in 2019 [1]. This year, they reported having 70 qubits [2]. Looking at the papers (and supplements), the gate fidelities and qubit lifetimes have stayed roughly the same. This really doesn't look like anything like Moore's law to me. [1] https://doi.org/10.1038/s41586-019-1666-5 https://doi.org/10.1038/s41586-019-1666-5 [2] https://doi.org/10.48550/arXiv.2304.11119 https://doi.org/10.48550/arXiv.2304.11119
- orlp 3y ago
  If we didn't invent photolithography, we'd still be using computers the size of buildings limited to universities and military installations. Right now no one knows how to build a scalable quantum computer. But as soon as we find out the equivalent of lithography for building quantum chips, the progress will come, and it will come quickly and suddenly.
  - Mistletoe 3y ago
    How do you know there is an equivalent process for quantum chips?
    - krastanov 3y ago
      There are some equivalents already in existence (spin qubits in CMOS processes), that use the exact same lithography techniques. There are a few other potential alternatives too. All of them suffer from harder engineering challenges than the much "easier" to produce (in small volumes) transmons and trapped ions/atoms/molecules. Thus a plausible future is one in which the first somewhat-useful quantum computers are tens of thousands of qubits in transmon/ion hybrid systems. Then (in that plausible future) the spin qubits in CMOS do catch up, and thanks to their superior manufacturing scalability, they blow past the capabilities of transmons/ions. Not too different from how we had to use vacuum lamps while we figure out how solid state systems can work... Or spinning hard drives before we figured out SDDs. Or maybe none of this would work out and the whole field would be a bust... but you know Clarke's laws https://en.wikipedia.org/wiki/Clarke%27s_three_laws https://en.wikipedia.org/wiki/Clarke%27s_three_laws
jessriedel 3y ago
At least as of 2020, it looked like both qubit counts and two-qubit gate quality were improving exponentially, and our naive extrapolation said RSA 2048 wouldn't get cracked by 2039 at 95% confidence. https://arxiv.org/abs/2009.05045 https://arxiv.org/abs/2009.05045 As far as I can tell, this website suggests that two-qubit gate infidelity has continued to improve exponentially, although it's hard to tell if these are reliable datapoints. https://metriq.info/Task/38 https://metriq.info/Task/38 Because there's typically an engineering tension between qubit count and gate quality, what you want to track is something like quantum volume, which looks to be on trend https://metriq.info/Task/34 https://metriq.info/Task/34 but it's notable that Google achieved quantum supremacy without having amazing quantum volume numbers, so it's not a perfect metric https://spectrum.ieee.org/quantum-computing-google-sycamore https://spectrum.ieee.org/quantum-computing-google-sycamore Worth noting that once you cross the fault tolerant threshold you will probably see a big shift in how engineering effort is distributed: many researchers think it will be harder to improve gate quality than just increase increase qubit counts to make up for it, so you may see gate quality stall and extrapolation become even less reliable.
- akvadrako 3y ago
  > once you cross the fault tolerant threshold If we cross the threshold. Until then, adding a qubit requires halving the noise floor, so the Moore's law equivalent to exponential scaling is basically adding a fixed number of qubits per year.
  - jessriedel 3y ago
    Not sure what you're saying. Are you suggesting that gates surpassing the fault tolerant threshold will never be achieved? The vast majority of experts disagree with this. Without fault tolerance, you have a hard wall on circuit depth because errors grow exponentially with depth. You can't make up for this by adding any number of qubits. "Halving the noise floor" means...what, improving gate fidelity?
    - akvadrako 3y ago
iraqmtpizza 3y ago
if qubit counts are doubling every year then why is 21 still the largest number ever factored with a quantum algorithm

tptacek 3y ago

More detail on progress towards quantum factoring of RSA (among other things): https://sam-jaques.appspot.com/quantum_landscape https://sam-jaques.appspot.com/quantum_landscape I'm not super concerned. Cynically: one big driver of research into PQ cryptography is that it's a full employment program for academic cryptographers. Not that there's anything wrong with that! I like a Richelot isogeny as much as the next guy, or I would if I understood what they were.

mirekrusin 3y ago

> Current chips have thousands of qubits, really? I thought we have 70 max?

cwillu 3y ago
I suspect d-wave nonsense was involved in the confusion.
MattPalmer1086 3y ago
IBM released a processor with 433 qubits last year, and they say they are on track to deliver a 1121 qubit processor this year. https://www.ibm.com/quantum/roadmap https://www.ibm.com/quantum/roadmap
- mirekrusin 3y ago
  Do you have links to some results for this 433 processor? The only results I've seen is this [0] from April which is 70 qbit and it's all about fighting with noise. It looks like overcoming noise is exponentially harder with more qubits and this whole quantum thing may never work for practical problems after all? [0] https://arxiv.org/pdf/2304.11119.pdf https://arxiv.org/pdf/2304.11119.pdf

sweis 3y ago

The record quantum computers can factor is 21 -- and that is by cheating by already knowing the factors are 3 and 7. There are other results that use special form composites which don't count. So a QC can factor a 5 bit number with Shor's algorithm in 2023 (with some cheating). That record has not changed for 10+ years. I publicly bet 8 years ago that nobody would factor the number 35 by 2030. I hope I'm proved wrong.

fsh 3y ago

Google's "quantum supremacy" paper was about a 53 qubit chip in 2019 [1]. This year, they reported having 70 qubits [2]. Looking at the papers (and supplements), the gate fidelities and qubit lifetimes have stayed roughly the same. This really doesn't look like anything like Moore's law to me. [1] https://doi.org/10.1038/s41586-019-1666-5 https://doi.org/10.1038/s41586-019-1666-5 [2] https://doi.org/10.48550/arXiv.2304.11119 https://doi.org/10.48550/arXiv.2304.11119

orlp 3y ago
If we didn't invent photolithography, we'd still be using computers the size of buildings limited to universities and military installations. Right now no one knows how to build a scalable quantum computer. But as soon as we find out the equivalent of lithography for building quantum chips, the progress will come, and it will come quickly and suddenly.
- Mistletoe 3y ago
  How do you know there is an equivalent process for quantum chips?
  - krastanov 3y ago
    There are some equivalents already in existence (spin qubits in CMOS processes), that use the exact same lithography techniques. There are a few other potential alternatives too. All of them suffer from harder engineering challenges than the much "easier" to produce (in small volumes) transmons and trapped ions/atoms/molecules. Thus a plausible future is one in which the first somewhat-useful quantum computers are tens of thousands of qubits in transmon/ion hybrid systems. Then (in that plausible future) the spin qubits in CMOS do catch up, and thanks to their superior manufacturing scalability, they blow past the capabilities of transmons/ions. Not too different from how we had to use vacuum lamps while we figure out how solid state systems can work... Or spinning hard drives before we figured out SDDs. Or maybe none of this would work out and the whole field would be a bust... but you know Clarke's laws https://en.wikipedia.org/wiki/Clarke%27s_three_laws https://en.wikipedia.org/wiki/Clarke%27s_three_laws

jessriedel 3y ago

At least as of 2020, it looked like both qubit counts and two-qubit gate quality were improving exponentially, and our naive extrapolation said RSA 2048 wouldn't get cracked by 2039 at 95% confidence. https://arxiv.org/abs/2009.05045 https://arxiv.org/abs/2009.05045 As far as I can tell, this website suggests that two-qubit gate infidelity has continued to improve exponentially, although it's hard to tell if these are reliable datapoints. https://metriq.info/Task/38 https://metriq.info/Task/38 Because there's typically an engineering tension between qubit count and gate quality, what you want to track is something like quantum volume, which looks to be on trend https://metriq.info/Task/34 https://metriq.info/Task/34 but it's notable that Google achieved quantum supremacy without having amazing quantum volume numbers, so it's not a perfect metric https://spectrum.ieee.org/quantum-computing-google-sycamore https://spectrum.ieee.org/quantum-computing-google-sycamore Worth noting that once you cross the fault tolerant threshold you will probably see a big shift in how engineering effort is distributed: many researchers think it will be harder to improve gate quality than just increase increase qubit counts to make up for it, so you may see gate quality stall and extrapolation become even less reliable.

akvadrako 3y ago
> once you cross the fault tolerant threshold If we cross the threshold. Until then, adding a qubit requires halving the noise floor, so the Moore's law equivalent to exponential scaling is basically adding a fixed number of qubits per year.
- jessriedel 3y ago
  Not sure what you're saying. Are you suggesting that gates surpassing the fault tolerant threshold will never be achieved? The vast majority of experts disagree with this. Without fault tolerance, you have a hard wall on circuit depth because errors grow exponentially with depth. You can't make up for this by adding any number of qubits. "Halving the noise floor" means...what, improving gate fidelity?
  - akvadrako 3y ago

iraqmtpizza 3y ago

if qubit counts are doubling every year then why is 21 still the largest number ever factored with a quantum algorithm