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

Scalable Spider Nests (...Or How to Graphically Grok Transversal Non-Clifford Gates)

Aleks Kissinger, John van de Wetering

Published Aug 9, 2024• 7 citations
arXivHTMLPDF

Abstract

This is the second in a series of "graphical grokking" papers in which we study how stabiliser codes can be understood using the ZX-calculus. In this paper we show that certain complex rules involving ZX-diagrams, called spider nest identities, can be captured succinctly using the scalable ZX-calculus, and all such identities can be proved inductively from a single new rule using the Clifford ZX-calculus. This can be combined with the ZX picture of CSS codes, developed in the first "grokking" paper, to give a simple characterisation of the set of all transversal diagonal gates at the third level of the Clifford hierarchy implementable in an arbitrary CSS code.

DOI
10.4204/eptcs.406.4

Related papers

AND-gates in ZX-calculus: Spider Nest Identities and QBC-completeness

Anthony Munson, Bob Coecke, Quanlong Wang

In this paper we exploit the utility of the triangle symbol which has a complicated expression in terms of spider diagrams in ZX-calculus, and its role within the ZX-representation of AND-gates in particular. First, we derive spider nest identities which are of key importance to recent developments in quantum circuit optimisation and T-count reduction in particular. Then, using the same rule set, we prove a completeness theorem for quantum Boolean circuits (QBCs) whose rewriting rules can be directly used for a new method of T-count reduction. We give an algorithm based on this method and show that the results of our algorithm outperform the results of all the previous best non-probabilistic algorithms.

arXiv:1910.06818•Electronic Proceedings in Theoretical Computer Science•Sep 6, 2021•15 citations

Transversal diagonal logical operators for stabiliser codes

Mark A Webster, Armanda O. Quintavalle, Stephen D. Bartlett

Abstract Storing quantum information in a quantum error correction code can protect it from errors, but the ability to transform the stored quantum information in a fault tolerant way is equally important. Logical Pauli group operators can be implemented on Calderbank-Shor-Steane (CSS) codes, a commonly-studied category of codes, by applying a series of physical Pauli X and Z gates. Logical operators of this form are fault-tolerant because each qubit is acted upon by at most one gate, limiting the spread of errors, and are referred to as transversal logical operators. Identifying transversal logical operators outside the Pauli group is less well understood. Pauli operators are the first level of the Clifford hierarchy which is deeply connected to fault-tolerance and universality. In this work, we study transversal logical operators composed of single- and multi-qubit diagonal Clifford hierarchy gates. We demonstrate algorithms for identifying all transversal diagonal logical operators on a CSS code that are more general or have lower computational complexity than previous methods. We also show a method for constructing CSS codes that have a desired diagonal logical Clifford hierarchy operator implemented using single qubit phase gates. Our methods rely on representing operators composed of diagonal Clifford hierarchy gates as diagonal XP operators and this technique may have broader applications.

arXiv:2303.15615•New Journal of Physics•Sep 22, 2023•21 citations

The Qupit Stabiliser ZX-travaganza: Simplified Axioms, Normal Forms and Graph-Theoretic Simplification

Boldizsár Poór, Robert I. Booth, Titouan Carette +2 more

We present a smorgasbord of results on the stabiliser ZX-calculus for odd prime-dimensional qudits (i.e.qupits).We derive a simplified rule set that closely resembles the original rules of qubit ZX-calculus.Using these rules, we demonstrate analogues of the spider-removing local complementation and pivoting rules.This allows for efficient reduction of diagrams to the affine with phases normal form.We also demonstrate a reduction to a unique form, providing an alternative and simpler proof of completeness.Furthermore, we introduce a different reduction to the graph state with local Cliffords normal form, which leads to a novel layered decomposition for qupit Clifford unitaries.Additionally, we propose a new approach to handle scalars formally, closely reflecting their practical usage.Finally, we have implemented many of these findings in DiZX, a new open-source Python library for qudit ZX-diagrammatic reasoning.

arXiv:2306.05204•Electronic Proceedings in Theoretical Computer Science•Aug 23, 2023•19 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•119 citations

The ZX-Calculus is Canonical in the Heisenberg Picture for Stabilizer Quantum Mechanics

Jacob Biamonte, Aly Nasrallah

In 2008 Coecke and Duncan proposed the graphical ZX-calculus rewrite system which came to formalize reasoning with quantum circuits, measurements and quantum states. The ZX-calculus is sound for qubit quantum mechanics. Hence, equality of diagrams under ZX-equivalent transformations lifts to an equality of corresponding equations over matrices. Conversely, in 2014 Backens proved completeness, establishing that any derivation done in stabilizer quantum mechanics with matrices can be derived graphically using the ZX-calculus. A graphical rewrite system that is both confluent and also terminates uniquely is called canonical: Applying alternate sequences of rewrites to the same initial diagram, a rewrite system is confluent whenever all resulting diagrams can be manipulated to establish graphical equivalence. Here we show that a reduced ZX-rewrite system is already confluent in the Heisenberg picture for stabilizer quantum mechanics. Moreover, any application of a subset of ZX-rewrites terminates uniquely and irrespective of the order of term rewrites in the Heisenberg picture for stabilizer quantum mechanics. The ZX-system is hence Heisenberg-canonical for stabiliser quantum mechanics. For a stabilizer circuit on $n$-qubits with $l$ single-qubit gates and $g$ two-qubit gates, the circuit output can be derived graphically in the Heisenberg picture using no more than $(\frac{1}{2}\cdot g+l)\cdot n$ graphical rewrites, thereby providing a graphical proof of the Gottesman-Knill theorem. Finally, we establish that each stabilizer state described by a Clifford circuit gives rise to a non-negative parent Hamiltonian with $n+1$ terms and a one-dimensional kernel spanned by the corresponding stabilizer state. Such parent Hamiltonians can be derived with $\mathcal{O}(t\cdot n)$ graphical rewrites for a low energy state prepared by a $t$-gate Clifford circuit.

arXiv:2301.05717•Jan 13, 2023•1 citation

Finding diagonal logical gates in CSS codes and circuits

Andreas Bauer

Finding efficient schemes for non-Clifford logic or magic state preparation is one of the central challenges on the way to fault-tolerant quantum computation. Many of the proposed schemes rely on diagonal non-Clifford logical gates acting on CSS codes in space or decorating CSS-type syndrome-extraction circuits in spacetime. Here we propose and implement efficient algorithms to find all (spacetime) logical gates of a given CSS code (circuit) composed from a prescribed set of ansatz gates. Depending on the choice of ansatz gates, this means finding transversal gates, more general locality-preserving logical circuits, folding gates, or similar. While we focus on qubit diagonal gates in the Clifford hierarchy, we also discuss the generalization to arbitrary diagonal non-hierarchy gates, certain non-diagonal gates, as well as prime and composite-dimensional qudits. Our method works by rephrasing code-space preserving gates as the kernel of the ``pullback'' of the $X$ check matrix onto phase functions, which maps between finite abelian 2-groups. We implement a fast ``filtration'' method to find this kernel. The runtime for finding fault-tolerant logical gates in a qLDPC code with $O(n)$ qubits or a circuit with $O(n)$ gates in a naive dense implementation is $O(n^3)$, with potential for improvement making use of sparsity.

quant-pharXiv:2607.26477•Jul 30, 2026•5 citations
This is the second in a series of "graphical grokking" papers in which we study how stabiliser codes can be understood using the ZX-calculus. In this paper we show that certain complex rules involving ZX-diagrams, called spider nest identities, can be captured succinctly using the scalable ZX-calculus, and all such identities can be proved inductively from a single new rule using the Clifford ZX-calculus. This can be combined with the ZX picture of CSS codes, developed in the first "grokking" paper, to give a simple characterisation of the set of all transversal diagonal gates at the third level of the Clifford hierarchy implementable in an arbitrary CSS code.
In this paper we exploit the utility of the triangle symbol which has a complicated expression in terms of spider diagrams in ZX-calculus, and its role within the ZX-representation of AND-gates in particular. First, we derive spider nest identities which are of key importance to recent developments in quantum circuit optimisation and T-count reduction in particular. Then, using the same rule set, we prove a completeness theorem for quantum Boolean circuits (QBCs) whose rewriting rules can be directly used for a new method of T-count reduction. We give an algorithm based on this method and show that the results of our algorithm outperform the results of all the previous best non-probabilistic algorithms.
Abstract Storing quantum information in a quantum error correction code can protect it from errors, but the ability to transform the stored quantum information in a fault tolerant way is equally important. Logical Pauli group operators can be implemented on Calderbank-Shor-Steane (CSS) codes, a commonly-studied category of codes, by applying a series of physical Pauli X and Z gates. Logical operators of this form are fault-tolerant because each qubit is acted upon by at most one gate, limiting the spread of errors, and are referred to as transversal logical operators. Identifying transversal logical operators outside the Pauli group is less well understood. Pauli operators are the first level of the Clifford hierarchy which is deeply connected to fault-tolerance and universality. In this work, we study transversal logical operators composed of single- and multi-qubit diagonal Clifford hierarchy gates. We demonstrate algorithms for identifying all transversal diagonal logical operators on a CSS code that are more general or have lower computational complexity than previous methods. We also show a method for constructing CSS codes that have a desired diagonal logical Clifford hierarchy operator implemented using single qubit phase gates. Our methods rely on representing operators composed of diagonal Clifford hierarchy gates as diagonal XP operators and this technique may have broader applications.
We present a smorgasbord of results on the stabiliser ZX-calculus for odd prime-dimensional qudits (i.e.qupits).We derive a simplified rule set that closely resembles the original rules of qubit ZX-calculus.Using these rules, we demonstrate analogues of the spider-removing local complementation and pivoting rules.This allows for efficient reduction of diagrams to the affine with phases normal form.We also demonstrate a reduction to a unique form, providing an alternative and simpler proof of completeness.Furthermore, we introduce a different reduction to the graph state with local Cliffords normal form, which leads to a novel layered decomposition for qupit Clifford unitaries.Additionally, we propose a new approach to handle scalars formally, closely reflecting their practical usage.Finally, we have implemented many of these findings in DiZX, a new open-source Python library for qudit ZX-diagrammatic reasoning.
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.
In 2008 Coecke and Duncan proposed the graphical ZX-calculus rewrite system which came to formalize reasoning with quantum circuits, measurements and quantum states. The ZX-calculus is sound for qubit quantum mechanics. Hence, equality of diagrams under ZX-equivalent transformations lifts to an equality of corresponding equations over matrices. Conversely, in 2014 Backens proved completeness, establishing that any derivation done in stabilizer quantum mechanics with matrices can be derived graphically using the ZX-calculus. A graphical rewrite system that is both confluent and also terminates uniquely is called canonical: Applying alternate sequences of rewrites to the same initial diagram, a rewrite system is confluent whenever all resulting diagrams can be manipulated to establish graphical equivalence. Here we show that a reduced ZX-rewrite system is already confluent in the Heisenberg picture for stabilizer quantum mechanics. Moreover, any application of a subset of ZX-rewrites terminates uniquely and irrespective of the order of term rewrites in the Heisenberg picture for stabilizer quantum mechanics. The ZX-system is hence Heisenberg-canonical for stabiliser quantum mechanics. For a stabilizer circuit on nnn-qubits with lll single-qubit gates and ggg two-qubit gates, the circuit output can be derived graphically in the Heisenberg picture using no more than (12⋅g+l)⋅n(\frac{1}{2}\cdot g+l)\cdot n(21​⋅g+l)⋅n graphical rewrites, thereby providing a graphical proof of the Gottesman-Knill theorem. Finally, we establish that each stabilizer state described by a Clifford circuit gives rise to a non-negative parent Hamiltonian with n+1n+1n+1 terms and a one-dimensional kernel spanned by the corresponding stabilizer state. Such parent Hamiltonians can be derived with O(t⋅n)\mathcal{O}(t\cdot n)O(t⋅n) graphical rewrites for a low energy state prepared by a ttt-gate Clifford circuit.
Finding efficient schemes for non-Clifford logic or magic state preparation is one of the central challenges on the way to fault-tolerant quantum computation. Many of the proposed schemes rely on diagonal non-Clifford logical gates acting on CSS codes in space or decorating CSS-type syndrome-extraction circuits in spacetime. Here we propose and implement efficient algorithms to find all (spacetime) logical gates of a given CSS code (circuit) composed from a prescribed set of ansatz gates. Depending on the choice of ansatz gates, this means finding transversal gates, more general locality-preserving logical circuits, folding gates, or similar. While we focus on qubit diagonal gates in the Clifford hierarchy, we also discuss the generalization to arbitrary diagonal non-hierarchy gates, certain non-diagonal gates, as well as prime and composite-dimensional qudits. Our method works by rephrasing code-space preserving gates as the kernel of the ``pullback'' of the XXX check matrix onto phase functions, which maps between finite abelian 2-groups. We implement a fast ``filtration'' method to find this kernel. The runtime for finding fault-tolerant logical gates in a qLDPC code with O(n)O(n)O(n) qubits or a circuit with O(n)O(n)O(n) gates in a naive dense implementation is O(n3)O(n^3)O(n3), with potential for improvement making use of sparsity.