paper

On the Physical Explanation for Quantum Computational Speedup

arXiv:1304.0208

Abstract

The aim of this dissertation is to clarify the debate over the explanation of quantum speedup and to submit a tentative resolution to it. In particular, I argue 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. Chapter 2 begins with a discussion of the most popular of the candidate physical explanations for quantum speedup: the many worlds explanation. I argue that unlike the neo-Everettian interpretation of quantum mechanics it does not have the conceptual resources required to overcome the `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.

Ph.D. Thesis submitted Winter Term 2013 at the University of Western Ontario. NOTE: because it has been compiled from source on the arXiv, this version has some very slight pagination differences as compared with the published version (http://ir.lib.uwo.ca/etd/1142/). However there are no differences in content whatsoever

References in corpus (43)

Cited by in corpus (2)