9

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.

Adam Zalcman
  • 22,278
  • 3
  • 34
  • 83
Laith Striegher
  • 101
  • 3
  • 4
    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. – Mark Spinelli Nov 14 '21 at 03:41
  • 3
    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 https://quantumfrontiers.com/2020/03/01/the-shape-of-mip-re/. Though the quantum computers required for such a task are likely impossible to construct. – Condo Nov 14 '21 at 18:00
  • 2
    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.. – Mark Spinelli Nov 15 '21 at 01:38
  • @Condo Thanks for the link! Fascinating read! It is perhaps relevant to note that the computers involved in $MIP^$ are not quantum computers in the usual sense of the word. The verifier is a classical computer and the provers are magical* quantum computers (in the sense that there are no bounds on their computational capabilities) that share arbitrary amount of entanglement, but cannot communicate with each other. As with non-deterministic Turing machines, I don't think anyone actually hopes to ever build one. Instead, their study sheds some light on the gap between search and verification. – Adam Zalcman Nov 15 '21 at 02:16
  • 1
    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 – user18835 Nov 15 '21 at 08:27
  • @Laith Striegher are you wondering whether a quantum computer can solve the halting problem, i.e. find an input $f$ for which a Turing machine $M$ halts, or whether it can verify if given a Turing machine $M$ halts on a specific input $f_0$? These are importantly different questions, however, realistically the answer is no for both. – Condo Nov 15 '21 at 14:37
  • 1
    @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. – Mark Spinelli Nov 15 '21 at 14:52

1 Answers1

10

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.

Adam Zalcman
  • 22,278
  • 3
  • 34
  • 83