We’re rewarding the question askers & reputations are being recalculated! Read more.
2

I will address the first two parts based on what I understood so far. 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–...


2

Taking the questions head on. 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. The question has been answered many times in QCSE that a quantum ...


1

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


Only top voted, non community-wiki answers of a minimum length are eligible