# Can a quantum computer tell whether a program is Turing complete?

I am very new to quantum computing and would like to know if a quantum computer can decide whether a given program is Turing complete.

• A quantum computer can be simulated by a classical computer, for example by keeping track of the wave function. It is also in general undecidable to determine whether a given machine is Turing complete, with a classical computer. So the answer to your question is “no”. But it’s still a reasonable question to ask. Nov 14, 2021 at 3:41
• It is correct that a quantum computer cannot solve the halting problem. However, what is true is that the "halting problem has an interactive proof involving quantum entangled provers". This is because MIP*=RE quantumfrontiers.com/2020/03/01/the-shape-of-mip-re. Though the quantum computers required for such a task are likely impossible to construct. Nov 14, 2021 at 18:00
• I wondered about this too. The OP’s question was specifically about showing Turing-completeness and not strictly about the halting problem. Presumably, from Rice’s theorem, MIP* also is powerful enough to decide whether a given Turing machine is complete, in polynomial time.. Nov 15, 2021 at 1:38
• It doesn't make sense to describe a program as "Turing complete". Turing completeness is a property of a computer or programming language or execution environment, not a property of a specific program Nov 15, 2021 at 8:27
• @user18835 I read the OP's question broadly to ask whether any given Turing machine $M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle$ is Turing-complete. This is a well-defined problem. Nov 15, 2021 at 14:52