  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.
