On the Necessity of Entanglement for the Explanation of Quantum Speedup

Michael Cuffaro
University of Western Ontario
Of the many and varied applications of quantum information theory, perhaps the most fascinating is the sub-field of quantum computation. In this sub-field, computational algorithms are designed which utilise the resources available in quantum systems in order to compute solutions to computational problems with, in some cases, exponentially fewer resources than any known classical algorithm. While the fact of quantum computational speedup is almost beyond doubt, the source of quantum speedup is still a matter of debate. 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 Cleve et al.'s solution to Deutsch's problem, Biham et al.'s mixed-state version of the Deutsch-Jozsa algorithm, and Knill & Laflamme's deterministic quantum computation with one qubit 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.
Keywords Entanglement  Quantum Computation  Quantum Information  Quantum Speedup
Categories (categorize this paper)
Reprint years 2011
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 40,000
Through your library

References found in this work BETA

View all 37 references / Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

On the Physical Explanation for Quantum Computational Speedup.Michael E. Cuffaro - 2013 - Dissertation, The University of Western Ontario
The Elusive Source of Quantum Speedup.Vlatko Vedral - 2010 - Foundations of Physics 40 (8):1141-1154.
Explanation, Emergence, and Quantum Entanglement.Andreas Hüttemann - 2005 - Philosophy of Science 72 (1):114-127.
Quantum Teleportation.H. J. Kimble - 1999 - Vienna Circle Institute Yearbook 7:141-146.
Quantum Mechanics and Computation.Bart D’Hooghe & Jaroslaw Pykacz - 2004 - Foundations of Science 9 (4):387-404.
A Quantum Computer Only Needs One Universe.A. M. Steane - 2003 - Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics 34 (3):469-478.
The Many‐Worlds Interpretation and Quantum Computation.Armond Duwell - 2007 - Philosophy of Science 74 (5):1007-1018.
Many Worlds, the Cluster-State Quantum Computer, and the Problem of the Preferred Basis.Michael E. Cuffaro - 2012 - Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics 43 (1):35-42.
Quantum Computation and Pseudotelepathic Games.Jeffrey Bub - 2008 - Philosophy of Science 75 (4):458-472.
The Subtleties of Entanglement and its Role in Quantum Information Theory.Rob Clifton - 2001 - Proceedings of the Philosophy of Science Association 2002 (3):S150-S167.
The Entanglement Structure of Quantum Field Systems.Vincent Lam - 2013 - International Studies in the Philosophy of Science 27 (1):59 - 72.
Quantum Repeaters for Quantum Communication.H. J. Briegel, J. I. Cirac, W. Dür, G. Giedke & P. Zoller - 1999 - Vienna Circle Institute Yearbook 7:147-154.


Added to PP index

Total views
166 ( #41,039 of 2,236,200 )

Recent downloads (6 months)
2 ( #765,248 of 2,236,200 )

How can I increase my downloads?


My notes

Sign in to use this feature