PaperlayerView exact revision on arXiv

Source-linked AI summary

ZX-calculus for the working quantum computer scientist

John van de Wetering

arXiv:2012.13966v1quant-ph

TL;DR

The paper addresses the need for an accessible introduction and concise literature overview of the increasingly used ZX-calculus. It explains the graphical language and its rewriting, surveys applications and extensions, and reports that the calculus can represent and reason about broad classes of quantum computation. The review also notes practical limits: universal representability does not guarantee convenient representations or efficient conversion to circuits.

  • Problem

    The ZX-calculus lacked a concise overview while its uses expanded across quantum-computing applications, and practitioners needed accessible guidance for using it in daily reasoning.

  • Method

    The paper combines a gentle introduction to diagrams and rewriting with a literature review covering Clifford computation, Toffoli gates, completeness, categorical origins, and extensions.

  • Results

    The review establishes that ZX-diagrams can represent any linear map between qubits and surveys completeness results supporting diagrammatic proofs of linear-map equalities.

  • Takeaways & Limitations

    ZX-calculus can serve as a practical graphical tool for reasoning about quantum circuits and states, with applications including optimisation, measurement-based computation, and surface-code reasoning.

  • Takeaways & Limitations

    Representing any linear map does not ensure a convenient diagram, and efficiently converting a unitary ZX-diagram into a circuit is likely difficult because unitarity is a global property.

Abstract

from arXiv · show

The ZX-calculus is a graphical language for reasoning about quantum computation that has recently seen an increased usage in a variety of areas such as quantum circuit optimisation, surface codes and lattice surgery, measurement-based quantum computation, and quantum foundations. The first half of this review gives a gentle introduction to the ZX-calculus suitable for those familiar with the basics of quantum computing. The aim here is to make the reader comfortable enough with the ZX-calculus that they could use it in their daily work for small computations on quantum circuits and states. The latter sections give a condensed overview of the literature on the ZX-calculus. We discuss Clifford computation and graphically prove the Gottesman-Knill theorem, we discuss a recently introduced extension of the ZX-calculus that allows for convenient reasoning about Toffoli gates, and we discuss the recent completeness theorems for the ZX-calculus that show that, in principle, all reasoning about quantum computation can be done using ZX-diagrams. Additionally, we discuss the categorical and algebraic origins of the ZX-calculus and we discuss several extensions of the language which can represent mixed states, measurement, classical control and higher-dimensional qudits.

1 Introduction

The paper introduces ZX-diagrams and graphical rewriting, then surveys the calculus’s applications, literature, completeness results, extensions, and practical resources. It aims to make readers comfortable using ZX-calculus for everyday quantum-computing reasoning.

  • ZX-diagrams graphically represent linear maps between qubits, while rewrite rules enable diagrammatic reasoning about those maps.
  • ZX-calculus applications include measurement-based quantum computation, circuit optimisation, equality validation, surface codes, lattice surgery, and quantum error-correcting codes.
  • The review targets readers with basic quantum-computing knowledge and seeks to provide both an accessible introduction and a concise literature overview.
  • The review covers Clifford computation, a diagrammatic proof of the Gottesman–Knill theorem, measurement-based computation, and transformations between ZX-diagrams and circuits.
  • Later sections discuss categorical origins, Toffoli gates through the ZH-calculus, completeness results, mixed processes, classical control, and higher-dimensional qudits.
  • PyZX supports conversion between quantum circuits and ZX-diagrams and automated diagram simplification, whereas Quantomatic is no longer actively developed.

2 Quantum circuits vs ZX-diagrams

This section contrasts circuit notation with ZX-diagrams and introduces graphical rules for translating, simplifying, and reasoning about quantum computations. It develops colour-based spider rules, Hadamard transformations, and the calculus’s universality.

  • Quantum circuits use horizontal qubit wires with gates, whereas ZX-diagrams provide a graphical representation of the same linear maps.
  • ZX-calculus translates standard gates into coloured dots and Hadamard boxes, while wires represent qubits and time flows from left to right in circuit notation.
  • Dots of the same colour commute and connected same-colour dots fuse, replacing collections of circuit-specific identities with general graphical rules.
  • A single-wire dot copies through an opposite-colour dot, two-wire dots can be removed, and wires have no directionality in ZX-diagrams.
  • Hadamard gates are self-inverse and conjugate Z-spiders into X-spiders, equivalently commuting through a dot while changing its colour.
  • ZX-diagrams yield a symmetric representation of CZ and already contain the ingredients to represent any linear map between qubits.

3 ZX-diagrams

ZX-diagrams are graphical representations of linear maps between qubits, built from spiders and composed horizontally or vertically. They can represent every 2^n × 2^m complex matrix, although useful maps may not always have simple diagrams.

  • Spiders: Z-spiders encode phases in the Z eigenbasis, while X-spiders use the X eigenbasis and corresponding states |0⟩, |1⟩, |+⟩, and |−⟩.Their phases appear as eiα on the matching basis component.
  • Spiders: A 1-input, 1-output Z-spider is an RZ(α) gate, and the analogous X-spider is an RX(α) gate; setting α = π yields the Pauli Z and X matrices.This connects spider phases directly to familiar single-qubit gates.
  • Building ZX-diagrams: ZX-diagrams represent linear maps between qubits using generators connected by wires, with composition corresponding to matrix multiplication and stacking corresponding to tensor products.Each wire carries a two-dimensional index, and connected wires represent tensor contractions.
  • Semantics: A diagram with n inputs and m outputs denotes a matrix with 2^n columns and 2^m rows; no-input diagrams are states, and no-output diagrams are effects.A diagram with neither inputs nor outputs is a complex scalar.
  • Graphical structure: ZX-diagrams are tensor networks equipped with rewrite rules acting directly on the network, distinguishing them from tensor-network notation alone.The rules support graphical reasoning in place of many matrix calculations.
  • Universality: The ZX-calculus is universal: every complex matrix of size 2^n × 2^m can be represented, but representations of useful maps such as Toffoli may be cumbersome.A derived generator is introduced later to make Toffoli representations more convenient.

4 The ZX-calculus

The ZX-calculus turns diagrammatic notation into a rewrite language for proving equalities of quantum maps. Its rules include spider fusion, identity removal, copy and π-commutation rules, bialgebraic interactions, and sound replacement within larger diagrams.

  • Core rewrite rules: Spider fusion merges connected same-colour spiders and adds their phases modulo 2π.It generalises the addition of rotations around the same Bloch-sphere axis.
  • Core rewrite rules: Identity removal eliminates zero-phase 1-input, 1-output spiders and, with fusion, expresses inverse rotations as phase negation.The rule also removes self-loops when combined with fusion.
  • Copy and π-commutation: State-copy rules describe how Pauli eigenstates and operators interact with spiders, including copying |0⟩, |1⟩, |+⟩, and |−⟩ through appropriate spiders.The colour-flipped versions provide the corresponding X-spider rules.
  • Copy and π-commutation: State-copy rules apply only when the copied spider has phase 0 or π; the analogous rule does not hold for other phases.This phase restriction is an essential condition when simplifying diagrams.
  • Soundness: Rewrite rules are sound because equal matrices remain equal under tensoring and composition, allowing a diagram to replace an equal subdiagram inside any larger diagram.This follows from the compositional semantics of ZX-diagrams.
  • Bialgebra and Hopf rules: Bialgebra and Hopf interactions reduce connected opposite-colour spiders, with n connecting wires reduced to n mod 2 and enabling the derivation that three CNOTs form a SWAP.The bialgebra rule itself requires zero phases, while a π-phase modification can be obtained using π-copy rules.

5 Some example derivations

Worked examples show how ZX rewrite rules simplify circuits and prove properties of states, operators, and protocols. The examples also illustrate classical-control variables, automation with PyZX, and phase-gadget representations.

  • Circuit and state identities: ZX simplification proves that a circuit produces the three-qubit GHZ state |000⟩ + |111⟩.The derivation begins by fusing same-colour spiders and removing identities, then simplifies the resulting state diagram.
  • Pauli propagation: Pauli propagation through a circuit can be derived with spider fusion and π-copy rules; the worked example transforms X⊗Z into Y⊗id.The graphical derivation makes the destination of each Pauli operator visible.
  • Classical control: Measurement-based classical control is represented by a Boolean variable for the measurement outcome, allowing a diagrammatic proof of magic-state injection correctness.The variable selects branches and controls whether the correction is applied.
  • Classical control: The same Boolean-variable technique represents teleportation measurement outcomes and supports a diagrammatic proof of the protocol.The derivation uses phase periodicity, including that 2bπ is 0 modulo 2π.
  • Systematic simplification: Systematic simplification uses fusion, identity removal, state copying, Hopf reduction, and Hadamard movement to expose entanglement structure.In the worked circuit, the resulting state reveals one unentangled qubit and a GHZ state on the remainder.
  • Automation: PyZX can verify and automatically simplify diagrams that are cumbersome to rewrite manually, doing the demonstrated simplification nearly instantaneously.The library supports circuit-to-diagram conversion and automated simplification.
  • Phase gadgets: Phase gadgets represent parity-controlled phases and correspond to circuit constructions using a CNOT ladder, a phase operation, and an inverse ladder.This connects a compact diagrammatic gadget to a standard circuit implementation.

6 Clifford computation

The Clifford fragment connects stabiliser-state structure with graph states and admits systematic ZX-diagram simplification. These tools yield diagrammatic proofs of Gottesman–Knill and completeness for Clifford computation.

  • Clifford states arise by applying Clifford unitaries to |0 · · · 0⟩ and support error correction, measurement-based computation, and quantum-information protocols despite not being universal.
  • Clifford linear maps are precisely the ZX-diagrams whose phases are multiples of π/2.The fragment includes diagrams for |0⟩, ⟨0|, CNOT, Hadamard, and S, and is closed under composition.
  • Graph states: A graph state is prepared from |+ · · · +⟩ by applying CZ gates for graph edges, which translate into Z-spiders linked by Hadamard-edges.Vertices become Z-spiders with outputs, while graph edges become connections carrying Hadamard structure.
  • Graph states: Every Clifford state equals a graph state acted on by local single-qubit Clifford unitaries.The local Cliffords can be composed from Hadamard and S gates and represented by phase gates with phases that are multiples of π/2.
  • Graph-like diagrams: Graph-like diagrams contain only Z-spiders connected by single Hadamard-edges and can be obtained by converting spiders, cancelling Hadamards, fusing spiders, and removing loops or duplicate edges.The resulting representation is specified by a simple graph, vertex phases, and input/output attachments.
  • Simplification and completeness: Clifford ZX-diagram simplification gives both a diagrammatic Gottesman–Knill proof and completeness of the Figure 1 rules for the Clifford fragment.An efficient GSLC comparison procedure uses local complementations to relate equal Clifford diagrams.

7 ZX-diagrams, categorically

Categorically, ZX-diagrams form a symmetric monoidal structure whose morphisms are interpreted as qubit linear maps. Universality corresponds to fullness, while completeness concerns faithfulness and requires extended rulesets here.

  • The ZX-calculus is treated as a symmetric monoidal category, allowing diagrams to compose sequentially and in parallel through tensor products.Its symmetry makes A ⊗ B canonically isomorphic to B ⊗ A.
  • In the category ZX, natural numbers denote parallel wires, ZX-diagrams are morphisms, and tensoring objects is addition.A morphism from n to m is a diagram with n inputs and m outputs.
  • ZX-diagram cups and caps provide compact-closed structure, allowing inputs to be transformed into outputs and vice versa.
  • The interpretation of a ZX-diagram is a functor from ZX to Qubit that maps each diagram to the linear map it implements.Qubit interprets n as the vector space (C^2)^⊗n and its morphisms as linear maps.
  • Universality of the ZX-calculus is fullness of the interpretation functor, meaning every qubit linear map has a representing ZX-diagram.
  • Rewriting and completeness: Completeness asks whether diagrams representing the same linear map can be rewritten into one another; the basic Figure 1 rules are not complete, though extended rulesets exist.The interpretation functor is therefore not faithful for the basic ruleset.
  • Algebraic structure: Z-spiders form a commutative special dagger-Frobenius algebra, and the spider equation characterises an orthonormal basis diagrammatically.

8 Toffoli gates and the ZH-calculus

The section extends the ZX-calculus with H-boxes to represent and reason about Toffoli and other multiply-controlled gates. It develops rewrite rules, controlled-unitary constructions, Fourier-transform connections, and completeness results for the resulting calculus.

  • 8.1 H-boxes: H-boxes split the coherent AND gate into two components that retain the symmetries of spiders, enabling concise diagrammatic representations.The resulting AND construction uses just two diagrammatic generators.
  • 8.1 H-boxes: An H-box is an arbitrary-arity matrix whose entries are 1 except for the bottom-right entry, labelled by an arbitrary complex number a.When a = −1, the 1-input 1-output H-box is a rescaled Hadamard.
  • 8.1 H-boxes: H-boxes construct the coherent AND gate and therefore yield a direct diagrammatic construction of the Toffoli gate.The resulting action is |x, y, z⟩ 7→ |x, y, (x · y) ⊕ z⟩.
  • 8.2 The ZH-calculus: The ZH-calculus adds rewrite rules motivated by AND gates and by relations between H-boxes with different labels.The phase-free rules, together with selected ZX rules, are complete for the Hadamard-Toffoli fragment.
  • 8.2 The ZH-calculus: Adding multiply, average, and introduction rules makes the ZH-calculus complete for all diagrams and therefore universal for qubit linear maps.The section also uses H-boxes to represent controlled unitaries and derive Toffoli optimisations.
  • 8.3 Controlled unitaries: The section connects H-boxes with Fourier transforms of semi-Boolean functions and uses them to derive controlled-Hadamard and CCZ constructions.A CCZ decomposition into the Clifford+T gate set is obtained using H-boxes and phase gates.

9 Completeness

The paper explains completeness as the ability of rewrite rules to prove every equality between diagrams representing the same linear map, surveying results across several fragments and axiomatisations. It traces how ZW-inspired and direct approaches culminated in complete calculi for universal quantum computation, while noting persistent complexity in non-linear phase relations and side conditions.

  • 9 Completeness: Completeness means that any two diagrams representing the same linear map can be connected by a sequence of allowed rewrites.The specific rewrite rules determine whether a calculus is complete, so multiple ZX-calculi exist.
  • 9 Completeness: The core ZX rules are complete for the Clifford fragment, where spider phases are restricted to multiples of π/2.Completeness has also been studied for Clifford+T and universal fragments.
  • 9.2 W-states and the ZW-calculus: The ZW-calculus is complete and universal for matrices over the integers, including Toffoli and Hadamard gates up to normalisation.Its rules were instrumental in early completeness results.
  • 9.2 W-states and the ZW-calculus: Extending ZW to an arbitrary commutative ring enables arithmetic within the calculus; over the complex numbers, this yields a complete calculus for universal quantum computing.The algebraic ZX-calculus similarly supports arbitrary rings and, additionally, semirings.
  • 9.3 The Oxford completeness results: The Oxford and Nancy approaches established completeness for major fragments using different trade-offs: many small axioms versus fewer but larger, harder-to-interpret axioms.The Oxford universal-fragment rules presented here were later described as more complex than the simplified proposal.
  • 9.5 Completeness from Euler decompositions: Vilmart’s simplified result makes the universal ZX-calculus complete by adding one non-linear rule expressing equivalent Euler decompositions of a single-qubit rotation.The same rule, together with the standard rules, suffices to derive the four new Nancy rules and prove completeness.
  • 9.5 Completeness from Euler decompositions: The standard rules encode Clifford behavior, while the additional Euler-decomposition rule supplies the rotational structure needed for complete qubit reasoning.The rule’s complicated phase relationship and side condition reduce the elegance of graphical reasoning.

10 Extensions of the language

The ZX-calculus can be extended to represent mixed processes, classical interactions, and higher-dimensional qudits. Discarding supports mixed-process reasoning, while doubled diagrams and group-based spiders extend the language to quantum-classical systems and arbitrary dimensions.

  • 10.1 Mixed states, decoherence and discarding: Adding a discarding generator extends ZX-diagrams from pure processes to mixed and decohered quantum processes.Discarding represents the partial trace, which enables mixed-process representations.
  • 10.1 Mixed states, decoherence and discarding: The universal ZX-calculus with discarding can represent any mixed quantum process, although partial decoherence lacks a known straightforward representation.The completeness extension described for discarding applies to the universal fragment, not the Clifford+T fragment.
  • 10.2 Quantum-classical interaction: Discarding a quantum spider produces a classical spider, allowing decoherence and same-basis measurement to encode quantum-classical interactions.Classical wires may be represented explicitly as thin wires, while quantum wires are thick in the doubled representation.
  • 10.3 ZX-calculus for qudits: Strongly complementary spiders in n dimensions correspond to an n-element finite abelian group, and their construction works in every dimension.The associated X-spider combines group-labelled basis states using the group operation.
  • 10.3 ZX-calculus for qudits: Higher-dimensional ZX-diagrams require group-specific treatment of Hadamard-like generators, while diagrams over any dimension remain universal for linear maps between qudits.For composite dimensions, spiders can be decomposed using products of cyclic groups; prime-dimensional cases use Fourier-transformed bases.

11 Concluding remarks

The paper concludes that the ZX-calculus provides an introduction, literature review, and practical graphical language for quantum-computation reasoning. Its use expanded substantially after completeness results, especially in non-unitary settings such as MBQC and surface-code computation.

  • 11 Concluding remarks: The review covers ZX-calculus foundations, Clifford circuits, Toffoli gates, categorical origins, completeness, mixed processes, and qudits.It presents both an introduction to the language and a survey of major extensions and results.
  • 11 Concluding remarks: Around 60 works appeared in both the first decade after the 2007 preprint and the period 2018–2020.The paper describes this as a dramatic increase following the 2017 completeness results.
  • 11 Concluding remarks: Recent applications prominently include measurement-based quantum computation, circuit optimisation, and surface-code quantum computing.Many recent works concern non-unitary models, including MBQC and surface-code quantum computing.
  • 11 Concluding remarks: Graphical rewrite rules may also support learning quantum computing by making computational identities and properties easier to remember.

A ZX-calculus cheatsheets

The appendices provide cheatsheets designed for reference and separate printing.

  • A ZX-calculus cheatsheets: The appendices contain several pages of cheatsheets intended for reference and separate printing.

A.1 Generators and their matrices

The appendix records matrix forms for the Z- and X-spider families, including their phase-dependent computational-basis expressions.

  • A.1 Generators and their matrices: The Z-spider family is represented by a phase-weighted sum of |0 · · · 0⟩⟨0 · · · 0| and |1 · · · 1⟩⟨1 · · · 1|.
  • A.1 Generators and their matrices: The X-spider family is represented analogously in the |+⟩ and |−⟩ basis with phase e^iα on the all-|−⟩ component.

A.2 Unitaries

This section lists common unitaries and their ZX-calculus representations, including an Ising interaction phase gadget. It also specifies how to obtain adjoints graphically.

  • The unitary table gives common names and ZX-calculus representations for listed unitaries.
  • An adjoint is obtained by horizontally flipping the diagram, negating phases, and conjugating any global scalar factor.
  • The Ising interaction phase gadget appears among the listed unitary representations.

A.3 Basic Rewrite rules

The basic ZX rewrite rules simplify diagrams through spider fusion, identity and Hadamard cancellation, phase propagation, copying, colour interchange, and complementary algebraic transformations.

  • The rewrite table applies with colours interchanged and inputs and outputs permuted arbitrarily.
  • Adjacent same-colour spiders fuse, adding their phases.
  • A phase-free spider of arity 2 can be removed, and two consecutive Hadamard gates cancel.
  • A π phase copies through an opposite-colour spider and flips that spider's phase, while computational basis states |0⟩ and |1⟩ copy through a spider.
  • Hadamard gates relate the two spider types and can be commuted through a spider; bialgebra expresses strong complementarity.
  • Multiple wires between opposite-colour spiders can be removed pairwise, while commuting adjacent phase-free Z- and X-spiders may introduce many more spiders.

A.4 Derived rewrite rules

The derived rewrite rules extend basic ZX transformations with Hadamard self-loop removal, connectivity-disconnecting identities, phase-gadget fusion, and local complementations.

  • The derived-rule table presents additional transformations for ZX-diagrams, with the table applying under the stated diagram symmetries.
  • A Hadamard gate connected twice to one spider is absorbed by introducing a π phase.
  • Multiple Hadamard-edges between same-type spiders can be disconnected.
  • One rule relates two representations of the Pauli Y eigenstates.
  • Phase gadgets with the same neighbouring spiders fuse, while π/2 or paired π spiders can be removed by complementing neighbour connectivity.

A.5 ZX-calculus full cheatsheet

The full ZX-calculus cheatsheet states the scope of the rewrite rules and provides their compact graphical forms.

  • The listed rewrite rules hold for all real α, β, α_i, β_j, and γ_k, and for a ∈ {0, 1}, up to a global non-zero scalar.
  • The cheatsheet includes compact graphical rewrite expressions for the general rules.

A.6 Circuit identities

This section presents circuit identities for common gates and phase gadgets, then introduces additional derived generators and their relations to Z- and X-spiders.

  • Circuit identities: Circuit identities connect X, Z, S, V, H, CNOT, CZ gates, and phase gadgets up to a global non-zero scalar.The identities hold for arbitrary real phases and remain valid under colour exchange, input-output reversal, or phase negation.
  • Circuit identities: One identity represents a Pauli gadget of the form exp(−iα 2 Z ⊗Y ).The text directs readers to further rules and Pauli gadgets for additional context.
  • Additional generators: Additional ZX-diagram generators include the triangle, λ-box, H-box, and W-spider.Their rules are given in separate figures and sections, and the generators are related to Z- and X-spiders.
  • Additional generators: H-boxes sum over all bitstrings, whereas W-spiders sum only over concatenated bitstrings containing exactly one 1.The H-box and W-spider definitions use bitstrings x⃗ and y⃗.
  • Additional generators: Further H-box identities hold up to a global non-zero scalar for arbitrary real α and complex a and b.
Loading 2012.13966v1…