Completeness of the ZH-calculus

Abstract

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 $\mathbb{Z}[\frac{1}{2}]$, 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.

68 pages, many many diagrams

References in corpus (18)

• Quantum cryptography: Public key distribution and coin tossing
• Surface codes: Towards practical large-scale quantum computation
• There and back again: A circuit extraction tale
• Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions
• A universal completion of the ZX-calculus
• The algebra of entanglement and the geometry of composition
• Optimising Clifford Circuits with Quantomatic
• Hypergraph Simplification: Linking the Path-sum Approach to the ZH-calculus
• Completeness of the ZX-calculus for Pure Qubit Clifford+T Quantum Mechanics
• Graphical Fourier Theory and the Cost of Quantum Addition
• Algebraic complete axiomatisation of ZX-calculus with a normal form via elementary matrix operations
• AKLT-states as ZX-diagrams: diagrammatic reasoning for quantum states
• The ZX&-calculus: A complete graphical calculus for classical circuits using spiders
• When Only Topology Matters
• Completeness of the Phase-free ZH-calculus
• On a recipe for quantum graphical languages
• Entanglement and Quaternions: The graphical calculus ZQ
• Graphical Calculi and their Conjecture Synthesis

Cited by in corpus (7)

• Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions
• ZX-calculus for the working quantum computer scientist
• Complete Equational Theories for the Sum-Over-Paths with Unbalanced Amplitudes
• Complete ZX-calculi for the stabiliser fragment in odd prime dimensions
• Optimal compilation of parametrised quantum circuits
• Rewriting and Completeness of Sum-Over-Paths in Dyadic Fragments of Quantum Computing
• A Complete and Natural Rule Set for Multi-Qutrit Clifford Circuits