Pictures of Processes: Automated Graph Rewriting for Monoidal Categories and Applications to Quantum Computing

Abstract

This work is about diagrammatic languages, how they can be represented, and what they in turn can be used to represent. More specifically, it focuses on representations and applications of string diagrams. String diagrams are used to represent a collection of processes, depicted as "boxes" with multiple (typed) inputs and outputs, depicted as "wires". If we allow plugging input and output wires together, we can intuitively represent complex compositions of processes, formalised as morphisms in a monoidal category. [...] The first major contribution of this dissertation is the introduction of a discretised version of a string diagram called a string graph. String graphs form a partial adhesive category, so they can be manipulated using double-pushout graph rewriting. Furthermore, we show how string graphs modulo a rewrite system can be used to construct free symmetric traced and compact closed categories on a monoidal signature. The second contribution is in the application of graphical languages to quantum information theory. We use a mixture of diagrammatic and algebraic techniques to prove a new classification result for strongly complementary observables. [...] We also introduce a graphical language for multipartite entanglement and illustrate a simple graphical axiom that distinguishes the two maximally-entangled tripartite qubit states: GHZ and W. [...] The third contribution is a description of two software tools developed in part by the author to implement much of the theoretical content described here. The first tool is Quantomatic, a desktop application for building string graphs and graphical theories, as well as performing automated graph rewriting visually. The second is QuantoCoSy, which performs fully automated, model-driven theory creation using a procedure called conjecture synthesis.

PhD Thesis. Passed examination. Minor corrections made and one theorem added at the end of Chapter 5. 182 pages, ~300 figures. See full text for unabridged abstract

References in corpus (6)

• Inductive Entanglement Classification of Four Qubits under SLOCC
• Generalized Flow and Determinism in Measurement-based Quantum Computation
• Inductive classification of multipartite entanglement under SLOCC
• The GHZ/W-calculus contains rational arithmetic
• The compositional structure of multipartite quantum entanglement
• Graphical Classification of Entangled Qutrits

Cited by in corpus (11)

• The algebra of entanglement and the geometry of composition
• ZX-calculus for the working quantum computer scientist
• ZX-Calculus and Extended Wolfram Model Systems II: Fast Diagrammatic Reasoning with an Application to Quantum Circuit Simplification
• Categorical Semantics for Schrödinger's Equation
• Fully graphical treatment of the quantum algorithm for the Hidden Subgroup Problem
• Diagrammatic Semantics for Digital Circuits
• Categorical Quantum Dynamics
• Rewriting Structured Cospans: A Syntax For Open Systems
• On the Killing form of Lie Algebras in Symmetric Ribbon Categories
• Tensors, !-graphs, and non-commutative quantum structures (extended version)
• A Diagrammatic Axiomatisation for Qubit Entanglement