CoChat
Sign Up
Cited by 839Quantum Computing Algorithms and ArchitectureQuantum Information and CryptographyQuantum Mechanics and Applications

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

Open access
Jozsa, Richard, Linden, Noah·2003·Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences
DOI 10.1098/rspa.2002.1097
Open this paper in CoChat — free accountOpen PDF

Abstract

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1098/rspa.2002.1097

Cites

20 of 20 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • If quantum entanglement is not used in a quantum algorithm, the same algorithm can be worked with classical 0 and 1 bits computer systems without any remarkable change in computational speed.

    “It has been demonstrated that if the 'quantum entanglement phenomenon' is not used in the quantum algorithm, then the same algorithm can be worked with classical 0 and 1 bits computer systems without any remarkable change in computational speed.”

    From Quantum Computing in the Next-Generation Computational Biology Landscape: From Protein Folding to Molecular Dynamics (2024) · cites this paper as [22]

    The Introduction (p. 3) says that a quantum algorithm on unentangled pure states can be classically simulated with equivalent resources. The claim omits the pure-state restriction: Section 5 (p. 17) says whether algorithms using unentangled mixed states can be efficiently simulated remains unresolved. (LLM, conf=0.88)

    Experimental — accuracy not yet measured

  • Quantum entanglement is the cornerstone of quantum calculation speed.

    “The 'quantum entanglement phenomenon' is the cornerstone of quantum calculation speed and pieces of literature are available [21, 22].”

    From Quantum Computing in the Next-Generation Computational Biology Landscape: From Protein Folding to Molecular Dynamics (2024) · cites this paper as [22]

    The Introduction (p. 5) says entanglement is necessary for exponential speed-up in pure-state quantum algorithms. But it explicitly cautions against concluding that entanglement is an essential resource for quantum computational power, and Section 6 (p. 19) says its significance depends on the mathematical formalism used. Calling it the unqualified “cornerstone” of quantum calculation speed overstates the paper’s conclusion. (LLM, conf=0.88)

    Experimental — accuracy not yet measured

  • The existence of entanglement is fundamental for useful quantum computation.

    “The existence of entanglement is fundamental for useful quantum computation.”

    From The prospects of quantum computing in computational molecular biology (2021) · cites this paper as [45]

  • Any quantum algorithm that does not employ entanglement can be enacted in a classical computer with no significant difference in speed.

    “It has been proved that any quantum algorithm that does not employ entanglement can be enacted in a classical computer with no significant difference in speed [44,45].”

    From The prospects of quantum computing in computational molecular biology (2021) · cites this paper as [45]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 17

  1. [2][2] Deutsch, D. (1985) Proc. Roy. Soc. London Ser A 400 , 96-117; Deutsch, D. and Jozsa, R. (1992) Proc. Roy. Soc. London Ser A 439 , 553-558. -
  2. [3][3] Bernstein, E. and Vazirani, U. S. I. A. M. Journal on Computing (1997) 26 , 1411-1473. -
  3. [4][4] Simon, D. (1994) Proc. of 35th Annual Symposium on the Foundations of Computer Science , (IEEE Computer Society, Los Alamitos), p. 116 (Extended Abstract). Full version of this paper appears in S. I. A. M. Journal on Computing (1997) 26 , 14741483. -
  4. [5][5] Grover, L. (1996) Proc. 28th Annual ACM Symposium on the Theory of Computing , (ACM Press, New York), 212-219. See also Grover, L. (1997) Phys. Rev. Lett. 78 , 325-328. -
  5. [6][6] Shor, P. (1994) Proc. of 35th Annual Symposium on the Foundations of Computer Science , (IEEE Computer Society, Los Alamitos), p. 124 (Extended Abstract). Full version of this paper appears in S. I. A. M. Journal on Computing 26 (1997), 14841510. -
  6. [8][8] Bennett, C. H., Bernstein, E., Brassard, G. and Vazirani, U. (1997) S. I. A. M. Journal on Computing 26 (1997), 1510-1523. -
  7. [10][10] Barenco, A. (1995) Proc. Roy. Soc. London Ser A , 449 , 679-683. -
  8. [11][11] Jozsa, R. (1998) Pages 369-379 in The Geometric Universe edited by S. Huggett, L. Mason, K. P. Tod, S. T. Tsou and N. Woodhouse, Oxford University Press. -
  9. [12][12] Jozsa, R. (1998) Proc. Roy. Soc. London Ser A , 454 , 323-337. -
  10. [13][13] Ekert, A. and Jozsa, R. (1998) Phil. Trans. Roy. Soc. London Ser A 356 , 1769-1782. -
  11. [15][15] Vazirani, U. (1998) Phil. Trans. Roy. Soc. London Ser A 356 , 1759-1768. -
  12. [16][16] Nielsen, M. (2001) Preprint available at http://xxx.arXiv.org/abs/quant-ph/0108020 - · arXiv
  13. [18][18] Nielsen, M. and Chuang,. I. Quantum Computation and Quantum Information , Cambridge University Press 2000. -
  14. [19][19] Raz, R. (1999) Proc. 31th Annual ACM Symposium on the Theory of Computing , (ACM Press, New York), 358-367. -
  15. [25][25] Gottesman, D. (1997) Stabiliser codes and quantum error correction , Ph.D. thesis, California Institute of Technology, Pasadena, CA. -
  16. [26][26] Valiant, L. (2001) Proc. 33th Annual ACM Symposium on the Theory of Computing , (ACM Press, New York) -
  17. [27][27] Terhal, B. and and DiVincenzo, D. (2001) Preprint available at http://xxx.arXiv.org/abs/quant-ph/0108010 · arXiv

Cited by

Sorted by citations

Related

Authors
Jozsa, R., & Linden, N.
Affiliations
University of Bristol (GB)
ORCID
Jozsa, Richard
Venue
Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences
Publisher
The Royal Society
Published
2003-08-08
Volume
459
Issue
2036
Pages
2011-2032
ISSN
  • 1364-5021 (ISSN-L)
  • 1471-2946
DOI
10.1098/rspa.2002.1097
OpenAlex
W2163036762
Cited by
839
References
18
Citations by year
2026: 30 · 2025: 71 · 2024: 55 · 2023: 61 · 2022: 56 · 2021: 48 · 2020: 46 · 2019: 33 · 2018: 40 · 2017: 33 · 2016: 33 · 2015: 40 · 2014: 36 · 2013: 45 · 2012: 20
FWCI
20.16
Type
journal article
Language
en
Open access
Locations
  • Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • Explore Bristol Research (submittedVersion)
  • CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
  • Cambridge University Engineering Department Publications Database (submittedVersion)
  • Bristol Research (University of Bristol) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
  • Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Mechanics and Applications
Keywords
quantum entanglement, multipartite entanglement, global entanglement, Shor's algorithm, classical simulation of quantum algorithms, exponential speedup, mixed states

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review