The report deals with the axiomatic approach to the phenomena of quantum computation and algorithms. It gives an overview of the classical approach (due to von Neumann) using the structures of Hilbert spaces, as well as mentions some major results in the field and discusses the flaws of the model and its current dominance. This leads to the introduction of a new axiomatization, first proposed by S. Abramsky and B. Coecke in 2007, which relies on the modern concepts of category theory. It is a field of mathematics originally created in the 1940s by specialists in algebraic topology but currently gaining popularity in other branches because of its abstract nature and emphasis on operations rather than objects. Most importantly, category theory is a powerful tool in functional analysis allowing mathematicians to reformulate the statements of Hilbert space theory in a more intuitive way, without matrix calculus. Finally, the logic behind quantum operations is discussed: it is revealed that the ideas of quantum algorithms have a strong connection to Jean-Yves Girard’s linear logic.
The report deals with the axiomatic approach to the phenomena of quantum computation and algorithms. It gives an overview of the classical approach (due to von Neumann) using the structures of Hilbert spaces, as well as mentions some major results in the field and discusses the flaws of the model and its current dominance. This leads to the introduction of a new axiomatization, first proposed by S. Abramsky and B. Coecke in 2007, which relies on the modern concepts of category theory. It is a field of mathematics originally created in the 1940s by specialists in algebraic topology but currently gaining popularity in other branches because of its abstract nature and emphasis on operations rather than objects. Most importantly, category theory is a powerful tool in functional analysis allowing mathematicians to reformulate the statements of Hilbert space theory in a more intuitive way, without matrix calculus. Finally, the logic behind quantum operations is discussed: it is revealed that the ideas of quantum algorithms have a strong connection to Jean-Yves Girard’s linear logic.
Quantum computation is a sub-discipline of computer science that studies computation performed using quantum-mechanical phenomena such as entanglement and the principle of quantum superposition. The work presented in this dissertation is part of a program of research initiated by S. Abramsky and B. Coecke that aims to establish a categorical foundation for quantum computation.
The usual axiomatisation of quantum computation uses the biproduct structure to express the classical fragment of the theory that comprises, for instance, the result of a measurement or classical control. Following the work of S. Abramsky and B. Coecke, that of P. Selinger for the quantum aspect, and that of B. Coecke and D. Pavlovic for the classical aspect, we will introduce a complete categorical semantics for quantum computation that includes bath the classical and the quantum fragments of the theory. In order to do so, we will introduce the notion of classical-quantum interface, which is sufficiently general to include the two fragments of the theory. Moreover, the classical fragment will be axiomatised exclusively with respect to the tensorial structure, i.e., without using biproducts. In particular, such an approach enables the use of an intuitive and rigorous graphical calculus as a proof technique which is often easier to use than the usual algebraic techniques. Moreover, we will see that the axiomatisation of basis structures from which is derived the notion of classical transformation also enables the definition of many families of classical transformations such as relations, functions, bijections, and stochastic and bistochastic transformations; the latter three being especially suitable in the context of quantum computation. Finally, we will present some quantum protocols and prove some results concerning these, using a graphical calculus developed for the categorical semantics in order to illustrates the usefulness and the well-foundedness of the theory.
Key words: Quantum computation. Classical control. Category theory. Compact closed categories. †-monoidal categories. †-compact categories. Classical-quantum interfaces.
Abstract Monoidal category theory serves as a powerful framework for describing logical aspects of quantum theory, giving an abstract language for parallel and sequential composition and a conceptual way to understand many high-level quantum phenomena. Here, we lay the foundations for this categorical quantum mechanics, with an emphasis on the graphical calculus that makes computation intuitive. We describe superposition and entanglement using biproducts and dual objects, and show how quantum teleportation can be studied abstractly using these structures. We investigate monoids, Frobenius structures and Hopf algebras, showing how they can be used to model classical information and complementary observables. We describe the CP construction, a categorical tool to describe probabilistic quantum systems. The last chapter introduces higher categories, surface diagrams and 2-Hilbert spaces, and shows how the language of duality in monoidal 2-categories can be used to reason about quantum protocols, including quantum teleportation and dense coding. Previous knowledge of linear algebra, quantum information or category theory would give an ideal background for studying this text, but it is not assumed, with essential background material given in a self-contained introductory chapter. Throughout the text, we point out links with many other areas, such as representation theory, topology, quantum algebra, knot theory and probability theory, and present nonstandard models including sets and relations. All results are stated rigorously and full proofs are given as far as possible, making this book an invaluable reference for modern techniques in quantum logic, with much of the material not available in any other textbook.
This thesis is a study of the construction and representation of typed models of quantum mechanics for use in quantum computation. We introduce logical and graphical syntax for quantum mechanical processes and prove that these formal systems provide sound and complete representations of abstract quantum mechanics. In addition, we demonstrate how these representations may be used to reason about the behaviour of quantum computational processes. Quantum computation is presently mired in low-level formalisms, mostly derived directly from matrices over Hilbert spaces. These formalisms are an obstacle to the full understanding and exploitation of quantum effects in informatics since they obscure the essential structure of quantum states and processes. The aim of this work is to introduce higher level tools for quantum mechanics which will be better suited to computation than those presently employed in the field. Inessential details of Hilbert space representations are removed and the informatic structures are presented directly. Entangled states are particularly important in this treatment, as is appropriate, since entanglement is a fundamental driver of quantum computation. The benefits two-fold: as well as producing foundational tools for the study of quantum computation this work also connects quantum mechanics to mainstream areas of computer science such as categorical logic, type theory, program language semantics, and rewriting. We describe, following Abramsky and Coecke, how quantum mechanics may be carried out without reference to Hilbert space, in a strongly compact closed category. In particular we show how to freely construct a categorical model of abstract quantum mechanics from an arbitrary category. We introduceMultiplicative Categorical Quantum Logic (mCQL), a sequent calculus whose proof rules capture the structure of compact closed categories. This sequent calculus is interpreted in a freely generated compact closed category, and its semantics is sound with respect to cut elimination. We define an equivalent graphical syntax, similar to linear logic’s proof-nets, and prove that these proof-nets provide a full and faithful representation of any freely generated compact closed category. Further analysis of the structure of quantum states which correspond to mCQL proofs using multiplicative linear logic shows that the linear type system describes the quantum entanglement found in such states. We show that the entanglement present in these states is always of a particularly simple form: collections of entangled pairs. In order to tackle arbitrary entanglement, we generalise the work of Kelly and Laplaza to give a representation theorem for the free compact closed category by a polycategory. Such categories are shown to be equivalent to a generalised system of proof-nets whose axioms may have more than one premise
§1. Introduction. Our understanding of Nature comes in layers, so should the development of logic. Classic logic is an indispensable part of our knowledge, and its interactions with computer science have recently dramatically changed our life. A new layer of logic has been developing ever since the discovery of quantum mechanics. G. D. Birkhoff and von Neumann introduced quantum logic in a seminal paper in 1936 [1]. But the definition of quantum logic varies among authors (see [2]). How to capture the logic structure inherent in quantum mechanics is very interesting and challenging. Given the close connection between classical logic and theoretical computer science as exemplified by the coincidence of computable functions through Turing machines, recursive function theory, and λ-calculus, we are interested in how to gain some insights about quantum logic from quantum computing. In this note we make some observations about quantum logic as motivated by quantum computing (see [5]) and hope more people will explore this connection. The quantum logic as envisioned by Birkhoff and von Neumann is based on the lattice of closed subspaces of a Hilbert space, usually an infinite dimensional one. The quantum logic of a fixed Hilbert space ℍ in this note is the variety of all the true equations with finitely many variables using the connectives meet, join and negation. Quantum computing is theoretically based on quantum systems with finite dimensional Hilbert spaces, especially the states space of a qubit ℂ2. (Actually the qubit is merely a convenience.
Elaborating on our joint work with Abramsky in [S. Abramsky, B. Coecke, B. (2004) A categorical semantics of quantum protocols. Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science (LiCS'04), IEEE Computer Science Press. Extended version including proofs at arXiv:quant-ph/0402130, S. Abramsky, B. Coecke, (2005) Abstract physical traces. Theory and Applications of Categories 14, 111–124] we further unravel the linear structure of Hilbert spaces into several constituents. Some prove to be very crucial for particular features of quantum theory while others obstruct the passage to a formalism which is not saturated with physically insignificant global phases. First we show that the bulk of the required linear structure is purely multiplicative, and arises from the strongly compact closed tensor which, besides providing a variety of notions such as scalars, trace, unitarity, self-adjointness and bipartite projectors [S. Abramsky, B. Coecke, B. (2004) A categorical semantics of quantum protocols. Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science (LiCS'04), IEEE Computer Science Press. Extended version including proofs at arXiv:quant-ph/0402130, S. Abramsky, B. Coecke, (2005) Abstract physical traces. Theory and Applications of Categories 14, 111–124], also provides Hilbert-Schmidt norm, Hilbert-Schmidt inner-product, and in particular, the preparation-state agreement axiom which enables the passage from a formalism of the vector space kind to a rather projective one, as it was intended in the (in)famous Birkhoff & von Neumann paper [G. Birkhoff, J. von Neumann, (1936) The logic of quantum mechanics. Annals of Mathematics 37, 823–843]. Next we consider additive types which distribute over the tensor, from which measurements can be build, and the correctness proofs of the protocols discussed in [S. Abramsky, B. Coecke, (2004) A categorical semantics of quantum protocols. Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science (LiCS'04), IEEE Computer Science Press. Extended version including proofs at arXiv:quant-ph/0402130] carry over to the resulting weaker setting. A full probabilistic calculus is obtained when the trace is moreover linear and satisfies the diagonal axiom, which brings us to a second main result, characterization of the necessary and sufficient additive structure of a both qualitatively and quantitatively effective categorical quantum formalism without redundant global phases. Along the way we show that if in a category a (additive) monoidal tensor distributes over a strongly compact closed tensor, then this category is always enriched in commutative monoids.
The aim of this chapter is to present (in a compact way) the fundamentals of conventional quantum theory. We select the for- mulation of QM as an axiomatic theory in the complete accordance with the Hilbert’s program on axiomatization of physical theories. We remark that the first step toward the present formulation of QM was done in the seminal work of Hilbert, Nordheim, and von Neumann [112]. This work was substantially extended, completed, and clarified in the book of von Neumann [296]. Another version of the rigorous mathematical approach to QM was presented in the book of Dirac [74]. From the mathematical viewpoint, the main difference between the approaches of von Neumann and Dirac is that the first one is based on the theory of self-adjoint operators in complex Hilbert space and the second one is based on the theory of self-adjoint operators acting (by using the modern mathematical terminology) in rigged Hilbert spaces. This theory operates with generalized eigenvectors belonging to the spaces of distributions. Although the von Neumann’s formalization of QM became dominant in quantum mathematical physics, the Dirac’s formalization is widely used in the works on the physical level of rigorousness. Moreover, the Dirac’s terminology, bra-and ket- vectors, became the standard for quantum information theory. However, since quantum information is based on the castrated version of QM, namely, QM in finite-dimensional Hilbert spaces, the so-called n-qubit spaces, the basic tool of the Dirac’s formalism, usage of generalized eigenvectors, is useless (since in the finite- dimensional case everything is reduced to manipulation with matrices). During the last 80 years, there were written hundreds of books on QM enlightening its foundational aspects. Unfortunately, the majority of these writings advertise exotic (and some of them really esoteric) views on QM and, in particular, on interpretation of the wave function. They are full of such terms as the collapse of the wave function, quantumnonlocality, manyworlds, thewave function of universe, the preparation of Schro¨dinger cats, influence of the future on the past, quantum teleportation. Of course, manipulations with such terminology create an atmosphere of mystery and a feeling that something unusual and impossible can happen. And this atmosphere plays a positive role in attracting young people to QM and especially to quantum foundations.