The Power of the Quantum Computer

Given the possible power of quantum parallelism, much work has been done to show formally with mathematical proofs how quantum computers differ from classical ones in their power to compute things. Here is a short list of some of the landmarks in the study of the power of quantum computers.

In 1980 Paul Benioff offered a classical Turing machine which used quantum mechanics in its workings, thus showing that theoretically a quantum computer was at least as powerful as a classical computer. (Benioff)

David Deutsch and Richard Jozsa showed in a paper in 1992 that there was an algorithm that could be run in poly-log time on a quantum computer, but required linear time on a deterministic Turing machine. This may have been the first example of a quantum computer being shown to be exponentially faster than a deterministic Turing machine. Unfortunately for the quantum computer, the problem could also be solved in poly-log time in a probabilistic Turing machine, a Turing machine which is capable of making a random choice. (Deutsch, Jozsa)

Also in 1992 Andre Berthiaume proved that $P \subset QP$, where $P$ is a complexity class as mentioned earlier and $QP$ corresponds to problems which can be solved in worst case polynomial time by a quantum computer, so with regards to tractability a quantum computer is in some sense more powerful than any classical computer. (Berthiaume, Brassard)