On the role of entanglement in quantum computational speed-up

R Jozsa, N Linden

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


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 classically efficiently simulated to within a prescribed tolerance \eta even if a suitably small amount of global entanglement (depending on \eta) is present. We explicitly identify the occurrence of increasing multi-partite entanglement in Shor'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 pages21
JournalProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences
Publication statusPublished - Jun 2003


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

Cite this