109
Part Three · A · Foundations of quantum information

ZX-calculus and graphical reasoning

Matrices are a clumsy way to reason about circuits: a three-qubit gate is 8 × 8, a ten-qubit one has a million entries. Bob Coecke and Ross Duncan proposed in 2008 a different language: draw the circuit as a network of coloured dots, called spiders, joined by wires, and reason by redrawing. A handful of rewrite rules replace pages of algebra. In this language, wires can be bent and spiders merged freely, and proofs become pictures that anyone can check by eye. Its practical payoff is circuit optimization, cutting the expensive T gates of Chapter 108.

On the plate: spiders, and the rules that let you redraw them. Every rule is checked against the matrices.

Spiders

A Z-spider, drawn here in amber (green in most papers), with phase α\alpha, mm input wires and nn output wires is the linear map ∣0⋯0⟩⟨0⋯0∣+eiα∣1⋯1⟩⟨1⋯1∣|0\cdots0\rangle\langle0\cdots0| + e^{i\alpha}|1\cdots1\rangle\langle1\cdots1|. An X-spider, drawn red, is the same in the ∣±⟩|\pm\rangle basis. With one input and one output, a Z-spider is the phase gate diag(1,eiα)\mathrm{diag}(1, e^{i\alpha}): S is a Z-spider with α=π/2\alpha = \pi/2, T with π/4\pi/4. A Hadamard is drawn as a small yellow box. Every circuit translates into a diagram; CNOT is a Z-spider on the control joined to an X-spider on the target. Established

The rules

Choose a rule: : two connected spiders of the same colour merge, adding phases; : Hadamards on every leg turn a Z-spider into an X-spider; : a phase-free spider with one in and one out is a plain wire; : an X-spider with phase π passes through a Z-spider, flipping its phase. The plate shows the rule and the numerical check: the largest difference between the matrices of the two sides.

The striking principle is that only connectivity matters: you can bend, stretch and rearrange wires and the diagram means the same map. Teleportation (Chapter 103), drawn this way, becomes a wire straightened out.

Completeness

Are the rules enough? For Clifford diagrams, yes: Miriam Backens proved in 2014 that any two diagrams denoting the same map can be rewritten into each other. For the universal Clifford+T fragment, completeness was established in 2018 by Emmanuel Jeandel, Simon Perdrix and Renaud Vilmart, and by Kang Feng Ng and Quanlong Wang, with a few extra rules. So the graphical calculus is a complete language for quantum circuits. The Gottesman–Knill theorem (Chapter 108) has a short graphical proof: Clifford diagrams always simplify to a normal form of size polynomial in the qubits. Established

Cutting T gates

Translate a circuit into ZX, simplify by fusing spiders and removing redundant ones, then extract a circuit again. Phases of non-Clifford spiders that meet during simplification merge, and pairs of T gates become S gates, which are cheap. Aleks Kissinger and John van de Wetering’s 2020 method, implemented in the PyZX package, reduced T counts in standard benchmark circuits, in some cases by large fractions, beyond what earlier methods found. Since T gates dominate the cost of fault-tolerant computation (Chapter 140), this saves real hardware.

What you now have

Z and X spiders, circuits as diagrams, the main rewrite rules and their matrix checks, “only connectivity matters”, completeness results, the graphical proof of Gottesman–Knill, and T-count reduction.

· · ·

Three questions to carry with you.

What does spider fusion do to phases?tap
Adds them.
How do you turn a Z-spider into an X-spider?tap
Put a Hadamard on every leg.
Why does ZX help fault-tolerant computing?tap
Simplification merges T phases, reducing the expensive T count.

And one to work out. Fuse two Z-spiders with phases π/4\pi/4 and π/4\pi/4. What is the resulting phase, in units of π\pi?

phase / π =

Sources: B. Coecke and R. Duncan, New J. Phys. 13, 043016 (2011) (from ICALP 2008). B. Coecke and A. Kissinger, Picturing Quantum Processes (2017). M. Backens, New J. Phys. 16, 093021 (2014). E. Jeandel, S. Perdrix and R. Vilmart, LICS 2018; K. F. Ng and Q. Wang, arXiv:1801.07993. A. Kissinger and J. van de Wetering, Phys. Rev. A 102, 022406 (2020). R. Duncan et al., Quantum 4, 279 (2020). J. van de Wetering, arXiv:2012.13966. Checked in the page: each rule’s two sides agree to machine precision as 2 × 2 or 4 × 4 matrices.

Next · Chapter 110
Oracle model and query complexity: Deutsch–Jozsa, Bernstein–Vazirani

A classical computer needs 2ⁿ⁻¹+1 questions. A quantum one needs 1. A randomized classical guesser needs only a handful.

Turn the page