Quantum Algorithms: Entanglement Enhanced Information Processing

Abstract

We discuss the fundamental role of entanglement as the essential nonclassical feature providing the computational speed-up in the known quantum algorithms. We review the construction of the Fourier transform on an Abelian group and the principles underlying the fast Fourier transform algorithm. We describe the implementation of the FFT algorithm for the group of integers modulo 2^n in the quantum context, showing how the group-theoretic formalism leads to the standard quantum network and identifying the property of entanglement that gives rise to the exponential speedup (compared to the classical FFT). Finally we outline the use of the Fourier transform in extracting periodicities, which underlies its utility in the known quantum algorithms.

17 pages latex, no figures. To appear in Phil. Trans. Roy. Soc. (Lond.) 1998, Proceedings of Royal Society Discussion Meeting ``Quantum Computation: Theory and Experiment'', held in November 1997

Cited by in corpus (103)

• Experimental One-Way Quantum Computing
• On the role of entanglement in quantum computational speed-up
• Separability of very noisy mixed states and implications for NMR quantum computing
• Decoherence-Free Subspaces and Subsystems
• Experimental Implementation of Discrete Time Quantum Random Walk on an NMR Quantum Information Processor
• Sophisticated quantum search without entanglement
• Quantum Computing with NMR
• Implementation of quantum search algorithm using classical Fourier optics
• Group-Invariant Quantum Machine Learning
• Classical wave-optics analogy of quantum information processing
• Experimental demonstration of entanglement-enhanced classical communication over a quantum channel with correlated noise
• Quantum factoring, discrete logarithms and the hidden subgroup problem
• Deterministic generation of large cluster states using non-deterministic collective measurements based on quantum Zeno effect
• Quantum Computing Without Entanglement
• Entanglement, discord and the power of quantum computation
• Exponential speed-up with a single bit of quantum information: Testing the quantum butterfly effect
• Classical model for bulk-ensemble NMR quantum computation
• Efficient classical simulation of the semi-classical Quantum Fourier Transform
• Computable and operationally meaningful multipartite entanglement measures
• Climbing Mount Scalable: Physical-Resource Requirements for a Scalable Quantum Computer
• Teleportation using coupled oscillator states
• Quantum correlations as precursors of entanglement
• Implementation of a quantum algorithm to solve Bernstein-Vazirani's parity problem without entanglement on an ensemble quantum computer
• Local Realistic Model for the Dynamics of Bulk-Ensemble NMR Information Processing
• Long-range entanglement generation via frequent measurements
• Teleportation with the entangled states of a beam splitter
• Genuine N-partite entanglement and distributed relationships in the background of dilation black holes
• Atom-photon entanglement generation and distribution
• Classical simulation of Quantum Entanglement using Optical Transverse Modes in Multimode Waveguides
• Geometric Algebra and Information Geometry for Quantum Computational Software
• Can quantum mechanics help distributed computing?
• Time-reversal formalism applied to maximal bipartite entanglement: Theoretical and experimental exploration
• Entanglement and Relativity
• Entanglement Classifier in Chemical Reactions
• Spin squeezing criterion with local unitary invariance
• The quantum dynamics of two coupled qubits
• On the Significance of the Gottesman-Knill Theorem
• Quantum Entanglement involved in Grover's and Shor's algorithms: the four-qubit case
• Bell inequality violation by entangled single photon states generated from a laser, a LED or a Halogen lamp
• Efficient option pricing with unary-based photonic computing chip and generative adversarial learning
• Exactly solvable model for the dynamics of two spin-1/2 particles embedded in separate spin star environments
• Entanglement of Periodic States, the Quantum Fourier Transform and Shor's Factoring Algorithm
• Entropy certification of a realistic QRNG based on single-particle entanglement
• Entanglement generation between distant spins via quasilocal reservoir engineering
• Quantifying Computational Advantage of Grover's Algorithm with the Trace Speed
• Primitive Nonclassical Structures of the $N$-qubit Pauli Group
• Two-message quantum interactive proofs and the quantum separability problem
• How to Compute Using Quantum Walks
• A Hierarchy of Multipartite Correlations Based on Concentratable Entanglement
• Single-experiment-detectable multipartite entanglement witness for ensemble quantum computing
• Entanglement gauge and the non-Abelian geometric phase with two photonic qubits
• Nonlinear-dissipation-induced Entanglement of Coupled Nonlinear Oscillators
• Mermin Polynomials for Entanglement Evaluation in Grover's algorithm and Quantum Fourier Transform
• Entanglement of pair cat states and teleportation
• Decoherence of two-electron spin states in quantum dots
• Entangling capacity of global phases and implications for Deutsch-Jozsa algorithm
• Simulated Quantum Computation of Global Minima
• Shortcuts to adiabaticity in superconducting circuits for fast multi-partite state generation
• Sudden death of entanglement in fermionic systems under collective decoherence
• The Deutsch-Jozsa Problem: De-quantisation and Entanglement
• Understanding the Quantum Computational Speed-up via De-quantisation
• Complete Genuine Multipartite Entanglement Monotone
• Witness Operator Provides Better Estimate of the Lower Bound of Concurrence of Bipartite Bound Entangled States in $d_1\otimes d_2$ Dimensional System
• Superfast solution of linear convolutional Volterra equations using QTT approximation
• Coherence Fraction in Grover Search Algorithm
• Tighter monogamy inequalities of multiqubit entanglement
• Generation of quantum-certified random numbers using on-chip path-entangled single photons from an LED
• A relational time-symmetric framework for analyzing the quantum computational speedup
• Role of interference and entanglement in quantum neural processing
• Witnessing entanglement by proxy
• Open Quantum Systems and Quantum Algorithms
• Embedded Quantum Correlations in thermalized quantum Rabi systems
• Physical-resource demands for scalable quantum computation
• Tighter parameterized monogamy relations
• Upper bounds of holographic entanglement entropy growth rate for thermofield double states
• Witness based nonlinear detection of quantum entanglement
• Comment on "Quantum waveguide array generator for performing Fourier transforms: Alternate route to quantum computing"
• Tensor Rank and Other Multipartite Entanglement Measures of Graph States
• A prime factorization based on quantum dynamics on a spin ensemble (I)
• Analyzing the free states of one quantum resource theory as resource states of another
• The universal quantum driving force to speed up a quantum computation -- The unitary quantum dynamics
• General Concurrence Percolation on Quantum Networks
• Fast State Stabilization using Deep Reinforcement Learning for Measurement-based Quantum Feedback Control
• On the Necessity of Entanglement for the Explanation of Quantum Speedup
• Three-Photon Polarization Entanglement of Green Light
• Nonclassical Structures within the N-qubit Pauli Group
• Search for an efficient entanglement witness operator for bound entangled states in bipartite quantum systems
• Measurement of an integral of a classical field with a single quantum particle
• On the Physical Explanation for Quantum Computational Speedup
• Coupling modifies the quantum fluctuations of entangled oscillators
• Stabilization of symmetry-protected long-range entanglement in stochastic quantum circuits
• Decoding Quantum Search Advantage: The Critical Role of State Properties in Random Walks
• The Study of Entangled States in Quantum Computation and Quantum Information Science
• The Quantum-House Effect and Its Demonstration on SpinQ Gemini
• Constructing a ball of separable and absolutely separable states for $2\otimes d$ quantum system
• Scalable, chip-based optically-controlled gates for quantum information processing
• The basic principles to construct a generalized state-locking pulse field and simulate efficiently the reversible and unitary halting protocol of a universal quantum computer
• Atom- photon entanglement beyond the multi-photon resonance condition
• NMR Quantum Information Processing and Entanglement
• Oracle problems as communication tasks and optimization of quantum algorithms
• Quantum Routing and Entanglement Dynamics Through Bottlenecks
• Power of photonic states: from quantum computation to cosmology
• Static and dynamic coherence fraction in the Bernstein-Vazirani algorithm