The Adjoint School 2019
The 2019 Adjoint School featured projects mentored by Miriam Backens, Tobias Fritz, Pieter Hofstra, Bartosz Milewski, Mehrnoosh Sadrzadeh, and David Spivak. It was organised by Daniel Cicala and Jules Hedges. The research week was held at Oxford in July 2019.
Research Projects
Simplifying quantum circuits using the ZX-calculus
Mentor: Miriam Backens
TA: Hector Bakewell
The ZX-calculus is a graphical calculus based on the category-theoretical formulation of quantum mechanics. A complete set of graphical rewrite rules is known for the ZX-calculus, but not for quantum circuits over any universal gate set. In this project, we aim to develop new strategies for using the ZX-calculus to simplify quantum circuits.
Participants and Blog Posts
- Blog post: The ZX-Calculus for Stabilizer Quantum Mechanics
- Associated reading: The ZX-calculus is complete for stabilizer quantum mechanics, Miriam Backens
- Blog post: Normalising Quantum Circuits
- Associated reading: A Finite Presentation of CNOT-Dihedral Operators, Matthew Amy, Jianxin Chen, and Neil J. Ross
Outcomes Following the Research Week
- Publication: There and back again: A circuit extraction tale, Miriam Backens, Hector Miller-Bakewell, Giovanni de Felice, Leo Lobski, and John van de Wetering
Partial evaluations, the bar construction, and second-order stochastic dominance
Mentor: Tobias Fritz
TA: Paolo Perrone
We all know that 2+2+1+1 evaluates to 6. A less familiar notion is that it can *partially evaluate* to 5+1. In this project, we aim to study the compositional structure of partial evaluation in terms of monads and the bar construction and see what this has to do with financial risk via second-order stochastic dominance.
Participants and Blog Posts
- Blog post: Partial Evaluations 1
- Associated reading: Monads, partial evaluations, and rewriting, Tobias Fritz, Paolo Perrone
- Blog post: Partial Evaluations 2
- Associated reading: The monads of classical algebra are seldom weakly cartesian , Maria Manuel Clementino, Dirk Hoffman, George Janelidze
Outcomes Following the Research Week
- Publication: Partial evaluations and the compositional structure of the bar construction , Carmen Constantin, Paolo Perrone, Tobias Fritz, and Brandon Shapiro
- Publication: Weak cartesian properties of simplicial sets , Carmen Constantin, Tobias Fritz, Paolo Perrone, and Brandon Shapiro
Complexity classes, computation, and Turing categories
Mentor: Pieter Hofstra
TA: Jonathan Gallagher
Turing categories form a categorical setting for studying computability without bias towards any particular model of computation. It is not currently clear, however, that Turing categories are useful to study practical aspects of computation such as complexity. This project revolves around the systematic study of step-based computation in the form of stack-machines, the resulting Turing categories, and complexity classes. This will involve a study of the interplay between traced monoidal structure and computation. We will explore the idea of stack machines qua programming languages, investigate the expressive power, and tie this to complexity theory. We will also consider questions such as the following: can we characterize Turing categories arising from stack machines? Is there an initial such category? How does this structure relate to other categorical structures associated with computability?
Participants and Blog Posts
- Blog post: Total Maps of Turing Categories
- Associated reading: Total Maps of Turing Categories, J.R.B. Cockett, P.J.W. Hofstra, and P. Hrubeš
- Blog post: Turing Categories
- Associated reading: Introduction to Turing categories, J.R.B. Cockett, and P.J.W. Hofstra
Traversal optics and profunctors
Mentor: Bartosz Milewski
TA: Derek Elkins
In functional programming, optics are ways to zoom into a specific part of a given data type and mutate it. Optics come in many flavors such as lenses and prisms and there is a well-studied categorical viewpoint, known as profunctor optics. Of all the optic types, only the traversal has resisted a derivation from first principles into a profunctor description. This project aims to do just this.
Participants and Blog Posts
- Blog post: Doubles for Monoidal Categories
- Associated reading: Doubles for Monoidal Categories , Craig Pastro and Ross Street
- Associated reading: Profunctor optics, categorical View, Bartosz Milewski
Outcomes Following the Research Week
- Publication: Profunctor optics, a categorical update , Bryce Clarke, Derek Elkins, Jeremy Gibbons, Fosco Loregian, Bartosz Milewski, Emily Pillmore, and Mario Román
Formal and experimental methods to reason about dialogue and discourse using categorical models of vector spaces
Mentor: Mehrnoosh Sadrzadeh
TA: Gijs Wijnholds
Distributional semantics argues that meanings of words can be represented by the frequency of their co-occurrences in context. A model extending distributional semantics from words to sentences has a categorical interpretation via Lambek’s syntactic calculus or pregroups. In this project, we intend to further extend this model to reason about dialogue and discourse utterances where people interrupt each other, there are references that need to be resolved, disfluencies, pauses, and corrections. Additionally, we would like to design experiments and run toy models to verify predictions of the developed models.
Participants and Blog Posts
- Blog post: Meeting the Dialogue Challenge
- Associated reading: Grammars as Parsers: Meeting the Dialogue Challenge , Matthew Purver, Ronnie Cann, and Ruth Kempson.
- Associated reading: A multi-modal analysis of anaphora and ellipsis, Gerhard Jager
Outcomes Following the Research Week
- Publication: Categorical Vector Space Semantics for Lambek Calculus with a Relevant Modality , Lachlan McPheat, Mehrnoosh Sadrzadeh, Hadi Wazni, Gijs Wijnholds
- Publication: Incremental Monoidal Grammars , Dan Shiebler, Alexis Toumi, Mehrnoosh Sadrzadeh
Toward a mathematical foundation for autopoiesis
Mentor: David Spivak
TA: Brendan Fong
An autopoietic organization—anything from a living animal to a political party to a football team—is a system that is responsible for adapting and changing itself, so as to persist as events unfold. We want to develop mathematical abstractions that are suitable to found a scientific study of autopoietic organizations. To do this, we’ll begin by using behavioral mereology and graphical logic to frame a discussion of autopoeisis, most of all what it is and how it can be best conceived. We do not expect to complete this ambitious objective; we hope only to make progress toward it.
Participants and Blog Posts
- Blog post: Behavioral Mereology
- Associated reading: Behavioral Mereology (Proofs and Properties) , Brendan Fong, David Jaz Myers, David I. Spivak
- Blog post: Graphical Regular Logic
- Associated reading: Graphical Regular Logic , Brendan Fong, David I Spivak