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:2206.10577 · ACM/IEEE Symposium on Logic in Computer Science (LICS)

A Complete Equational Theory for Quantum Circuits

Alexandre Clément, Nicolas Heurtel, Shane Mansfield, Simon Perdrix, Benoît Valiron

Published Jun 26, 2023• 13 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/lics56636.2023.10175801

Related papers

Minimal Equational Theories for Quantum Circuits

Alexandre Clément, Noé Delorme, Simon Perdrix

We introduce the first minimal and complete equational theory for quantum circuits. Hence, we show that any true equation on quantum circuits can be derived from simple rules, all of them being standard except a novel but intuitive one which states that a multi-control 2π rotation is nothing but the identity. Our work improves on the recent complete equational theories for quantum circuits, by getting rid of several rules including a fairly impractical one. One of our main contributions is to prove the minimality of the equational theory, i.e. none of the rules can be derived from the other ones. More generally, we demonstrate that any complete equational theory on quantum circuits (when all gates are unitary) requires rules acting on an unbounded number of qubits. Finally, we also simplify the complete equational theories for quantum circuits with ancillary qubits and/or qubit discarding.

arXiv:2311.07476•ACM/IEEE Symposium on Logic in Computer Science (LICS)•Jun 21, 2024•3 citations

A Complete Equational Theory for Real-Clifford+CH Quantum Circuits

Alexandre Clément

We introduce a complete equational theory for the fragment of quantum circuits generated by the real Clifford gates plus the two-qubit controlled-Hadamard gate. That is, we give a simple set of equalities between circuits of this fragment, and prove that any other true equation can be derived from these. This is the first such completeness result for a finitely-generated, universal fragment of quantum circuits, with no parameterized gates and no need for ancillas.

quant-pharXiv:2602.06644•Feb 9, 2026•0 citations

Graphical Languages for Quantum Control and Linear Optics

Alexandre Clément

In the models of quantum computing usually considered, some quantum data is manipulated by means of operations which are controlled in an essentially classical way. Controlling these operations in a quantum way is actually possible, but has been much less studied. In particular, quantum control misses a formalism in which one could represent it in a simple way in order to efficiently reason on processes involving it. The first contribution of this thesis is to lay the foundations of a formal framework dedicated to quantum control, in the form of a graphical language. Our main result about this language is the introduction of a complete equational theory, that is, a set of equations that makes it possible, by successive local rewriting, to transform a given diagram into any other diagram representing the same program or physical process. A second contribution is to apply this formalism, on the one hand, to the problem of resource optimisation of processes involving quantum control, and on the other hand, to the characterisation of the observational equivalence of quantum communication channels. A third contribution of this thesis is to introduce a language for linear optical circuits. We equip this language with a complete equational theory, together with a simple normal form, reachable via a strongly normalising and confluent rewriting system. The last contribution of this thesis, maybe the most significant one, is to introduce a complete equational theory for the language of quantum circuits. We obtain this result by exploiting a correspondence between quantum circuits and optical circuits, which allows us to transfer the equational theory already obtained for optical circuits.

•May 16, 2023•0 citations

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

A Complete Equational Theory for Real-Clifford+CH Quantum Circuits

Alexandre Clément

We introduce a complete equational theory for the fragment of quantum circuits generated by the real Clifford gates plus the two-qubit controlled-Hadamard gate. That is, we give a simple set of equalities between circuits of this fragment, and prove that any other true equation can be derived from these. This is the first such completeness result for a finitely-generated, universal fragment of quantum circuits, with no parameterized gates and no need for ancillas.

Leibniz international proceedings in informatics•Jan 1, 2026•0 citations

A Complete Equational Theory for Real-Clifford+CH Quantum Circuits

Alexandre Clément

We introduce a complete equational theory for the fragment of quantum circuits generated by the real Clifford gates plus the two-qubit controlled-Hadamard gate. That is, we give a simple set of equalities between circuits of this fragment, and prove that any other true equation can be derived from these. This is the first such completeness result for a finitely-generated, universal fragment of quantum circuits, with no parameterized gates and no need for ancillas.

•Jul 20, 2026•0 citations
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.
We introduce the first minimal and complete equational theory for quantum circuits. Hence, we show that any true equation on quantum circuits can be derived from simple rules, all of them being standard except a novel but intuitive one which states that a multi-control 2π rotation is nothing but the identity. Our work improves on the recent complete equational theories for quantum circuits, by getting rid of several rules including a fairly impractical one. One of our main contributions is to prove the minimality of the equational theory, i.e. none of the rules can be derived from the other ones. More generally, we demonstrate that any complete equational theory on quantum circuits (when all gates are unitary) requires rules acting on an unbounded number of qubits. Finally, we also simplify the complete equational theories for quantum circuits with ancillary qubits and/or qubit discarding.
In the models of quantum computing usually considered, some quantum data is manipulated by means of operations which are controlled in an essentially classical way. Controlling these operations in a quantum way is actually possible, but has been much less studied. In particular, quantum control misses a formalism in which one could represent it in a simple way in order to efficiently reason on processes involving it. The first contribution of this thesis is to lay the foundations of a formal framework dedicated to quantum control, in the form of a graphical language. Our main result about this language is the introduction of a complete equational theory, that is, a set of equations that makes it possible, by successive local rewriting, to transform a given diagram into any other diagram representing the same program or physical process. A second contribution is to apply this formalism, on the one hand, to the problem of resource optimisation of processes involving quantum control, and on the other hand, to the characterisation of the observational equivalence of quantum communication channels. A third contribution of this thesis is to introduce a language for linear optical circuits. We equip this language with a complete equational theory, together with a simple normal form, reachable via a strongly normalising and confluent rewriting system. The last contribution of this thesis, maybe the most significant one, is to introduce a complete equational theory for the language of quantum circuits. We obtain this result by exploiting a correspondence between quantum circuits and optical circuits, which allows us to transfer the equational theory already obtained for optical circuits.
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.