[ibab]

You have to take into account that quantum processes are governed by a kind of "randomness" that is different from the one in stochastic processes. Scott Aaronson explains the basics of quantum mechanics very succinctly in one of his lectures [1].

The exponential->polynomial speedup we might get from a quantum computer doesn't really apply to stochastic processes, because we can already execute them in polynomial time on a classical computer (just use a random number generator).

Having a quantum computer would still be truly amazing, though. Even just being able to simulate quantum mechanics efficiently would be revolutionary.

[1] - http://www.scottaaronson.com/democritus/lec9.html

[pjungwir]

I upvoted this comment as soon as I read it, but just to follow up: that link is amazing. I read lecture 9, then 10, 10.5, 11, . . . Eventually I bought the book and am reading it from the beginning. Godel and the Halting Problem has been a pet interest for ~17 years, and I've often wondered about implications similar to Penrose's argument. The recent death of a young promising friend has made me want to research these things more seriously, and Aaronson seems like a wonderful guide. Thank you so much!