Prof. Aaronson mentions that the quantum extended Church-Turing (quantum ECT) thesis has no known counterexamples cf. around 14:18 but doesn't mention its precise statement.


  1. What precisely is the statement of the quantum extended Church-Turing thesis? Original references appreciated.

  2. Is there any quantum Church-Turing thesis (i.e. a non-extended version that doesn't concern itself with the efficiency of computation)? If yes, what's its precise statement?

  3. Is there any fundamental difference between the quantum extended Church-Turing thesis and Deutsch's 1985 version? Does the former include or imply any assertion about "finitely realizable physical systems" like the latter does?

†: "Every finitely realizable physical system can be perfectly simulated by a universal model computing machine operating by finite means."

  • 1
    $\begingroup$ Regarding 2 - how would you expect a "quantum Church-Turing thesis" to be different than the classical Church-Turing thesis? Neither quantum nor classical Turing machines can solve the halting problem. It's a good question - I'm wondering if there's an advantage to QC outside of efficiency. $\endgroup$ – Mark S May 7 at 16:27
  • $\begingroup$ @MarkS 1. I'd expect the "quantum Church-Turing thesis" to be along the lines of "A quantum Turing machine can simulate any realistic model of computation" (similar to Wikipedia's definition of quantum complexity-theoretic Church–Turing thesis). 2. The classical version of CT thesis doesn't talk about efficiency while the extended CT thesis does, but is widely believed to be false (with the advent of quantum computing and quantum fault-tolerance). 3. I'm not sure why you mention the halting problem; CT specifically talks about computable functions. $\endgroup$ – Sanchayan Dutta May 7 at 16:48
  • $\begingroup$ @MarkS If you're interested, Gil Kalai has written an answer on exactly this topic on CS Theory. To clarify, I don't think the classical statement of Church-Turing thesis is false (albeit it's only as good as its assumptions), but that its physical versions are (at least the ones before Deutsch's version). $\endgroup$ – Sanchayan Dutta May 7 at 17:01
  • 1
    $\begingroup$ Classical Church-Turing thesis holds in quantum world since we can simulate (ineffectively) quantum computation on a classical device. This means quantum computers can calculate only ordinary computable functions. And they can't solve the halting problem. $\endgroup$ – Danylo Y May 7 at 17:14
  • 2
    $\begingroup$ @MarkS I think I get what you were trying to say now. A "quantum CT thesis" would not be much different from the "classical CT thesis" (at least the way I'm thinking about it), because without any efficiency considerations they're supposedly equivalent. $\endgroup$ – Sanchayan Dutta May 7 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.