Skip to main content
Computer Science

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

7
  • 12
    $\begingroup$ As stated, this is wrong, or at least very imprecise: a classical Turing machine (TM) can compute everything that a quantum Turing machine (QTM) can. However, there is evidence to suggest that a QTM may solve certain problems exponentially faster than a TM, and that's probably what Deutsch is referring to. This remains a conjecture, because we lack the tools to prove strong complexity bounds against Turing machines. $\endgroup$ Commented Jun 2, 2016 at 14:14
  • 6
    $\begingroup$ David Deutsch's book is fascinating but contains some errors. For instance, he says that intuitionistic mathematics denies the existence of infinitely many natural numbers, and he confuses Hilbert's problems (gets the numbers wrong), so don't use it as a reference. $\endgroup$ Commented Jun 2, 2016 at 14:38
  • 2
    $\begingroup$ @PeterLeupold, can you give a reference for the claim that there is a reasonable quantum computation model which can compute a function over natural numbers which is not computable by a Turing machine? $\endgroup$ Commented Jun 2, 2016 at 18:02
  • 1
    $\begingroup$ @Kaveh Maybe Peter means non-uniform models which can compute any function. $\endgroup$ Commented Jun 2, 2016 at 19:16
  • 2
    $\begingroup$ @Sasho, I am sure that is what Peter mean, although they can computable functions which are not computable by classical Turing machines, that is because of their nonuniformity, not quantumness; nonuniform classical models do that as well. $\endgroup$ Commented Jun 3, 2016 at 0:30