[drdeca]

A Turing machine, that is, the mathematical formalism, can definitely simulate quantum mechanics. A classical Turing machine simulating a quantum Turing machine, or other model of quantum computation, would, aiui, incur a super-polynomial slowdown (maybe exponential? My impression is that that it might not be known to exponential. But at worst basically exponential).

The randomness is not an issue. Just don’t add any wave function collapse, or just list the probability of each outcome.

[ZeroFries]

This is just not the case, even with infinite energy and time. There are properties of quantum Turing machines that are not reproducible with classical Turing machines.

https://web.archive.org/web/20081123183419/http://www.ceid.u...

[drdeca]

That abstract appears to be referring to the superpolynomial slowdown in simulating one, which I already pointed out.

(If there is more than the abstract there, the scrolling isn’t working on my phone.)

There is no function that a QTM can compute that a TM cannot. But a QTM can compute some functions much faster.

Or, as phrased in the abstract “these do not include the computation of any non-recursive function”.

Edit: of course, there are things that can can be done with QM that can’t be with a TM (such as the entangled multi-party prover/verifier setup), but none of them are “compute this function (with no limit on how long it takes)” or “simulate this situation (with no limit on how long it takes)”