PaperlayerView exact revision on arXiv

Source-linked AI summary

The ZX&-calculus: A complete graphical calculus for classical circuits using spiders

Cole Comfort

arXiv:2004.05287v5cs.LOmath.CTquant-ph

TL;DR

The paper addresses how to give a complete graphical presentation of the classical ZX-calculus fragment ZX&. It builds this presentation through completions of TOF and a two-way translation, establishing completeness for matrices over the natural numbers.

  • Problem

    The paper asks for a complete presentation of the ZX-calculus fragment generated by copying and addition spiders, the not gate, and the and gate.

    Source: §1 · p. 1

  • Method

    The paper adds unit and counit structure to TOF and translates between the resulting category and ZX&.

    Source: §1 · p. 1, §4 · p. 8

  • Results

    ZX& is complete for the prop of 2^n × 2^m matrices over the natural numbers.

    Source: §4 · p. 10

  • Takeaways & Limitations

    The resulting presentation is isomorphic to spans between ordinals 2^n, identified with qubit multirelations.

    Source: §1 · p. 1, §4 · p. 10

    The modified CP∞ composition without universal quantification over test maps is not obviously well-defined unless the base category embeds in a compact closed category.

    Source: §3 · p. 6

Abstract

from arXiv · show

We give a complete presentation for the fragment, ZX&, of the ZX-calculus generated by the Z and X spiders (corresponding to copying and addition) along with the not gate and the and gate. To prove completeness, we freely add a unit and counit to the category TOF generated by the Toffoli gate and ancillary bits, showing that this yields the full subcategory of finite ordinals and functions with objects powers of two; and then perform a two way translation between this category and ZX&. A translation to some extension of TOF, as opposed to some fragment of the ZX-calculus, is a natural choice because of the multiplicative nature of the Toffoli gate. To this end, we show that freely adding counits to the semi-Frobenius algebras of a discrete inverse category is the same as constructing the Cartesian completion. In particular, for a discrete inverse category, the category of classical channels, the Cartesian completion and adding counits all produce the same category. Therefore, applying these constructions to TOF produces the full subcategory of finite ordinals and partial maps with objects powers of two. By glueing together the free counit completion and the free unit completion, this yields "qubit multirelations."

1 Introduction

The introduction presents ZX& as a complete graphical calculus for a classical fragment of the ZX-calculus, and outlines the categorical constructions used to establish that result. It also relates the presentation to existing circuit identities and graphical calculi.

1 Introduction

  • ZX&, generated by black and white spiders, the not gate, and the and gate, has a complete set of identities and presents qubit multirelations.The paper identifies qubit multirelations with 2^n × 2^m matrices over N.Source: §1 · p. 1
  • The identities are near the union of known complete identities for Boolean functions and Span∼(Mat(F2)), while the paper supplies a completeness result and structural account.The introduction notes related identities in earlier presentations and the ZH-calculus.Source: §1 · p. 1
  • The proof proceeds through restriction and inverse category machinery, classical channels, and a two-way translation between ZX& and a completion of TOF.The introduction says these constructions yield a canonical presentation isomorphic to spans between ordinals 2^n.Source: §1 · pp. 1–2

2 Restriction and Inverse Categories

This section reviews restriction and inverse categories as categorical settings for partial and reversible computation, then motivates a suitable notion of copying for inverse categories. It introduces the Cartesian completion that supplies the needed counital structure.

2 Restriction and Inverse Categories

  • Restriction categories model partial computation, while inverse categories model reversible computation; restriction in partial maps restricts a function to its domain of definition.A map is total when it equals the identity, and partial isomorphisms have partial inverses.Source: §2 · p. 2
  • The weakened products used for restriction categories do not sufficiently constrain how a diagonal interacts with its partial inverse in inverse categories.This motivates seeking a more suitable notion of copying for inverse categories.Source: §2 · pp. 3–4
  • Discrete inverse categories supply the relevant weakened-product structure through natural special commutative dagger semi-Frobenius algebras compatible with tensor product.The section relates discrete inverse categories to discrete Cartesian categories and presents the Cartesian completion as a construction that adds history to partial isomorphisms.Source: §2 · p. 4
  • The Cartesian completion eX has a counital induced Frobenius algebra.Its counit is given by the unitor in the construction described in the proof.Source: §2 · p. 5

3 Categorical quantum mechanics and completely positive maps

The section seeks an algebraic account of classical channels in discrete inverse categories and relates them to counit completion and Cartesian completion. It presents a route using decoherence maps, while noting a well-definedness caveat for the modified construction.

3 Categorical quantum mechanics and completely positive maps

  • The paper proposes combining STOCH and CP∞ ideas to handle dagger semi-Frobenius algebras when compact closure is not assumed.It describes a modified CP∞ construction without quantification over all test maps, followed by a Karoubi-envelope subcategory on decoherence maps.Source: §3 · p. 6
  • The modified CP∞ composition is not obviously well-defined on a discrete inverse category unless the base category embeds in a compact closed category.This caveat qualifies the construction that omits universal quantification over test maps.Source: §3 · p. 6
  • The motivating question is whether classical channels can be characterized algebraically through a discarding morphism, without doubling.The section frames this as an environment-structure question for classical channels of discrete inverse categories.Source: §3 · p. 8
  • For a discrete inverse category, freely adjoining counits gives a discrete Cartesian restriction category isomorphic to its Cartesian completion.The counital completion adds a counit to each chosen semi-Frobenius algebra, compatibly with the monoidal structure.Source: §3 · p. 8

4 ZX&

The paper constructs ZX& by adjoining units and counits to TOF and translating between the resulting category and a graphical calculus. The translations establish an isomorphism and yield completeness for matrices over the natural numbers of the stated dimensions.

4 ZX&

  • Adding a unit and counit to TOF is presented through ZX&, generated by copy and addition spiders, NOT, and AND.The construction glues the counital and unital completions of TOF together.Source: §4 · p. 8
  • TOF is isomorphic to partial isomorphisms between ordinals 2^n, and its completion is presented as a pushout for the subcategory generated by powers of two.The construction uses the pushout described in Lemma 4.3.Source: §4 · p. 8
  • ZX& identities are formed from commutative monoids and comonoids linked by distributive laws and monoid maps.The spider rules also identify the compact-closed units and counits induced by Z and X.Source: §4 · pp. 9–10, Figure 3 · p. 9
  • The two interpretation functors are inverses, making TOF’s completion and ZX& isomorphic as strongly compact closed props.The interpretation maps between the categories are presented as strict symmetric †-monoidal functors.Source: §4 · p. 10
  • ZX& is complete for 2^n × 2^m matrices over the natural numbers.The paper relates this result to the monoidal equivalence between spans of finite ordinals and natural-number matrices under the Kronecker product.Source: §4 · p. 10

5 Conclusion

The conclusion identifies possible extensions and questions beyond the presented calculus. These include adding a white π phase and investigating links with ZH-calculus, triangles, and distributive-law presentations.

5 Conclusion

  • Further directions include a normal form from distributive laws and investigating the 2-categorical structure and associated category of relations [2].The conclusion also points to strict factorization systems and distributive laws in spans.Source: §5 · pp. 10–11
  • Adding the white π phase is proposed as a route to an approximately universal graphical calculus, but the paper does not prove axiom minimality.The proposed extension would use distributive laws and monoid maps; the unnormalized Hadamard is said to be derivable in that fragment.Source: §5 · p. 11
  • The paper proposes studying connections with ZH-calculus and triangle fragments, including natural-number-labelled H-boxes [20].The triangle diagram is interpreted as x∧¬y = ⊥, equivalent to material implication x ⇒ y.Source: §5 · p. 11

A Proof of Lemma 2.14

The fragment records an equation involving f and g in the proof of Lemma 2.14.

A Proof of Lemma 2.14

B Proof of lemma 3.5

The proof establishes that the counit completion c(X) and Cartesian completion eX are isomorphic as discrete Cartesian restriction categories. It constructs inverse identity-on-objects functors and verifies their functoriality.

B Proof of lemma 3.5

  • For a discrete inverse category X, c(X) and eX are isomorphic as discrete Cartesian restriction categories.Source: B Proof of lemma 3.5 · p. 14
  • The proof defines identity-on-objects functors in both directions by sending counits to ancillary space and plugging counits into that space.The maps are inverses and preserve the discrete Cartesian restriction structure.Source: B Proof of lemma 3.5 · p. 14
  • To show F is a functor, the proof uses the counital Frobenius algebra on each eX object, compatible with the monoidal structure.The unit is the image under F of the freely adjoined counit.Source: B Proof of lemma 3.5 · p. 14
  • The proof of G’s functoriality starts from equivalent representatives (f,S) and (g,T) in eX and uses counitality and faithfulness of X → eX.It also invokes the alternate equivalence relation of eX.Source: B Proof of lemma 3.5 · pp. 14–15

C Proof of Lemma 4.3

The proof presents the full subcategory of spans on powers of two via a pushout and develops properties of TOF and ZX& that support their comparison. It also relates black-spider phase fusion to a bialgebra interaction.

C Proof of Lemma 4.3

  • The pushout presents the full subcategory of Span~(FinOrd) generated by powers of two.The proof establishes fullness by factoring functions through a power-of-two extension of their finite domain.Source: C Proof of Lemma 4.3 · pp. 15–16

D Identities of TOF

  • Generalized controlled-NOT gates can be partially commuted when x is not in Y, with a trailing generalized controlled-NOT gate as a side effect.Source: D Identities of TOF · p. 19

E.1 Basic properties of the (co)unitual completion of TOF

E.2 Basic properties of ZX&

  • In ZX&, black-spider phase fusion is equivalent to the interaction of the and-unit and copying-counit as a bialgebra.Source: §E.2 · p. 20

E.3 Proof of Proposition 4.5

The proof establishes that the interpretation is a strict symmetric monoidal functor by checking the ZX& axioms in TOF.

E.3 Proof of Proposition 4.5

  • The interpretation is a strict symmetric monoidal functor.Source: §E.3 · p. 21
  • The proof checks the ZX& axioms in TOF, using Lemma E.4 for unitality.Source: §E.3 · p. 21
  • Several listed axioms are immediate, and [ZX&.16] is identified with [TOF.7].Source: §E.3 · pp. 22, 24

E.4 Proof of Proposition 4.6

The interpretation from TOF to ZX& is established as a strict symmetric monoidal functor by checking TOF's axioms in ZX&. The proof also notes that the two Frobenius algebras induce the same compact closed structure.

E.4 Proof of Proposition 4.6

  • The interpretation from TOF to ZX& is a strict symmetric monoidal functor.Source: §E.4 · p. 24
  • The proof verifies TOF's axioms in ZX&, deriving several from the spider law and showing [TOF.10] is redundant.[TOF.8] follows from Lemma E.5 and [ZX&.7].Source: §E.4 · pp. 25–26
  • Both Frobenius algebras induce the same compact closed structure, as implied by the spider law.Source: §E.4 · p. 30

E.5 Proof of Theorem 4.7

Theorem 4.7 identifies the interpretations of ZX& and TOF as isomorphic strongly compact closed props. Its proof checks translations in both directions, including the spider, and-gate, ancilla, and Toffoli cases.

E.5 Proof of Theorem 4.7

  • The interpretations of ZX& and TOF are isomorphic as strongly compact closed props.Source: §E.5 · p. 30
  • The proof checks translations in both directions, covering the white and grey spiders, and gate, ancillae, and Toffoli gate.Source: §E.5 · pp. 30–31

F The identities of CNOT

Loading 2004.05287v5…