The DOI matches its Crossref record; 20 of the 20 references it cites were found in a registry or an index.
On the role of entanglement in quantum-computational speed-up
Open accessAbstract
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.
Overview
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.
Integrity signals
Registry
Cites
Statistics
Verification
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.
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?
The source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“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]
Experimental — accuracy not yet measuredThe source backs part of the claim, not all of it — or backs it for a different population, condition or comparison.
In the citing paper
“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]
Experimental — accuracy not yet measuredIn the citing paper
“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]
In the citing paper
“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.
Citations
Cites
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830
Simulating physics with computers
Feynman, R. P. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02650179 · Cited by 7,691
Raussendorf, R., & Briegel, H. J. (2001) · Physical Review Letters · doi:10.1103/physrevlett.86.5188 · Cited by 4,477
Quantum Mechanics Helps in Searching for a Needle in a Haystack
Grover, L. K. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.325 · Cited by 4,306
Rapid solution of problems by quantum computation
Deutsch, D., & Jozsa, R. (1992) · Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences · doi:10.1098/rspa.1992.0167 · Cited by 2,700
Self-citationBhatia, R. (1997) · Graduate texts in mathematics · doi:10.1007/978-1-4612-0653-8 · Cited by 2,334
Volume of the set of separable states
Życzkowski, K., Horodecki, P., Sanpera, A., & Lewenstein, M. (1998) · Physical Review A · doi:10.1103/physreva.58.883 · Cited by 1,411
Power of One Bit of Quantum Information
Knill, E. H., & Laflamme, R. (1998) · Physical Review Letters · doi:10.1103/physrevlett.81.5672 · Cited by 918
Vidal, G., & Tarrach, R. (1999) · Physical Review A · doi:10.1103/physreva.59.141 · Cited by 601
Separability of Very Noisy Mixed States and Implications for NMR Quantum Computing
Braunstein, S. L., Caves, C. M., Jozsa, R., Linden, N., Popescu, S., & Schack, R. (1999) · Physical Review Letters · doi:10.1103/physrevlett.83.1054 · Cited by 566
Self-citationClassical simulation of noninteracting-fermion quantum circuits
Terhal, B. M., & DiVincenzo, D. P. (2002) · Physical Review A · doi:10.1103/physreva.65.032325 · Cited by 329
Nonlinear Quantum Mechanics Implies Polynomial-Time Solution for NP -Complete and # P Problems
Abrams, D. S., & Lloyd, S. (1998) · Physical Review Letters · doi:10.1103/physrevlett.81.3992 · Cited by 269
Quantum algorithms: entanglement–enhanced information processing
EKERT, A. K., & Jozsa, R. (1998) · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rsta.1998.0248 · Cited by 230
Self-citationA universal two-bit gate for quantum computation
Barenco, A. (1995) · Proceedings of the Royal Society of London Series A Mathematical and Physical Sciences · doi:10.1098/rspa.1995.0066 · Cited by 225
Exponential separation of quantum and classical communication complexity
Raz, R. (1999) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/301250.301343 · Cited by 223
Quantum algorithms and the Fourier transform
Jozsa, R. (1998) · Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rspa.1998.0163 · Cited by 217
Self-citationGood Dynamics versus Bad Kinematics: Is Entanglement Needed for Quantum Computation?
Linden, N., & Popescu, S. (2001) · Physical Review Letters · doi:10.1103/physrevlett.87.047901 · Cited by 113
Self-citationOn the power of quantum computation
Vazirani, U. V. (1998) · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences · doi:10.1098/rsta.1998.0247 · Cited by 82
Quantum computing via measurements onlyPreprint
Raussendorf, R., & Briegel, H. J. (2000) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0010033 · Cited by 57
Speed-up and entanglement in quantum searchingPreprint
Braunstein, S. L., & Pati, A. K. (2000) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/0008018 · Cited by 2
Research works printed but not linked: 12
- Ambainis A. Schulman L. & Vazirani U. 2000 Proc. 32nd Annual ACM Symp. Theory of Computing. New York: ACM Press.
- Bennett C. H., 1997, SIAM J, Computing, 26, 1510
- Bernstein E., 1997, SIAM J, Computing, 26, 1411
- Braunstein S., 2002, Quant, Informat. Computat., 2, 399
- Deutsch D., 1985, Proc, R. Soc. Lond. A, 400, 96
- Gottesman D. 1997 Stabiliser codes and quantum error correction. PhD thesis California Institute of Technology Pasadena CA.
- Jozsa R. 1998 The geometric universe (ed. S. Huggett L. Mason K. P. Tod S. T. Tsou & N. Woodhouse) pp. 369-379. Oxford University Press.
- Nielsen M. 2001 Universal quantum computation using only projective measurement quantum memory and preparation of the 0 state. (Available at http://xxx.arXiv.org/abs/quantph/0108020.)
- Nielsen M. & Chuang I. 2000 Quantum computation and quantum information. Cambridge University Press.
- Shor P., 1997, SIAM J, Computing, 26, 1484
- Simon D., 1997, SIAM J, Computing, 26, 1474
- Valiant L. 2001 Proc. 33rd Annual ACM Symp. Theory of Computing. New York: ACM Press.
Cited by
Sorted by citations
Efficient Classical Simulation of Slightly Entangled Quantum Computations
Vidal, G. (2003) · Physical Review Letters · doi:10.1103/physrevlett.91.147902 · Cited by 2,368
Verstraete, F., Murg, V., & Cirac, J. I. (2008) · Advances In Physics · doi:10.1080/14789940801912366 · Cited by 1,841
Measurement-based quantum computation on cluster states
Raussendorf, R., Browne, D. E., & Briegel, H. J. (2003) · Physical Review A · doi:10.1103/physreva.68.022312 · Cited by 1,655
The classical-quantum boundary for correlations: Discord and related measures
Modi, K., Brodutch, A., Cable, H., Paterek, T., & Vedral, V. (2012) · Reviews of Modern Physics · doi:10.1103/revmodphys.84.1655 · Cited by 1,600
Albash, T., & Lidar, D. A. (2018) · Reviews of Modern Physics · doi:10.1103/revmodphys.90.015002 · Cited by 1,546
Metadata
- 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
- 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
- green
- arxiv.org
- 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 › Physics and Astronomy › Atomic and Molecular Physics, and Optics › 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
