(1) Departement Wiskunde, Vrije Universiteit Brussel, Pleinlaan 2, 1050 Brussel, Belgium;(2) Instytut Matematyki, Uniwersytet Gdaski, Wita Stwosza 57, 80-952 Gdask, Poland
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.