For any quantum algorithm operating on pure states, we prove that the presence of multi-partite entanglement, with a number of parties that increases unboundedly with input size, is necessary if the quantum algorithm is to offer an exponential speed-up over classical computation. Furthermore, we prove that the algorithm can be efficiently simulated classically to within a prescribed tolerance 77 even if a suitably small amount of global entanglement is present. We explicitly identify the occurrence of increasing multi-partite entanglement in Sher's algorithm. Our results do not apply to quantum algorithms operating on mixed states in general and we discuss the suggestion that an exponential computational speed-up might be possible with mixed states in the total absence of entanglement. Finally, despite the essential role of entanglement for pure-state algorithms, we argue that it is nevertheless misleading to view entanglement as a key resource for quantum-computational power.
|Translated title of the contribution||On the role of entanglement in quantum-computational speed-up|
|Pages (from-to)||2011 - 2032|
|Number of pages||22|
|Journal||Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences|
|Publication status||Published - Aug 2003|
Bibliographical notePublisher: Royal Society London
Other identifier: IDS number 710NQ