5 ms·

You divide the number of physical qubits by 5 to get the number of fault tolerant error corrected qubits. [0] If their algorithm works, they need a 1860 (372*5

You divide the number of physical qubits by 5 to get the number of fault tolerant error corrected qubits. [0] If their algorithm works, they need a 1860 (372*5) qubit computer to break 2048 bit RSA. IBM expects to get there by 2025. [1] [0] https://en.wikipedia.org/wiki/Five-qubit_error_correcting_code https://en.wikipedia.org/wiki/Five-qubit_error_correcting_co... [1] https://www.ibm.com/quantum/roadmap https://www.ibm.com/quantum/roadmap

andrewla 4y ago
If this roadmap is accurate for the present, the types of qbits here are NISQ qubits, so not useful for any sort of generalized computation no matter how many they have. Which is to say that Osprey has 433 qubits, so should be capable of 86 fault tolerant error corrected qubits, so they should be able to factor (not bothering with the math) AT LEAST ONE NUMBER using Shor's algorithm, and yet they cannot.
krastanov 4y ago
If the paper is to be believed you are wrong in two different ways: 1) If the paper is right, they are claiming they need 300ish physical qubits that can sustain about 1000 gates before decohering. No need for scalable error correction. 2) Independently of the veracity of the paper, if you actually need logical error corrected (and fault tolerant) qubits, you need error correcting codes with much more severe overhead than the 5-qubit code. The 5-qubit code is a pedagogical example, not something that would actually work under realistic conditions. And even the 5-qubit code needs quite a few extra ancillary qubits for fault tolerance (which is more expensive than simple error correction).
greggarious 4y ago
What practical things can be done once RSA is broken?
- quotemstr 4y ago
  Decrypt decades of pre-PFS archived encrypted internet traffic.
  - retrocryptid 4y ago
    If only someone archived it in a data center in the desert.
    - greggarious 4y ago
      >> Decrypt decades of pre-PFS archived encrypted internet traffic. > If only someone archived it in a data center in the desert. Uh oh https://en.wikipedia.org/wiki/Utah_Data_Center https://en.wikipedia.org/wiki/Utah_Data_Center Good think I declared moral bankruptcy this year, all that is the old me :-)
- nunez 4y ago
  isn't most stuff elliptic curve now?
- bawolff 4y ago
  Breaking RSA is a practical thing. E.g. forge email (most dkim keys are 1024 bit rsa). Break ssh (depends on key algo chose). Break pgp (depending on settings). Mitm https connections, Etc.
  - greggarious 4y ago
    So if you were going to explain it to someone who's less technical, maybe saying "remove HTTPS" would be an oversimplified way to explain? (I don't think my contacts aren't going to know what SSH or PGP is, if that helps.)
    - deleted 4y ago
      [deleted]
    - tialaramex 4y ago
      Not exactly. For the vast majority of HTTPS (say, for example, Google or Hacker News) RSA is not used to agree the encryption. So although quantum computers would be a threat for other reasons, breaking RSA in particular doesn't just "remove HTTPS". However, RSA is used to prove the identity of the server for most web sites even with a newer key agreement. So if an adversary can get on path between you and the server, they could get in the middle and masquerade successfully as the server - arranging key agreement with you, and then providing a convincing fake proof of identity, if they do so live. In TLS 1.2 optionally, and to a greater extent in older versions (which are no longer used by popular web browsers) you can also use RSA to agree the encryption, and for sites using that breaking RSA would allow an adversary to interpose in real time, or to decrypt communication after the fact, but I'd be astonished if anywhere important still does that when talking a halfway modern browser.
    - bawolff 4y ago
      The way id explain it to a non-technical person - it would (among other things) allow the person running the sketchy wifi at the coffee shop to see all the sites you are visiting and any data you enter.
Strilanc 4y ago
The amount of error correction you need is more than what the five qubit code provides. A more typical estimate is that you'd need 1000 physical qubits per logical qubit. For example, using the surface code, a back of the envelope estimate would be that you need a code distance of d = ln(number_of_operations). Each logical qubit will use 2d^2 physical qubits. So for a million operations you'd need around 400 physical qubits per logical qubit and for a trillion operations you'd need around 1500 physical qubits per logical qubit. So, way more than 5. (A major practical obstacle to using almost-anything-that-isn't-the-surface-code is that the surface code has forgiving connectivity and maximum-allowed-physical-noise requirements.)
- XorNot 4y ago
  The other issue when you start talking about very large numbers of qubits is that they're not independent. Building more qubits influences your noise environment substantially. Expectations of a Moore's law type improvement rate are going to be left wanting.
- gronky_ 4y ago
  So if the paper is correct then you need about a half a million qubits? Is this roughly a 40x improvement on the 20M qubits in 8 hours or is there more to it?
  - Strilanc 4y ago
    If the paper is correct then yes, it would be a huge improvement in the required space even accounting for the overhead of error correction. Shor's algorithm requires performing a modular exponentiation under superposition. For an n bit modulus this requires 2n or 3n qubits of storage, plus let's say 50% overhead for routing and gates. You end up needing 5n to 10n logical qubits for an n bit number. So to factor a 2048 bit number you'd need on the order of ten thousand logical qubits. Improving that to a few hundred logical qubits would be a big improvement. Also, there's fewer operations so the code distance can be lower. ...but don't forget that "if the paper is correct" bit.
reikonomusha 4y ago
A 5-qubit code corrects against single qubit errors. You could say a factor of 5 is a lower bound. In more technical terms, this scheme fixes all weight-1 errors. More realistically [1], you'd have a factor of around 1,600 for a distance-27 code. [1] https://arxiv.org/pdf/1905.09749.pdf https://arxiv.org/pdf/1905.09749.pdf

andrewla 4y ago

If this roadmap is accurate for the present, the types of qbits here are NISQ qubits, so not useful for any sort of generalized computation no matter how many they have. Which is to say that Osprey has 433 qubits, so should be capable of 86 fault tolerant error corrected qubits, so they should be able to factor (not bothering with the math) AT LEAST ONE NUMBER using Shor's algorithm, and yet they cannot.

krastanov 4y ago

If the paper is to be believed you are wrong in two different ways: 1) If the paper is right, they are claiming they need 300ish physical qubits that can sustain about 1000 gates before decohering. No need for scalable error correction. 2) Independently of the veracity of the paper, if you actually need logical error corrected (and fault tolerant) qubits, you need error correcting codes with much more severe overhead than the 5-qubit code. The 5-qubit code is a pedagogical example, not something that would actually work under realistic conditions. And even the 5-qubit code needs quite a few extra ancillary qubits for fault tolerance (which is more expensive than simple error correction).

greggarious 4y ago

What practical things can be done once RSA is broken?

quotemstr 4y ago
Decrypt decades of pre-PFS archived encrypted internet traffic.
- retrocryptid 4y ago
  If only someone archived it in a data center in the desert.
  - greggarious 4y ago
    >> Decrypt decades of pre-PFS archived encrypted internet traffic. > If only someone archived it in a data center in the desert. Uh oh https://en.wikipedia.org/wiki/Utah_Data_Center https://en.wikipedia.org/wiki/Utah_Data_Center Good think I declared moral bankruptcy this year, all that is the old me :-)
nunez 4y ago
isn't most stuff elliptic curve now?
bawolff 4y ago
Breaking RSA is a practical thing. E.g. forge email (most dkim keys are 1024 bit rsa). Break ssh (depends on key algo chose). Break pgp (depending on settings). Mitm https connections, Etc.
- greggarious 4y ago
  So if you were going to explain it to someone who's less technical, maybe saying "remove HTTPS" would be an oversimplified way to explain? (I don't think my contacts aren't going to know what SSH or PGP is, if that helps.)
  - deleted 4y ago
    [deleted]
  - tialaramex 4y ago
    Not exactly. For the vast majority of HTTPS (say, for example, Google or Hacker News) RSA is not used to agree the encryption. So although quantum computers would be a threat for other reasons, breaking RSA in particular doesn't just "remove HTTPS". However, RSA is used to prove the identity of the server for most web sites even with a newer key agreement. So if an adversary can get on path between you and the server, they could get in the middle and masquerade successfully as the server - arranging key agreement with you, and then providing a convincing fake proof of identity, if they do so live. In TLS 1.2 optionally, and to a greater extent in older versions (which are no longer used by popular web browsers) you can also use RSA to agree the encryption, and for sites using that breaking RSA would allow an adversary to interpose in real time, or to decrypt communication after the fact, but I'd be astonished if anywhere important still does that when talking a halfway modern browser.
  - bawolff 4y ago
    The way id explain it to a non-technical person - it would (among other things) allow the person running the sketchy wifi at the coffee shop to see all the sites you are visiting and any data you enter.

Strilanc 4y ago

The amount of error correction you need is more than what the five qubit code provides. A more typical estimate is that you'd need 1000 physical qubits per logical qubit. For example, using the surface code, a back of the envelope estimate would be that you need a code distance of d = ln(number_of_operations). Each logical qubit will use 2d^2 physical qubits. So for a million operations you'd need around 400 physical qubits per logical qubit and for a trillion operations you'd need around 1500 physical qubits per logical qubit. So, way more than 5. (A major practical obstacle to using almost-anything-that-isn't-the-surface-code is that the surface code has forgiving connectivity and maximum-allowed-physical-noise requirements.)

XorNot 4y ago
The other issue when you start talking about very large numbers of qubits is that they're not independent. Building more qubits influences your noise environment substantially. Expectations of a Moore's law type improvement rate are going to be left wanting.
gronky_ 4y ago
So if the paper is correct then you need about a half a million qubits? Is this roughly a 40x improvement on the 20M qubits in 8 hours or is there more to it?
- Strilanc 4y ago
  If the paper is correct then yes, it would be a huge improvement in the required space even accounting for the overhead of error correction. Shor's algorithm requires performing a modular exponentiation under superposition. For an n bit modulus this requires 2n or 3n qubits of storage, plus let's say 50% overhead for routing and gates. You end up needing 5n to 10n logical qubits for an n bit number. So to factor a 2048 bit number you'd need on the order of ten thousand logical qubits. Improving that to a few hundred logical qubits would be a big improvement. Also, there's fewer operations so the code distance can be lower. ...but don't forget that "if the paper is correct" bit.

reikonomusha 4y ago

A 5-qubit code corrects against single qubit errors. You could say a factor of 5 is a lower bound. In more technical terms, this scheme fixes all weight-1 errors. More realistically [1], you'd have a factor of around 1,600 for a distance-27 code. [1] https://arxiv.org/pdf/1905.09749.pdf https://arxiv.org/pdf/1905.09749.pdf