Computational complexity theory is a branch of computer science dedicated to classifying computational problems in terms of their difficulty. While computability theory tells us what we can compute in principle, complexity theory informs us regarding our practical limits. In this chapter I argue that the science of \emph{quantum computing} illuminates complexity theory by emphasising that its fundamental concepts are not model-independent, but that this does not, as some suggest, force us to radically revise the foundations of the theory. For model-independence (...) never has been essential to those foundations. The fundamental aim of complexity theory is to describe what is achievable in practice under various models of computation for our various practical purposes. Reflecting on quantum computing illuminates complexity theory by reminding us of this, too often under-emphasised, fact. (shrink)

Combining physics, mathematics and computer science, quantum computing and its sister discipline of quantum information have developed in the past few decades from visionary ideas to two of the most fascinating areas of quantum theory. General interest and excitement in quantum computing was initially triggered by Peter Shor (1994) who showed how a quantum algorithm could exponentially “speed-up” classical computation and factor large numbers into primes far more efficiently than any (known) classical algorithm. Shor’s algorithm was soon followed by several (...) other algorithms that aimed to solve combinatorial and algebraic problems, and in the years since theoretical study of quantum systems serving as computational devices has achieved tremendous progress. Common belief has it that the implementation of Shor’s algorithm on a large scale quantum computer would have devastating consequences for current cryptography protocols which rely on the premise that all known classical worst-case algorithms for factoring take time exponential in the length of their input (see, e.g., Preskill 2005). Consequently, experimentalists around the world are engaged in attempts to tackle the technological difficulties that prevent the realisation of a large scale quantum computer. But regardless whether these technological problems can be overcome (Unruh 1995; Ekert and Jozsa 1996; Haroche and Raimond 1996), it is noteworthy that no proof exists yet for the general superiority of quantum computers over their classical counterparts. -/- The philosophical interest in quantum computing is manifold. From a social-historical perspective, quantum computing is a domain where experimentalists find themselves ahead of their fellow theorists. Indeed, quantum mysteries such as entanglement and nonlocality were historically considered a philosophical quibble, until physicists discovered that these mysteries might be harnessed to devise new efficient algorithms. But while the technology for harnessing the power of 50–100 qubits (the basic unit of information in the quantum computer) is now within reach (Preskill 2018), only a handful of quantum algorithms exist, and the question of whether these can truly outperform any conceivable classical alternative is still open. From a more philosophical perspective, advances in quantum computing may yield foundational benefits. For example, it may turn out that the technological capabilities that allow us to isolate quantum systems by shielding them from the effects of decoherence for a period of time long enough to manipulate them will also allow us to make progress in some fundamental problems in the foundations of quantum theory itself. Indeed, the development and the implementation of efficient quantum algorithms may help us understand better the border between classical and quantum physics (Cuffaro 2017, 2018a; cf. Pitowsky 1994, 100), and perhaps even illuminate fundamental concepts such as measurement and causality. Finally, the idea that abstract mathematical concepts such as computability and complexity may not only be translated into physics, but also re-written by physics bears directly on the autonomous character of computer science and the status of its theoretical entities—the so-called “computational kinds”. As such it is also relevant to the long-standing philosophical debate on the relationship between mathematics and the physical world. (shrink)

The aim of this paper is to address a particular interpretation of quantum computational processes, namely, the so called Many World Interpretation. I will show that if such an interpretation is supported by the Quantum Parallelism Thesis and the Physical Information Thesis at the same time, then it falls under circularity. I will suggest, in fact, that as long as this variation states both PIT and QPT cannot furnish a physical explanation of the latter unless it is already stating the (...) truth of MWI. This specific case suggests the more general conclusion that MWI and other accounts of quantum computational processes instill very different concepts of information. I will show that the concept instilled by MWI advocates is too abstract in order to be a reliable source for a physical interpretation of quantum computational processes. I will nevertheless then suggest that MWI is not completely useless for our understanding of quantum computation. (shrink)

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. (shrink)

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. (shrink)

I argue that the many worlds explanation of quantum computation is not licensed by, and in fact is conceptually inferior to, the many worlds interpretation of quantum mechanics from which it is derived. I argue that the many worlds explanation of quantum computation is incompatible with the recently developed cluster state model of quantum computation. Based on these considerations I conclude that we should reject the many worlds explanation of quantum computation.

The Many-Worlds Interpretation (MWI) is an approach to quantum mechanics according to which, in addition to the world we are aware of directly, there are many other similar worlds which exist in parallel at the same space and time. The existence of the other worlds makes it possible to remove randomness and action at a distance from quantum theory and thus from all physics.