Who needs qubits? Factoring algorithm run on a probabilistic computer

Re:Who needs qubits? Factoring algorithm run on a probabilis... by bo1024 on Thursday September 19, 2019 @10:50AM (#21016704)

This doesn't make sense to me (theoretical computer scientist). If I run the code

    x = rand() % 2

Then mathematically, x is a p-bit. That is, it is in a classical "superposition" having value 0 with probability 0.5 and having value 1 with probability 0.5.

So you don't need any special hardware to do classical probabilistic computations. You just need a source of entropy and a standard computer.

Now it might be that a different architecture than the standard von Neumann processor+memory one could give a polynomial speedup for certain problems. And that would be fine. But the focus of this Ars article as well as the Nature letter abstract is on p-bits, which seems nonsensical to me.

(Added later) I see there is an emphasis on the bits fluctuating or evolving over time, annealing I guess. We could of course simulate this on a standard computer, but not as easily. Still I am reminded of Aaronson's soap bubbles...

[ Parent | on HN ]

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 ]