On the Necessity of Entanglement for the Explanation of Quantum Speedup
arXiv:1112.1347
Abstract
In this paper I argue that entanglement is a necessary component for any explanation of quantum speedup and I address some purported counter-examples that some claim show that the contrary is true. In particular, I address Biham et al.'s mixed-state version of the Deutsch-Jozsa algorithm, and Knill & Laflamme's deterministic quantum computation with one qubit (DQC1) model of quantum computation. I argue that these examples do not demonstrate that entanglement is unnecessary for the explanation of quantum speedup, but that they rather illuminate and clarify the role that entanglement does play.
arXiv commentMany clarificatory changes, and improved argumentation. Comments and criticisms are still welcome
References in corpus (33)
- Separability Criterion for Density Matrices
- A computable measure of entanglement
- Introducing Quantum Discord
- Classical, quantum and total correlations
- Quantum Algorithms Revisited
- Quantum discord and the power of one qubit
- On the Power of One Bit of Quantum Information
- In defense of the epistemic view of quantum states: a toy theory
- Separability of very noisy mixed states and implications for NMR quantum computing
- Quantum information can be negative
- Entanglement and the Power of One Qubit
- Interpreting quantum discord through quantum state merging
- Operational interpretations of quantum discord
- Characterizing quantum theory in terms of information-theoretic constraints
- Einselection and Decoherence from an Information Theory Perspective
- Quantum Algorithms: Entanglement Enhanced Information Processing
- Dynamics of initially entangled open quantum systems
- Conservation law for distributed entanglement of formation and quantum discord
- All entangled states are useful for information processing
- Physical accessibility of non-completely positive maps
- Good dynamics versus bad kinematics. Is entanglement needed for quantum computation?
- Quantum Computing Without Entanglement
- Nonlocal character of quantum theory?
- Separable balls around the maximally mixed multipartite quantum states
- Entanglement, discord and the power of quantum computation
- The elusive source of quantum effectiveness
- Generalized information theoretic measure to discern the quantumness of correlations
- Generation and detection of bound entanglement
- An introduction to many worlds in quantum computation
- On the Debate Concerning the Proper Characterisation of Quantum Dynamical Evolution
- Quantumness of correlations and entanglement
- Many Worlds, the Cluster-state Quantum Computer, and the Problem of the Preferred Basis
- On the Physical Explanation for Quantum Computational Speedup