Hacker News new | ask | show | jobs
by drdeca 1912 days ago
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)”