Dissertation, The University of Western Ontario (2013)

Michael Cuffaro
Ludwig Maximilians Universität, München
The aim of this dissertation is to clarify the debate over the explanation of quantum speedup and to submit, for the reader's consideration, a tentative resolution to it. In particular, I argue, in this dissertation, that the physical explanation for quantum speedup is precisely the fact that the phenomenon of quantum entanglement enables a quantum computer to fully exploit the representational capacity of Hilbert space. This is impossible for classical systems, joint states of which must always be representable as product states. I begin the dissertation by considering, in Chapter 2, the most popular of the candidate physical explanations for quantum speedup: the many worlds explanation of quantum computation. I argue that, although it is inspired by the neo-Everettian interpretation of quantum mechanics, unlike the latter it does not have the conceptual resources required to overcome objections such as the so-called `preferred basis objection'. I further argue that the many worlds explanation, at best, can serve as a good description of the physical process which takes place in so-called network-based computation, but that it is incompatible with other models of computation such as cluster state quantum computing. I next consider, in Chapter 3, a common component of most other candidate explanations of quantum speedup: quantum entanglement. I investigate whether entanglement can be said to be a necessary component of any explanation for quantum speedup, and I consider two major purported counter-examples to this claim. I argue that neither of these, in fact, show that entanglement is unnecessary for speedup, and that, on the contrary, we should conclude that it is. In Chapters 4 and 5 I then ask whether entanglement can be said to be sufficient as well. In Chapter 4 I argue that despite a result that seems to indicate the contrary, entanglement, considered as a resource, can be seen as sufficient to enable quantum speedup. Finally, in Chapter 5 I argue that entanglement is sufficient to explain quantum speedup as well.
Keywords quantum computing  quantum information  many worlds interpretation  entanglement  Bell's theorem  Gottesman-Knill theorem  quantum-classical divide  scientific explanation
Categories (categorize this paper)
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

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

References found in this work BETA

The Scientific Image.William Demopoulos & Bas C. van Fraassen - 1982 - Philosophical Review 91 (4):603.
Studies in the Logic of Explanation.Carl Gustav Hempel & Paul Oppenheim - 1948 - Philosophy of Science 15 (2):135-175.
The Scientific Image.Michael Friedman - 1982 - Journal of Philosophy 79 (5):274-283.
On Computable Numbers, with an Application to the N Tscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.

View all 75 references / Add more references

Citations of this work BETA

On the Significance of the Gottesman–Knill Theorem.Michael E. Cuffaro - 2017 - British Journal for the Philosophy of Science 68 (1):91-121.

Add more citations

Similar books and articles

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.
Explanation, Emergence, and Quantum Entanglement.Andreas Hüttemann - 2005 - Philosophy of Science 72 (1):114-127.
The Elusive Source of Quantum Speedup.Vlatko Vedral - 2010 - Foundations of Physics 40 (8):1141-1154.
Do We Really Understand Quantum Mechanics?Franck Laloë - 2012 - Cambridge University Press.
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.
Quantum Gravity on a Quantum Computer?Achim Kempf - 2014 - Foundations of Physics 44 (5):472-482.
Quantum Mechanics and Computation.Bart D’Hooghe & Jaroslaw Pykacz - 2004 - Foundations of Science 9 (4):387-404.
The Many‐Worlds Interpretation and Quantum Computation.Armond Duwell - 2007 - Philosophy of Science 74 (5):1007-1018.
Quantum Communication Complexity.Gilles Brassard - 2003 - Foundations of Physics 33 (11):1593-1616.


Added to PP index

Total views
147 ( #78,565 of 2,499,401 )

Recent downloads (6 months)
8 ( #89,651 of 2,499,401 )

How can I increase my downloads?


My notes