Abstract

In quantum computation non classical features such as superposition states and entanglement are used to solve problems in new ways, impossible on classical digital computers.We illustrate by Deutsch algorithm how a quantum computer can use superposition states to outperform any classical computer. We comment on the view of a quantum computer as a massive parallel computer and recall Amdahls law for a classical parallel computer. We argue that the view on quantum computation as a massive parallel computation disregards the presence of entanglement in a general quantum computation and the non classical way in which parallel results are combined to obtain the final output.