6 ms·

https://eprint.iacr.org/2015/1018.pdf https://eprint.iacr.org/2015/1018.pdf As pointed out in [57], there has never been a genuine implementation of Shor’s a

by thesz 2y ago

https://eprint.iacr.org/2015/1018.pdf https://eprint.iacr.org/2015/1018.pdf As pointed out in [57], there has never been a genuine implementation of Shor’s algorithm. The only numbers ever to have been factored by that type of algorithm are 15 and 21, and those factorizations used a simplified version of Shor’s algorithm that requires one to know the factorization in advance.

adastra22 2y ago
What’s the point of quoting this?
- thesz 2y ago
  To me it was eye opening on how skewed is the presentation of these quantum computing number factoring advances. It is completely in line of the "The Case Against..."
  - adastra22 2y ago
    No one is claiming number factoring advances. That would require much longer lived qubits entanglement than is currently possible. The tech is clearly advancing forward though.
  - bawolff 2y ago
    That feels like a straw man. Nobody was claiming otherwise.
  - rcxdude 2y ago
    It feels more like the time to develop the tech has outlived the hype cycle around the tech, perhaps moreso than usual. That doesn't mean it isn't going anywhere, just that it's still slow (and in fact, after the hype cycle, the average press release is more likely to be substantive than during it, even if it's still incremental). (From my reading/understanding of it, for a while there's been little point in trying to make a quantum computer big enough to do such work, because the individual parts would not work well enough for it to have any chance of success, while this result primarily is showing that they're now at the cusp of the predicted tipping point where the qubits have a low enough error rate that building a larger system out of them has a hope of working. That's the big news in google's recent announcement, not them pushing up the numbers in this somewhat contrived benchmark)
- sampo 2y ago
  > What’s the point of quoting this? To remind us of the large difference between the public image vs the reality of quantum computing. Expectation: From the news, people are getting a feeling that quantum computing revolution is almost behind the corner, and current cryptosystems will soon become irrelevant. People are (here, in Hacker News) asking "is our society ready for this", "what could I do if I had this chip at home", "existing cryptography technology is in danger", "is it time to 100x key length on browsers". Reality: Using Shor's algorithm to factor 15 = 5×3 is still far beyond the reach of current quantum computers. We can factor 15 = 5×3 and even 21 = 7×3 if we cheat by eliminating those branches from the calculation that are not on the happy path the correct answer.
  - jppittma 2y ago
    What are the chances that the CIA has a manhattan project style quantum computer somewhere? I can’t believe that if the current SOTA could break commonly used encryption methods that it would be widely known.
    - GTP 2y ago
      I think it's still unlikely. In the case of the Manhattan project, the USA government wasn't racing against private companies but against other governments. Therefore, all advances in the field where highly secret. In this case, the CIA would be racing against private companies as well, which are hiring the best physicists and engineers too. So, while it's possible that a governmental agency is ahead of what it is publicly know, I doubt that they would be dramatically ahead. This is similar to part of the argument I would present if someone asks me why I believe cryptography in general is secure.
      - zelon88 2y ago
        > In this case, the CIA would be racing against private companies as well... You mean like Skunkworks when they designed the SR-71? Or DARPA with Atlas? Or the DoD with the global GPS network? Or the NSA's ANT catalogue? Yeah, the government has never had any issues outpacing the private sector. You only ever find out about it when they want you to. Usually that happens 5 to 30 years after the market has already caught up.

by thesz 2y ago

adastra22 2y ago

What’s the point of quoting this?

thesz 2y ago
To me it was eye opening on how skewed is the presentation of these quantum computing number factoring advances. It is completely in line of the "The Case Against..."
- adastra22 2y ago
  No one is claiming number factoring advances. That would require much longer lived qubits entanglement than is currently possible. The tech is clearly advancing forward though.
- bawolff 2y ago
  That feels like a straw man. Nobody was claiming otherwise.
- rcxdude 2y ago
  It feels more like the time to develop the tech has outlived the hype cycle around the tech, perhaps moreso than usual. That doesn't mean it isn't going anywhere, just that it's still slow (and in fact, after the hype cycle, the average press release is more likely to be substantive than during it, even if it's still incremental). (From my reading/understanding of it, for a while there's been little point in trying to make a quantum computer big enough to do such work, because the individual parts would not work well enough for it to have any chance of success, while this result primarily is showing that they're now at the cusp of the predicted tipping point where the qubits have a low enough error rate that building a larger system out of them has a hope of working. That's the big news in google's recent announcement, not them pushing up the numbers in this somewhat contrived benchmark)
sampo 2y ago
> What’s the point of quoting this? To remind us of the large difference between the public image vs the reality of quantum computing. Expectation: From the news, people are getting a feeling that quantum computing revolution is almost behind the corner, and current cryptosystems will soon become irrelevant. People are (here, in Hacker News) asking "is our society ready for this", "what could I do if I had this chip at home", "existing cryptography technology is in danger", "is it time to 100x key length on browsers". Reality: Using Shor's algorithm to factor 15 = 5×3 is still far beyond the reach of current quantum computers. We can factor 15 = 5×3 and even 21 = 7×3 if we cheat by eliminating those branches from the calculation that are not on the happy path the correct answer.
- jppittma 2y ago
  What are the chances that the CIA has a manhattan project style quantum computer somewhere? I can’t believe that if the current SOTA could break commonly used encryption methods that it would be widely known.
  - GTP 2y ago
    I think it's still unlikely. In the case of the Manhattan project, the USA government wasn't racing against private companies but against other governments. Therefore, all advances in the field where highly secret. In this case, the CIA would be racing against private companies as well, which are hiring the best physicists and engineers too. So, while it's possible that a governmental agency is ahead of what it is publicly know, I doubt that they would be dramatically ahead. This is similar to part of the argument I would present if someone asks me why I believe cryptography in general is secure.
    - zelon88 2y ago
      > In this case, the CIA would be racing against private companies as well... You mean like Skunkworks when they designed the SR-71? Or DARPA with Atlas? Or the DoD with the global GPS network? Or the NSA's ANT catalogue? Yeah, the government has never had any issues outpacing the private sector. You only ever find out about it when they want you to. Usually that happens 5 to 30 years after the market has already caught up.