# Can a quantum computer (theoretically) do things a classical computer (literally) can't? [duplicate]

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.

• "said regular computer had infinite power (or processing speed or whatever)" You mean a Turing Machine? Commented Feb 6, 2015 at 13:48
• 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.
– usul
Commented Feb 6, 2015 at 15:13
• E.g. "quantum advantages for classically defined tasks" journals.aps.org/pra/abstract/10.1103/PhysRevA.77.052310
– usul
Commented Feb 6, 2015 at 15:14
• 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
– vzn
Commented Feb 7, 2015 at 19:57

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