On the Necessity of Entanglement for the Explanation of Quantum Speedup

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.

Many clarificatory changes, and improved argumentation. Comments and criticisms are still welcome

References in corpus (12)

• Quantum discord and the power of one qubit
• Quantum information can be negative
• Interpreting quantum discord through quantum state merging
• Operational interpretations of quantum discord
• Characterizing quantum theory in terms of information-theoretic constraints
• Conservation law for distributed entanglement of formation and quantum discord
• Entanglement, discord and the power of quantum computation
• Generalized information theoretic measure to discern the quantumness of correlations
• 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