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.
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)”
drdeca|5 years ago
(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)”