# 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.

## migrated from cstheory.stackexchange.comFeb 7 '15 at 18:16

This question came from our site for theoretical computer scientists and researchers in related fields.

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

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