# What precisely is the quantum extended Church-Turing thesis?

### Context

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.

### Questions

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."

• 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. – Mark S May 7 at 16:27
• @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. – Sanchayan Dutta May 7 at 16:48
• @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). – Sanchayan Dutta May 7 at 17:01
• 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. – Danylo Y May 7 at 17:14
• @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. – Sanchayan Dutta May 7 at 17:32

1. I'm not sure that original references are very much the point, although there are some. It's not a hard question. The statement is that realistic polynomial time equals what a quantum computer (if you want to be rigorous, say a QTM) can do in polynomial time.

2. The question has been answered many times in QCSE that a quantum computer can be simulated by a classical computer with exponential overhead. Therefore, without the "extended" part, meaning limits on computation time, quantum computability is the same as classical computability.

3. I read Deutsch's paper differently. He argues that quantum mechanics disproves the classical extended Church-Turing thesis, and his quote basically states that there should be some realistic or "physical" ECT. But I think that his paper conservatively does not say what the true version of ECT should be, only that it should be at least as much as what a quantum computer can do.

All that said, my own view is that when you see a revolution in science, you don't usually need or get another one of the exact same kind. In other words, even when scientists (as a group) get a fundamental question wrong on the first try, they usually get it right on the second or third try. I think that quantum computers are realistic in principle, but I have never seen any good argument for some fantastic new thing afterwards that is even more powerful than quantum computers. It's hard to call that impossible, but only because there is no way to argue against the unforseeable.

• Thanks for answering! Regarding 3, I am not exactly clear on what Deutsch meant in his CDT principle. I more or less think that he meant that a quantum Turing machine can simulate any physical process in the universe (assuming quantum mechanics is an accurate description of all physical phenomena and compatible with general relativity, etc.). What did he mean by "finitely realizable physical system" and "finite means" though? Could you please elaborate on that a bit? – Sanchayan Dutta Oct 31 at 15:55
• Although I'm sure Deutsch believes that QM is accurate, he clearly wasn't ready to declare it everything for computational purposes. If had been decided on that point, he would have said so. On the other hand, in your quote he does endorse finite computation of some kind as all that you need for simulation and complexity theory. There are definitions of infinite computers, but he implies that such definitions are some combination of unrealistic and unnecessary. – Greg Kuperberg Oct 31 at 15:59

I will address the first two parts based on what I understood so far.

1. The extended Church–Turing thesis or (classical) complexity-theoretic Church–Turing thesis states that "A probabilistic Turing machine can efficiently simulate any realistic model of computation.", whereas the quantum extended Church–Turing thesis or quantum complexity-theoretic Church–Turing thesis states "A quantum Turing machine can efficiently simulate any realistic model of computation.". The key point being:

If BQP is shown to be a strict superset of BPP, it would invalidate the complexity-theoretic Church–Turing thesis. In other words, there would be efficient quantum algorithms that perform tasks that do not have efficient probabilistic algorithms. This would not, however, invalidate the original Church–Turing thesis, since a quantum computer can always be simulated by a Turing machine, but it would invalidate the classical complexity-theoretic Church–Turing thesis for efficiency reasons.

2. A quantum Church-Turing thesis such as "A quantum Turing machine can simulate any realistic model of computation" would not be essentially different from the original Church-Turing thesis which states "A classical Turing machine can simulate any realistic model of computation", because without efficiency considerations they're equivalent. A classical Turing machine can certainly simulate a quantum Turing machine, although not necessarily efficiently, and vice-versa.

Regarding the "quantum (non-extended) Church-Turing Thesis," I think this asserts that there is no physical process, like a quasar or some other astronomical woo, that we know could produce a steady supply of qubits all in the same state $$\alpha|0\rangle+\beta|1\rangle$$, with the property that $$\beta^2=\Omega_C$$, that is, Chaitin's halting probability. We can also say classically that there is no magic coin that we know lands heads with probability precisely $$\Omega_C$$.

However, after recent proofs that $$\mathrm{NEEXP}\subset\mathrm{MIP^*}$$ (multi-prover interactive proofs with entangled provers), there is some indication that perhaps two God-like entities that are able to share an infinite amount of entanglement can convince a mere mortal of some undecidable proposition, maybe even in only a polynomial amount of time! See here I think.

• Regarding the point in your first paragraph, I guess that lies in the realm of hypercomputation in general (which is widely considered to be physically unrealizable). Indeed, if the possibility of hypercomputation is demonstrated that would violate the quantum CTT. This citation seems relevant. – Sanchayan Dutta Oct 31 at 15:14