Categories and Quantum Computing

Octavio Malherbe

This dissertation has two main parts. The first part deals with questions relating to Haghverdi and Scott's notion of partially traced categories. The main result is a representation theorem for such categories: we prove that every partially traced category can be faithfully embedded in a totally traced category. Also conversely, every monoidal subcategory of a totally traced category is partially traced, so this characterizes the partially traced categories completely. The main technique we use is based on Freyd's paracategories, along with a partial version of Joyal, Street, and Verity's Int construction. Along the way, we discuss some new examples of partially traced categories, mostly arising in the context of quantum computation. The second part deals with the construction of categorical models of higher-order quantum computation. We construct a concrete semantic model of Selinger and Valiron's quantum lambda calculus, which has been an open problem until now. We do this by considering presheaf categories over appropriate base categories arising from first-order quantum computation. The main technical ingredients are Day's convolution theory and Kelly and Freyd's notion of continuity of functors. We first give an abstract description of the properties required of the base categories for the model construction to work; then exhibit a specific example of base categories satisfying these properties.

Davor Pavuna

Peter Selinger

The search for a semantics for higher-order quantum computation leads naturallyto the study of categories of normed cones. In the first part of this paper, we develop the theory of continuous normed cones, and prove some of their basic properties, includinga Hahn-Banach style theorem. We then describe two different concrete *-autonomous categories of normed cones. The first of these categories is built from completelypositive maps as in the author's semantics of first-order quantum computation. The second category is a reformulation of Girard's quantum coherent spaces. We also pointout why ultimately, neither of these categories is a satisfactory model of higher-order quantum computation.

Y. Yamamoto, Fumiko Yamaguchi

André Berthiaume

Fatimah Rita Ahmadi

Unitary Ribbon Fusion Categories (URFC) formalize anyonic theories. It has been widely assumed that the same category formalizes a topological quantum computing model. However, in previous work, we addressed and resolved this confusion and demonstrated while the former could be any fusion category, the latter is always a subcategory of Hilb. In this paper, we argue that a categorical formalism that captures and unifies both anyonic theories (the Hardware of quantum computing) and a model of topological quantum computing is a braided (fusion) 2-category. In this 2-category, 0-morphisms describe anyonic types and Hom-categories describe different models of quantum computing. This picture provides an insightful perspective on superselection rules. It presents furthermore a clear distinction between fusion of anyons versus tensor products as defined in linear algebra, between vector spaces of 1-morphisms. The former represents a monoidal product and sum between 0-morphisms and the latter a tensor product and direct sum between 1-morphisms.