30 ms·

This strikes me as a perfect application for quantum computers---but I'm just an amateur, so I'd love to hear an expert opinion. My understanding is this 1982 t

This strikes me as a perfect application for quantum computers---but I'm just an amateur, so I'd love to hear an expert opinion. My understanding is this 1982 talk by Feynman [1] more or less launched the study of quantum computers, and it's all about how they can carry a probabilistic value through their computations rather than a definite one. And one of the lessons from that paper (if I'm reading & remembering right---maybe it's another paper) is that simulating quantum behavior with a non-quantum computer turns a lot of polynomial-time problems into exponential-time problems, so that having a real quantum computer would be very helpful for solving the performance & scalability issues described in the OP. Thoughts? [1] http://www.cs.berkeley.edu/~christos/classics/Feynman.pdf http://www.cs.berkeley.edu/~christos/classics/Feynman.pdf

ibab 12y ago
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 http://www.scottaaronson.com/democritus/lec9.html
- pjungwir 12y ago
  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!

ibab 12y ago

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 http://www.scottaaronson.com/democritus/lec9.html

pjungwir 12y ago
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!