PaperlayerView exact revision on arXiv

Source-linked AI summary

ZH: A Complete Graphical Calculus for Quantum Computations Involving Classical Non-linearity

Miriam Backens, Aleks Kissinger

arXiv:1805.02175v2quant-ph

TL;DR

Graphical calculi provide a unified way to reason about quantum operations, states, and measurement projections, while typical ZX encodings of AND are comparatively costly. The paper introduces ZH-calculus, combining computational-basis spiders with n-ary H-boxes, and proves its completeness using unique normal forms. Its compact representations cover nonlinear Boolean circuits and related quantum constructions.

  • Problem

    Graphical calculi unify reasoning about quantum operations, states, and measurement projections, but a typical ZX-calculus encoding of an AND gate requires 25 generators and non-Clifford phases.

    Source: §1 · pp. 1–2

  • Method

    ZH-calculus combines computational-basis Z-spiders with n-ary H-boxes and proves diagram equality through a unique normal form.

    Source: §1 · pp. 1–2

  • Results

    The ZH-calculus is complete: diagrams with equal matrix interpretations are interderivable, and its normal forms are unique.

    Source: §3 · pp. 8, 11

  • Takeaways & Limitations

    The calculus gives Boolean circuits and hypergraph-state constructions low-constant-overhead encodings, supporting analysis of nonlinear classical and quantum operations together.

    Source: §1 · p. 2

    Techniques for working with hypergraph states and their relationship to known manipulation rules remain topics for future work.

    Source: §4 · p. 12

Abstract

from arXiv · show

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.

1 Introduction

The ZH-calculus extends graphical reasoning toward hypergraph states and nonlinear classical functions through computational-basis spiders and n-ary H-boxes. The paper presents a self-contained completeness proof based on a unique normal form.

1 Introduction

  • ZH-calculus is presented as a graphical counterpart to the relationship between graph states and hypergraph states.Hypergraph states generalize graph states and have been studied in quantum search, Bell violations, and universal measurement-based quantum computation.Source: §1 · p. 1
  • The calculus combines computational-basis Z-spiders with n-ary H-boxes that generalize Hadamard gates and satisfy a variation of spider fusion.H-boxes can introduce hyperedges between n vertices, rather than the two-vertex edges associated with Hadamard gates.Source: §1 · pp. 1–2
  • H-boxes are closely related to n-ary AND gates, enabling Boolean circuits to be encoded in ZH with low constant overhead.The introduction contrasts this with a typical ZX-calculus AND encoding requiring 25 generators and non-Clifford phases.Source: §1 · p. 2
  • The completeness proof uses a unique normal form expressing matrices as Schur products of elementary matrices that are all ones except at most one entry.The introduction contrasts this multiplicative normal form with the additive normal form of the ZW-calculus.Source: §1 · p. 2
  • The soundness, completeness, and universality proofs are self-contained rather than relying on translation into another calculus.This contrasts with completeness proofs for universal ZX-calculus versions that use the ZW-completeness proof through translations.Source: §1 · p. 2

2 Definition of the ZH-calculus

The ZH-calculus uses Z-spiders and H-boxes as generators, with diagrams interpreted as matrices. Its relations are sound, and !-box notation expresses families of diagrams and equations.

2.1 The generators and their interpretation

  • ZH diagrams are generated by computational-basis Z-spiders and complex-labelled H-boxes, with juxtaposition and composition interpreted as tensor product and matrix product.Grey spiders and NOT are introduced as derived generators.Source: §2.1 · p. 3

2 Definition of the ZH-calculus

  • The ZH generators suffice to express any linear map C2m → C2n, and the paper also gives a normal-form route to universality independent of the ZX encoding.The calculus adds an !-box meta-notation for diagram families and uses it to generalize several rules.Source: §2.1 · p. 4, §2.3 · p. 6

2.2 The relations, and soundness

  • The calculus is sound: its relations preserve matrix interpretation, and topological deformation is justified by treating string diagrams as morphisms in a compact closed category.Generators are symmetric and undirected, so same-generator inputs or outputs can be swapped and inputs can be bent into outputs.Source: §2.2 · p. 4

2.3 !-box notation

  • A !-box indexed by a finite set represents copies of its contents for each index, while matching indexed boxes on both sides express corresponding copies in an equation.Rules using !-boxes can represent families of equations replicated an arbitrary number of times.Source: §2.3 · pp. 4, 6, 7

3 Completeness

The completeness proof reduces diagrams to a unique normal form by showing that generators and diagram operations can be normalized. This yields completeness: diagrams with equal matrix interpretations are provably equal in the ZH-calculus.

3 Completeness

  • The proof treats diagrams as states with only outputs, since inputs can be bent into outputs; states are interpreted as column vectors.Schur products and tensor products of normal forms can also be brought into normal form.Source: §3 · pp. 7, 9
  • Normal forms are built from H-boxes labelled by coefficients for bitstrings, and equation (6) constructs any vector in C2n.The construction supports universality independently of the earlier encoding into ZX.Source: §3 · pp. 7–8
  • Extension, convolution, and contraction combine normal forms; contraction is the hardest case and uses the Disconnect Lemma, proved with Quantomatic.The lemma uses rule (O) to split a 2n-legged spider into 2n−1 separate cups.Source: §3 · pp. 9–10
  • Unique normal forms characterize ZH diagrams, and the proof uses this result to establish completeness for diagrams with equal matrix interpretations.The theorem states that any two diagrams interpreted as the same matrix are convertible using ZH rules.Source: §3 · pp. 8, 11
  • The proof reduces completeness to normalizing arbitrary diagrams, first showing that H-boxes and Z-spiders can each be brought into normal form.Tensor products and arbitrary wiring are then normalized using closure results for tensor products and caps.Source: §3 · pp. 10–12

4 Applications and future work

The ZH-calculus extends controlled-Z diagrams to n-controlled-Z gates and supports analogous diagrammatic techniques for hypergraph states. It also encodes phase-polynomial unitaries, suggesting possible applications to circuit optimization and fault-tolerant computation.

4 Applications and future work

  • N-ary H-boxes generalize the diagrammatic controlled-Z description to n-controlled-Z gates.Replacing ∧Z with ∧nZ gives an analogous representation for hypergraph states.Source: §4 · p. 12
  • Introducing !-boxes into graph-state rules generalizes them to hypergraph states, including local complementation of arbitrary-arity hyperedges overlapping at one vertex.The relationship between these techniques and known hypergraph-state manipulation rules remains future work.Source: §4 · p. 12
  • With H-boxes labelled by a fixed root of unity, ZH diagrams encode phase-polynomial unitaries, with Z-spiders for variables and labelled H-boxes for polynomial terms.The unitaries have the form Uφ|b⟩ = ω^φ(b)|b⟩ for a Boolean-variable polynomial φ.Source: §4 · pp. 12–13
  • ZH rules show basic properties of these unitaries, while their diagrammatic phase-polynomial structure may offer new approaches to circuit optimization or fault-tolerant computation.For m = 2, the phase-polynomial formalism has been used in Clifford+T circuit optimization; diagonal Clifford-hierarchy gates are also of this form.Source: §4 · p. 13

A Proofs of the !-box versions of basic rules

The appendix establishes !-box versions of basic ZH-calculus rules, including results for scalar and arbitrary-arity H-boxes. These lemmas support scalar manipulation and together provide a proof of Lemma 2.3.

A Proofs of the !-box versions of basic rules

B Proof of the disconnect lemma

The disconnect lemma proof uses recursive bitstring splitting to reduce the diagram to the claimed right-hand side. Quantomatic produced the proof, including exported derivations for Lemmas B.1 and B.3.

B Proof of the disconnect lemma

  • Quantomatic assisted the proof; Lemmas B.1 and B.3 were exported from the disconnect-4 and gen-disconnect-4 derivations in the zh project.Source: B Proof of the disconnect lemma · p. 16
  • The proof splits B_n−1 according to its most significant bit, then splits the bottom spider and !-box before repeating the process on the shorter bitstrings.Source: B Proof of the disconnect lemma · p. 19
  • Repeatedly splitting the bitstring by successive bits reduces the diagram until spiders connect pairs of H-spiders that disagree on the least significant bit.Replacing the resulting two-legged spiders with cups yields the right-hand side of equation (8).Source: B Proof of the disconnect lemma · p. 20
Loading 1805.02175v2…