The Church-Turing-Deutsche (CTD) Principle is the idea that all physical processes are computable by a quantum computer (i.e. quantum Turing machine).

Before I knew this idea had a name, I always thought this was the case since all physical phenomena boil down to the unitary transformation and measurement of quantum systems(?). And indeed, all a quantum algorithm is is a series of unitary transforms and measurements on a quantum system. What finite realizable physical system could possibly be uncomputable?

But reading the literature gives me the sense that there are multiple opinions on this despite me thinking that this is an empirical question. What am I missing here?

P.S. I was going to post this in the quantum computing stack exchange but thought that this question is less about quantum computing/information/algorithms and more about quantum physics in general.

P.P.S. By computable I am strictly talking about just that, computable. Not efficiently computable.

  • $\begingroup$ Good question! It would be helpful to distinguish, though, between "computable" and "efficiently computable." Someone will doubtless post a better answer than I can, but taking the idea of a quantum computer sufficiently broadly it should probably be the case that physically processes are computable, almost by definition. But efficiently computable is another question entirely, and places much more stringent restrictions on the types of problems we can address, although these constraints are also not completely understood. $\endgroup$ – Will May 7 at 2:23
  • 1
    $\begingroup$ I agree, and I indeed meant computable and not the more specific efficiently computable. I'll edit the question to make this clear. $\endgroup$ – Ozaner Hansha May 7 at 2:28

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.