This paper explores the difference between Connectionist proposals for cognitive a r c h i t e c t u r e a n d t h e s o r t s o f m o d e l s t hat have traditionally been assum e d i n c o g n i t i v e s c i e n c e . W e c l a i m t h a t t h (...) e m a j o r d i s t i n c t i o n i s t h a t , w h i l e b o t h Connectionist and Classical architectures postulate representational mental states, the latter but not the former are committed to a symbol-level of representation, or to a ‘language of thought’: i.e., to representational states that have combinatorial syntactic and semantic structure. Several arguments for combinatorial structure in mental representations are then reviewed. These include arguments based on the ‘systematicity’ of mental representation: i.e., on the fact that cognitive capacities always exhibit certain symmetries, so that the ability to entertain a given thought implies the ability to entertain thoughts with semantically related contents. We claim that such arguments make a powerful case that mind/brain architecture is not Connectionist at the cognitive level. We then consider the possibility that Connectionism may provide an account of the neural (or ‘abstract neurological’) structures in which Classical cognitive architecture is implemented. We survey a n u m b e r o f t h e s t a n d a r d a r g u m e n t s t h a t h a v e b e e n o f f e r e d i n f a v o r o f Connectionism, and conclude that they are coherent only on this interpretation. (shrink)

David Wallace argues that we should take quantum theory seriously as an account of what the world is like--which means accepting the idea that the universe is constantly branching into new universes. He presents an accessible but rigorous account of the 'Everett interpretation', the best way to make coherent sense of quantum physics.

An extraordinary and challenging synthesis of ideas uniting Quantum Theory, and the theories of Computation, Knowledge and Evolution, Deutsch's extraordinary book explores the deep connections between these strands which reveal the fabric ...

This essay explains what the Causal Markov Condition says and defends the condition from the many criticisms that have been launched against it. Although we are skeptical about some of the applications of the Causal Markov Condition, we argue that it is implicit in the view that causes can be used to manipulate their effects and that it cannot be surrendered without surrendering this view of causation.

Relative to digital computation, analogue computation has been neglected in the philosophical literature. To the extent that attention has been paid to analogue computation, it has been misunderstood. The received view—that analogue computation has to do essentially with continuity—is simply wrong, as shown by careful attention to historical examples of discontinuous, discrete analogue computers. Instead of the received view, I develop an account of analogue computation in terms of a particular type of analogue representation that allows for discontinuity. This account (...) thus characterizes all types of analogue computation, whether continuous or discrete. Furthermore, the structure of this account can be generalized to other types of computation: analogue computation essentially involves analogue representation, whereas digital computation essentially involves digital representation. Besides being a necessary component of a complete philosophical understanding of computation in general, understanding analogue computation is important for computational explanation in contemporary neuroscience and cognitive science. (shrink)

We argue that the intractable part of the measurement problem -- the 'big' measurement problem -- is a pseudo-problem that depends for its legitimacy on the acceptance of two dogmas. The first dogma is John Bell's assertion that measurement should never be introduced as a primitive process in a fundamental mechanical theory like classical or quantum mechanics, but should always be open to a complete analysis, in principle, of how the individual outcomes come about dynamically. The second dogma is the (...) view that the quantum state has an ontological significance analogous to the significance of the classical state as the 'truthmaker' for propositions about the occurrence and non-occurrence of events, i.e., that the quantum state is a representation of physical reality. We show how both dogmas can be rejected in a realist information-theoretic interpretation of quantum mechanics as an alternative to the Everett interpretation. The Everettian, too, regards the 'big' measurement problem as a pseudo-problem, because the Everettian rejects the assumption that measurements have definite outcomes, in the sense that one particular outcome, as opposed to other possible outcomes, actually occurs in a quantum measurement process. By contrast with the Everettians, we accept that measurements have definite outcomes. By contrast with the Bohmians and the GRW 'collapse' theorists who add structure to the theory and propose dynamical solutions to the 'big' measurement problem, we take the problem to arise from the failure to see the significance of Hilbert space as a new kinematic framework for the physics of an indeterministic universe, in the sense that Hilbert space imposes kinematic objective probabilistic constraints on correlations between events. (shrink)

This book offers a thorough technical elaboration and philosophical defense of an objectivist informational interpretation of quantum mechanics according to which its novel content is located in its kinematical framework, that is, in how the theory describes systems independently of the specifics of their dynamics. -/- It will be of interest to researchers and students in the philosophy of physics and in theoretical physics with an interest in the foundations of quantum mechanics. Additionally, parts of the book may be used (...) as the basis for courses introducing non-physics majors to quantum mechanics, or for self-study by those outside of the university with an interest in quantum mechanics. (shrink)

We present a toy theory that is based on a simple principle: the number of questions about the physical state of a system that are answered must always be equal to the number that are unanswered in a state of maximal knowledge. Many quantum phenomena are found to have analogues within this toy theory. These include the noncommutativity of measurements, interference, the multiplicity of convex decompositions of a mixed state, the impossibility of discriminating nonorthogonal states, the impossibility of a universal (...) state inverter, the distinction between bipartite and tripartite entanglement, the monogamy of pure entanglement, no cloning, no broadcasting, remote steering, teleportation, entanglement swapping, dense coding, mutually unbiased bases, and many others. The diversity and quality of these analogies is taken as evidence for the view that quantum states are states of incomplete knowledge rather than states of reality. A consideration of the phenomena that the toy theory fails to reproduce, notably, violations of Bell inequalities and the existence of a Kochen-Specker theorem, provides clues for how to proceed with this research program. (shrink)

A survey of the field of hypercomputation, including discussion of a variety of objections.

Although computation and the science of physical systems would appear to be unrelated, there are a number of ways in which computational and physical concepts can be brought together in ways that illuminate both. This volume examines fundamental questions which connect scholars from both disciplines: is the universe a computer? Can a universal computing machine simulate every physical process? What is the source of the computational power of quantum computers? Are computational approaches to solving physical problems and paradoxes always fruitful? (...) Contributors from multiple perspectives reflecting the diversity of thought regarding these interconnections address many of the most important developments and debates within this exciting area of research. Both a reference to the state of the art and a valuable and accessible entry to interdisciplinary work, the volume will interest researchers and students working in physics, computer science, and philosophy of science and mathematics. (shrink)

One finds, in Maxwell's writings on thermodynamics and statistical physics, a conception of the nature of these subjects that differs in interesting ways from the way that they are usually conceived. In particular, though—in agreement with the currently accepted view—Maxwell maintains that the second law of thermodynamics, as originally conceived, cannot be strictly true, the replacement he proposes is different from the version accepted by most physicists today. The modification of the second law accepted by most physicists is a probabilistic (...) one: although statistical fluctuations will result in occasional spontaneous differences in temperature or pressure, there is no way to predictably and reliably harness these to produce large violations of the original version of the second law. Maxwell advocates a version of the second law that is strictly weaker; the validity of even this probabilistic version is of limited scope, limited to situations in which we are dealing with large numbers of molecules en masse and have no ability to manipulate individual molecules. Connected with this is his concept of the thermodynamic concepts of heat, work, and entropy; on the Maxwellian view, these are concepts that must be relativized to the means we have available for gathering information about and manipulating physical systems. The Maxwellian view is one that deserves serious consideration in discussions of the foundation of statistical mechanics. It has relevance for the project of recovering thermodynamics from statistical mechanics because, in such a project, it matters which version of the second law we are trying to recover. (shrink)

A true Turing machine requires an infinitely long paper tape. Thus a TM can be housed in the infinite world of Newtonian spacetime, but not necessarily in our world, because our world-at least according to our best spacetime theory, general relativity-may be finite. All the same, one can argue for the "existence" of a TM on the basis that there is no such housing problem in some other relativistic worlds that are similar to our world. But curiously enough-and this is (...) the main point of this paper-some of these close worlds have a special spacetime structure that allows TMs to perform certain Turing unsolvable tasks. For example, in one kind of spacetime a TM can be used to solve first-order predicate logic and the halting problem. And in a more complicated spacetime, TMs can be used to decide arithmetic. These new computers serve to show that Church's thesis is a thoroughly contingent claim. Moreover, since these new computers share the fundamental properties of a TM in ordinary operation, a computability theory based on these non-Turing computers is no less worthy of investigation than orthodox computability theory. Some ideas about this new mathematical theory are given. (shrink)

In this article we set out to understand the significance of the process matrix formalism and the quantum causal modelling programme for ongoing disputes about the role of causation in fundamental physics. We argue that the process matrix programme has correctly identified a notion of ‘causal order’ which plays an important role in fundamental physics, but this notion is weaker than the common-sense conception of causation because it does not involve asymmetry. We argue that causal order plays an important role (...) in grounding more familiar causal phenomena. Then we apply these conclusions to the causal modelling programme within quantum foundations, arguing that since no-signalling quantum correlations cannot exhibit causal order, they should not be analysed using classical causal models. This resolves an open question about how to interpret fine-tuning in classical causal models of no-signalling correlations. Finally we observe that a quantum generalization of causal modelling can play a similar functional role to standard causal reasoning, but we emphasize that this functional characterisation does not entail that quantum causal models offer novel explanations of quantum processes. (shrink)

We describe a possible physical device that computes a function that cannot be computed by a Turing machine. The device is physical in the sense that it is compatible with General Relativity. We discuss some objections, focusing on those which deny that the device is either a computer or computes a function that is not Turing computable. Finally, we argue that the existence of the device does not refute the Church–Turing thesis, but nevertheless may be a counterexample to Gandy's thesis.

Causal modelling provides a powerful set of tools for identifying causal structure from observed correlations. It is well known that such techniques fail for quantum systems, unless one introduces 'spooky' hidden mechanisms. Whether one can produce a genuinely quantum framework in order to discover causal structure remains an open question. Here we introduce a new framework for quantum causal modelling that allows for the discovery of causal structure. We define quantum analogues for core features of classical causal modelling techniques, including (...) the causal Markov condition and faithfulness. Based on the process matrix formalism, this framework naturally extends to generalised structures with indefinite causal order. (shrink)

Accelerating Turing machines have attracted much attention in the last decade or so. They have been described as “the work-horse of hypercomputation” (Potgieter and Rosinger 2010: 853). But do they really compute beyond the “Turing limit”—e.g., compute the halting function? We argue that the answer depends on what you mean by an accelerating Turing machine, on what you mean by computation, and even on what you mean by a Turing machine. We show first that in the current literature the term (...) “accelerating Turing machine” is used to refer to two very different species of accelerating machine, which we call end-stage-in and end-stage-out machines, respectively. We argue that end-stage-in accelerating machines are not Turing machines at all. We then present two differing conceptions of computation, the internal and the external, and introduce the notion of an epistemic embedding of a computation. We argue that no accelerating Turing machine computes the halting function in the internal sense. Finally, we distinguish between two very different conceptions of the Turing machine, the purist conception and the realist conception; and we argue that Turing himself was no subscriber to the purist conception. We conclude that under the realist conception, but not under the purist conception, an accelerating Turing machine is able to compute the halting function in the external sense. We adopt a relatively informal approach throughout, since we take the key issues to be philosophical rather than mathematical. (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)

I explore the reduction of thermodynamics to statistical mechanics by treating the former as a control theory: a theory of which transitions between states can be induced on a system by means of operations from a fixed list. I recover the results of standard thermodynamics in this framework on the assumption that the available operations do not include measurements which affect subsequent choices of operations. I then relax this assumption and use the framework to consider the vexed questions of Maxwell's (...) demon and Landauer's principle. Throughout I assume rather than prove the basic irreversibility features of statistical mechanics, taking care to distinguish them from the conceptually distinct assumptions of thermodynamics proper. (shrink)

The nature of quantum computation is discussed. It is argued that, in terms of the amount of information manipulated in a given time, quantum and classical computation are equally efficient. Quantum superposition does not permit quantum computers to ''perform many computations simultaneously'' except in a highly qualified and to some extent misleading sense. Quantum computation is therefore not well described by interpretations of quantum mechanics which invoke the concept of vast numbers of parallel universes. Rather, entanglement makes available types of (...) computation processes which, while not exponentially larger than classical ones, are unavailable to classical systems. The essence of quantum computation is that it uses entanglement to generate and manipulate a physical representation of the correlations between logical entities, without the need to completely represent the logical entities themselves. (shrink)

What is the relationship between, on the one hand, the sorts of causal claims found in the special sciences (and in common sense) and, on the other hand, the world as described by physics? A standard picture goes like this: the fundamental laws of physics are causal laws in the sense that they can be interpreted as telling us that realizations of one set of physical factors or properties “causes” realizations of other properties. Causal claims in the special sciences are (...) then true (to the extent that they are) in virtue of “instantiating” these underlying causal laws; as it is often put, the latter serve as “truth-makers” for the former. The picture is thus one according to which the notion of cause, as it occurs in the special sciences, is reflected or “grounded” in a fairly straightforward and transparent way in a similar notion that occurs in fundamental physics. This paper explores some alternatives to this picture. (shrink)

Recent suggestions to supply quantum mechanics (QM) with realistic foundations by reformulating it in light of quantum information theory (QIT) are examined and are found wanting by pointing to a basic conceptual problem that QIT itself ignores, namely, the measurement problem. Since one cannot ignore the measurement problem and at the same time pretend to be a realist, as they stand, the suggestions to reformulate QM in light of QIT are nothing but instrumentalism in disguise.

A primary goal of quantum computer science is to find an explanation for the fact that quantum computers are more powerful than classical computers. In this paper I argue that to answer this question is to compare algorithmic processes of various kinds and to describe the possibility spaces associated with these processes. By doing this, we explain how it is possible for one process to outperform its rival. Further, in this and similar examples little is gained in subsequently asking a (...) how-actually question. Once one has explained how-possibly, there is little left to do. (shrink)

From the philosopher’s perspective, the interest in quantum computation stems primarily from the way that it combines fundamental concepts from two distinct sciences: Physics, in particular Quantum Mechanics, and Computer Science, each long a subject of philosophical speculation and analysis in its own right. Quantum computing combines both of these more traditional areas of inquiry into one wholly new, if not quite independent, science. Over the course of this chapter we will be discussing some of the most important philosophical questions (...) that arise from this merger and philosophical lessons to be learned. (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)

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)

1. The Physical Church-Turing Thesis. Physicists often interpret the Church-Turing Thesis as saying something about the scope and limitations of physical computing machines. Although this was not the intention of Church or Turing, the Physical Church Turing thesis is interesting in its own right. Consider, for example, Wolfram’s formulation: One can expect in fact that universal computers are as powerful in their computational capabilities as any physically realizable system can be, that they can simulate any physical system . . . (...) No physically implementable procedure could then shortcut a computationally irreducible process. (Wolfram 1985) Wolfram’s thesis consists of two parts: (a) Any physical system can be simulated (to any degree of approximation) by a universal Turing machine (b) Complexity bounds on Turing machine simulations have physical significance. For example, suppose that the computation of the minimum energy of some system of n particles takes at least exponentially (in n) many steps. Then the relaxation time of the actual physical system to its minimum energy state will also take exponential time. (shrink)

We examine the interrelationships between analog computational modelling and analogue (physical) modelling. To this end, we attempt a regimentation of the informal distinction between analog and digital, which turns on the consideration of computing in a broader context. We argue that in doing so one comes to see that (scientific) computation is better conceptualised as an epistemic process relative to agents, wherein representations play a key role. We distinguish between two, conceptually distinct, kinds of representation that, we argue, are both (...) involved in each case of computing. Based on the semantic and syntactic properties of each of these representations, we put forward a new account of the distinction between analog and digital computing. We discuss how the developed account is able to explain various properties of different models of computation, and we finish by conceptually comparing analog computational modelling to analogue (scale) modelling. It is concluded that, contrary to the standard view, the two practices are orthogonal, differing both in their foundations and in the epistemic functions they fulfil. (shrink)

Wilfried Sieg and John Byrnes. AnModel for Parallel Computation: Gandy's Thesis.

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.

This book provides the first unified overview of the burgeoning research area at the interface between Quantum Foundations and Quantum Information. Topics include: operational alternatives to quantum theory, information-theoretic reconstructions of the quantum formalism, mathematical frameworks for operational theories, and device-independent features of the set of quantum correlations. Powered by the injection of fresh ideas from the field of Quantum Information and Computation, the foundations of Quantum Mechanics are in the midst of a renaissance. The last two decades have seen (...) an explosion of new results and research directions, attracting broad interest in the scientific community. The variety and number of different approaches, however, makes it challenging for a newcomer to obtain a big picture of the field and of its high-level goals. Here, fourteen original contributions from leading experts in the field cover some of the most promising research directions that have emerged in the new wave of quantum foundations. The book is directed at researchers in physics, computer science, and mathematics and would be appropriate as the basis of a graduate course in Quantum Foundations. (shrink)

I flesh out the sense in which the informational approach to interpreting quantum mechanics, as defended by Pitowsky and Bub and lately by a number of other authors, is (neo-)Bohrian. I argue that on this approach, quantum mechanics represents what Bohr called a “natural generalisation of the ordinary causal description” in the sense that the idea (which philosophers of science like Stein have argued for on the grounds of practical and epistemic necessity) that understanding a theory as a theory of (...) physics requires that one be able to “schematise the observer” within it is elevated in quantum mechanics to the level of a postulate in the sense that interpreting the outcome of a measurement interaction, as providing us with information about the world, requires as a matter of principle, the specification of a schematic representation of an observer in the form of a ‘Boolean frame’—the Boolean algebra representing the yes-or-no questions associated with a given observable representative of a given experimental context. I argue that the approach’s central concern is with the methodological question of how to assign physical properties to what one takes to be a system in a given experimental context, rather than the metaphysical question of what a given state vector represents independently of any context, and I show how the quantum generalisation of the concept of an open system may be used to assuage Einstein’s complaint that the orthodox approach to quantum mechanics runs afoul of the supposedly fundamental methodological requirement to the effect that one must always be able, according to Einstein, to treat spatially separated systems as isolated from one another. (shrink)

A remarkable theorem by Clifton, Bub and Halvorson (2003) (CBH) characterizes quantum theory in terms of information--theoretic principles. According to Bub (2004, 2005) the philosophical significance of the theorem is that quantum theory should be regarded as a ``principle'' theory about (quantum) information rather than a ``constructive'' theory about the dynamics of quantum systems. Here we criticize Bub's principle approach arguing that if the mathematical formalism of quantum mechanics remains intact then there is no escape route from solving the measurement (...) problem by constructive theories. We further propose a (Wigner--type) thought experiment that we argue demonstrates that quantum mechanics on the information--theoretic approach is incomplete. (shrink)

I examine the classical idea of ‘algorithm’ as a sequential, step-by-step, deterministic procedure (i.e., the idea of ‘algorithm’ that was already in use by the 1930s), with respect to three themes, its relation to the notion of an ‘effective procedure’, its different roles and uses in logic, computer science, and mathematics (focused on numerical analysis), and its different formal definitions proposed by practitioners in these areas. I argue that ‘algorithm’ has been conceptualized and used in contrasting ways in the above (...) areas, and discuss challenges and prospects for adopting a final foundational theory of (classical) ‘algorithms’. (shrink)

This book provides a general survey of the main concepts, questions and results that have been developed in the recent interactions between quantum information, quantum computation and logic. Divided into 10 chapters, the books starts with an introduction of the main concepts of the quantum-theoretic formalism used in quantum information. It then gives a synthetic presentation of the main “mathematical characters” of the quantum computational game: qubits, quregisters, mixtures of quregisters, quantum logical gates. Next, the book investigates the puzzling entanglement-phenomena (...) and logically analyses the Einstein–Podolsky–Rosen paradox and introduces the reader to quantum computational logics, and new forms of quantum logic. The middle chapters investigate the possibility of a quantum computational semantics for a language that can express sentences like “Alice knows that everybody knows that she is pretty”, explore the mathematical concept of quantum Turing machine, and illustrate some characteristic examples that arise in the framework of musical languages. The book concludes with an analysis of recent discussions, and contains a Mathematical Appendix which is a survey of the definitions of all main mathematical concepts used in the book. (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.

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.

Jeff Bub has developed an information-theoretic interpretation of quantum mechanics on the basis of the programme to reaxiomatise the theory in terms of information-theoretic principles. According to the most recent version of the interpretation, reaxiomatisation can dissolve some of the demands for explanation traditionally associated with the task of providing an interpretation for the theory. The key idea is that the real lesson we should take away from quantum mechanics is that the ‘structure of in- formation’ is not what we (...) thought it was. In particular a feature of the new structure is intrinsic randomness of measurement, which allegedly dissolves a significant part of the measurement problem. I argue that it is difficult to find an appropriate argument to support the claim that measurement is intrinsically random in the relevant sense. (shrink)

David Deutsch and others have suggested that the Many-Worlds Interpretation of quantum mechanics is the only interpretation capable of explaining the special efficiency quantum computers seem to enjoy over classical ones. I argue that this view is not tenable. Using a toy algorithm I show that the Many-Worlds Interpretation must crucially use the ontological status of the universal state vector to explain quantum computational efficiency, as opposed to the particular ontology of the MWI, that is, the computational histories of worlds. (...) As such, any other interpretation that treats the state vector as representing real ontological features of a system can explain quantum speedup too. ‡Thanks to Soazig Le Bihan for her critical comments on this paper. †To contact the author, please write to: Department of Philosophy, Liberal Arts 101, University of Montana, Missoula, MT 59812; e-mail: armond. duwell @umontana.edu. (shrink)

Quantum information theory has given rise to a renewed interest in, and a new perspective on, the old issue of understanding the ways in which quantum mechanics differs from classical mechanics. The task of distinguishing between quantum and classical theory is facilitated by neutral frameworks that embrace both classical and quantum theory. In this paper, I discuss two approaches to this endeavour, the algebraic approach, and the convex set approach, with an eye to the strengths of each, and the relations (...) between the two. I end with a discussion of one particular model, the toy theory devised by Rob Spekkens, which, with minor modifications, fits neatly within the convex sets framework, and which displays in an elegant manner some of the similarities and differences between classical and quantum theories. The conclusion suggested by this investigation is that Schrödinger was right to find the essential difference between classical and quantum theory in their handling of composite systems, though Schrödinger's contention that it is entanglement that is the distinctive feature of quantum mechanics needs to be modified. (shrink)

This book presents fresh insights into analogue quantum simulation. It argues that these simulations are a new instrument of science. They require a bespoke philosophical analysis, sensitive to both the similarities to and the differences with conventional scientific practices such as analogical argument, experimentation, and classical simulation. -/- The analysis situates the various forms of analogue quantum simulation on the methodological map of modern science. In doing so, it clarifies the functions that analogue quantum simulation serves in scientific practice. To (...) this end, the authors introduce a number of important terminological distinctions. They establish that analogue quantum ‘computation' and ‘emulation' are distinct scientific practices and lead to distinct forms of scientific understanding. The authors also demonstrate the normative value of the computation vs. emulation distinction at both an epistemic and a pragmatic level. -/- The volume features a range of detailed case studies focusing on: i) cold atom computation of many-body localisation and the Higgs mode; ii) photonic emulation of quantum effects in biological systems; and iii) emulation of Hawking radiation in dispersive optical media. Overall, readers will discover a normative framework to isolate and support the goals of scientists undertaking analogue quantum simulation and emulation. This framework will prove useful to both working scientists and philosophers of science interested in cutting-edge scientific practice. (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)

One might think that, once we know something is computable, how efficiently it can be computed is a practical question with little further philosophical importance. In this essay, I offer a detailed case that one would be wrong. In particular, I argue that computational complexity theory---the field that studies the resources needed to solve computational problems---leads to new perspectives on the nature of mathematical knowledge, the strong AI debate, computationalism, the problem of logical omniscience, Hume's problem of induction and Goodman's (...) grue riddle, the foundations of quantum mechanics, economic rationality, closed timelike curves, and several other topics of philosophical interest. I end by discussing aspects of complexity theory itself that could benefit from philosophical analysis. (shrink)