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:2103.06610 · Compositionality

Completeness of the ZH-calculus

Miriam Backens, Aleks Kissinger, Hector Miller-Bakewell, John van de Wetering, Sal Wolffs

Published Jul 12, 2023• 9 citations
arXivHTMLPDF

Abstract

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.

DOI
10.32408/compositionality-5-5

Related papers

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

Completeness of the Phase-free ZH-calculus

John van de Wetering, Sal Wolffs

The ZH-calculus is a graphical calculus for linear maps between qubits that allows a natural representation of the Toffoli+Hadamard gate set. The original version of the calculus, which allows every generator to be labelled by an arbitrary complex number, was shown to be complete by Backens and Kissinger. Even though the calculus is complete, this does not mean it allows one to easily reason in restricted settings such as is the case in quantum computing. In this paper we study the fragment of the ZH-calculus that is phase-free, and thus is closer aligned to physically implementable maps. We present a modified rule-set for the phase-free ZH-calculus and show that it is complete. We further discuss the minimality of this rule-set and we give an intuitive interpretation of the rules. Our completeness result follows by reducing to Vilmart's rule-set for the phase-free $Δ$ZX-calculus.

arXiv:1904.07545•Apr 16, 2019•5 citations

The Qudit ZH-Calculus: Generalised Toffoli+Hadamard and Universality

Patrick Roy, John van de Wetering, Lia Yeh

We introduce the qudit ZH-calculus and show how to generalise the phase-free qubit rules to qudits.We prove that for prime dimensions d, the phase-free qudit ZH-calculus is universal for matrices over the ring Z[e 2πi/d ].For qubits, there is a strong connection between phase-free ZH-diagrams and Toffoli+Hadamard circuits, a computationally universal fragment of quantum circuits.We generalise this connection to qudits, by finding that the two-qudit |0 -controlled X gate can be used to construct all classical reversible qudit logic circuits in any odd qudit dimension, which for qubits requires the three-qubit Toffoli gate.We prove that our construction is asymptotically optimal up to a logarithmic term.Twenty years after the celebrated result by Shi proving universality of Toffoli+Hadamard for qubits, we prove that circuits of |0 -controlled X and Hadamard gates are approximately universal for qudit quantum computing for any odd prime d, and moreover that phase-free ZH-diagrams correspond precisely to such circuits allowing postselections.

arXiv:2307.10095•Electronic Proceedings in Theoretical Computer Science•Aug 23, 2023•8 citations

An Algebraic Axiomatisation of ZX-calculus

Quanlong Wang

ZX-calculus is a graphical language for quantum computing which is complete in the sense that calculation in matrices can be done in a purely diagrammatic way. However, all previous universally complete axiomatisations of ZX-calculus have included at least one rule involving trigonometric functions such as sin and cos which makes it difficult for application purpose. In this paper we give an algebraic complete axiomatisation of ZX-calculus instead such that there are only ring operations involved for phases. With this algebraic axiomatisation of ZX-calculus, we are able to establish for the first time a simple translation of diagrams from another graphical language called ZH-calculus and to derive all the ZX-translated rules of ZH-calculus. As a consequence, we have a great benefit that all techniques obtained in ZH-calculus can be transplanted to ZX-calculus, which can't be obtained by just using the completeness of ZX-calculus.

arXiv:1911.06752•Electronic Proceedings in Theoretical Computer Science•Sep 6, 2021•14 citations

Picturing Counting Reductions with the ZH-Calculus

Tuomas Laakkonen, Konstantinos Meichanetzidis, John van de Wetering

Counting the solutions to Boolean formulae defines the problem #SAT, which is complete for the complexity class #P. We use the ZH-calculus, a universal and complete graphical language for linear maps which naturally encodes counting problems in terms of diagrams, to give graphical reductions from #SAT to several related counting problems. Some of these graphical reductions, like to #2SAT, are substantially simpler than known reductions via the matrix permanent. Additionally, our approach allows us to consider the case of counting solutions modulo an integer on equal footing. Finally, since the ZH-calculus was originally introduced to reason about quantum computing, we show that the problem of evaluating ZH-diagrams in the fragment corresponding to the Clifford+T gateset, is in FP^#P. Our results show that graphical calculi represent an intuitive and useful framework for reasoning about counting problems.

arXiv:2304.02524•Electronic Proceedings in Theoretical Computer Science•Aug 23, 2023•4 citations

Hypergraph Simplification: Linking the Path-sum Approach to the ZH-calculus

Louis Lemonnier, John van de Wetering, Aleks Kissinger

The ZH-calculus is a complete graphical calculus for linear maps between qubits that admits a straightforward encoding of hypergraph states and circuits arising from the Toffoli+Hadamard gate set. In this paper, we establish a correspondence between the ZH-calculus and the path-sum formalism, a technique recently introduced by Amy to verify quantum circuits. In particular, we find a bijection between certain canonical forms of ZH-diagrams and path-sum expressions. We then introduce and prove several new simplification rules for the ZH-calculus, which are in direct correspondence to the simplification rules of the path-sum formalism. The relatively opaque path-sum rules are shown to arise naturally from two powerful families of rewrite rules in the ZH-calculus. The first is the extension of the familiar graph-theoretic simplifications based on local complementation and pivoting to their hypergraph-theoretic analogues: hyper-local complementation and hyper-pivoting. The second is the graphical Fourier transform introduced by Kuijpers et al., which enables effective simplification of ZH-diagrams encoding multi-linear phase polynomials with arbitrary real coefficients.

arXiv:2003.13564•Electronic Proceedings in Theoretical Computer Science•Sep 6, 2021•16 citations
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.
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 ZH-calculus is a graphical calculus for linear maps between qubits that allows a natural representation of the Toffoli+Hadamard gate set. The original version of the calculus, which allows every generator to be labelled by an arbitrary complex number, was shown to be complete by Backens and Kissinger. Even though the calculus is complete, this does not mean it allows one to easily reason in restricted settings such as is the case in quantum computing. In this paper we study the fragment of the ZH-calculus that is phase-free, and thus is closer aligned to physically implementable maps. We present a modified rule-set for the phase-free ZH-calculus and show that it is complete. We further discuss the minimality of this rule-set and we give an intuitive interpretation of the rules. Our completeness result follows by reducing to Vilmart's rule-set for the phase-free ΔΔΔZX-calculus.
We introduce the qudit ZH-calculus and show how to generalise the phase-free qubit rules to qudits.We prove that for prime dimensions d, the phase-free qudit ZH-calculus is universal for matrices over the ring Z[e 2πi/d ].For qubits, there is a strong connection between phase-free ZH-diagrams and Toffoli+Hadamard circuits, a computationally universal fragment of quantum circuits.We generalise this connection to qudits, by finding that the two-qudit |0 -controlled X gate can be used to construct all classical reversible qudit logic circuits in any odd qudit dimension, which for qubits requires the three-qubit Toffoli gate.We prove that our construction is asymptotically optimal up to a logarithmic term.Twenty years after the celebrated result by Shi proving universality of Toffoli+Hadamard for qubits, we prove that circuits of |0 -controlled X and Hadamard gates are approximately universal for qudit quantum computing for any odd prime d, and moreover that phase-free ZH-diagrams correspond precisely to such circuits allowing postselections.
ZX-calculus is a graphical language for quantum computing which is complete in the sense that calculation in matrices can be done in a purely diagrammatic way. However, all previous universally complete axiomatisations of ZX-calculus have included at least one rule involving trigonometric functions such as sin and cos which makes it difficult for application purpose. In this paper we give an algebraic complete axiomatisation of ZX-calculus instead such that there are only ring operations involved for phases. With this algebraic axiomatisation of ZX-calculus, we are able to establish for the first time a simple translation of diagrams from another graphical language called ZH-calculus and to derive all the ZX-translated rules of ZH-calculus. As a consequence, we have a great benefit that all techniques obtained in ZH-calculus can be transplanted to ZX-calculus, which can't be obtained by just using the completeness of ZX-calculus.
Counting the solutions to Boolean formulae defines the problem #SAT, which is complete for the complexity class #P. We use the ZH-calculus, a universal and complete graphical language for linear maps which naturally encodes counting problems in terms of diagrams, to give graphical reductions from #SAT to several related counting problems. Some of these graphical reductions, like to #2SAT, are substantially simpler than known reductions via the matrix permanent. Additionally, our approach allows us to consider the case of counting solutions modulo an integer on equal footing. Finally, since the ZH-calculus was originally introduced to reason about quantum computing, we show that the problem of evaluating ZH-diagrams in the fragment corresponding to the Clifford+T gateset, is in FP^#P. Our results show that graphical calculi represent an intuitive and useful framework for reasoning about counting problems.
The ZH-calculus is a complete graphical calculus for linear maps between qubits that admits a straightforward encoding of hypergraph states and circuits arising from the Toffoli+Hadamard gate set. In this paper, we establish a correspondence between the ZH-calculus and the path-sum formalism, a technique recently introduced by Amy to verify quantum circuits. In particular, we find a bijection between certain canonical forms of ZH-diagrams and path-sum expressions. We then introduce and prove several new simplification rules for the ZH-calculus, which are in direct correspondence to the simplification rules of the path-sum formalism. The relatively opaque path-sum rules are shown to arise naturally from two powerful families of rewrite rules in the ZH-calculus. The first is the extension of the familiar graph-theoretic simplifications based on local complementation and pivoting to their hypergraph-theoretic analogues: hyper-local complementation and hyper-pivoting. The second is the graphical Fourier transform introduced by Kuijpers et al., which enables effective simplification of ZH-diagrams encoding multi-linear phase polynomials with arbitrary real coefficients.