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

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

Patrick Roy, John van de Wetering, Lia Yeh

Published Aug 23, 2023• 8 citations
arXivHTMLPDF

Abstract

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.

DOI
10.4204/eptcs.384.9

Related papers

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 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 for Arbitrary Finite Fields: Universality and Application

Dichuan

We propose a generalization of the graphical ZH calculus to qudits of prime-power dimensions $q = p^t$, implementing field arithmetic in arbitrary finite fields. This is an extension of a previous result by Roy which implemented arithmetic of prime-sized fields; and an alternative to a result by de Beaudrap which extended the ZH to implement cyclic ring arithmetic in $\mathbb Z / q\mathbb Z$ rather than field arithmetic in $\mathbb F_q$. We show this generalized ZH calculus to be universal over matrices $\mathbb C^{q^n} \to \mathbb C^{q^m}$ with entries in the ring $\mathbb Z[ω]$ where $ω$ is a $p$th root of unity. As an illustration of the necessity of such an extension of ZH for field rather than cyclic ring arithmetic, we offer a graphical description and proof for a quantum algorithm for polynomial interpolation. This algorithm relies on the invertibility of multiplication, and therefore can only be described in a graphical language that implements field, rather than ring, multiplication.

arXiv:2406.02219•Jun 4, 2024•0 citations

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

A Simple Proof that Toffoli and Hadamard are Quantum Universal

Dorit Aharonov

Recently Shi proved that Toffoli and Hadamard are universal for quantum computation. This is perhaps the simplest universal set of gates that one can hope for, conceptually; It shows that one only needs to add the Hadamard gate to make a 'classical' set of gates quantum universal. In this note we give a few lines proof of this fact relying on Kitaev's universal set of gates, and discuss the meaning of the result.

arXiv:quant-ph/0301040•Jan 9, 2003•122 citations

A Sound and Complete Equational Theory for 3-Qubit Toffoli-Hadamard Circuits

Matthew Amy, Neil J. Ross, Scott Wesley

We give a sound and complete equational theory for 3-qubit quantum circuits over the Toffoli-Hadamard gate set { X, CX, CCX, H }. That is, we introduce a collection of true equations among Toffoli-Hadamard circuits on three qubits that is sufficient to derive any other true equation between such circuits. To obtain this equational theory, we first consider circuits over the Toffoli-K gate set { X, CX, CCX, K }, where K = HxH. The Toffoli-Hadamard and Toffoli-K gate sets appear similar, but they are crucially different on exactly three qubits. Indeed, in this case, the former generates an infinite group of operators, while the latter generates the finite group of automorphisms of the well-known E8 lattice. We take advantage of this fact, and of the theory of automorphism groups of lattices, to obtain a sound and complete collection of equations for Toffoli-K circuits. We then extend this equational theory to one for Toffoli-Hadamard circuits by leveraging prior work of Li et al. on Toffoli-Hadamard operators.

arXiv:2407.11152•Electronic Proceedings in Theoretical Computer Science•Aug 9, 2024•0 citations
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.
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.
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 propose a generalization of the graphical ZH calculus to qudits of prime-power dimensions q=ptq = p^tq=pt, implementing field arithmetic in arbitrary finite fields. This is an extension of a previous result by Roy which implemented arithmetic of prime-sized fields; and an alternative to a result by de Beaudrap which extended the ZH to implement cyclic ring arithmetic in Z/qZ\mathbb Z / q\mathbb ZZ/qZ rather than field arithmetic in Fq\mathbb F_qFq​. We show this generalized ZH calculus to be universal over matrices Cqn→Cqm\mathbb C^{q^n} \to \mathbb C^{q^m}Cqn→Cqm with entries in the ring Z[ω]\mathbb Z[ω]Z[ω] where ωωω is a pppth root of unity. As an illustration of the necessity of such an extension of ZH for field rather than cyclic ring arithmetic, we offer a graphical description and proof for a quantum algorithm for polynomial interpolation. This algorithm relies on the invertibility of multiplication, and therefore can only be described in a graphical language that implements field, rather than ring, multiplication.
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.
We give a sound and complete equational theory for 3-qubit quantum circuits over the Toffoli-Hadamard gate set { X, CX, CCX, H }. That is, we introduce a collection of true equations among Toffoli-Hadamard circuits on three qubits that is sufficient to derive any other true equation between such circuits. To obtain this equational theory, we first consider circuits over the Toffoli-K gate set { X, CX, CCX, K }, where K = HxH. The Toffoli-Hadamard and Toffoli-K gate sets appear similar, but they are crucially different on exactly three qubits. Indeed, in this case, the former generates an infinite group of operators, while the latter generates the finite group of automorphisms of the well-known E8 lattice. We take advantage of this fact, and of the theory of automorphism groups of lattices, to obtain a sound and complete collection of equations for Toffoli-K circuits. We then extend this equational theory to one for Toffoli-Hadamard circuits by leveraging prior work of Li et al. on Toffoli-Hadamard operators.