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

2002/01/31 by Richard Jozsa, Noah Linden · 1 voice · 676 citations
Computer Science · Physics and Astronomy · #Exponential function #Key (lock) #Quantum #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Mechanics and Applications #Quantum discord #Quantum entanglement #Quantum state #Squashed entanglement #State (computer science) #quant-ph

paper · pdf · doi:10.1098/rspa.2002.1097

published in Proceedings of the Royal Society A Mathematical Physical and Engineering Sciences 459(2036), 2011-2032 (Royal Society) · Main proofs simplified. A few further explanatory remarks added. 22 pages, plain latex

arxiv created 2002/03/08 · openalex publication_date 2003/08/08 · arxiv updated 2009/12/01 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05

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.

Citations

• A universal two-bit gate for quantum computation
• A fast quantum mechanical algorithm for database search
• Nonlinear Quantum Mechanics Implies Polynomial-Time Solution forNP-Complete and #PProblems
• Simulating physics with computers
• Matrix Analysis

Cited by

• Entanglement from Expansion: High Rank-Width in Deterministic Graphs
• Studies on the Role of Entanglement in Mixed-state Quantum Computation
• Quantum magic of strongly correlated fermions - the Hubbard dimer
• On the existence of fully inseparable biseparable Gaussian states
• Micromagnons and long-range entanglement in ferrimagnetic ground states
• Spin correlation of hyperon-antihyperon systems in e⁺e^- annihilation
• Computing-heightened low-cost high-dimensional controlled-SUM gates
• Path-integral Monte Carlo method for Rényi entanglement entropies
• Classical emulation of a quantum computer
• Quantum Key Distribution with Classical Bob
• Generation of a maximally entangled state using collective optical pumping
• Qubit entanglement generation by Gaussian non-Markovian dynamics
• Detecting genuine non-Gaussian entanglement
• Experimental Quantum Computing without Entanglement
• Quantum circuits for maximally entangled states
• Multipartite entanglement detection for hypergraph states
• Quantum correlations and distinguishability of quantum states
• Entanglement of indistinguishable particles: A comparative study
• Absolutely classical spin states
• Efficient simulatability of continuous-variable circuits with large Wigner negativity
• Multiqubit symmetric states with maximally mixed one-qubit reductions
• Nanomaterials for Quantum Information Science and Engineering

Discussions

• While entanglement in a quantum circuit certainly makes it much more time consuming for a classical computer to complete the same task, I have not found any evidence that entanglement is useful comput [stackexchange, 1 points]