DROPS

Document

DOI: 10.4230/LIPIcs.LICS.2026.56

One Rig to Control Them All

Authors: Chris Heunen, Robin Kaarsgaard, and Louis Lemonnier

Published in: LIPIcs, Volume 380, 41st Annual Symposium on Logic in Computer Science (LICS 2026)

Abstract

Controlled commands - computations whose execution depends on a separate input - play a central role in reversible Boolean circuits and quantum circuits. However, existing formalisms typically treat control only implicitly, entangled with other aspects of computation. From a semantic perspective, control is most naturally expressed in semisimple rig categories, which - unlike standard circuit models such as props - support both parallel and conditional composition. We present a construction that freely adjoins an explicit syntactic notion of control to a circuit theory specified as a suitable prop, subject to eight universally quantified equations. Our main result is that these equations are sound and complete for the intended semantics of control: the resulting theory satisfies a universal property, identifying it exactly as the circuit subtheory of the free semisimple rig completion. The proof combines coherence for rig categories with a new method based on induction over Gray codes. We illustrate the usefulness of the framework by showing that it simplifies several existing sound and complete axiomatisations of quantum circuits, isolating a small and conceptually clean set of generators and equations. In addition, the same equations yield a sound and complete axiomatisation of the multiply controlled Toffoli gate set, that is universal for reversible Boolean circuits.

Cite as

Chris Heunen, Robin Kaarsgaard, and Louis Lemonnier. One Rig to Control Them All. In 41st Annual Symposium on Logic in Computer Science (LICS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 380, pp. 56:1-56:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{heunen_et_al:LIPIcs.LICS.2026.56,
  author =	{Heunen, Chris and Kaarsgaard, Robin and Lemonnier, Louis},
  title =	{{One Rig to Control Them All}},
  booktitle =	{41st Annual Symposium on Logic in Computer Science (LICS 2026)},
  pages =	{56:1--56:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-434-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{380},
  editor =	{Faggian, Claudia and Katoen, Joost-Pieter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.LICS.2026.56},
  URN =		{urn:nbn:de:0030-drops-268435},
  doi =		{10.4230/LIPIcs.LICS.2026.56},
  annote =	{Keywords: Quantum control, rig categories, complete equational theories}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2021.17

Graph Traversals as Universal Constructions

Authors: Siddharth Bhaskar and Robin Kaarsgaard

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract

We exploit a decomposition of graph traversals to give a novel characterization of depth-first and breadth-first traversals by means of universal constructions. Specifically, we introduce functors from two different categories of edge-ordered directed graphs into two different categories of transitively closed edge-ordered graphs; one defines the lexicographic depth-first traversal and the other the lexicographic breadth-first traversal. We show that each functor factors as a composition of universal constructions, and that the usual presentation of traversals as linear orders on vertices can be recovered with the addition of an inclusion functor. Finally, we raise the question of to what extent we can recover search algorithms from the categorical description of the traversal they compute.

Cite as

Siddharth Bhaskar and Robin Kaarsgaard. Graph Traversals as Universal Constructions. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bhaskar_et_al:LIPIcs.MFCS.2021.17,
  author =	{Bhaskar, Siddharth and Kaarsgaard, Robin},
  title =	{{Graph Traversals as Universal Constructions}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{17:1--17:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.17},
  URN =		{urn:nbn:de:0030-drops-144573},
  doi =		{10.4230/LIPIcs.MFCS.2021.17},
  annote =	{Keywords: graph traversals, adjunctions, universal constructions, category theory}
}

Search Results

Documents authored by Kaarsgaard, Robin

One Rig to Control Them All

Abstract

Cite as

Graph Traversals as Universal Constructions

Abstract

Cite as

Thanks for your feedback!

Could not send message