Quantum search without entanglement

Abstract

Entanglement of quantum variables is usually thought to be a prerequisite for obtaining quantum speed-ups of information processing tasks such as searching databases. This paper presents methods for quantum search that give a speed-up over classical methods, but that do not require entanglement. These methods rely instead on interference to provide a speed-up. Search without entanglement comes at a cost: although they outperform analogous classical devices, the quantum devices that perform the search are not universal quantum computers and require exponentially greater overhead than a quantum computer that operates using entanglement. Quantum search without entanglement is compared to classical search using waves.

9 pages, TeX, submitted to Physical Review Letters

References in corpus (4)

• Experimental realization of a quantum algorithm
• Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer
• Implementation of a Quantum Algorithm to Solve Deutsch's Problem on a Nuclear Magnetic Resonance Quantum Computer
• Deutsch-Jozsa algorithm as a test of quantum computation

Cited by in corpus (62)

• Quantum Computing in Molecular Magnets
• Sophisticated quantum search without entanglement
• Implementation of quantum search algorithm using classical Fourier optics
• Ultracold polar molecules as qudits
• Entanglement Is Not Necessary for Perfect Discrimination between Unitary Operations
• Coherent oscillations in a superconducting multi-level quantum system
• Single-photon two-qubit "entangled'' states: preparation and measurement
• Climbing Mount Scalable: Physical-Resource Requirements for a Scalable Quantum Computer
• Exponential complexity of an adiabatic algorithm for an NP-complete problem
• Quantum interference as a resource for quantum speedup
• Resonant cancellation of off-resonant effects in a multilevel qubit
• Implementation of a quantum algorithm to solve Bernstein-Vazirani's parity problem without entanglement on an ensemble quantum computer
• Characterization of pure quantum states of multiple qubits using the Groverian entanglement measure
• Design and Construction of a Brain-Like Computer: A New Class of Frequency-Fractal Computing Using Wireless Communication in a Supramolecular Organic, Inorganic System
• Geometric Strategy for the Optimal Quantum Search
• Quantum Optical Systems for the Implementation of Quantum Information Processing
• The Groverian Measure of Entanglement for Mixed States
• Geometric Algebra and Information Geometry for Quantum Computational Software
• Implementation of a Deutsch-like quantum algorithm utilizing entanglement at the two-qubit level, on an NMR quantum information processor
• Simple implementation of a quantum search with trapped ions
• Efficient option pricing with unary-based photonic computing chip and generative adversarial learning
• Phase information revealed by interferences in the ionization of rotational wave packets
• Interferometric computation beyond quantum theory
• Rabi Oscillations in Systems with Small Anharmonicity
• A Quantum-Classical Model of Brain Dynamics
• The Representation of Natural Numbers in Quantum Mechanics
• Quantifying Computational Advantage of Grover's Algorithm with the Trace Speed
• Time and frequency domain solutions in an optical analogue of Grover's search algorithm
• Direct Measurement of Kirkwood-Rihaczek distribution for spatial properties of coherent light beam
• Correlation dynamics of a two-qubit system in a Bell-diagonal state under non-identical local noises
• Nonclassical Imaging for a quantum search of trapped ions
• A classical limit of Grover's algorithm induced by dephasing: Coherence vs entanglement
• Sudden Decoherence Transitions for Quantum Discord
• Role of interference and entanglement in quantum neural processing
• Partial Distinguishability as a Coherence Resource in Boson Sampling
• Physical-resource demands for scalable quantum computation
• Noise resilience and entanglement evolution in two non-equivalent classes of quantum algorithms
• Quantum Logical States and Operators for Josephson-like Systems
• Scattering Expansion for Localization in One Dimension: from Disordered Wires to Quantum Walks
• Quantum Advantage without Entanglement
• Finding Solutions to NP Problems: Philosophical Difference Between Quantum and Evolutionary Search Algorithms
• How big is a quantum computer?
• Ghost factors in Gauss-sum factorization with transmon qubits
• Quantum Effects and Genetics Code: Dynamics and Information Transfer in DNA Replication
• A prime factorization based on quantum dynamics on a spin ensemble (I)
• Visualizing quantum mechanics in an interactive simulation -- Virtual Lab by Quantum Flytrap
• Measurement of an integral of a classical field with a single quantum particle
• Scattering Expansion for Localization in One Dimension
• Integer Programming Using A Single Atom
• Spin-wave dynamics controlled by tunable ac magnonic crystal
• Algebra, Logic and Qubits: Quantum Abacus
• Constructing a ball of separable and absolutely separable states for $2\otimes d$ quantum system
• The Representation of Numbers in Quantum Mechanics
• Quantum Probes Reduce Measurements: Application to Distributed Grover Algorithm
• Investigations in quantum games using EPR-type set-ups
• Testing Quantum Dynamics in Genetic Information Processing
• Power of photonic states: from quantum computation to cosmology
• Optimal-speed unitary quantum time evolutions and propagation of light with maximal degree of coherence
• Entanglement and its applications in systems with many degrees of freedom
• Oracle problems as communication tasks and optimization of quantum algorithms
• Gaussian Amplitude Amplification for Quantum Pathfinding
• Encoding a qubit into multilevel subspaces