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)

This article defends a modest version of the Physical Church-Turing thesis (CT). Following an established recent trend, I distinguish between what I call Mathematical CT—the thesis supported by the original arguments for CT—and Physical CT. I then distinguish between bold formulations of Physical CT, according to which any physical process—anything doable by a physical system—is computable by a Turing machine, and modest formulations, according to which any function that is computable by a physical system is computable by a Turing machine. (...) I argue that Bold Physical CT is not relevant to the epistemological concerns that motivate CT and hence not suitable as a physical analog of Mathematical CT. The correct physical analog of Mathematical CT is Modest Physical CT. I propose to explicate the notion of physical computability in terms of a usability constraint, according to which for a process to count as relevant to Physical CT, it must be usable by a finite observer to obtain the desired values of a function. Finally, I suggest that proposed counterexamples to Physical CT are still far from falsifying it because they have not been shown to satisfy the usability constraint. (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)

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)

A version of the Church-Turing Thesis states that every effectively realizable physical system can be simulated by Turing Machines (‘Thesis P’). In this formulation the Thesis appears to be an empirical hypothesis, subject to physical falsification. We review the main approaches to computation beyond Turing definability (‘hypercomputation’): supertask, non-well-founded, analog, quantum, and retrocausal computation. The conclusions are that these models reduce to supertasks, i.e. infinite computation, and that even supertasks are no solution for recursive incomputability. This yields that the realization (...) of hypercomputing devices is implausible, and that Thesis P is not essentially different from the standard Church-Turing Thesis. (shrink)

I argue that our judgements regarding the locally causal models that are compatible with a given constraint implicitly depend, in part, on the context of inquiry. It follows from this that certain quantum no-go theorems, which are particularly striking in the traditional foundational context, have no force when the context switches to a discussion of the physical systems we are capable of building with the aim of classically reproducing quantum statistics. I close with a general discussion of the possible implications (...) of this for our understanding of the limits of classical description, and for our understanding of the fundamental aim of physical investigation. _1_ Introduction _2_ No-Go Results _2.1_ The CHSH inequality _2.2_ The GHZ equality _3_ Classically Simulating Quantum Statistics _3.1_ GHZ statistics _3.2_ Singlet statistics _4_ What Is a Classical Computer Simulation? _5_ Comparing the All-or-Nothing GHZ with Statistical equalities _6_ General Discussion _7_ Conclusion. (shrink)

I discuss the philosophical implications that the rising new science of quantum computing may have on the philosophy of computer science. While quantum algorithms leave the notion of Turing-Computability intact, they may re-describe the abstract space of computational complexity theory hence militate against the autonomous character of some of the concepts and categories of computer science.

A recent attempt to compute a (recursion‐theoretic) noncomputable function using the quantum adiabatic algorithm is criticized and found wanting. Quantum algorithms may outperform classical algorithms in some cases, but so far they retain the classical (recursion‐theoretic) notion of computability. A speculation is then offered as to where the putative power of quantum computers may come from.

Within the current mainstream research in the foundations of physics, much attention has been turned to the program of Axiomatic Reconstruction of Quantum Theory in terms of Information-Theoretic principles (ARQIT). ARQIT aims at finding a few general information-theoretic principles from which, once translated into mathematical terms, one can formally derive the structure of quantum theory. This chapter explores the role of mechanistic explanations and mathematical explanations (in particular, structural explanations) within ARQIT. With such considerations as a point of departure, we (...) investigate how ARQIT contributes to the explanation of quantum phenomena, and the possible prospects for explanations provided by mechanical interpretations of quantum theory. (shrink)

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)

The principle of 'information causality' can be used to derive an upper bound---known as the 'Tsirelson bound'---on the strength of quantum mechanical correlations, and has been conjectured to be a foundational principle of nature. In this paper, however, I argue that the principle has not to date been sufficiently motivated to play this role; the motivations that have so far been given are either unsatisfactorily vague or else amount to little more than an appeal to intuition. I then consider how (...) one might begin to successfully motivate the principle. I argue that a compelling way of so doing is to understand it as a generalisation of Einstein's principle of the mutually independent existence---the 'being-thus'---of spatially distant things, interpreted as a special methodological principle. More specifically: I describe an argument, due to Demopoulos, to the effect that the quantum-mechanical no-signalling condition can be viewed as a generalisation, appropriate to an irreducibly statistical theory such as quantum mechanics, of the Einsteinian principle. And I then argue that a compelling way to motivate information causality is to in turn consider it as a further generalisation of the Einsteinian principle that is appropriate to a theory of communication. I nevertheless describe important obstacles that must yet be overcome if the project of establishing information causality as a foundational principle of nature is to succeed. (shrink)

In quantum computing, where algorithms exist that can solve computational problems more efficiently than any known classical algorithms, the elimination of errors that result from external disturbances or from imperfect gates has become the ...

Quantum computers are hypothetical quantum information processing (QIP) devices that allow one to store, manipulate, and extract information while harnessing quantum physics to solve various computational problems and do so putatively more efficiently than any known classical counterpart. Despite many ‘proofs of concept’ (Aharonov and Ben–Or 1996; Knill and Laflamme 1996; Knill et al. 1996; Knill et al. 1998) the key obstacle in realizing these powerful machines remains their scalability and susceptibility to noise: almost three decades after their conceptions, experimentalists (...) still struggle to maintain useful quantum coherence in QIP devices with more than a pair of qubits (e.g., Blatt and Wineland 2008). This slow progress has prompted debates on the feasibility of quantum computers, yet the quantum information community has dismissed the skepticism as “ideology” (Aaronson 2004), claiming that the obstacles are merely technological (Kaye et al. 2007, 240). In a recent paper (Hagar 2009) I’ve argued that such a skepticism with respect to the feasibility of quantum computers need not be deemed ideological at all, and that the aforementioned ‘proofs of concept’ are physically suspect. Using analogies from the foundations of classical statistical mechanics (SM), I’ve also argued that instead of active error correction, the appropriate framework for debating the feasibility of large–scale, fault–tolerant and computationally superior quantum computers should be the project of error avoidance: rather than trying to constantly ‘cool down’ the QIP device and prevent its thermalization, one should try to locate those regions in the device’s state space which are thermodynamically ‘abnormal’, i.e., those regions in the device’s state space which resist thermalization regardless of external noise. This paper is intended as a further contribution to the debate on the feasibility of large–scale, fault–tolerant and computationally superior quantum computers. Relying again on analogies from the foundations of classical SM, it suggests a skeptical conjecture and frames it in the ‘passive’, error avoidance, context.. (shrink)

Although the formalizations of computability provided in the 1930s have proven to be equivalent, two different accounts of computability may be distinguished regarding computability as an epistemic concept. While computability, according to the epistemic account, should be based on epistemic constraints related to the capacities of human computers, the non-epistemic account considers computability as based on manipulations of symbols that require no human capacities other than the capacity of manipulating symbols according to a set of rules. In this paper, I (...) shall evaluate, both from a logical and physical point of view, whether computability should be regarded as an epistemic concept, i.e., whether epistemic constraints should be added on computability for considering functions as computable. Specifically, I shall argue that the introduction of epistemic constraints have deep implications for the set of computable functions, for the logical and physical Church-Turing thesis—cornerstones of logical and physical computability respectively—might turn out to be false according to which epistemic constraints are accepted. (shrink)