Michael Cuffaro

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.

Wittgenstein did not write very much on the topic of probability. The little we have comes from a few short pages of the Tractatus, some 'remarks' from the 1930s, and the informal conversations which went on during that decade with the Vienna Circle. Nevertheless, Wittgenstein's views were highly influential in the later development of the logical theory of probability. This paper will attempt to clarify and defend Wittgenstein's conception of probability against some oft-cited criticisms that stem from a misunderstanding of his views. Max Black, for instance, criticises Wittgenstein for formulating a theory of probability that is capable of being used only against the backdrop of the ideal language of the Tractatus. I argue that on the contrary, by appealing to the 'hypothetical laws of nature', Wittgenstein is able to make sense of probability statements involving propositions that have not been completely analysed. G.H. von Wright criticises Wittgenstein's characterisation of these very hypothetical laws. He argues that by introducing them Wittgenstein makes what is distinctive about his theory superfluous, for the hypothetical laws are directly inspired by statistical observations and hence these observations indirectly determine the mechanism by which the logical theory of probability operates. I argue that this is not the case at all, and that while statistical observations play a part in the formation of the hypothetical laws, these observations are only necessary, but not sufficient conditions for the introduction of these hypotheses.

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.

I argue that Kant's and Frege's refutations of the ontological argument are more similar than has generally been acknowledged. As I clarify, for both Kant and Frege, to say that something exists is to assert of a concept that it is instantiated. With such an assertion one expresses that there is a particular relation between the instantiating object and a rational subject - a particular mode of presentation for the object in question. By its very nature such a relation cannot be the property of an object and thus cannot be included in the concept of that object. Thus the ontological argument, which takes existence to be a part of the concept of the supreme being, cannot, according to Kant and Frege, succeed. A secondary goal of the paper is to illuminate what I take to be an important affinity between Kant's and Frege's views more generally: that Frege's fundamental distinction between the sense and the referent of a proposition echoes, in an important way, Kant's distinction between concepts and the formal principles for their application to experience.

A growing number of commentators have, in recent years, noted the important affinities in the views of Immanuel Kant and Niels Bohr. While these commentators are correct, the picture they present of the connections between Bohr and Kant is painted in broad strokes; it is open to the criticism that these affinities are merely superficial. In this essay, I provide a closer, structural, analysis of both Bohr's and Kant's views that makes these connections more explicit. In particular, I demonstrate the similarities between Bohr's argument, on the one hand, that neither the wave nor the particle description of atomic phenomena pick out an object in the ordinary sense of the word, and Kant's requirement, on the other hand, that both ‘mathematical’ (having to do with magnitude) and ‘dynamical’ (having to do with an object's interaction with other objects) principles must be applicable to appearances in order for us to determine them as objects of experience. I argue that Bohr's ‘complementarity interpretation’ of quantum mechanics, which views atomic objects as idealizations, and which licenses the repeal of the principle of causality for the domain of atomic physics, is perfectly compatible with, and indeed follows naturally from a broadly Kantian epistemological framework.

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.

Kant's arguments for the synthetic a priori status of geometry are generally taken to have been refuted by the development of non-Euclidean geometries. Recently, however, some philosophers have argued that, on the contrary, the development of non-Euclidean geometry has confirmed Kant's views, for since a demonstration of the consistency of non-Euclidean geometry depends on a demonstration of its equi-consistency with Euclidean geometry, one need only show that the axioms of Euclidean geometry have 'intuitive content' in order to show that both Euclidean and non-Euclidean geometry are bodies of synthetic a priori truths. Michael Friedman has argued that this defence presumes a polyadic conception of logic that was foreign to Kant. According to Friedman, Kant held that geometrical reasoning itself relies essentially on intuition, and that this precludes the very possibility of non-Euclidean geometry. While Friedman's characterization of Kant's views on geometrical reasoning is correct, I argue that Friedman's conclusion that non-Euclidean geometries are logically impossible for Kant is not. I argue that Kant is best understood as a proto-constructivist and that modern constructive axiomatizations (unlike Hilbert-style axiomatizations) of both Euclidean and non-Euclidean geometry capture Kant's views on the essentially constructive nature of geometrical reasoning well.

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.