5 ms·

So how many gates are we talking to factor some "cryptographically useful" number? Is there some pathway that makes quantum computers useful this century?

dsclough 1y ago
Saw this earlier: https://x.com/adamscochran/status/1962148452072124879?s=46 https://x.com/adamscochran/status/1962148452072124879?s=46 As a layman the pathway seems to exist behind multiple massive materials science breakthroughs
- andrewflnr 1y ago
  How is it that we need to build logical qubits out of physical qubits for error correction purposes, but then still need to blow out our logic qubit numbers for error correction purposes, again? It seems like there's something missing from this explanation, at least.
  - adgjlsfhk1 1y ago
    the blow-up is in physical qbits
TacticalCoder 1y ago
[dead]
tripplyons 1y ago
Not sure about the gate count, but if you look at the number of logical qubits required, we are still very far away from factoring numbers that traditional computing has already factored like the 829-bit RSA-250 number.
Legend2440 1y ago
Realistically, you want millions to billions of qubits to compete with classical computers that already have trillions of transistors.
- jameshart 1y ago
  Ah - this helped me understand the numbers in quantum computing a little more clearly. I had been under the impression (based on my naive interpretation of the naming) that the number of qubits in a quantum processor might be something analogous to the number of bits of register state in a regular CPU; that qubits should be thought of more as analogous to transistors or maybe even gates makes it a little clearer why you need so many more qubits to perform more complex operations.
- adgjlsfhk1 1y ago
  the difference is that you need millions of 1 qbits to factor rsa 4096, but you only need 10s of millions to factor rsa 32k. qbits and quantum time scale almost linearly with factor size, but super-polynomially for regular computers
lisper 1y ago
> So how many gates are we talking to factor some "cryptographically useful" number? That is a hard question to answer for two reasons. First, there is no bright line that delineates "cryptographically useful". And second, the exact design of a QC that could do such a calculation is not yet known. It's kind of like trying to estimate how many traditional gates would be needed to build a "semantically useful" neural network back in 1985. But the answer is almost certainly in the millions. [UPDATE] There is a third reason this is hard to predict: for quantum error correction, there is a tradeoff between the error rate in the raw qbit and the number of gates needed to build a reliable error-corrected virtual qbit. The lower the error rate in the raw qbit, the fewer gates are needed. And there is no way to know at this point what kind of raw error rates can be achieved. > Is there some pathway that makes quantum computers useful this century? This century has 75 years left in it, and that is an eternity in tech-time. 75 years ago the state of the art in classical computers was (I'll be generous here) the Univac [1]. Figuring out how much less powerful it was than a modern computer makes an interesting exercise, especially if you do it in terms of ops/watt. I haven't done the math, but it's many, many, many orders of magnitude. If the same progress can be achieved in quantum computing, then pre-quantum encryption is definitely toast by 2100. And it pretty much took only one breakthrough, the transistor, to achieve the improvement in classical computing that we enjoy today. We still don't have the equivalent of that for QC, but who knows when or if it will happen. Everything seems impossible until someone figures it out for the first time. --- [1] https://en.wikipedia.org/wiki/UNIVAC_I#Technical_description https://en.wikipedia.org/wiki/UNIVAC_I#Technical_description
- deleted 1y ago
  [deleted]
- fhdkweig 1y ago
  >> Is there some pathway that makes quantum computers useful this century? > This century has 75 years left in it, and that is an eternity in tech-time. As a comparison, we went from first heavier than air flight to man walking on the moon in only 66 years.
  - thechao 1y ago
nabla9 1y ago
For RSA 4096 10^7 qubits with 10^-4 error rate (order of magnitude). You can do useful and valuable quantum chemistry calculations already with few 100s of qubits with that low error rates, while post-quantum algorithms are becoming more common everyday removing incentives to build crypto cracking quantum computers. I think the quantum computing will advance fastest in directions that are not easy to use in cryptography.
- HappyPanacea 1y ago
  Which valuable quantum chemistry calculations you can do with few 100s of qubits with that low error rates?
  - nabla9 1y ago
    The general idea is that with N fault-tolerant qubits, you can find the ground-state energy of an electronic system with N spin orbitals. 100 spin orbitals is the practical upper limit of current computers, so when you get into several hundred qubits, you can start seeing gains. In some special problems hybrid methods start giving gains in 100 qubits or below. Gate count estimates for performing quantum chemistry on small quantum computers https://arxiv.org/pdf/1312.1695 https://arxiv.org/pdf/1312.1695 A Perspective on Quantum Computing Applications in Quantum Chemistry using 25--100 Logical Qubits https://arxiv.org/pdf/2506.19337 https://arxiv.org/pdf/2506.19337
- smj-edison 1y ago
  Honestly, if all quantum computers manage to pull off is quantum chemistry, I feel like that'll be enough. It would be a massive boon to the field of material sciences at any rate, which underlies so much of current infrastructure.
gjrq 1y ago
Latest numbers are about 1e6 qubits with 1e-4 error rate: https://arxiv.org/abs/2505.15917 https://arxiv.org/abs/2505.15917. Gates (in the sense the OP means) is harder to quantify in the error corrected context once you compile to the operations that are native to your code. Total compute time of about a week assuming a 1MHz "clock" (code cycle time, for the experts). In some ways this is the harder metric to meet than the qubit numbers. Note that the magic of quantum error correction (exponential improvement in the error rate goes both ways): if you could get another 9 in qubit fidelity, you get a much larger improvement in qubit numbers. On the other hand, if you need to split your computation over several systems, things get much worse.
- adgjlsfhk1 1y ago
  given the correct state of gate noise progress, it seems likely that we might get an extra order of magnitude of error before we get the 3 orders of magnitude in gates.
Strilanc 1y ago
> So how many gates are we talking to factor some "cryptographically useful" number? Table 5 of [1] estimates 7 billion Toffoli gates to factor 2048 bit RSA integers. > Is there some pathway that makes quantum computers useful this century? The pathway to doing billions of gates is quantum error correction. [1] estimates distance 25 surface codes would be sufficient for those 7 billion gates (given the physical assumptions it lists). This amplifies the qubit count from 1400 logical qubits to a million physical noisy qubits. Samuel Jacques had a pretty good talk at PQCrypto this year, and he speculates about timelines in it [2]. (I'm the author of this blog post and of [1].) [1]: https://arxiv.org/pdf/2505.15917 https://arxiv.org/pdf/2505.15917 [2]: https://www.youtube.com/watch?v=nJxENYdsB6c https://www.youtube.com/watch?v=nJxENYdsB6c
- ktallett 1y ago
  It's not just quantum error correction that is required, it's also hard to make devices small enough due to cooling, to allow thousands of qubits let alone billions.
  - ziofill 1y ago
    not all implementations of QC require cryogenic cooling
    - ktallett 1y ago
      That is true but all will have components that require some cooling and scaling to billions of qubits will require cooling on a larger scale for said components.
- sllabres 1y ago
  From the talk of Samuel Jacques: Timeline for RSA-2048 at about 2088 (conservative extrapolation) or ~2052 (Moore’s‑law‑style growth)
  - throwmeaway222 1y ago
    it will be done much faster than that, guessing 2035
aaron695 1y ago
[dead]

dsclough 1y ago

Saw this earlier: https://x.com/adamscochran/status/1962148452072124879?s=46 https://x.com/adamscochran/status/1962148452072124879?s=46 As a layman the pathway seems to exist behind multiple massive materials science breakthroughs

andrewflnr 1y ago
How is it that we need to build logical qubits out of physical qubits for error correction purposes, but then still need to blow out our logic qubit numbers for error correction purposes, again? It seems like there's something missing from this explanation, at least.
- adgjlsfhk1 1y ago
  the blow-up is in physical qbits

TacticalCoder 1y ago

[dead]

tripplyons 1y ago

Not sure about the gate count, but if you look at the number of logical qubits required, we are still very far away from factoring numbers that traditional computing has already factored like the 829-bit RSA-250 number.

Legend2440 1y ago

Realistically, you want millions to billions of qubits to compete with classical computers that already have trillions of transistors.

jameshart 1y ago
Ah - this helped me understand the numbers in quantum computing a little more clearly. I had been under the impression (based on my naive interpretation of the naming) that the number of qubits in a quantum processor might be something analogous to the number of bits of register state in a regular CPU; that qubits should be thought of more as analogous to transistors or maybe even gates makes it a little clearer why you need so many more qubits to perform more complex operations.
adgjlsfhk1 1y ago
the difference is that you need millions of 1 qbits to factor rsa 4096, but you only need 10s of millions to factor rsa 32k. qbits and quantum time scale almost linearly with factor size, but super-polynomially for regular computers

lisper 1y ago

> So how many gates are we talking to factor some "cryptographically useful" number? That is a hard question to answer for two reasons. First, there is no bright line that delineates "cryptographically useful". And second, the exact design of a QC that could do such a calculation is not yet known. It's kind of like trying to estimate how many traditional gates would be needed to build a "semantically useful" neural network back in 1985. But the answer is almost certainly in the millions. [UPDATE] There is a third reason this is hard to predict: for quantum error correction, there is a tradeoff between the error rate in the raw qbit and the number of gates needed to build a reliable error-corrected virtual qbit. The lower the error rate in the raw qbit, the fewer gates are needed. And there is no way to know at this point what kind of raw error rates can be achieved. > Is there some pathway that makes quantum computers useful this century? This century has 75 years left in it, and that is an eternity in tech-time. 75 years ago the state of the art in classical computers was (I'll be generous here) the Univac [1]. Figuring out how much less powerful it was than a modern computer makes an interesting exercise, especially if you do it in terms of ops/watt. I haven't done the math, but it's many, many, many orders of magnitude. If the same progress can be achieved in quantum computing, then pre-quantum encryption is definitely toast by 2100. And it pretty much took only one breakthrough, the transistor, to achieve the improvement in classical computing that we enjoy today. We still don't have the equivalent of that for QC, but who knows when or if it will happen. Everything seems impossible until someone figures it out for the first time. --- [1] https://en.wikipedia.org/wiki/UNIVAC_I#Technical_description https://en.wikipedia.org/wiki/UNIVAC_I#Technical_description

deleted 1y ago
[deleted]
fhdkweig 1y ago
>> Is there some pathway that makes quantum computers useful this century? > This century has 75 years left in it, and that is an eternity in tech-time. As a comparison, we went from first heavier than air flight to man walking on the moon in only 66 years.
- thechao 1y ago

nabla9 1y ago

For RSA 4096 10^7 qubits with 10^-4 error rate (order of magnitude). You can do useful and valuable quantum chemistry calculations already with few 100s of qubits with that low error rates, while post-quantum algorithms are becoming more common everyday removing incentives to build crypto cracking quantum computers. I think the quantum computing will advance fastest in directions that are not easy to use in cryptography.

HappyPanacea 1y ago
Which valuable quantum chemistry calculations you can do with few 100s of qubits with that low error rates?
- nabla9 1y ago
  The general idea is that with N fault-tolerant qubits, you can find the ground-state energy of an electronic system with N spin orbitals. 100 spin orbitals is the practical upper limit of current computers, so when you get into several hundred qubits, you can start seeing gains. In some special problems hybrid methods start giving gains in 100 qubits or below. Gate count estimates for performing quantum chemistry on small quantum computers https://arxiv.org/pdf/1312.1695 https://arxiv.org/pdf/1312.1695 A Perspective on Quantum Computing Applications in Quantum Chemistry using 25--100 Logical Qubits https://arxiv.org/pdf/2506.19337 https://arxiv.org/pdf/2506.19337
smj-edison 1y ago
Honestly, if all quantum computers manage to pull off is quantum chemistry, I feel like that'll be enough. It would be a massive boon to the field of material sciences at any rate, which underlies so much of current infrastructure.

gjrq 1y ago

Latest numbers are about 1e6 qubits with 1e-4 error rate: https://arxiv.org/abs/2505.15917 https://arxiv.org/abs/2505.15917. Gates (in the sense the OP means) is harder to quantify in the error corrected context once you compile to the operations that are native to your code. Total compute time of about a week assuming a 1MHz "clock" (code cycle time, for the experts). In some ways this is the harder metric to meet than the qubit numbers. Note that the magic of quantum error correction (exponential improvement in the error rate goes both ways): if you could get another 9 in qubit fidelity, you get a much larger improvement in qubit numbers. On the other hand, if you need to split your computation over several systems, things get much worse.

adgjlsfhk1 1y ago
given the correct state of gate noise progress, it seems likely that we might get an extra order of magnitude of error before we get the 3 orders of magnitude in gates.

Strilanc 1y ago

> So how many gates are we talking to factor some "cryptographically useful" number? Table 5 of [1] estimates 7 billion Toffoli gates to factor 2048 bit RSA integers. > Is there some pathway that makes quantum computers useful this century? The pathway to doing billions of gates is quantum error correction. [1] estimates distance 25 surface codes would be sufficient for those 7 billion gates (given the physical assumptions it lists). This amplifies the qubit count from 1400 logical qubits to a million physical noisy qubits. Samuel Jacques had a pretty good talk at PQCrypto this year, and he speculates about timelines in it [2]. (I'm the author of this blog post and of [1].) [1]: https://arxiv.org/pdf/2505.15917 https://arxiv.org/pdf/2505.15917 [2]: https://www.youtube.com/watch?v=nJxENYdsB6c https://www.youtube.com/watch?v=nJxENYdsB6c

ktallett 1y ago
It's not just quantum error correction that is required, it's also hard to make devices small enough due to cooling, to allow thousands of qubits let alone billions.
- ziofill 1y ago
  not all implementations of QC require cryogenic cooling
  - ktallett 1y ago
    That is true but all will have components that require some cooling and scaling to billions of qubits will require cooling on a larger scale for said components.
sllabres 1y ago
From the talk of Samuel Jacques: Timeline for RSA-2048 at about 2088 (conservative extrapolation) or ~2052 (Moore’s‑law‑style growth)
- throwmeaway222 1y ago
  it will be done much faster than that, guessing 2035

aaron695 1y ago

[dead]