Source-linked AI summary
Completeness of the ZH-calculus
Miriam Backens, Aleks Kissinger, Hector Miller-Bakewell, John van de Wetering, Sal Wolffs
TL;DR
The paper addresses how a calculus motivated by Boolean-function identities can also reason about quantum computation. It develops ZH rewrite rules and proves completeness for the Toffoli-Hadamard fragment and for an extended calculus over rings where 2 is not a zero divisor.
Problem
The paper asks how rewrite rules expressed as identities between Boolean functions can suffice for reasoning about quantum computation.
Source: §2.3 · pp. 8, 10Method
The authors develop a small set of ZH rewrite rules motivated by Boolean-function identities and extend the calculus to arbitrary rings.
Source: §2.3 · p. 8, §9 · p. 64Results
The ZH rules are complete for the Toffoli-Hadamard fragment, and the extended ruleset is complete over any ring where 2 is not a zero divisor.
Source: §9 · p. 64Takeaways & Limitations
The calculus represents the AND gate through H-boxes and Hadamards, with the Hadamard relating COPY and XOR maps.
Source: §2.3 · p. 10The authors do not know whether rules (m) and (o) are necessary for completeness.
Source: §8.2 · p. 61
Abstract
from arXiv · showhide
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}[\frac12]$, 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.
1.1 Related work
The paper situates ZH among related graphical calculi and outlines a completeness proof built around labelled H-box rewrite rules, normal forms, and arithmetic on their labels. It then extends the completeness study to arbitrary rings.
1.1 Related work
- ZH is the youngest of the three basic qubit graphical calculi identified in, and its completeness concludes the program of finding complete calculi for qubits.The related work also connects ZH to the triangle generator [40], the ZW-calculus [26], and ringR [39].Source: §1.1 · p. 4
- ZH diagrams have also been used for hypergraph states, path-sums, quantum multiple-valued decision diagrams, AKLT states, and spin-networks.The passage cites [37] for hypergraph states, [49] for path-sums, [50] for decision diagrams, for AKLT states, and [21] for spin-networks.Source: §1.1 · p. 4
1.2 Overview of the paper and structure of the main proof
- The main completeness proof introduces labelled H-boxes, establishes special cases of multiply, intro, and average, then uses normal forms and proves the rules generally.The normal-form reduction is first shown conditionally on those rules; the later arithmetic and general-rule proofs complete the argument.Source: §1.2 · pp. 4–5
- The paper separately studies ZH over arbitrary rings, assuming multiply, intro, and average as axioms for its completeness proof.It then considers modifications to the calculus and rules.Source: §1.2 · p. 5
3 Special cases of multiply, intro and average
This section proves selected integer cases of three rewrite-rule families for labelled H-boxes, while postponing their general proofs. The rules combine labels, introduce wires, and average labels using a half-factor.
3 Special cases of multiply, intro and average
- The section establishes these rule families first for selected small integers, leaving their general proofs until after the normal-form diagrams are introduced.The general proofs are deferred to Section 6.Source: §3 · p. 21
3.1 The multiply rule
- The multiply rule fuses labelled H-boxes connected to the same white spiders by multiplying their labels, and its cases for b = 0, 1, or -1 hold for every integer a.The general rule is postponed; the arbitrary-arity version extends the same fusion operation.Source: §3.1 · pp. 21–22
3.2 The intro rule
- The intro rule adds wires to an H-box, and its instances for a = -1, 0, 1, or 2 are proved, including their !-boxed generalisations.Applying the rule repeatedly can connect the H-box to a larger set of wires.Source: §3.2 · pp. 22, 25
3.3 The average rule
- The average rule combines labels and multiplies by a NOT 2 H-box that acts like multiplying by one half; selected cases for a, b in {0, 1, -1} are proved.The section also establishes cases when one label is zero and when the labels are opposites, given the corresponding intro rules.Source: §3.3 · pp. 26–27
5 Arithmetic
The section establishes arithmetic rewrite rules for labelled H-boxes: their labels can be added, and the multiplication rule holds for all integers. It builds addition from natural numbers to integers and proves multiplication through natural-number properties and reduction of negative inputs.
5 Arithmetic
- The section establishes that labelled H-boxes can be added and that the multiply rule holds for all integers.Adding labels is identified as crucial to the general average rule proved in Section 6.Source: §5 · p. 38, §5.3 · p. 45
5.1 Proving addition for natural numbers
- For natural-number addition, adding 1 acts as the successor, and the addition gadget is associative.These lemmas support the proof of addition for natural numbers.Source: §5.1 · p. 40
5.2 Proving addition for all integers
- Addition is extended to arbitrary integers using the inverse of the successor and the natural-number addition result.The successor's initially one-sided inverse is shown to be two-sided by conjugating with a negate spider.Source: §5.2 · pp. 41–42
5.3 Proving multiplication
- The multiplication gadget distributes over natural-number addition, and the multiply rule is proved for all integers by reducing negative inputs to non-negative ones.The natural-number proof uses induction; two copies of the negation cancel.Source: §5.3 · pp. 45–46
6 Completeness
The section proves the rules required by a conditional completeness result: intro and average, alongside the multiply rule established earlier. It then applies that result to conclude that the ZH-calculus is complete.
6 Completeness
- The ternary X-spider can be brought to normal form as part of the section's normal-form proof steps.The right-hand side of Equation (30) uses this result before being brought to normal form.Source: §6 · pp. 46–47
- The average rule is proved for all integers, completing the remaining rule required by the conditional completeness result.The proof brings both sides of Equation (30) to normal form.Source: §6 · pp. 46–47
- The section proves the intro rule for all integers, reducing the task to natural numbers using a lemma that derives I_(a·b) from I_a and I_b.In particular, the lemma derives I_(-a) from I_a.Source: §6 · p. 48
- The ZH-calculus is complete because the multiply, average, and intro rules are provable for all integers.The proof combines Propositions 5.16, 6.2, and 6.4 with the conditional completeness result of Proposition 4.21.Source: §6 · p. 51
8 Modifications to the ZH-calculus
The section gives variations on the ZH-calculus, including equivalent rules and a parameter-free version for Toffoli+Hadamard matrices. It also shows that the (hh) rule is derivable from the other rules.
8.1 Replacing the (o) rule
- The ortho rule (o) is equivalent, in the presence of the other ZH-calculus rules, to the union of two rules about post-selected AND and COPY followed by AND.The two rules are Lemmas 2.28 and 5.1.Source: §8.1 · pp. 59, 61
8.2 The (hh) rule is not necessary
- The (hh) rule can be derived from the other rules, while the authors identify several rules as necessary and leave the necessity of (m) and (o) unresolved.They identify (zs), (hh), (id), and at least one of (ba1) and (ba2) as necessary.Source: §8.2 · p. 61
8.3 Merging the intro and average rule
- For a ring with a half, the intro and average rules together are equivalent to a single larger rule in the presence of the other Figure 3 rules.The section also gives an alternative rule equivalent to (A) under those conditions.Source: §8.3 · p. 62
8.4 ZH-calculus as a complete language for Toffoli+Hadamard circuits
- Redefining a generator yields a parameter-free ZH-calculus complete for matrices of the form (1/√2)^n A, where A has integer entries.An additional rewrite rule handles the zero-matrix case and preserves completeness for this matrix class.Source: §8.4 · p. 64
9 Conclusion
The authors give rewrite rules proving completeness of the ZH-calculus for the Toffoli-Hadamard fragment and extend completeness to arbitrary rings where 2 is not a zero divisor. They also identify open questions about the rules and describe potential applications and connections to the ZX-calculus.
9 Conclusion
- The authors prove completeness for the Toffoli-Hadamard fragment and extend the ZH-calculus to be complete over arbitrary rings where 2 is not a zero divisor.They characterize both versions as the simplest complete graphical calculus for an approximately universal quantum-computing fragment found so far.Source: §9 · p. 64
- The rule (hh) is derivable from the other rules, while rule (o) can be replaced by two simpler rules.The authors believe the remaining rules are necessary, though they note that one of the two replacement rules might suffice.Source: §9 · p. 64
- For the ZHR-calculus, completeness without the scalar-cancellation meta-rule remains unclear.The authors state that this meta-rule is required in a case involving scalar cancellation.Source: §9 · p. 64
- The phase-free calculus and its translation to Boolean functions clarify the relationship between classical computation and universal quantum computation with Toffoli-Hadamard gates.The authors suggest the arbitrary-ring calculus may help analyze multiply-controlled gates and quantum computation or error-correction schemes involving hypergraph states.Source: §9 · p. 64
- A Fourier-transform relationship between the ZH-calculus over C and the ZX-calculus [36] motivates translation between them and combined calculi such as ZXH.The authors describe the ZH-calculus, alone or combined with other graphical languages, as applicable across a broad range of quantum-computing areas.Source: §9 · p. 64