7 ms·

You will find that this machine can't even factor the number 15 properly, as it's not error corrected, or a general purpose quantum computer. FWIIW nobody has f

You will find that this machine can't even factor the number 15 properly, as it's not error corrected, or a general purpose quantum computer. FWIIW nobody has factored the number 15 using quantum algorithms using the Shor algorithm yet; only using the subset of gates they know produces the numbers 3 and 5.

cthalupa 7y ago
You keep repeating this, but as best as I can tell, it hasn't been factually accurate in a decade, unless you really want to quibble over the fact that they finished the calculation on a general purpose computer. https://www.schneier.com/blog/archives/2009/09/quantum_compute.html https://www.schneier.com/blog/archives/2009/09/quantum_compu... >Instead, it came up with an answer to the "order-finding routine," the "computationally hard" part of Shor's algorithm that requires a quantum calculation to solve the problem in a reasonable amount of time. They weren't the first team to do this, either, they just miniaturized parts of the hardware.
- scottlocklin 7y ago
  The result you cite doesn't even say what you think it says; in fact it directly says they didn't factor a damn thing. If I'm wrong and IBM's latest "quantum computer" can actually do the Shor algorithm on the number 15 using 4608 gate operations, I will publically eat one of my shoes like Werner Herzog. Assuming I can get someone else to take the other side of the bet, of course.
  - gjm11 7y ago
    It says: > the chip itself didn't just spit out 5 and 3. Instead, it came up with an answer to the "order-finding routine" O noes! The quantum computer only did the "order-finding" part of Shor's algorithm! ... But wait. Here's the Wikipedia page for Shor's algorithm: > Shor's algorithm consists of two parts: 1. A reduction, which can be done on a classical computer, of the factoring problem to the problem of order-finding. 2. A quantum algorithm to solve the order-finding problem. So, the article GP cited says that a quantum computer did the part of factoring the number 15 that actually uses a quantum computer. Nothing wrong with that. The article's link to the actual paper is broken, which makes it harder to tell whether as you say they cheated somehow, but here's another article about factoring 15 with a quantum computer https://science.sciencemag.org/content/351/6277/1068 https://science.sciencemag.org/content/351/6277/1068 which so far as I can see claims to have actually done the whole of (the relevant part of) Shor's algorithm on actual QC hardware.
    - scottlocklin 7y ago
      Even assuming I humor you and refuse to notice they left out the gates to the wrong answer, and assuming I humor the authors in agreeing that this is a scalable form of the Shor algorithm (I deny both of these for the record) .... congratulations: by 2016 someone was able to factor the number 15. I guess quantum supremacy is right around the corner!
      - DebtDeflation 7y ago
        >to notice they left out the gates to the wrong answer Can you explain this a little more? I've seen similar references to this elsewhere. If it means what I think it means, it's kind of a really big deal. But it may mean something else.
        scottlocklin 7y ago
        http://www.theory.caltech.edu/~preskill/pubs/preskill-1996-networks.pdf http://www.theory.caltech.edu/~preskill/pubs/preskill-1996-n...
        gjm11 7y ago
        That doesn't explain in what sense this entirely different paper from 20 years later allegedly "left out the gates to the wrong answer". The paper I linked to says, e.g., the following: > Subsequent multipliers can similarly be replaced with maps by considering only possible outputs of the previous multiplications. However, using such maps will become intractable, [...] Thus, controlled full modular multipliers should be implemented. So in at least one case they are explicitly not taking a particular shortcut because it doesn't scale to factorizing larger numbers. If you say they are taking other shortcuts that don't scale by "leaving out the gates to the wrong answer", then I think you owe us an actual explanation of what shortcuts they are taking and how you know you're taking them, rather than just a link to a paper from 1996 that says how to take some shortcuts.
        7y ago
acqq 7y ago
For those who are interested in the papers about this topic: https://arxiv.org/abs/1301.7007 https://arxiv.org/abs/1301.7007 "Pretending to factor large numbers on a quantum computer (2013)" "Of course this should not be considered a serious demonstration of Shor’s algorithm. It does, however, illustrate the danger in “compiled” demonstrations of Shor’s algorithm. To varying degrees, all previous factorization experiments have benefited from this artifice. While there is no objection to having a classical compiler help design a quantum circuit (indeed, probably all quantum computers will function in this way), it is not legitimate for a compiler to know the answer to the problem being solved. To even call such a procedure compilation is an abuse of language." More references: https://crypto.stackexchange.com/questions/59795/largest-integer-factored-by-shors-algorithm/59796#59796 https://crypto.stackexchange.com/questions/59795/largest-int...

cthalupa 7y ago

You keep repeating this, but as best as I can tell, it hasn't been factually accurate in a decade, unless you really want to quibble over the fact that they finished the calculation on a general purpose computer. https://www.schneier.com/blog/archives/2009/09/quantum_compute.html https://www.schneier.com/blog/archives/2009/09/quantum_compu... >Instead, it came up with an answer to the "order-finding routine," the "computationally hard" part of Shor's algorithm that requires a quantum calculation to solve the problem in a reasonable amount of time. They weren't the first team to do this, either, they just miniaturized parts of the hardware.

scottlocklin 7y ago
The result you cite doesn't even say what you think it says; in fact it directly says they didn't factor a damn thing. If I'm wrong and IBM's latest "quantum computer" can actually do the Shor algorithm on the number 15 using 4608 gate operations, I will publically eat one of my shoes like Werner Herzog. Assuming I can get someone else to take the other side of the bet, of course.
- gjm11 7y ago
  It says: > the chip itself didn't just spit out 5 and 3. Instead, it came up with an answer to the "order-finding routine" O noes! The quantum computer only did the "order-finding" part of Shor's algorithm! ... But wait. Here's the Wikipedia page for Shor's algorithm: > Shor's algorithm consists of two parts: 1. A reduction, which can be done on a classical computer, of the factoring problem to the problem of order-finding. 2. A quantum algorithm to solve the order-finding problem. So, the article GP cited says that a quantum computer did the part of factoring the number 15 that actually uses a quantum computer. Nothing wrong with that. The article's link to the actual paper is broken, which makes it harder to tell whether as you say they cheated somehow, but here's another article about factoring 15 with a quantum computer https://science.sciencemag.org/content/351/6277/1068 https://science.sciencemag.org/content/351/6277/1068 which so far as I can see claims to have actually done the whole of (the relevant part of) Shor's algorithm on actual QC hardware.
  - scottlocklin 7y ago
    Even assuming I humor you and refuse to notice they left out the gates to the wrong answer, and assuming I humor the authors in agreeing that this is a scalable form of the Shor algorithm (I deny both of these for the record) .... congratulations: by 2016 someone was able to factor the number 15. I guess quantum supremacy is right around the corner!
    - DebtDeflation 7y ago
      >to notice they left out the gates to the wrong answer Can you explain this a little more? I've seen similar references to this elsewhere. If it means what I think it means, it's kind of a really big deal. But it may mean something else.
      - scottlocklin 7y ago
        http://www.theory.caltech.edu/~preskill/pubs/preskill-1996-networks.pdf http://www.theory.caltech.edu/~preskill/pubs/preskill-1996-n...
        gjm11 7y ago
        That doesn't explain in what sense this entirely different paper from 20 years later allegedly "left out the gates to the wrong answer". The paper I linked to says, e.g., the following: > Subsequent multipliers can similarly be replaced with maps by considering only possible outputs of the previous multiplications. However, using such maps will become intractable, [...] Thus, controlled full modular multipliers should be implemented. So in at least one case they are explicitly not taking a particular shortcut because it doesn't scale to factorizing larger numbers. If you say they are taking other shortcuts that don't scale by "leaving out the gates to the wrong answer", then I think you owe us an actual explanation of what shortcuts they are taking and how you know you're taking them, rather than just a link to a paper from 1996 that says how to take some shortcuts.
        7y ago

acqq 7y ago

For those who are interested in the papers about this topic: https://arxiv.org/abs/1301.7007 https://arxiv.org/abs/1301.7007 "Pretending to factor large numbers on a quantum computer (2013)" "Of course this should not be considered a serious demonstration of Shor’s algorithm. It does, however, illustrate the danger in “compiled” demonstrations of Shor’s algorithm. To varying degrees, all previous factorization experiments have benefited from this artifice. While there is no objection to having a classical compiler help design a quantum circuit (indeed, probably all quantum computers will function in this way), it is not legitimate for a compiler to know the answer to the problem being solved. To even call such a procedure compilation is an abuse of language." More references: https://crypto.stackexchange.com/questions/59795/largest-integer-factored-by-shors-algorithm/59796#59796 https://crypto.stackexchange.com/questions/59795/largest-int...