On the role of entanglement in quantum-computational speed-up

RO Jozsa, N Linden

Research output: Contribution to journalArticle (Academic Journal)peer-review

379 Citations (Scopus)


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 contributionOn the role of entanglement in quantum-computational speed-up
Original languageEnglish
Pages (from-to)2011 - 2032
Number of pages22
JournalProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
Volume459 (2036)
Publication statusPublished - Aug 2003

Bibliographical note

Publisher: Royal Society London
Other identifier: IDS number 710NQ


Dive into the research topics of 'On the role of entanglement in quantum-computational speed-up'. Together they form a unique fingerprint.

Cite this