Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2510.05032 · Leibniz international proceedings in informatics

Complete ω-Regular Supermartingale Certificates

Alessandro Abate, Giacobbe, Mirco, Ichtchenko, Sergey, Diptarko Roy

Published Oct 6, 2025• 2 citations
arXivHTMLPDF

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.

DOI
10.4230/lipics.lics.2026.3

Related papers

A Complete Equational Theory for Quantum Circuits with Generalized Control

William Schober, Scott Wesley

Controlled subcircuits are commonplace in quantum algorithms as they represent the quantum analogue of branching statements (if then).We introduce a generalization of controlled subcircuits in the form of a binary operation which sends pairs of unitary quantum circuits to a generalized controlled operation, whose semantics are based on matrix exponentials and logarithms.The family of quantum circuits with generalized controlled operations and circuit exponentiation is denoted HQC for Hierarchical Quantum Circuits.We formalize HQC as a modified prop category using a novel category-theoretic construction, and provide a sound and complete equational theory for diagrammatic reasoning in HQC.

arXiv:2611.07207•Electronic Proceedings in Theoretical Computer Science•Nov 2, 2026•1 citation

A Complete Equational Presentation of Qudit Circuits via Polycontrolled PROPs

Colin Blake

High-dimensional quantum computation needs a native circuit-level equational theory for qudits. We give the first finite schematic equational theory that is sound and complete for exact unitary qudit circuits in every finite dimension at least two. Circuits are built from local gates, sequential and parallel composition, and value-controls; equality is derivable exactly when the standard unitary denotations agree. For each dimension, a finite list of local bounded-arity axiom schemata presents the theory, and the diagrammatic shapes do not depend on d. Primitive value-control makes control on a chosen basis value part of the language, so local rules generate the internal algebra of controlled operations within the circuit PROP. This gives a finite, dimension-uniform basis for exact equational reasoning about qudit circuits.

quant-pharXiv:2602.09873•Leibniz international proceedings in informatics•Feb 11, 2026•0 citations

With a Few Square Roots, Quantum Computing Is as Easy as Pi

Jacques Carette, Chris Heunen, Robin Kaarsgaard +1 more

Rig groupoids provide a semantic model of Π , a universal classical reversible programming language over finite types. We prove that extending rig groupoids with just two maps and three equations about them results in a model of quantum computing that is computationally universal and equationally sound and complete for a variety of gate sets. The first map corresponds to an 8th root of the identity morphism on the unit 1. The second map corresponds to a square root of the symmetry on 1 + 1 . As square roots are generally not unique and can sometimes even be trivial, the maps are constrained to satisfy a nondegeneracy axiom, which we relate to the Euler decomposition of the Hadamard gate. The semantic construction is turned into an extension of Π , called Π , that is a computationally universal quantum programming language equipped with an equational theory that is sound and complete with respect to the Clifford gate set, the standard gate set of Clifford+T restricted to ≤ 2 qubits, and the computationally universal Gaussian Clifford+T gate set.

arXiv:2310.14056•Proceedings of the ACM on Programming Languages•Jan 2, 2024•18 citations

Controlled PROP: Theory and Applications to Quantum Circuits

Noé Delorme, Simon Perdrix

Control is a fundamental concept in quantum and reversible computational models. It enables the conditional application of a transformation to a system, depending on the state of another system. We introduce a general framework for diagrammatic reasoning featuring control as a constructor. To this end, we provide an elementary axiomatization of control functors, extending the standard formalism of PROPs to controlled PROPs. As an application, we show that controlled PROPs facilitate diagrammatic reasoning for quantum circuits. In particular, they admit a simple and complete axiomatization involving at most three qubits, whereas in the standard PROP setting, completeness necessarily requires axioms involving arbitrarily many qubits.

quant-pharXiv:2610.23192•Oct 19, 2026•0 citations

A Complete Equational Theory for Quantum Circuits

Alexandre Clément, Nicolas Heurtel, Shane Mansfield +2 more

We introduce the first complete equational theory for quantum circuits. More precisely, we introduce a set of circuit equations that we prove to be sound and complete: two circuits represent the same unitary map if and only if they can be transformed one into the other using the equations. The proof is based on the properties of multi-controlled gates – that are defined using elementary gates – together with an encoding of quantum circuits into linear optical circuits, which have been proved to have a complete axiomatisation.

arXiv:2206.10577•ACM/IEEE Symposium on Logic in Computer Science (LICS)•Jun 26, 2023•36 citations

Parameterized Quantum Circuit Semantics Through Enriched Categories

Neil J. Ross, Scott Wesley

It is well-known that combinatorial circuits are modeled mathematically by string diagrams in monoidal categories. Given a gate set $Σ$, the circuits over $Σ$ can be thought of as string diagrams in the free monoidal category generated by $Σ$. In this model, circuit semantics are then given by monoidal functors out of this free category. For quantum circuits, this functor is often valued in the category of unitary matrices. This model suffices for concrete quantum circuits, but fails to describe parameterized families of quantum circuits, such as those which arise in the analysis of ansatz circuits. In this paper, we introduce an approach to parameterized circuit semantics, which is based on enriched category theory. We first introduce an abstract categorical construction, and use this to gain new insights on controlled operations and quantum communication. We then study the special cases of Cartesian monoidal parameters and monoidal closed parameters, both endowing the parameterized semantics with useful constructions. We conclude by showing that the monoidal closed case can be used to unify two perspectives on quantum control.

quant-pharXiv:2607.16114•Jul 20, 2026•0 citations
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.
Controlled subcircuits are commonplace in quantum algorithms as they represent the quantum analogue of branching statements (if then).We introduce a generalization of controlled subcircuits in the form of a binary operation which sends pairs of unitary quantum circuits to a generalized controlled operation, whose semantics are based on matrix exponentials and logarithms.The family of quantum circuits with generalized controlled operations and circuit exponentiation is denoted HQC for Hierarchical Quantum Circuits.We formalize HQC as a modified prop category using a novel category-theoretic construction, and provide a sound and complete equational theory for diagrammatic reasoning in HQC.
High-dimensional quantum computation needs a native circuit-level equational theory for qudits. We give the first finite schematic equational theory that is sound and complete for exact unitary qudit circuits in every finite dimension at least two. Circuits are built from local gates, sequential and parallel composition, and value-controls; equality is derivable exactly when the standard unitary denotations agree. For each dimension, a finite list of local bounded-arity axiom schemata presents the theory, and the diagrammatic shapes do not depend on d. Primitive value-control makes control on a chosen basis value part of the language, so local rules generate the internal algebra of controlled operations within the circuit PROP. This gives a finite, dimension-uniform basis for exact equational reasoning about qudit circuits.
Rig groupoids provide a semantic model of Π , a universal classical reversible programming language over finite types. We prove that extending rig groupoids with just two maps and three equations about them results in a model of quantum computing that is computationally universal and equationally sound and complete for a variety of gate sets. The first map corresponds to an 8th root of the identity morphism on the unit 1. The second map corresponds to a square root of the symmetry on 1 + 1 . As square roots are generally not unique and can sometimes even be trivial, the maps are constrained to satisfy a nondegeneracy axiom, which we relate to the Euler decomposition of the Hadamard gate. The semantic construction is turned into an extension of Π , called Π , that is a computationally universal quantum programming language equipped with an equational theory that is sound and complete with respect to the Clifford gate set, the standard gate set of Clifford+T restricted to ≤ 2 qubits, and the computationally universal Gaussian Clifford+T gate set.
Control is a fundamental concept in quantum and reversible computational models. It enables the conditional application of a transformation to a system, depending on the state of another system. We introduce a general framework for diagrammatic reasoning featuring control as a constructor. To this end, we provide an elementary axiomatization of control functors, extending the standard formalism of PROPs to controlled PROPs. As an application, we show that controlled PROPs facilitate diagrammatic reasoning for quantum circuits. In particular, they admit a simple and complete axiomatization involving at most three qubits, whereas in the standard PROP setting, completeness necessarily requires axioms involving arbitrarily many qubits.
We introduce the first complete equational theory for quantum circuits. More precisely, we introduce a set of circuit equations that we prove to be sound and complete: two circuits represent the same unitary map if and only if they can be transformed one into the other using the equations. The proof is based on the properties of multi-controlled gates – that are defined using elementary gates – together with an encoding of quantum circuits into linear optical circuits, which have been proved to have a complete axiomatisation.
It is well-known that combinatorial circuits are modeled mathematically by string diagrams in monoidal categories. Given a gate set ΣΣΣ, the circuits over ΣΣΣ can be thought of as string diagrams in the free monoidal category generated by ΣΣΣ. In this model, circuit semantics are then given by monoidal functors out of this free category. For quantum circuits, this functor is often valued in the category of unitary matrices. This model suffices for concrete quantum circuits, but fails to describe parameterized families of quantum circuits, such as those which arise in the analysis of ansatz circuits. In this paper, we introduce an approach to parameterized circuit semantics, which is based on enriched category theory. We first introduce an abstract categorical construction, and use this to gain new insights on controlled operations and quantum communication. We then study the special cases of Cartesian monoidal parameters and monoidal closed parameters, both endowing the parameterized semantics with useful constructions. We conclude by showing that the monoidal closed case can be used to unify two perspectives on quantum control.