Monoidal Categories‚ Graphical Reasoning‚ and Quantum Computation

Abstract

Graphs provide a natural mechanism for visualising many algebraic systems. They are particularly useful for describing algebras in a monoidal category, such as Frobenius algebras and bialgebras, which play a vital role in quantum computation. In this context, terms in the algebra are represented as graphs, and algebraic identities as graph rewrite rules. To describe the theory of a more powerful monoidal algebra, one needs a concise way to define infinite sets of rules. This is addressed by introducing pattern graphs and pattern graph rewriting. An algorithm for matching is described. This is implemented in a tool called Quantomatic, which allows a user to explore a graphical theory by constructing graphs and performing automated and semi-automated rewrites.