A diagrammatic approach to networks of spans and relations

Thesis

In this thesis we exhibit nondeterministic semantics for various classes of circuits. Motivated initially by quantum circuits, we also give nondeterministic semantics for circuits for classical mechanical systems and Boolean algebra. More formally, we interpret these classes of circuits in terms of categories of spans or relations: in less categorical terms these are equivalent to matrices over the natural numbers or the Boolean semiring. In the relational picture, we characterize circuits in terms of which inputs and outputs are jointly possible; and in the spans picture, how often inputs and outputs are jointly possible. Specifically, we first show that the class of circuits generated by the Toffoli gate as well the states |0⟩, |1⟩, √2|+⟩ and their adjoints is characterized in terms of spans of finite sets. We also give a complete axiomatization for these circuits. With this semantics in mind, we discuss the connection to partial and reversible computation. Shifting to the phase-space picture we also characterize circuits in terms of how they relate abstract positions and momenta. We show how this gives a unifying relational semantics for certain classes circuits for classical mechanical systems, as well as for stabilizer quantum circuits

Authors: Comfort, C

• DOI: 10.5287/ora-avnkvq09n
• Type of award: DPhil
• Level of award: Doctoral
• Awarding institution: University of Oxford
• Language: English
• Keywords: quantum computing; string diagrams; Lagrangian relations; diagrammatic methods; classical mechanics; quantum mechanics; category theory; symplectic geometry
• Subjects: Quantum computing; Categories (Mathematics)