Quantum Computing Without Entanglement
arXiv:quant-ph/0306182 · doi:10.1016/j.tcs.2004.03.041
Abstract
It is generally believed that entanglement is essential for quantum computing. We present here a few simple examples in which quantum computing without entanglement is better than anything classically achievable, in terms of the reliability of the outcome after a xed number of oracle calls. Using a separable (that is, unentangled) n-qubit state, we show that the Deutsch-Jozsa problem and the Simon problem can be solved more reliably by a quantum computer than by the best possible classical algorithm, even probabilistic. We conclude that: (a) entanglement is not essential for quantum computing; and (b) some advantage of quantum algorithms over classical algorithms persists even when the quantum state contains an arbitrarily small amount of information|that is, even when the state is arbitrarily close to being totally mixed.
18 pages. Presented at FoCM'02 (Aug 2002, see http://www.cs.technion.ac.il/~danken/pub/QCnoEnt.pdf), QIP'03 (Dec 2002, see http://www.msri.org/publications/ln/msri/2002/qip/brassard/1/), Qubit'03 (Apr 2003, see http://www.cs.technion.ac.il/~talmo/Qubitconf/QUBIT-2003/program/)
References in corpus (2)
Cited by in corpus (52)
- Quantum entanglement
- The classical-quantum boundary for correlations: discord and related measures
- Experimental One-Way Quantum Computing
- Quantum Key Distribution with Classical Bob
- Semi-Quantum Key Distribution
- Signatures of non-classicality in mixed-state quantum computation
- Entanglement Is Not Necessary for Perfect Discrimination between Unitary Operations
- Universal quantum computation with little entanglement
- Deterministic generation of large cluster states using non-deterministic collective measurements based on quantum Zeno effect
- Maximally discordant mixed states of two qubits
- Experimental evidence of non-classical brain functions
- Quantum discord and multipartite correlations
- The elusive source of quantum effectiveness
- Orthogonal measurements are {\it almost} sufficient for quantum discord of two qubits
- Quantum Correlations in Large-Dimensional States of High Symmetry
- Quantum computation with classical light: implementation of the Deutsch-Jozsa Algorithm
- Experimental investigation of quantum correlations in a two-qutrit spin system
- Noisy One-Way Quantum Computations: The Role of Correlations
- Entanglement and coherence in Bernstein-Vazirani algorithm
- Classical analog of qubit logic based on a magnon Bose-Einstein condensate
- Difficulties in analytic computation for relative entropy of entanglement
- On two-qubit states ordering with quantum discords
- Quantum discord versus second-order MQ NMR coherence intensity in dimers
- Can communication power of separable correlations exceed that of entanglement resource?
- Entanglement and deterministic quantum computing with one qubit
- Qubit Analog with Polariton Superfluid in an Annular Trap
- Quantum correlations of identical particles subject to classical environmental noise
- Quantum computing with mixed states
- A Quantum-Classical Model of Brain Dynamics
- Sharp complexity phase transitions generated by entanglement
- Quantifying Computational Advantage of Grover's Algorithm with the Trace Speed
- Universal quantum Controlled-NOT gate
- Geometric measure of quantum discord and total quantum correlations in a N-partite quantum state
- Total correlations and mutual information
- Non-separability of Physical Systems as a Foundation of Consciousness
- Genuine Multipartite Entanglement in Quantum Optimization
- Quantum correlation evolution of GHZ and W states under noisy channels using ameliorated measurement-induced disturbance
- The Deutsch-Jozsa Problem: De-quantisation and Entanglement
- Generalizations of Quantum Discord
- Nonclassical correlations in subsystems of globally entangled quantum states
- Approximation, Proof Systems, and Correlations in a Quantum World
- Quantum Advantage without Entanglement
- On the Physical Explanation for Quantum Computational Speedup
- The Dynamics of Entanglement in the Adiabatic Search and Deutsch Algorithms
- A Thermodynamic Turing Machine: Artificial Molecular Computing Using Classical Reversible Logic Switching Networks
- Integer Programming Using A Single Atom
- On the Necessity of Entanglement for the Explanation of Quantum Speedup
- Multipartite Generalization of Geometric measure of Discord
- Towards a Pattern Language for Quantum Algorithms
- Constructing a ball of separable and absolutely separable states for quantum system
- Quantum Computation via Paraconsistent Computation
- Oracle problems as communication tasks and optimization of quantum algorithms