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:2004.05287 · Electronic Proceedings in Theoretical Computer Science

The ZX&-calculus: A complete graphical calculus for classical circuits using spiders

Cole Comfort

Published Sep 6, 2021• 9 citations
arXivHTMLPDF

Abstract

We give a complete presentation for the fragment, ZX&, of the ZX-calculus generated by the Z and X spiders (corresponding to copying and addition) along with the not gate and the and gate. To prove completeness, we freely add a unit and counit to the category TOF generated by the Toffoli gate and ancillary bits, showing that this yields the full subcategory of finite ordinals and functions with objects powers of two; and then perform a two way translation between this category and ZX&. A translation to some extension of TOF, as opposed to some fragment of the ZX-calculus, is a natural choice because of the multiplicative nature of the Toffoli gate. To this end, we show that freely adding counits to the semi-Frobenius algebras of a discrete inverse category is the same as constructing the Cartesian completion. In particular, for a discrete inverse category, the category of classical channels, the Cartesian completion and adding counits all produce the same category. Therefore, applying these constructions to TOF produces the full subcategory of finite ordinals and partial maps with objects powers of two. By glueing together the free counit completion and the free unit completion, this yields "qubit multirelations."

DOI
10.4204/eptcs.340.4

Related papers

Circuit Relations for Real Stabilizers: Towards TOF+H

Cole Comfort

The real stabilizer fragment of quantum mechanics was shown to have a complete axiomatization in terms of the angle-free fragment of the ZX-calculus. This fragment of the ZX-calculus---although abstractly elegant---is stated in terms of identities, such as spider fusion which generally do not have interpretations as circuit transformations. We complete the category CNOT generated by the controlled not gate and the computational ancillary bits, presented by circuit relations, to the real stabilizer fragment of quantum mechanics. This is performed first, by adding the Hadamard gate and the scalar sqrt 2 as generators. We then construct translations to and from the angle-free fragment of the ZX-calculus, showing that they are inverses. We then discuss how this could potentially lead to a complete axiomatization, in terms of circuit relations, for the approximately universal fragment of quantum mechanics generated by the Toffoli gate, Hadamard gate and computational ancillary bits.

arXiv:1904.10614•Apr 24, 2019•1 citation

Distributive Laws, Spans and the ZX-Calculus

Cole Comfort

We modularly build increasingly larger fragments of the ZX-calculus by modularly adding new generators and relations, at each point, giving some concrete semantics in terms of some category of spans. This is performed using Lack's technique of composing props via distributive laws, as well as the technique of pushout cubes of Zanasi. We do this for the fragment of the ZX-calculus with only the black $π$-phase (and no Hadamard gate) as well as well as the fragment which additionally has the and gate as a generator (which is equivalent to the natural number H-box fragment of the ZH-calculus). In the former case, we show that this is equivalent to the full subcategory of spans of (possibly empty) free, finite dimensional affine $\mathbb F_2$-vector spaces, where the objects are the non-empty affine vector spaces. In the latter case, we show that this is equivalent to the full subcategory of spans of finite sets where the objects are powers of the two element set. Because these fragments of the ZX-calculus have semantics in terms of full subcategories of categories of spans, they can not be presented by distributive laws over groupoids. Instead, we first construct their subcategories of partial isomorphisms via distributive laws over all isomorphims with subobjects adjoined. After which, the full subcategory of spans are obtained by freely adjoining units and counits the the semi-Frobenius structures given by the diagonal and codiagonal maps.

arXiv:2102.04386•Feb 8, 2021•1 citation

ZH: A Complete Graphical Calculus for Quantum Computations Involving Classical Non-linearity

Miriam Backens, Aleks Kissinger

We present a new graphical calculus that is sound and complete for a universal family of quantum circuits, which can be seen as the natural string-diagrammatic extension of the approximately (real-valued) universal family of Hadamard+CCZ circuits. The diagrammatic language is generated by two kinds of nodes: the so-called 'spider' associated with the computational basis, as well as a new arity-N generalisation of the Hadamard gate, which satisfies a variation of the spider fusion law. Unlike previous graphical calculi, this admits compact encodings of non-linear classical functions. For example, the AND gate can be depicted as a diagram of just 2 generators, compared to ~25 in the ZX-calculus. Consequently, N-controlled gates, hypergraph states, Hadamard+Toffoli circuits, and diagonal circuits at arbitrary levels of the Clifford hierarchy also enjoy encodings with low constant overhead. This suggests that this calculus will be significantly more convenient for reasoning about the interplay between classical non-linear behaviour (e.g. in an oracle) and purely quantum operations. After presenting the calculus, we will prove it is sound and complete for universal quantum computation by demonstrating the reduction of any diagram to an easily describable normal form.

arXiv:1805.02175•Electronic Proceedings in Theoretical Computer Science•Jan 31, 2019•73 citations

ZX-calculus is Complete for Finite-Dimensional Hilbert Spaces

Boldizsár Poór, Razin Abdulrauf Shaikh, Quanlong Wang

The ZX-calculus is a graphical language for reasoning about quantum computing and quantum information theory.As a complete graphical language, it incorporates a set of axioms rich enough to derive any equation of the underlying formalism.While completeness of the ZX-calculus has been established for qubits and the Clifford fragment of prime-dimensional qudits, universal completeness beyond two-level systems has remained unproven until now.In this paper, we present a proof establishing the completeness of finite-dimensional ZX-calculus, incorporating only the mixeddimensional Z-spider and the qudit X-spider as generators.Our approach builds on the completeness of another graphical language, the finite-dimensional ZW-calculus, with direct translations between these two calculi.By proving its completeness, we lay a solid foundation for the ZX-calculus as a versatile tool not only for quantum computation but also for various fields within finite-dimensional quantum theory.

arXiv:2405.10896•Electronic Proceedings in Theoretical Computer Science•Aug 19, 2025•2 citations

Completeness of the ZH-calculus

Miriam Backens, Aleks Kissinger, Hector Miller-Bakewell +2 more

There are various gate sets used for describing quantum computation. A particularly popular one consists of Clifford gates and arbitrary single-qubit phase gates. Computations in this gate set can be elegantly described by the ZX-calculus, a graphical language for a class of string diagrams describing linear maps between qubits. The ZX-calculus has proven useful in a variety of areas of quantum information, but is less suitable for reasoning about operations outside its natural gate set such as multi-linear Boolean operations like the Toffoli gate. In this paper we study the ZH-calculus, an alternative graphical language of string diagrams that does allow straightforward encoding of Toffoli gates and other more complicated Boolean logic circuits. We find a set of simple rewrite rules for this calculus and show it is complete with respect to matrices over Z[12] , which correspond to the approximately universal Toffoli+Hadamard gateset. Furthermore, we construct an extended version of the ZH-calculus that is complete with respect to matrices over any ring R where 1+1 is not a zero-divisor.

arXiv:2103.06610•Compositionality•Jul 12, 2023•9 citations

Completeness of the ZX-calculus for Pure Qubit Clifford+T Quantum Mechanics

Kang Feng Ng, Quanlong Wang

Recently, we gave a complete axiomatisation of the ZX-calculus for the overall pure qubit quantum mechanics. Based on this result, here we also obtain a complete axiomatisation of the ZX-calculus for the Clifford+T quantum mechanics by restricting the ring of complex numbers to its subring corresponding to the Clifford+T fragment resting on the completeness theorem of the ZW-calculus for arbitrary commutative ring. In contrast to the first complete axiomatisation of the ZX-calculus for the Clifford+T fragment, we have two new generators as features rather than novelties: the triangle can be employed as an essential component to construct a Toffoli gate in a very simple form, while the lambda box can be slightly extended to a generalised phase so that the generalised supplementarity (cyclotomic supplementarity ) is naturally seen as a special case of the generalised spider rule.

arXiv:1801.07993•Jan 22, 2018•15 citations
We give a complete presentation for the fragment, ZX&, of the ZX-calculus generated by the Z and X spiders (corresponding to copying and addition) along with the not gate and the and gate. To prove completeness, we freely add a unit and counit to the category TOF generated by the Toffoli gate and ancillary bits, showing that this yields the full subcategory of finite ordinals and functions with objects powers of two; and then perform a two way translation between this category and ZX&. A translation to some extension of TOF, as opposed to some fragment of the ZX-calculus, is a natural choice because of the multiplicative nature of the Toffoli gate. To this end, we show that freely adding counits to the semi-Frobenius algebras of a discrete inverse category is the same as constructing the Cartesian completion. In particular, for a discrete inverse category, the category of classical channels, the Cartesian completion and adding counits all produce the same category. Therefore, applying these constructions to TOF produces the full subcategory of finite ordinals and partial maps with objects powers of two. By glueing together the free counit completion and the free unit completion, this yields "qubit multirelations."
The real stabilizer fragment of quantum mechanics was shown to have a complete axiomatization in terms of the angle-free fragment of the ZX-calculus. This fragment of the ZX-calculus---although abstractly elegant---is stated in terms of identities, such as spider fusion which generally do not have interpretations as circuit transformations. We complete the category CNOT generated by the controlled not gate and the computational ancillary bits, presented by circuit relations, to the real stabilizer fragment of quantum mechanics. This is performed first, by adding the Hadamard gate and the scalar sqrt 2 as generators. We then construct translations to and from the angle-free fragment of the ZX-calculus, showing that they are inverses. We then discuss how this could potentially lead to a complete axiomatization, in terms of circuit relations, for the approximately universal fragment of quantum mechanics generated by the Toffoli gate, Hadamard gate and computational ancillary bits.
We modularly build increasingly larger fragments of the ZX-calculus by modularly adding new generators and relations, at each point, giving some concrete semantics in terms of some category of spans. This is performed using Lack's technique of composing props via distributive laws, as well as the technique of pushout cubes of Zanasi. We do this for the fragment of the ZX-calculus with only the black πππ-phase (and no Hadamard gate) as well as well as the fragment which additionally has the and gate as a generator (which is equivalent to the natural number H-box fragment of the ZH-calculus). In the former case, we show that this is equivalent to the full subcategory of spans of (possibly empty) free, finite dimensional affine F2\mathbb F_2F2​-vector spaces, where the objects are the non-empty affine vector spaces. In the latter case, we show that this is equivalent to the full subcategory of spans of finite sets where the objects are powers of the two element set. Because these fragments of the ZX-calculus have semantics in terms of full subcategories of categories of spans, they can not be presented by distributive laws over groupoids. Instead, we first construct their subcategories of partial isomorphisms via distributive laws over all isomorphims with subobjects adjoined. After which, the full subcategory of spans are obtained by freely adjoining units and counits the the semi-Frobenius structures given by the diagonal and codiagonal maps.
We present a new graphical calculus that is sound and complete for a universal family of quantum circuits, which can be seen as the natural string-diagrammatic extension of the approximately (real-valued) universal family of Hadamard+CCZ circuits. The diagrammatic language is generated by two kinds of nodes: the so-called 'spider' associated with the computational basis, as well as a new arity-N generalisation of the Hadamard gate, which satisfies a variation of the spider fusion law. Unlike previous graphical calculi, this admits compact encodings of non-linear classical functions. For example, the AND gate can be depicted as a diagram of just 2 generators, compared to ~25 in the ZX-calculus. Consequently, N-controlled gates, hypergraph states, Hadamard+Toffoli circuits, and diagonal circuits at arbitrary levels of the Clifford hierarchy also enjoy encodings with low constant overhead. This suggests that this calculus will be significantly more convenient for reasoning about the interplay between classical non-linear behaviour (e.g. in an oracle) and purely quantum operations. After presenting the calculus, we will prove it is sound and complete for universal quantum computation by demonstrating the reduction of any diagram to an easily describable normal form.
The ZX-calculus is a graphical language for reasoning about quantum computing and quantum information theory.As a complete graphical language, it incorporates a set of axioms rich enough to derive any equation of the underlying formalism.While completeness of the ZX-calculus has been established for qubits and the Clifford fragment of prime-dimensional qudits, universal completeness beyond two-level systems has remained unproven until now.In this paper, we present a proof establishing the completeness of finite-dimensional ZX-calculus, incorporating only the mixeddimensional Z-spider and the qudit X-spider as generators.Our approach builds on the completeness of another graphical language, the finite-dimensional ZW-calculus, with direct translations between these two calculi.By proving its completeness, we lay a solid foundation for the ZX-calculus as a versatile tool not only for quantum computation but also for various fields within finite-dimensional quantum theory.
There are various gate sets used for describing quantum computation. A particularly popular one consists of Clifford gates and arbitrary single-qubit phase gates. Computations in this gate set can be elegantly described by the ZX-calculus, a graphical language for a class of string diagrams describing linear maps between qubits. The ZX-calculus has proven useful in a variety of areas of quantum information, but is less suitable for reasoning about operations outside its natural gate set such as multi-linear Boolean operations like the Toffoli gate. In this paper we study the ZH-calculus, an alternative graphical language of string diagrams that does allow straightforward encoding of Toffoli gates and other more complicated Boolean logic circuits. We find a set of simple rewrite rules for this calculus and show it is complete with respect to matrices over Z[12] , which correspond to the approximately universal Toffoli+Hadamard gateset. Furthermore, we construct an extended version of the ZH-calculus that is complete with respect to matrices over any ring R where 1+1 is not a zero-divisor.
Recently, we gave a complete axiomatisation of the ZX-calculus for the overall pure qubit quantum mechanics. Based on this result, here we also obtain a complete axiomatisation of the ZX-calculus for the Clifford+T quantum mechanics by restricting the ring of complex numbers to its subring corresponding to the Clifford+T fragment resting on the completeness theorem of the ZW-calculus for arbitrary commutative ring. In contrast to the first complete axiomatisation of the ZX-calculus for the Clifford+T fragment, we have two new generators as features rather than novelties: the triangle can be employed as an essential component to construct a Toffoli gate in a very simple form, while the lambda box can be slightly extended to a generalised phase so that the generalised supplementarity (cyclotomic supplementarity ) is naturally seen as a special case of the generalised spider rule.