5 ms·

> The oft-cited examples of quantum computers factoring small numbers with Shor's algorithm demonstrate that the principles are correct, but do not actually fac

> The oft-cited examples of quantum computers factoring small numbers with Shor's algorithm demonstrate that the principles are correct, but do not actually factor the numbers; instead they basically assign probabilities; effectively (not literally) saying that there is a non-zero probability that 11 is a factor of 21. I don't understand this particular complaint. Quantum computing is inherently probabilistic, of course, but that's only because quantum mechanics is inherently probabilistic. It's a feature of the calculation, not a bug. At any rate, it's not really a problem if the factorization is sometimes incorrect. If you doubt the result, just multiply the numbers together on a classical computer. If the numbers don't match, repeat the process. Even if your quantum computer only yields the correct result 50% of the time, you'd still be better off using a quantum computer than brute forcing for large enough numbers. (Of course, and I suppose this is your point, quantum computers with a sufficient numbers of qubits to prove supremacy in factorization do not yet exist.)

ithkuil 4y ago
> I don't understand this particular complaint. Quantum computing is inherently probabilistic, of course, but that's only because quantum mechanics is inherently probabilistic. The substrate of physical digital computers is analog and probabilistic too. We just put a threshold above which a logic signal is considered 1 and we give enough time for a state transition to be considered done. We also throw in the mix a large number of electrons so that it's very likely that the aggregate effect produces a definite answer. This is not all that unlike what we have to do with quantum computers. You just have to find a suitable threshold after which your desired answer is sufficiently likely to come out.
- tromp 4y ago
  But even under these conditions no team has been able to demonstrate a working implementation of Shor's algorithm that can factor arbitrary 6-bit prime products. Quoting from [1]: > In 2019 an attempt was made to factor the number {\displaystyle 35}{\displaystyle 35} using Shor's algorithm on an IBM Q System One, but the algorithm failed because of accumulating errors.[13] Though larger numbers have been factored by quantum computers using other algorithms,[14] these algorithms are similar to classical brute-force checking of factors, so unlike Shor's algorithm, they are not expected to ever perform better than classical factoring algorithms. [1] https://en.wikipedia.org/wiki/Shor%27s_algorithm#See_also https://en.wikipedia.org/wiki/Shor%27s_algorithm#See_also
andrewla 4y ago
> (Of course, and I suppose this is your point, quantum computers with a sufficient numbers of qubits to prove supremacy in factorization do not yet exist.) That is sort of the point, but not quite. We do not have general-purpose quantum computers with even a single qubit! We've redefined qubits in the NISQ context for the purpose of demonstrating quantum supremacy, and that is all they are good for. If Google expands Sycamore to hold a billion qubits, it will not be capable of factoring 6. The hope is that if we accomplished that, then we could use those learnings to make single-purpose quantum computers or general-purpose quantum computers. But we haven't gotten there yet. This is not a matter of adding more NISQ qubits to any of the existing projects! > result 50% of the time 50% would be astonishingly good. If all the quantum computer can say is "well, one of these sqrt(N) possibilities are 50% likely to be a factor" then we haven't improved anything. And the IBM result on attempting to factor 35 seems to fall into this pattern; the noise level is too high.

ithkuil 4y ago

> I don't understand this particular complaint. Quantum computing is inherently probabilistic, of course, but that's only because quantum mechanics is inherently probabilistic. The substrate of physical digital computers is analog and probabilistic too. We just put a threshold above which a logic signal is considered 1 and we give enough time for a state transition to be considered done. We also throw in the mix a large number of electrons so that it's very likely that the aggregate effect produces a definite answer. This is not all that unlike what we have to do with quantum computers. You just have to find a suitable threshold after which your desired answer is sufficiently likely to come out.

tromp 4y ago
But even under these conditions no team has been able to demonstrate a working implementation of Shor's algorithm that can factor arbitrary 6-bit prime products. Quoting from [1]: > In 2019 an attempt was made to factor the number {\displaystyle 35}{\displaystyle 35} using Shor's algorithm on an IBM Q System One, but the algorithm failed because of accumulating errors.[13] Though larger numbers have been factored by quantum computers using other algorithms,[14] these algorithms are similar to classical brute-force checking of factors, so unlike Shor's algorithm, they are not expected to ever perform better than classical factoring algorithms. [1] https://en.wikipedia.org/wiki/Shor%27s_algorithm#See_also https://en.wikipedia.org/wiki/Shor%27s_algorithm#See_also

andrewla 4y ago

> (Of course, and I suppose this is your point, quantum computers with a sufficient numbers of qubits to prove supremacy in factorization do not yet exist.) That is sort of the point, but not quite. We do not have general-purpose quantum computers with even a single qubit! We've redefined qubits in the NISQ context for the purpose of demonstrating quantum supremacy, and that is all they are good for. If Google expands Sycamore to hold a billion qubits, it will not be capable of factoring 6. The hope is that if we accomplished that, then we could use those learnings to make single-purpose quantum computers or general-purpose quantum computers. But we haven't gotten there yet. This is not a matter of adding more NISQ qubits to any of the existing projects! > result 50% of the time 50% would be astonishingly good. If all the quantum computer can say is "well, one of these sqrt(N) possibilities are 50% likely to be a factor" then we haven't improved anything. And the IBM result on attempting to factor 35 seems to fall into this pattern; the noise level is too high.