Contents

About This Version
1 Introduction
1.1 How to read this book
1.1.1 From scratch
1.1.2 Coming from Picturing Quantum Processes
1.1.3 Coming from another quantum computing background
1.2 Overview
2 The Quantum Circuit Model
2.1 Preliminaries
2.1.1 Some things you should know about complex numbers
2.1.2 Hilbert spaces
2.1.3 Types of linear maps
2.1.4 Tensors and the tensor product
2.1.5 Sums and diagrams
2.1.6 Tensor networks and string diagrams
2.1.7 Cups and caps
2.2 A bluffer’s intro to quantum theory
2.2.1 Quantum states
2.2.2 Qubits and the Bloch sphere
2.2.3 Unitary evolution
2.2.4 Measurements and the Born rule
2.3 Gates and circuits
2.3.1 Classical computation with quantum gates
2.3.2 Pauli and phase gates
2.3.3 Hadamard gates
2.3.4 Controlled unitaries
2.3.5 (Approximate) universality
2.3.6 Quantum circuit notation
2.4 A dash of quantum algorithms
2.5 A dash of complexity theory
2.5.1 Asymptotic growth
2.5.2 Classical complexity classes
2.5.3 BQP
2.6 Summary: What to remember
2.7 Advanced Material*
2.7.1 Quantum mixed states and channels*
2.8 References and further reading
3 The ZX-Calculus
3.1 ZX-diagrams
3.1.1 Spiders
3.1.2 Defining ZX-diagrams
3.1.3 Symmetries
3.1.4 Scalars
3.1.5 Adjoints, transpose and conjugate
3.1.6 Hadamards
3.1.7 Universality
3.2 The rules of the ZX-calculus
3.2.1 Spider fusion and identity removal
3.2.2 The copy rule and π-commutation
3.2.3 Colour changing
3.2.4 Strong complementarity
3.2.5 Euler decomposition
3.3 ZX in action
3.3.1 Magic state injection
3.3.2 Teleportation
3.3.3 Detecting entanglement
3.3.4 The Bernstein-Vazirani algorithm
3.4 Extracting circuits from ZX-diagrams
3.4.1 ZX-diagrams to circuits with post-selection
3.4.2 Circuit-like diagrams and optimisation
3.5 Summary: What to remember
3.6 Advanced Material*
3.6.1 Formal rewriting and soundness*
3.6.2 Dealing with scalars*
3.7 References and further reading
4 CNOT circuits and phase-free ZX-diagrams
4.1 CNOT circuits and parity matrices
4.1.1 The two-element field and the parity of a bit string
4.1.2 From CNOT circuits to parity maps
4.1.3 CNOT circuit synthesis
4.2 The phase-free ZX calculus
4.2.1 Reducing a ZX-diagram to normal form
4.2.2 Graphical CNOT circuit extraction
4.3 Phase-free states and 𝔽2 linear subspaces
4.3.1 Phase-free completeness
4.3.2 X-Z normal forms and orthogonal subspaces
4.3.3 Relating parity matrices and subspaces
4.4 Summary: What to remember
4.5 Advanced Material*
4.5.1 Better CNOT circuit extraction*
4.6 References and further reading
5 Clifford circuits and diagrams
5.1 Clifford circuits and Clifford ZX-diagrams
5.1.1 Graph-like diagrams
5.1.2 Graph states
5.2 Simplifying Clifford diagrams
5.2.1 Transforming graph states using local complementation
5.2.2 Pivoting
5.2.3 Removing spiders in Clifford diagrams
5.3 Clifford normal forms
5.3.1 The affine with phases normal form
5.3.2 GSLC normal form
5.3.3 Normal form for Clifford circuits
5.4 Classical simulation of Clifford circuits
5.4.1 Simulating Cliffords efficiently
5.4.2 Weak vs strong simulation
5.5 Completeness of Clifford ZX-diagrams
5.5.1 A normal form for scalars
5.5.2 A unique normal form for Clifford diagrams
5.6 Summary: What to remember
5.7 References and further reading
6 Stabiliser theory
6.1 Paulis and stabilisers
6.1.1 Clifford conjugation, a.k.a. pushin’ Paulis
6.1.2 Stabiliser subspaces
6.2 Stabiliser measurements
6.2.1 The Fundamental Theorem of Stabiliser Theory
6.3 Stabiliser states and the Clifford group
6.3.1 Maximal stabiliser groups
6.3.2 Stabiliser states
6.3.3 The Clifford group
6.3.4 Putting it all together
6.4 Stabiliser tableaux
6.4.1 Cliffords are determined by Pauli conjugations
6.4.2 Stabiliser tableaux
6.4.3 Paulis as bit strings
6.4.4 Cliffords as symplectic matrices
6.4.5 Adding back in the phases
6.4.6 Putting it all together
6.5 The Clifford hierarchy
6.6 Summary: What to remember
6.7 References and further reading
7 Universal circuits
7.1 Phase polynomials and path sums
7.1.1 Phase polynomials
7.1.2 Phase gadgets
7.1.3 Synthesis from phase polynomials
7.1.4 Universal circuits with path sums
7.1.5 Quantum Fourier transform
7.2 Scalable ZX notation
7.2.1 Dividers and gatherers
7.2.2 Scalable phase gadgets
7.3 Pauli exponentials
7.3.1 Unitaries from Pauli boxes
7.3.2 Matrix exponentials
7.3.3 Building unitaries as exponentials
7.3.4 Pauli exponentials
7.4 Pauli exponential compilation
7.4.1 Pauli exponentials are a universal gate set
7.4.2 Compiling to Pauli exponentials
7.4.3 Phase folding
7.5 Hamiltonian simulation
7.6 Simplifying universal diagrams
7.6.1 Removing non-Clifford spiders
7.6.2 Circuits from universal diagrams
7.7 Summary: What to remember
7.8 Advanced material*
7.8.1 Simulating universal circuits*
7.8.2 Higher-order Trotterisation*
7.8.3 Randomised compiling*
7.9 References and further reading
8 Cheatsheets
8.1 ZX-calculus cheatsheets
8.1.1 Generators and their matrices
8.1.2 Basic Rewrite rules
9 Measurement-based quantum computation
9.1 Measurement fragments
9.1.1 Universal resources
9.2 Determinism and gflow
9.2.1 Graph-like ZX-diagrams as measurement fragments
9.2.2 The measurement correction game
9.2.3 Diagrams with gflow are deterministic measurement patterns
9.2.4 From circuits to measurement patterns
9.2.5 Focussed gflow
9.3 Optimising deterministic measurement patterns
9.4 From measurement patterns to circuits
9.5 Measurements in three planes
9.5.1 Rewriting 3-plane gflow
9.5.2 Circuit extraction, now phase gadget compatible
9.6 There and back again
9.7 Summary: What to remember
9.8 References and further reading
10 Controlled gates and classical oracles
10.1 Controlled unitaries
10.1.1 The Toffoli gate
10.1.2 Diagonal controlled gates and phase polynomials
10.1.3 Fourier transforming diagonal unitaries
10.2 H-boxes
10.2.1 AND gates
10.2.2 Rules for the H-box
10.2.3 Constructing controlled unitaries using H-boxes
10.3 Reversible Logic synthesis
10.4 Constructing Toffoli gates with many controls
10.4.1 Quantum tricks for optimising Toffoli gates
10.4.2 Adding controls to other quantum gates
10.5 Adders
10.6 Summary: what to remember
10.7 Advanced Material*
10.7.1 From truth tables to Toffolis*
10.7.2 2-level operators*
10.7.3 More rules for the H-box*
10.7.4 W-spiders*
10.8 References and further reading
11 Clifford+T
11.1 Universality of Clifford+T circuits
11.1.1 Exact synthesis of one-qubit gates
11.1.2 Approximating arbitrary single-qubit gates
11.2 Rewriting Clifford+T diagrams
11.2.1 Spider nests as strongly 3-even matrices
11.2.2 Proving all spider nest identities
11.2.3 Spider nests as Boolean polynomials
11.3 Advanced T-count optimisation
11.3.1 Reed-Muller decoding
11.3.2 Symmetric 3-tensor factorisation
11.4 Catalysis
11.4.1 Catalysis as a resource for compilation
11.4.2 Computational universality via catalysis
11.4.3 Catalysing completeness
11.5 Summary: What to remember
11.6 Advanced Material*
11.6.1 Exact synthesis of Clifford+T states*
11.6.2 Exact unitary synthesis*
11.6.3 Approximate single-qubit Clifford+T synthesis*
11.6.4 Computational universality of Toffoli-Hadamard*
11.7 References and further reading
12 Quantum error correction
12.1 Classical codes and parameters
12.2 Quantum stabiliser codes
12.2.1 Code distance for stabiliser codes
12.2.2 Detecting and correcting quantum errors
12.2.3 Encoders and logical operators
12.2.4 The decoder
12.3 CSS codes
12.3.1 Stabilisers and Pauli ZX diagrams
12.3.2 Maximal CSS codes as ZX diagrams
12.3.3 Non-maximal CSS codes as ZX encoder maps
12.3.4 The surface code
12.3.5 Scalable ZX notation for CSS codes
12.4 Fault-tolerance
12.4.1 Fault-tolerant computation with transversal gates
12.4.2 Fault-tolerant Pauli measurements
12.4.3 Lattice surgery
12.5 Magic state distillation
12.5.1 CCZ distillation and catalysis
12.6 Summary: What to remember
12.7 References and Further Reading