9
$\begingroup$

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.

$\endgroup$
7
  • 4
    $\begingroup$ 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. $\endgroup$
    – Mark S
    Nov 14, 2021 at 3:41
  • 3
    $\begingroup$ 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. $\endgroup$
    – Condo
    Nov 14, 2021 at 18:00
  • 2
    $\begingroup$ 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.. $\endgroup$
    – Mark S
    Nov 15, 2021 at 1:38
  • 1
    $\begingroup$ 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 $\endgroup$
    – user18835
    Nov 15, 2021 at 8:27
  • 1
    $\begingroup$ @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. $\endgroup$
    – Mark S
    Nov 15, 2021 at 14:52

1 Answer 1

10
$\begingroup$

Classical and quantum computers are equivalent as far as questions of computability are concerned. The difference between them lies "merely" in the resource use.

The equivalence follows from the fact that a quantum computer can simulate a classical computer and a classical computer can simulate a quantum computer. The former can be achieved with little overhead by performing reversible variant of the classical computation in the computational basis. The latter can be done for example using Feynman's algorithm at the cost of exponential time overhead.

Consequently, quantum computers will not solve the Halting problem, answer questions about Turing completeness or decide other non-trivial semantic properties of computer programs.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.