I've been searching the net for an answer to this question, but it's guetting quite confusing. I want to know if there are some undecidable problems for a classical computer that a quantum computer could do. The examples I've seen are things like Shor's algorithm, but that's "just" because the quantum computer is more powerfull than the classical one, and can do stuff like Integer factorization faster. Or at least that's how I understand it so far. Basically my question is this : is there anything a quantum computer can do that a regular one can't if said regular computer had infinite power (or processing speed or whatever)? Examples, explanations, sources would be greatly appreciated, but a simple yes/no would please me also.

  • $\begingroup$ "said regular computer had infinite power (or processing speed or whatever)" You mean a Turing Machine? $\endgroup$ – Logan Mayfield Feb 6 '15 at 13:48
  • $\begingroup$ It might depend what you mean by "things". We typically think of simply computing an input on an output, in which case the answer is "no" in that a classical computer can simulate the quantum one (it might take a long time though). However, I (non-expert) feel like I have heard the answer could be "yes" if the thing we want to do involves a system or network of computers and quantum entanglement/randomness is involved. For instance, playing some guessing game with probability higher than any classical computer could. $\endgroup$ – usul Feb 6 '15 at 15:13
  • 1
    $\begingroup$ E.g. "quantum advantages for classically defined tasks" journals.aps.org/pra/abstract/10.1103/PhysRevA.77.052310 $\endgroup$ – usul Feb 6 '15 at 15:14
  • $\begingroup$ this was a pretty good question until that phrase "...if said regular computer had infinite power or processing speed or whatever" which unf doesnt make much scientific sense, its a counterfactual $\endgroup$ – vzn Feb 7 '15 at 19:57

No. Quantum computers cannot solve undecidable problems.

A quantum computer can be simulated by a classical computer. So, if a quantum algorithm could solve an undecidable problem, then we could also solve it classically via simulation. However, we already know that if a problem has no classical solution, then it must not have a quantum solution either.

Also, you said:

that's "just" because the quantum computer is more powerful than the classical one.

This is an open problem. We do not yet know if $BPP \subset BQP$.


I quantum computer isn't more powerful than a classical one, according to Church-Turing's thesis, a function on the natural numbers is computable if and only if it is computable by a Turing machine, that means that there isn't a computer model that is more powerful than a Turing Machine.