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)

Whilst a straightforward consequence of the formalism of non-relativistic quantum mechanics, the phenomenon of quantum teleportation has given rise to considerable puzzlement. In this paper, the teleportation protocol is reviewed and these puzzles dispelled. It is suggested that they arise from two primary sources: (1) the familiar error of hypostatizing an abstract noun (in this case, ‘information’) and (2) failure to differentiate interpretation dependent from interpretation independent features of quantum mechanics. A subsidiary source of error, the simulation fallacy, is also (...) identified. The resolution presented of the puzzles of teleportation illustrates the benefits of paying due attention to the logical status of ‘information’ as an abstract noun. Introduction The quantum teleportation protocol 2.1 Some information-theoretic aspects of teleportation 2.1.1 Preamble 2.1.2Application to teleportation The puzzles of teleportation Resolving (dissolving) the problem 4.1 The simulation fallacy The teleportation process under different interpretations 5.1 Collapse interpretations:Dirac/von Neumann, GRW 5.2 No collapse and no extra values: Everett 5.3 No collapse, but extra values: Bohm 5.3.1 A note on active information 5.4 Ensemble and statistical viewpoints Concluding remarks. (shrink)

I argue that although Ockham’s Razor (OR) has its origins in a-priorist ontological mandates according to the purposes of natural theology and natural philosophy as influenced by it, the principle has taken on significant empirical and contingent materialist connotations and conceptual content since the scientific revolution. I briefly discuss the pluralism of the concept of OR historically and in contemporary science and philosophy. I then attempt to align scientific metaphysics with contemporary conceptions of OR, and to demonstrate that ontic parsimony (...) is an indispensable element of scientific (contingent and anti-a-priorist) metaphysics. I then further deploy that scientific metaphysics to propose a contingently grounded semi-formal approach, with set theoretic features, and then with information theoretic features, to provide a way of assessing when a scientific theory and its ontology are aligned with OR appropriately in the context of the proposed scientific metaphysics. (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)

The interpretation of quantum mechanics is an area of increasing interest to many working physicists. In particular, interest has come from those involved in quantum computing and information theory, as there has always been a strong foundational element in this field. This paper introduces one interpretation of quantum mechanics, a modern ‘many-worlds’ theory, from the perspective of quantum computation. Reasons for seeking to interpret quantum mechanics are discussed, then the specific ‘neo-Everettian’ theory is introduced and its claim as the best (...) available interpretation defended. The main objections to the interpretation, including the so-called “problem of probability” are shown to fail. The local nature of the interpretation is demonstrated, and the implications of this both for the interpretation and for quantum mechanics more generally are discussed. Finally, the consequences of the theory for quantum computation are investigated, and common objections to using many worlds to describe quantum computing are answered. We find that using this particular many-worlds theory as a physical foundation for quantum computation gives several distinct advantages over other interpretations, and over not interpreting quantum theory at all. (shrink)

According to the Gottesman–Knill theorem, quantum algorithms that utilize only the operations belonging to a certain restricted set are efficiently simulable classically. Since some of the operations in this set generate entangled states, it is commonly concluded that entanglement is insufficient to enable quantum computers to outperform classical computers. I argue in this article that this conclusion is misleading. First, the statement of the theorem is, on reflection, already evident when we consider Bell’s and related inequalities in the context of (...) a discussion of computational machines. This, in turn, helps us to understand that the appropriate conclusion to draw from the Gottesman–Knill theorem is not that entanglement is insufficient to enable a quantum performance advantage, but rather that if we limit ourselves to the operations referred to in the Gottesman–Knill theorem, we will not have used the resources provided by an entangled quantum system to their full potential. (shrink)

Christopher G. Timpson provides the first full-length philosophical treatment of quantum information theory and the questions it raises for our understanding of the quantum world. He argues for an ontologically deflationary account of the nature of quantum information, which is grounded in a revisionary analysis of the concepts of information.

Quantum Information Theory and the Foundations of Quantum Mechanics is a conceptual analysis of one of the most prominent and exciting new areas of physics, providing the first full-length philosophical treatment of quantum information theory and the questions it raises for our understanding of the quantum world. -/- Beginning from a careful, revisionary, analysis of the concepts of information in the everyday and classical information-theory settings, Christopher G. Timpson argues for an ontologically deflationary account of the nature of quantum information. (...) Against what many have supposed, quantum information can be clearly defined (it is not a primitive or vague notion) but it is not part of the material contents of the world. Timpson's account sheds light on the nature of nonlocality and information flow in the presence of entanglement and, in particular, dissolves puzzles surrounding the remarkable process of quantum teleportation. In addition it permits a clear view of what the ontological and methodological lessons provided by quantum information theory are; lessons which bear on the gripping question of what role a concept like information has to play in fundamental physics. Topics discussed include the slogan 'Information is Physical', the prospects for an informational immaterialism (the view that information rather than matter might fundamentally constitute the world), and the status of the Church-Turing hypothesis in light of quantum computation. -/- With a clear grasp of the concept of information in hand, Timpson turns his attention to the pressing question of whether advances in quantum information theory pave the way for the resolution of the traditional conceptual problems of quantum mechanics: the deep problems which loom over measurement, nonlocality and the general nature of quantum ontology. He marks out a number of common pitfalls to be avoided before analysing in detail some concrete proposals, including the radical quantum Bayesian programme of Caves, Fuchs, and Schack. One central moral which is drawn is that, for all the interest that the quantum information-inspired approaches hold, no cheap resolutions to the traditional problems of quantum mechanics are to be had. (shrink)

In this paper we attempt to consider quantum superpositions from the perspective of the logos categorical approach presented in [26]. We will argue that our approach allows us not only to better visualize the structural features of quantum superpositions providing an anschaulich content to all terms, but also to restore —through the intensive valuation of graphs and the notion of immanent power— an objective representation of what QM is really talking about. In particular, we will discuss how superpositions relate to (...) some of the main features of the theory of quanta, namely, contextuality, paraconsistency, probability and measurement. (shrink)

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.

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 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)

The objective of this thesis is to present a naturalised metaphysics of information, or to naturalise information, by way of deploying a scientific metaphysics according to which contingency is privileged and a-priori conceptual analysis is excluded (or at least greatly diminished) in favour of contingent and defeasible metaphysics. The ontology of information is established according to the premises and mandate of the scientific metaphysics by inference to the best explanation, and in accordance with the idea that the primacy of physics (...) constraint accommodates defeasibility of theorising in physics. This metametaphysical approach is used to establish a field ontology as a basis for an informational structural realism. This is in turn, in combination with information theory and specifically mathematical and algorithmic theories of information, becomes the foundation of what will be called a source ontology, according to which the world is the totality of information sources. Information sources are to be understood as causally induced configurations of structure that are, or else reduce to and/or supervene upon, bounded (including distributed and non-contiguous) regions of the heterogeneous quantum field (all quantum fields combined) and fluctuating vacuum, all in accordance with the above-mentioned quantum field-ontic informational structural realism (FOSIR.) Arguments are presented for realism, physicalism, and reductionism about information on the basis of the stated contingent scientific metaphysics. In terms of philosophical argumentation, realism about information is argued for primarily by way of an indispensability argument that defers to the practice of scientists and regards concepts of information as just as indispensable in their theories as contingent representations of structure. Physicalism and reductionism about information are adduced by way of the identity thesis that identifies the substance of the structure of ontic structural realism as identical to selections of structure existing in re to combined heterogeneous quantum fields, and to the total heterogeneous quantum field comprised of all such fields. Adjunctly, an informational statement of physicalism is arrived at, and a theory of semantic information is proposed, according to which information is intrinsically semantic and alethically neutral. (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)