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

By Richard Jozsa, Noah Linden. Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences, 2002

822 citations recorded by the source corpus.

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 η even if a suitably small amount of global entanglement 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.

Subfields: Artificial Intelligence, Atomic and Molecular Physics, and Optics

View Paper: https://www.semanticscholar.org/paper/bfdd559dc1293560912cca8b2cbfd83b0bb20603

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Atomic and Molecular Physics, and Optics

Citations in the corpus

Distributed Quantum Computing: a Survey (2022, neutral): “These states are referred to as entangled states and they represent the key ingredient in quantum computing [32, 33].”
Integrated Source of Spectrally Filtered Correlated Photons for Large-Scale Quantum Photonic Systems (2014, background): “[72] R.”
Quantum machine learning: a classical perspective (2017, background): “Although the true roots, and extents, of quantum speed-ups are still unclear, it is believed that structure, certain symmetries and non-classical correlations play an important role in the observed advantages [15,16].”
The classical-quantum boundary for correlations: Discord and related measures (2011, background): “(Jozsa and Linden, 2003) show, using a rigorous analysis, that a classical algorithm can in fact efficiently simulate all quantum computations using pure states for which the entanglement remains bounded throughout.”