Why is a quantum computer not capable of solving more problems than a classical computer?

Answered By : David Richerby

Because a quantum computer can be simulated using a classical computer: it's essentially just linear algebra. Given a probability distribution for each of the qubits, you can keep track of how each quantum gate modifies those distributions as time progresses. This isn't very efficient (which is why people want to build actual quantum computers) but it works.

Problem Detail: 

On the Wikipedia page for quantum algorithm I read that

[a]ll problems which can be solved on a quantum computer can be solved on a classical computer. In particular, problems which are undecidable using classical computers remain undecidable using quantum computers.

I expected that the fundamental changes that a quantum computer brings would lead to the possibility of not only solving problems that could already be solved with a classical computer, but also new problems that could not be solved before. Why is it that a quantum computer can only solve the same problems?

Asked By : Erwin Rooijakkers

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/44823