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

Question

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.

Answer 1

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.