String diagram

String diagrams are a formal graphical language for representing morphisms in monoidal categories, or more generally 2-cells in 2-categories. They are a prominent tool in applied category theory. When interpreted in the monoidal category of vector spaces and linear maps with the tensor product, string diagrams are called tensor networks or Penrose graphical notation. This has led to the development of categorical quantum mechanics where the axioms of quantum theory are expressed in the language of monoidal categories.

History

Günter Hotz gave the first mathematical definition of string diagrams in order to formalise electronic circuits.^[1] However, the invention of string diagrams is usually credited to Roger Penrose,^[2] with Feynman diagrams also described as a precursor.^[3] They were later characterised as the arrows of free monoidal categories in a seminal article by André Joyal and Ross Street.^[4] While the diagrams in these first articles were hand-drawn, the advent of typesetting software such as LaTeX and PGF/TikZ made the publication of string diagrams more wide-spread.^[5]

The existential graphs and diagrammatic reasoning of Charles Sanders Peirce are arguably the oldest form of string diagrams, they are interpreted in the monoidal category of finite sets and relations with the Cartesian product.^[6] The lines of identity of Peirce's existential graphs can be axiomatised as a Frobenius algebra, the cuts are unary operators on homsets that axiomatise logical negation. This makes string diagrams a sound and complete two-dimensional deduction system for first-order logic,^[7] invented independently from the one-dimensional syntax of Gottlob Frege's Begriffsschrift.

Intuition

String diagrams are made of boxes ${\displaystyle f:x\to y}$, which represent processes, with a list of wires ${\displaystyle x}$ coming in at the top and ${\displaystyle y}$ at the bottom, which represent the input and output systems being processed by the box ${\displaystyle f}$. Starting from a collection of wires and boxes, called a signature, one may generate the set of all string diagrams by induction:

• each box ${\displaystyle f:x\to y}$ is a string diagram,
• for each list of wires ${\displaystyle x}$, the identity ${\displaystyle {\text{id}}(x):x\to x}$ is a string diagram representing the process which does nothing to its input system, it is drawn as a bunch of parallel wires,
• for each pair of string diagrams ${\displaystyle f:x\to y}$ and ${\displaystyle f':x'\to y'}$, their tensor ${\displaystyle f\otimes f':xx'\to yy'}$ is a string diagram representing the parallel composition of processes, it is drawn as the horizontal concatenation of the two diagrams,
• for each pair of string diagrams ${\displaystyle f:x\to y}$ and ${\displaystyle g:y\to z}$, their composition ${\displaystyle g\circ f:x\to z}$ is a string diagram representing the sequential composition of processes, it is drawn as the vertical concatenation of the two diagrams.

Definition

Algebraic

Let the Kleene star ${\displaystyle X^{\star }}$ denote the free monoid, i.e. the set of lists with elements in a set ${\displaystyle X}$.

A monoidal signature ${\displaystyle \Sigma }$ is given by:

• a set ${\displaystyle \Sigma _{0}}$ of generating objects, the lists of generating objects in ${\textstyle \Sigma _{0}^{\star }}$ are also called types,
• a set ${\displaystyle \Sigma _{1}}$ of generating arrows, also called boxes,
• a pair of functions ${\displaystyle {\text{dom}},{\text{cod}}:\Sigma _{1}\to \Sigma _{0}^{\star }}$ which assign a domain and codomain to each box, i.e. the input and output types.

A morphism of monoidal signature ${\displaystyle F:\Sigma \to \Sigma '}$ is a pair of functions ${\displaystyle F_{0}:\Sigma _{0}\to \Sigma '_{0}}$ and ${\displaystyle F_{1}:\Sigma _{1}\to \Sigma '_{1}}$ which is compatible with the domain and codomain, i.e. such that ${\displaystyle {\text{dom}}\circ F_{1}\ =\ F_{0}\circ {\text{dom}}}$ and ${\displaystyle {\text{cod}}\circ F_{1}\ =\ F_{0}\circ {\text{cod}}}$. Thus we get the category ${\displaystyle \mathbf {MonSig} }$ of monoidal signatures and their morphisms.

There is a forgetful functor ${\displaystyle U:\mathbf {MonCat} \to \mathbf {MonSig} }$ which sends a monoidal category to its underlying signature and a monoidal functor to its underlying morphism of signatures, i.e. it forgets the identity, composition and tensor. The free functor ${\displaystyle C_{-}:\mathbf {MonSig} \to \mathbf {MonCat} }$, i.e. the left adjoint to the forgetful functor, sends a monoidal signature ${\displaystyle \Sigma }$ to the free monoidal category ${\displaystyle C_{\Sigma }}$ it generates.

String diagrams (with generators from ${\displaystyle \Sigma }$) are arrows in the free monoidal category ${\displaystyle C_{\Sigma }}$.^[8] The interpretation in a monoidal category ${\displaystyle D}$ is a defined by a monoidal functor ${\displaystyle F:C_{\Sigma }\to D}$, which by freeness is uniquely determined by a morphism of monoidal signatures ${\displaystyle F:\Sigma \to U(D)}$. Intuitively, once the image of generating objects and arrows are given, the image of every diagram they generate is fixed.

Geometric

A topological graph, also called a one-dimensional cell complex, is a tuple ${\displaystyle (\Gamma ,\Gamma _{0},\Gamma _{1})}$ of a Hausdorff space ${\displaystyle \Gamma }$, a closed discrete subset ${\displaystyle \Gamma _{0}\subseteq \Gamma }$ of nodes and a set of connected components ${\displaystyle \Gamma _{1}}$ called edges, each homeomorphic to an open interval with boundary in ${\displaystyle \Gamma _{0}}$ and such that ${\textstyle \Gamma -\Gamma _{0}=\coprod \Gamma _{1}}$.

A plane graph between two real numbers ${\displaystyle a,b\in \mathbb {R} }$ with ${\displaystyle a<b}$ is a finite topological graph embedded in ${\displaystyle \mathbb {R} \times [a,b]}$ such that every point ${\displaystyle x\in \Gamma \ \cap \ \mathbb {R} \times \{a,b\}}$ is also a node ${\displaystyle x\in \Gamma _{0}}$ and belongs to the closure of exactly one edge in ${\displaystyle \Gamma _{1}}$. Such points are called outer nodes, they define the domain and codomain ${\displaystyle {\text{dom}}(\Gamma ),{\text{cod}}(\Gamma )\in \Gamma _{1}^{\star }}$ of the string diagram, i.e. the list of edges that are connected to the top and bottom boundary. The other nodes ${\displaystyle f\in \Gamma _{0}\ -\ \{a,b\}\times \mathbb {R} }$ are called inner nodes.

A plane graph is progressive, also called recumbent, when the vertical projection ${\displaystyle e\to [a,b]}$ is injective for every edge ${\displaystyle e\in \Gamma _{1}}$. Intuitively, the edges in a progressive plane graph go from top to bottom without bending backward. In that case, each edge can be given a top-to-bottom orientation with designated nodes as source and target. One can then define the domain and codomain ${\displaystyle {\text{dom}}(f),{\text{cod}}(f)\in \Gamma _{1}^{\star }}$ of each inner node ${\displaystyle f}$, given by the list of edges that have source and target.

A plane graph is generic when the vertical projection ${\displaystyle \Gamma _{0}-\{a,b\}\times \mathbb {R} \to [a,b]}$ is injective, i.e. no two inner nodes are at the same height. In that case, one can define a list ${\displaystyle {\text{boxes}}(\Gamma )\in \Gamma _{0}^{\star }}$ of the inner nodes ordered from top to bottom.

A progressive plane graph is labeled by a monoidal signature ${\displaystyle \Sigma }$ if it comes equipped with a pair of functions ${\displaystyle v_{0}:\Gamma _{1}\to \Sigma _{0}}$ from edges to generating objects and ${\displaystyle v_{1}:\Gamma _{0}-\{a,b\}\times \mathbb {R} \to \Sigma _{1}}$ from inner nodes to generating arrows, in a way compatible with domain and codomain.

A deformation of plane graphs is a continuous map ${\displaystyle h:\Gamma \times [0,1]\to [a,b]\times \mathbb {R} }$ such that

• the image of ${\displaystyle h(-,t)}$ defines a plane graph for all ${\displaystyle t\in [0,1]}$,
• for all ${\displaystyle x\in \Gamma _{0}}$, if ${\displaystyle h(x,t)}$ is an inner node for some ${\displaystyle t}$ it is inner for all ${\displaystyle t\in [0,1]}$.

A deformation is progressive (generic, labeled) if ${\displaystyle h(-,t)}$ is progressive (generic, labeled) for all ${\displaystyle t\in [0,1]}$. Deformations induce an equivalence relation with ${\displaystyle \Gamma \sim \Gamma '}$ if and only if there is some ${\displaystyle h}$ with ${\displaystyle h(-,0)=\Gamma }$ and ${\displaystyle h(-,1)=\Gamma '}$. String diagrams are equivalence classes of labeled progressive plane graphs. Indeed, one can define:

• the identity diagram ${\displaystyle {\text{id}}(x)}$ as a set of parallel edges labeled by some type ${\displaystyle x\in \Sigma _{0}^{\star }}$,
• the composition of two diagrams as their vertical concatenation with the codomain of the first identified with the domain of the second,
• the tensor of two diagrams as their horizontal concatenation.

Combinatorial

While the geometric definition makes explicit the link between category theory and low-dimensional topology, a combinatorial definition is necessary to formalise string diagrams in computer algebra systems and use them to define computational problems. One such definition is to define string diagrams as equivalence classes of well-typed formulae generated by the signature, identity, composition and tensor. In practice, it is more convenient to encode string diagrams as formulae in generic form, which are in bijection with the labeled generic progressive plane graphs defined above.

Fix a monoidal signature ${\displaystyle \Sigma }$. A layer is defined as a triple ${\displaystyle (x,f,y)\in \Sigma _{0}^{\star }\times \Sigma _{1}\times \Sigma _{0}^{\star }=:L(\Sigma )}$ of a type ${\displaystyle x}$ on the left, a box ${\displaystyle f}$ in the middle and a type ${\displaystyle y}$ on the right. Layers have a domain and codomain ${\displaystyle {\text{dom}},{\text{cod}}:L(\Sigma )\to \Sigma _{0}^{\star }}$ defined in the obvious way. This forms a directed multigraph, also known as a quiver, with the types as vertices and the layers as edges. A string diagram ${\displaystyle d}$ is encoded as a path in this multigraph, i.e. it is given by:

• a domain ${\displaystyle {\text{dom}}(d)\in \Sigma _{0}^{\star }}$ as starting point
• a length ${\displaystyle {\text{len}}(d)=n\geq 0}$,
• a list of ${\displaystyle {\text{layers}}(d)=d_{1}\dots d_{n}\in L(\Sigma )}$

such that ${\displaystyle {\text{dom}}(d_{1})={\text{dom}}(d)}$ and ${\displaystyle {\text{cod}}(d_{i})={\text{dom}}(d_{i+1})}$ for all ${\displaystyle i<n}$. In fact, the explicit list of layers is redundant, it is enough to specify the length of the type to the left of each layer, known as the offset. The whiskering ${\displaystyle d\otimes z}$ of a diagram ${\displaystyle d=(x_{1},f_{1},y_{1})\dots (x_{n},f_{n},y_{n})}$ by a type ${\displaystyle z}$ is defined as the concatenation to the right of each layer ${\displaystyle d\otimes z=(x_{1},f_{1},y_{1}z)\dots (x_{n},f_{n},y_{n}z)}$ and symmetrically for the whiskering ${\displaystyle z\otimes d}$ on the left. One can then define:

• the identity diagram ${\displaystyle {\text{id}}(x)}$ with ${\displaystyle {\text{len}}({\text{id}}(x))=0}$ and ${\displaystyle {\text{dom}}({\text{id}}(x))=x}$,
• the composition of two diagrams as the concatenation of their list of layers,
• the tensor of two diagrams as the composition of whiskerings ${\displaystyle d\otimes d'=d\otimes {\text{dom}}(d')\ \circ \ {\text{cod}}(d)\otimes d'}$.

Note that because the diagram is in generic form (i.e. each layer contains exactly one box) the definition of tensor is necessarily biased: the diagram on the left hand-side comes above the one on the right-hand side. One could have chosen the opposite definition ${\textstyle d\otimes d'={\text{dom}}(d)\otimes d'\ \circ \ d\otimes {\text{cod}}(d')}$.

Two diagrams are equal (up to the axioms of monoidal categories) whenever they are in the same equivalence class of the congruence relation generated by the interchanger:$${\displaystyle d\otimes {\text{dom}}(d')\ \circ \ {\text{cod}}(d)\otimes d'\quad =\quad {\text{dom}}(d)\otimes d'\ \circ \ d\otimes {\text{cod}}(d')}$$That is, if the boxes in two consecutive layers are not connected then their order can be swapped. Intuitively, if there is no communication between two parallel processes then the order in which they happen is irrelevant.

The word problem for free monoidal categories, i.e. deciding whether two given diagrams are equal, can be solved in polynomial time. The interchanger is a confluent rewriting system on the subset of boundary connected diagrams, i.e. whenever the plane graphs have no more than one connected component which is not connected to the domain or codomain and the Eckmann–Hilton argument does not apply.^[9]

Extension to 2-categories

The idea is to represent structures of dimension d by structures of dimension 2-d, using Poincaré duality. Thus,

• an object is represented by a portion of plane,
• a 1-cell ${\displaystyle f:A\to B}$ is represented by a vertical segment—called a string—separating the plane in two (the right part corresponding to A and the left one to B),
• a 2-cell ${\displaystyle \alpha :f\Rightarrow g:A\to B}$ is represented by an intersection of strings (the strings corresponding to f above the link, the strings corresponding to g below the link).

The parallel composition of 2-cells corresponds to the horizontal juxtaposition of diagrams and the sequential composition to the vertical juxtaposition of diagrams.

Duality between commutative diagrams (on the left hand side) and string diagrams (on the right hand side)

A monoidal category is equivalent to a 2-category with a single 0-cell. Intuitively, going from monoidal categories to 2-categories amounts to adding colours to the background of string diagrams.

Examples

The snake equation

Consider an adjunction ${\displaystyle (F,G,\eta ,\varepsilon )}$ between two categories ${\displaystyle {\mathcal {C}}}$ and ${\displaystyle {\mathcal {D}}}$ where ${\displaystyle F:{\mathcal {C}}\leftarrow {\mathcal {D}}}$ is left adjoint of ${\displaystyle G:{\mathcal {C}}\rightarrow {\mathcal {D}}}$ and the natural transformations ${\displaystyle \eta :I\rightarrow GF}$ and ${\displaystyle \varepsilon :FG\rightarrow I}$ are respectively the unit and the counit. The string diagrams corresponding to these natural transformations are:

String diagram of the unit

String diagram of the counit

String diagram of the identity

The string corresponding to the identity functor is drawn as a dotted line and can be omitted. The definition of an adjunction requires the following equalities:

${\displaystyle {\begin{aligned}(\varepsilon F)\circ F(\eta )&=1_{F}\\G(\varepsilon )\circ (\eta G)&=1_{G}\end{aligned}}}$

The first one is depicted as

Diagrammatic representation of the equality ${\displaystyle (\varepsilon F)\circ F(\eta )=1_{F}}$

A monoidal category where every object has a left and right adjoint is called a rigid category. String diagrams for rigid categories can be defined as non-progressive plane graphs, i.e. the edges can bend backward.

In the context of categorical quantum mechanics, this is known as the snake equation.

The category of Hilbert spaces is rigid, this fact underlies the proof of correctness for the quantum teleportation protocol. The unit and counit of the adjunction are an abstraction of the Bell state and the Bell measurement respectively. If Alice and Bob share two qubits Y and Z in an entangled state and Alice performs a (post-selected) entangled measurement between Y and another qubit X, then this qubit X will be teleported from Alice to Bob: quantum teleportation is an identity morphism.

An illustration of the diagrammatic calculus: the quantum teleportation protocol as modeled in categorical quantum mechanics.

The same equation appears in the definition of pregroup grammars where it captures the notion of information flow in natural language semantics. This observation has led to the development of the DisCoCat framework and quantum natural language processing.

Hierarchy of graphical languages

Many extensions of string diagrams have been introduced to represent arrows in monoidal categories with extra structure, forming a hierarchy of graphical languages which is classified in Selinger's Survey of graphical languages for monoidal categories.^[10]

• Braided monoidal categories with 3-dimensional diagrams, a generalisation of braid groups.
• Symmetric monoidal categories with 4-dimensional diagrams where edges can cross, a generalisation of the symmetric group.
• Ribbon categories with 3-dimensional diagrams where the edges are undirected, a generalisation of knot diagrams.
• Compact closed categories with 4-dimensional diagrams where the edges are undirected, a generalisation of Penrose graphical notation.
• Dagger categories where every diagram has a horizontal reflection.

List of applications

String diagrams have been used to formalise the following objects of study.

• Concurrency theory^[11]
• Artificial neural networks^[12]
• Game theory^[13]
• Bayesian probability^[14]
• Consciousness^[15]
• Markov kernels^[16]
• Signal-flow graphs^[17]
• Conjunctive queries^[18]
• Bidirectional transformations^[19]
• Categorical quantum mechanics
• Quantum circuits, measurement-based quantum computing and quantum error correction, see ZX-calculus
• Natural language processing, see DisCoCat
• Quantum natural language processing

See also

• Proof nets, a generalisation of string diagrams used to denote proofs in linear logic
• Existential graphs, a precursor of string diagrams used to denote formulae in first-order logic
• Penrose graphical notation and Feynman diagrams, two precursors of string diagrams in physics
• Tensor networks, the interpretation of string diagrams in vector spaces, linear maps and tensor product

References

1. Hotz, Günter (1965). "Eine Algebraisierung des Syntheseproblems von Schaltkreisen I.". Elektronische Informationsverarbeitung und Kybernetik. 1 (3): 185–205.
2. Penrose, Roger (1971). "Applications of negative dimensional tensors". Combinatorial Mathematics and Its Applications. 1: 221–244.
3. Baez, J.; Stay, M. (2011), Coecke, Bob (ed.), "Physics, Topology, Logic and Computation: A Rosetta Stone", New Structures for Physics, Lecture Notes in Physics, vol. 813, Berlin, Heidelberg: Springer, pp. 95–172, arXiv:0903.0340, Bibcode:2011LNP...813...95B, doi:10.1007/978-3-642-12821-9_2, ISBN 978-3-642-12821-9, S2CID 115169297, retrieved 2022-11-08
4. Joyal, André; Street, Ross (1991). "The geometry of tensor calculus, I". Advances in Mathematics. 88 (1): 55–112. doi:10.1016/0001-8708(91)90003-P.
5. "Categories: History of string diagrams (thread, 2017may02-...)". angg.twu.net. Retrieved 2022-11-11.
6. Brady, Geraldine; Trimble, Todd H (2000). "A categorical interpretation of CS Peirce's propositional logic Alpha". Journal of Pure and Applied Algebra. 149 (3): 213–239. doi:10.1016/S0022-4049(98)00179-0.
7. Haydon, Nathan; Sobociński, Pawe\l (2020). "Compositional diagrammatic first-order logic". International Conference on Theory and Application of Diagrams. Springer: 402–418.
8. Joyal, André; Street, Ross (1988). "Planar diagrams and tensor algebra". Unpublished Manuscript, Available from Ross Street's Website.
9. Vicary, Jamie; Delpeuch, Antonin (2022). "Normalization for planar string diagrams and a quadratic equivalence algorithm". Logical Methods in Computer Science. 18.
10. Selinger, Peter (2010), "A survey of graphical languages for monoidal categories", New structures for physics, Springer, pp. 289–355, retrieved 2022-11-08
11. Abramsky, Samson (1996). "Retracing some paths in process algebra". International Conference on Concurrency Theory. Springer: 1–17.
12. Fong, Brendan; Spivak, David I.; Tuyéras, Rémy (2019-05-01). "Backprop as Functor: A compositional perspective on supervised learning". arXiv:1711.10455 [math.CT].
13. Ghani, Neil; Hedges, Jules; Winschel, Viktor; Zahn, Philipp (2018). "Compositional Game Theory". Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science. pp. 472–481. doi:10.1145/3209108.3209165. ISBN 9781450355834. S2CID 17887510.
14. Coecke, Bob; Spekkens, Robert W (2012). "Picturing classical and quantum Bayesian inference". Synthese. 186 (3): 651–696. arXiv:1102.2368. doi:10.1007/s11229-011-9917-5. S2CID 3736082.
15. Signorelli, Camilo Miguel; Wang, Quanlong; Coecke, Bob (2021-10-01). "Reasoning about conscious experience with axiomatic and graphical mathematics". Consciousness and Cognition. 95: 103168. doi:10.1016/j.concog.2021.103168. hdl:10230/53097. ISSN 1053-8100. PMID 34627099. S2CID 235683270.
16. Fritz, Tobias (August 2020). "A synthetic approach to Markov kernels, conditional independence and theorems on sufficient statistics". Advances in Mathematics. 370: 107239. arXiv:1908.07021. doi:10.1016/j.aim.2020.107239. S2CID 201103837.
17. Bonchi, Filippo; Sobociński, Pawel; Zanasi, Fabio (September 2014). "A Categorical Semantics of Signal Flow Graphs". CONCUR 2014 – Concurrency Theory. Lecture Notes in Computer Science. Vol. CONCUR 2014 - Concurrency Theory - 25th International Conference. Rome, Italy. pp. 435–450. doi:10.1007/978-3-662-44584-6_30. ISBN 978-3-662-44583-9. S2CID 18492893.{{cite book}}: CS1 maint: location missing publisher (link)
18. Bonchi, Filippo; Seeber, Jens; Sobocinski, Pawel (2018-04-20). "Graphical Conjunctive Queries". arXiv:1804.07626 [cs.LO].
19. Riley, Mitchell (2018). "Categories of optics". arXiv:1809.00738 [math.CT].

External links

• TheCatsters (2007). String diagrams 1 (streamed video). Youtube. Archived from the original on 2021-12-19.
• String diagrams at the nLab
• DisCoPy, a Python toolkit for computing with string diagrams

External links

• Media related to String diagram at Wikimedia Commons