9 ms·

Just to be clear such a machine has not yet been built. This is only a theoretical paper at the moment.

by stirlo 6y ago

reagent_finder 6y ago
Yeah, I was thinking "Waaait, aren't they at <100 qubits still?"
- deleted 6y ago
  [deleted]
elephantum 6y ago
Do I understand correctly, that largest quantum computer that exists today contains less than 100 qubits? Also it does not seem that there's an exponential grow in this area: https://www.statista.com/statistics/993634/quantum-computers-by-number-of-qubits/#:~:text=Quantum%20computers%20by%20number%20of%20qubits%20achieved%20up%20to%202019%2C%20by%20organization&text=The%20statistic%20shows%20the%20number,new%20quantum%20computer%20by%20IBM https://www.statista.com/statistics/993634/quantum-computers.... They hit the wall in 2017. We should be safe for now :)
- cameronperot 6y ago
  IBM has 1000 qubits on their roadmap by 2023 [1]. I'm interested to see how that goes, and what we can learn from it about scaling up these systems into the thousands of qubits. Edit: for anyone interested in learning more about quantum computation, I have a list of resources on my website [2]. [1] https://www.ibm.com/blogs/research/2020/09/ibm-quantum-roadmap/ https://www.ibm.com/blogs/research/2020/09/ibm-quantum-roadm... [2] https://cameronperot.com/resources/#quantum-physics https://cameronperot.com/resources/#quantum-physics
  - akvadrako 6y ago
    Since I didn't see it mentioned, I assume those are 1000 noisy qubits, so they'll require error correction. I wonder how many ideal qubits they are equivalent to.
- megiddo 6y ago
  And the error rate of 10^-3 seems problematic, as well.
- CodesInChaos 6y ago
  Those quantum computers can't execute Shor's algorithm, which is required to attack RSA. AFAIK the best relevant factoring result is still 21=3*7 from 2012. There are claims of bigger factored numbers, but they exploited special cases (e.g. factors differing by only two bits) and have no hope of being extended to attack cryptography. https://crypto.stackexchange.com/questions/59795/largest-integer-factored-by-shors-algorithm https://crypto.stackexchange.com/questions/59795/largest-int... A 2019 paper manged to factor 21 on a 16 qubit ibmqx5, but failed to go up to 35: > the algorithm fails to factor N=35. This is due to the cumulative errors coming from the increasing number of two-qubits gates necessary to implement the more complex MEF needed for this case https://arxiv.org/abs/1903.00768 https://arxiv.org/abs/1903.00768
  - graderjs 6y ago
    Jennifer and Peter Shor wrote a limerick that seems relevant: If computers that you build are quantum, Then spies of all factions will want 'em. Our codes will all fail, And they'll read our email, Till we've crypto that's quantum, and daunt 'em. And Volker Strassen responded at a conference: To read our E-mail, how mean of the spies and their quantum machine; Be comforted though, they do not yet know how to factorize twelve or fifteen. Source: http://www-math.mit.edu/~shor/notapoet.html http://www-math.mit.edu/~shor/notapoet.html
    - CodesInChaos 6y ago
      > Till we've crypto that's quantum, and daunt 'em. Luckily there are asymmetric algorithms which are are secure against quantum computers, so we don't have to resort to quantum-key-exchanges.
      - _hl_ 6y ago
        "Secure against quantum" doesn't really mean much because too little is known to make that claim confidently. AFAIK the term generally refers to algorithms that don't rely on factoring being hard, but instead make some different hardness assumptions that we currently don't have classical or quantum algorithms for.
- DebtDeflation 6y ago
  >largest quantum computer that exists today contains less than 100 qubits The numbers reported in the press are physical qubits not logical qubits. You need multiple physical qubits + error correction to create a single logical qubit. The main type of error correction used today is something called "surface codes". With this type of error correction it's estimated that MILLIONS of physical qubits will be required to create a SINGLE fully error corrected logical qubit. https://www.ncbi.nlm.nih.gov/books/NBK538709/ https://www.ncbi.nlm.nih.gov/books/NBK538709/ We do not have actual quantum computers today and we don't seem to be much closer to having them than we were a decade ago. What we have are really interesting quantum science experiments that get misrepresented by the press (and a handful of companies with a commercial interest in doing so).
- mikewave 6y ago
  The largest production quantum computer that exists today - as in, the largest you personally can get access to - has 5,436 qubits: the D-Wave Advantage system. Admittedly, it's not a gate-model machine that can run Shor's Algorithm, but it is a quantum computer, and at more than double the number of qubits plus far higher inter-qubit connectivity than our previous D-Wave 2000Q, it definitely demonstrates tremendous progress. If you have a moment, you can sign up to use it for free at https://cloud.dwavesys.com https://cloud.dwavesys.com - we have an online IDE, Jupyter notebook training material and tons of docs, a community forum, and of course some shiny demos that submit problems to the live QPU if you want to try them out.
hk1337 6y ago
So, then I am definitely good using 4096 RSA?
- upofadown 6y ago
  Sure, but ridiculously large key sizes like 4096 bit RSA are not really any more resistant to quantum computing than smaller sizes. This is probably a joke, but the suggestion was made that you might be OK with a 1 TB RSA key size: * https://www.schneier.com/blog/archives/2017/05/post-quantum_rs.html https://www.schneier.com/blog/archives/2017/05/post-quantum_...
  - bcaa7f3a8bbc 6y ago
    That pqRSA paper by DJB is a joke, but it's mathematically correct and an interesting thought experiment - RSA really becomes post-quantum when you use a 1 TB key because it outgrows what Shor's algorithm can scale at that point. The paper is actually better, it proposed an original algorithm, GEECM, that's faster than Shor's algorithm for numbers with many small factors, then also showed pqRSA is safe from GEECM. He even submitted the algorithm to the NIST Post-Quantum Competition for review (among his more practical algorithms like Classic McEliece), it's just hilarious. > DJB yelling from the back of the room "How much RAM does the NIST benchmarking machine have??" Dustin Moody replying "Dan, we're not benchmarking pqRSA!" https://crypto.stackexchange.com/questions/59591/why-is-pqrsa-in-the-nist-pqc-submissions https://crypto.stackexchange.com/questions/59591/why-is-pqrs... Here's his explanation of the idea: https://cr.yp.to/talks/2017.06.27/slides-djb-20170627-pqrsa-16x9.pdf https://cr.yp.to/talks/2017.06.27/slides-djb-20170627-pqrsa-...
    - SAI_Peregrinus 6y ago
      Given the number of Star Wars references in the various NIST Post-Quantum Competition scheme names (CRYSTALS-KYBER, SABER, NewHope) I'm rather sad he didn't call it "Post Quantum RSA - The Phantom Menace".
  - deleted 6y ago
    [deleted]
SilasX 6y ago
I would have preferred they title it "How to factor 2048 ..."

Just to be clear such a machine has not yet been built. This is only a theoretical paper at the moment.

by stirlo 6y ago

Just to be clear such a machine has not yet been built. This is only a theoretical paper at the moment.

reagent_finder 6y ago

Yeah, I was thinking "Waaait, aren't they at <100 qubits still?"

deleted 6y ago
[deleted]

elephantum 6y ago

Do I understand correctly, that largest quantum computer that exists today contains less than 100 qubits? Also it does not seem that there's an exponential grow in this area: https://www.statista.com/statistics/993634/quantum-computers-by-number-of-qubits/#:~:text=Quantum%20computers%20by%20number%20of%20qubits%20achieved%20up%20to%202019%2C%20by%20organization&text=The%20statistic%20shows%20the%20number,new%20quantum%20computer%20by%20IBM https://www.statista.com/statistics/993634/quantum-computers.... They hit the wall in 2017. We should be safe for now :)

cameronperot 6y ago
IBM has 1000 qubits on their roadmap by 2023 [1]. I'm interested to see how that goes, and what we can learn from it about scaling up these systems into the thousands of qubits. Edit: for anyone interested in learning more about quantum computation, I have a list of resources on my website [2]. [1] https://www.ibm.com/blogs/research/2020/09/ibm-quantum-roadmap/ https://www.ibm.com/blogs/research/2020/09/ibm-quantum-roadm... [2] https://cameronperot.com/resources/#quantum-physics https://cameronperot.com/resources/#quantum-physics
- akvadrako 6y ago
  Since I didn't see it mentioned, I assume those are 1000 noisy qubits, so they'll require error correction. I wonder how many ideal qubits they are equivalent to.
megiddo 6y ago
And the error rate of 10^-3 seems problematic, as well.
CodesInChaos 6y ago
Those quantum computers can't execute Shor's algorithm, which is required to attack RSA. AFAIK the best relevant factoring result is still 21=3*7 from 2012. There are claims of bigger factored numbers, but they exploited special cases (e.g. factors differing by only two bits) and have no hope of being extended to attack cryptography. https://crypto.stackexchange.com/questions/59795/largest-integer-factored-by-shors-algorithm https://crypto.stackexchange.com/questions/59795/largest-int... A 2019 paper manged to factor 21 on a 16 qubit ibmqx5, but failed to go up to 35: > the algorithm fails to factor N=35. This is due to the cumulative errors coming from the increasing number of two-qubits gates necessary to implement the more complex MEF needed for this case https://arxiv.org/abs/1903.00768 https://arxiv.org/abs/1903.00768
- graderjs 6y ago
  Jennifer and Peter Shor wrote a limerick that seems relevant: If computers that you build are quantum, Then spies of all factions will want 'em. Our codes will all fail, And they'll read our email, Till we've crypto that's quantum, and daunt 'em. And Volker Strassen responded at a conference: To read our E-mail, how mean of the spies and their quantum machine; Be comforted though, they do not yet know how to factorize twelve or fifteen. Source: http://www-math.mit.edu/~shor/notapoet.html http://www-math.mit.edu/~shor/notapoet.html
  - CodesInChaos 6y ago
    > Till we've crypto that's quantum, and daunt 'em. Luckily there are asymmetric algorithms which are are secure against quantum computers, so we don't have to resort to quantum-key-exchanges.
    - _hl_ 6y ago
      "Secure against quantum" doesn't really mean much because too little is known to make that claim confidently. AFAIK the term generally refers to algorithms that don't rely on factoring being hard, but instead make some different hardness assumptions that we currently don't have classical or quantum algorithms for.
DebtDeflation 6y ago
>largest quantum computer that exists today contains less than 100 qubits The numbers reported in the press are physical qubits not logical qubits. You need multiple physical qubits + error correction to create a single logical qubit. The main type of error correction used today is something called "surface codes". With this type of error correction it's estimated that MILLIONS of physical qubits will be required to create a SINGLE fully error corrected logical qubit. https://www.ncbi.nlm.nih.gov/books/NBK538709/ https://www.ncbi.nlm.nih.gov/books/NBK538709/ We do not have actual quantum computers today and we don't seem to be much closer to having them than we were a decade ago. What we have are really interesting quantum science experiments that get misrepresented by the press (and a handful of companies with a commercial interest in doing so).
mikewave 6y ago
The largest production quantum computer that exists today - as in, the largest you personally can get access to - has 5,436 qubits: the D-Wave Advantage system. Admittedly, it's not a gate-model machine that can run Shor's Algorithm, but it is a quantum computer, and at more than double the number of qubits plus far higher inter-qubit connectivity than our previous D-Wave 2000Q, it definitely demonstrates tremendous progress. If you have a moment, you can sign up to use it for free at https://cloud.dwavesys.com https://cloud.dwavesys.com - we have an online IDE, Jupyter notebook training material and tons of docs, a community forum, and of course some shiny demos that submit problems to the live QPU if you want to try them out.

hk1337 6y ago

So, then I am definitely good using 4096 RSA?

upofadown 6y ago
Sure, but ridiculously large key sizes like 4096 bit RSA are not really any more resistant to quantum computing than smaller sizes. This is probably a joke, but the suggestion was made that you might be OK with a 1 TB RSA key size: * https://www.schneier.com/blog/archives/2017/05/post-quantum_rs.html https://www.schneier.com/blog/archives/2017/05/post-quantum_...
- bcaa7f3a8bbc 6y ago
  That pqRSA paper by DJB is a joke, but it's mathematically correct and an interesting thought experiment - RSA really becomes post-quantum when you use a 1 TB key because it outgrows what Shor's algorithm can scale at that point. The paper is actually better, it proposed an original algorithm, GEECM, that's faster than Shor's algorithm for numbers with many small factors, then also showed pqRSA is safe from GEECM. He even submitted the algorithm to the NIST Post-Quantum Competition for review (among his more practical algorithms like Classic McEliece), it's just hilarious. > DJB yelling from the back of the room "How much RAM does the NIST benchmarking machine have??" Dustin Moody replying "Dan, we're not benchmarking pqRSA!" https://crypto.stackexchange.com/questions/59591/why-is-pqrsa-in-the-nist-pqc-submissions https://crypto.stackexchange.com/questions/59591/why-is-pqrs... Here's his explanation of the idea: https://cr.yp.to/talks/2017.06.27/slides-djb-20170627-pqrsa-16x9.pdf https://cr.yp.to/talks/2017.06.27/slides-djb-20170627-pqrsa-...
  - SAI_Peregrinus 6y ago
    Given the number of Star Wars references in the various NIST Post-Quantum Competition scheme names (CRYSTALS-KYBER, SABER, NewHope) I'm rather sad he didn't call it "Post Quantum RSA - The Phantom Menace".
- deleted 6y ago
  [deleted]

SilasX 6y ago

I would have preferred they title it "How to factor 2048 ..."