Who needs qubits? Factoring algorithm run on a probabilistic computer

Re:Who needs qubits? Factoring algorithm run on a probabilis... by deepnotderp on Thursday September 19, 2019 @04:40PM (#21020525)

If I understand correctly, the key difference is that the rand() function in a Turing machine cannot generate true random numbers (I think it's something like Martin-Lof?).

[ Parent | on HN ]

Re:Who needs qubits? Factoring algorithm run on a probabilis... by bo1024 on Thursday September 19, 2019 @07:33PM (#21021792)

Pseudorandomness is related, but doesn't affect this issue. We can hook up a physically random process to a computer for a source of "true" random bits, then go from there.

[ Parent | on HN ]

Re:Who needs qubits? Factoring algorithm run on a probabilis... by sokrates85 on Friday September 20, 2019 @02:48PM (#21029966)

x = rand() % 2 always gives a random number. You can't correlate them that way.

Needs to be a tunable random number and technically needs to be "true" as mentioned.

But I don't think that the authors would disagree with your larger point - their point is to provide polynomial speed-up over digital computers for a certain class of problems. That this can be done with classical computers isn't exactly a deep insight, it's rather obvious.

[ Parent | on HN ]