4 ms·

Particle physics simulations are one of the areas where quantum computers would be exceedingly useful, dropping many calculations from exponential-time to, in t

Particle physics simulations are one of the areas where quantum computers would be exceedingly useful, dropping many calculations from exponential-time to, in the best case, linear. That's if you're trying to find exact solutions. Which you can't, but even the approximations we've got are frankly awful. So, basically a lack of computing resources. QCs aren't generally that much faster than classical ones, but in this particular case they are--understandably so, given the universe runs on quantum mechanics. Turing machines are not good enough for this, and no number of Intel CPUs will let us overcome that barrier. Physicists try really hard anyway, but the approximations are... Well. As I said, awful.

eru 9y ago
> Turing machines are not good enough for this, [...] Usually we only bring up Turing machines for decidability, ie when the only thing that matters is whether it takes finite or infinite amounts of time. (Yes, I know, you can also calculate exact runtimes with Turing machines, but nobody really cares, I think?) I guess you mean to say classical computer or so? > [...] and no number of Intel CPUs will let us overcome that barrier. Or at least that's everybody's best guess. On similar footing to the empirical evidence for P != NP. It's still theoretically possible that BQP = BPP, if memory serves right. (https://en.wikipedia.org/wiki/BQP https://en.wikipedia.org/wiki/BQP vs https://en.wikipedia.org/wiki/BPP_(complexity) https://en.wikipedia.org/wiki/BPP_(complexity))
- cgmg 9y ago
  The best 'physical' model of computation is probably the reversible 3D mesh (R3M) model: http://iopscience.iop.org/article/10.1088/0957-4484/9/3/005/meta http://iopscience.iop.org/article/10.1088/0957-4484/9/3/005/....
  - eru 9y ago
    Of course, it depends a bit on what you are trying to model. Most of the time the different ways to model computing only have a polynomial slowdown to emulate each other. In that sense, quantum computers are different from Turing machines: the best way we know to emulate quantum computers on Turing machines has exponential slow downs.
evanb 9y ago
LQCD is approximation-free, once you take the continuum and infinite-volume limits (if you're operating with physical parameters). But I obviously agree that large-scale universal quantum computers (or even specialized quantum emulators) would be extremely useful! For example, you can solve many notoriously difficult fermion sign problems, or study real-time dynamics with one.

eru 9y ago

> Turing machines are not good enough for this, [...] Usually we only bring up Turing machines for decidability, ie when the only thing that matters is whether it takes finite or infinite amounts of time. (Yes, I know, you can also calculate exact runtimes with Turing machines, but nobody really cares, I think?) I guess you mean to say classical computer or so? > [...] and no number of Intel CPUs will let us overcome that barrier. Or at least that's everybody's best guess. On similar footing to the empirical evidence for P != NP. It's still theoretically possible that BQP = BPP, if memory serves right. (https://en.wikipedia.org/wiki/BQP https://en.wikipedia.org/wiki/BQP vs https://en.wikipedia.org/wiki/BPP_(complexity) https://en.wikipedia.org/wiki/BPP_(complexity))

cgmg 9y ago
The best 'physical' model of computation is probably the reversible 3D mesh (R3M) model: http://iopscience.iop.org/article/10.1088/0957-4484/9/3/005/meta http://iopscience.iop.org/article/10.1088/0957-4484/9/3/005/....
- eru 9y ago
  Of course, it depends a bit on what you are trying to model. Most of the time the different ways to model computing only have a polynomial slowdown to emulate each other. In that sense, quantum computers are different from Turing machines: the best way we know to emulate quantum computers on Turing machines has exponential slow downs.

evanb 9y ago

LQCD is approximation-free, once you take the continuum and infinite-volume limits (if you're operating with physical parameters). But I obviously agree that large-scale universal quantum computers (or even specialized quantum emulators) would be extremely useful! For example, you can solve many notoriously difficult fermion sign problems, or study real-time dynamics with one.