Abstract Physical Traces

Introduction

In [Abramsky and Coecke CTCS‘02] we showed that vector space projectors

In [Abramsky and Coecke LiCS‘04] we showed that such projectors can be defined and their crucial properties proved at the abstract level of strongly compact closed categories. This categorical structure is a major ingredient of the categorical axiomatization in [Abramsky and Coecke LiCS‘04] of quantum theory [von Neumann 1932]. It captures quantum entanglement and its behavioral properties [Coecke 2003]. In this paper we will improve on the definition of strong compact closure, enabling a characterization in terms of adjoints - in the linear algebra sense, suitably abstracted - and yanking, without explicit reference to compact closure, and enabling a nicer treatment of bipartite projectors, coherent with the treatment of arbitrary projectors in [Abramsky and Coecke LiCS‘04].

We are then able to show that the constructions in [Abramsky and Coecke CTCS‘02] for realizing arbitrary morphisms and the trace by projectors also carry over to the abstract level, and that these constructions admit an information-flow interpretation in the spirit of the one for additive traces [Abramsky 1996, Abramsky, Haghverdi and Scott 2002]. It is the information flow due to (strong) compact closure which is crucial for the abstract formulation, and for the proofs of correctness of protocols such as quantum teleportation [Abramsky and Coecke LiCS‘04].

A concise presentation of (very) basic quantum mechanics which supports the developments in this paper can be found in [Abramsky and Coecke CTCS‘02, Coecke 2003]. However, the reader with a sufficient categorical background might find the abstract presentation in [Abramsky and Coecke LiCS‘04] more enlightening.

Strongly compact closed categories

As shown in [Kelly and Laplaza 1980], in any monoidal category ${\bf C}$, the endomorphism monoid ${\bf C}({\rm I},{\rm I})$ is commutative. Furthermore any $s:{\rm I}\to{\rm I}$ induces a natural transformation {diagram} Hence, setting $s\bullet f$ for $f\circ s_{A}=s_{B}\circ f$ for $f:A\rightarrow B$, we have

Recall from [Kelly and Laplaza 1980] that a compact closed category is a symmetric monoidal category ${\bf C}$, in which, when ${\bf C}$ is viewed as a one-object bicategory, every one-cell $A$ has a left adjoint $A^{*}$. Explicitly this means that for each object $A$ of ${\bf C}$ there exists a dual object $A^{*}$, a unit $\eta_{A}:{\rm I}\to A^{*}\otimes A$ and a counit $\epsilon_{A}:A\otimes A^{*}\to{\rm I}$, and that the diagrams

both commute. Alternatively, a compact closed category may be defined as a $*$-autonomous category [Barr 1979] with a self-dual tensor, hence a model of ‘degenerate’ linear logic [Seely 1998].

For each morphism $f:A\to B$ in a compact closed category we can construct a dual $f^{*}$, a name $\ulcorner f\urcorner$ and a coname $\llcorner f\lrcorner$, respectively as {diagram} {diagram} In particular, the assignment $f\mapsto f^{*}$ extends $A\mapsto A^{*}$ into a contravariant endofunctor with $A\simeq A^{**}$. In any compact closed category, we have

so ‘elements’ of $A\otimes B$ are in biunique correspondence with names/conames of morphisms $f:A\to B$

Typical examples are $({\bf Rel},\times)$ where $X^{*}=X$ and where for $R\subseteq X\times Y$,

where $\{\bar{e}_{i}^{V}\}_{i=1}^{i=n}$ is the base of $V^{*}$ satisfying $\bar{e}_{i}^{V}(e^{V}_{j})=\delta_{ij}$, and similarly for $W$. Another example is the category $n$Cob of $n$-dimensional cobordisms which is regularly considered in mathematical physics, e.g. [Baez 2004].

Each compact closed category admits a categorical trace, that is, for every morphism $f:A\otimes C\to B\otimes C$ a trace ${\rm Tr}_{A,B}^{C}(f):A\to B$ is specified and satisfies certain axioms [Joyal, Street and Verity 1996]. Indeed, we can set

where $\rho_{X}:X\simeq X\otimes{\rm I}$ and $\sigma_{X,Y}:X\otimes Y\simeq Y\otimes X$. In $({\bf Rel},\times)$ this yields

where $(m_{ikjl})$ is the matrix of $f$ in bases $\{e_{i}^{V}\!\otimes e_{k}^{U}\}_{ik}$ and $\{e_{j}^{W}\!\otimes e_{l}^{U}\}_{jl}$.

A strongly compact closed category is a compact closed category ${\bf C}$ in which $A=A^{**}$ and $(A\otimes B)^{*}\!\!=A^{*}\otimes B^{*}$, and which comes together with an involutive covariant compact closed functor $(\ )_{*}:{\bf C}\to{\bf C}$ which assigns each object $A$ to its dual $A^{*}$.

So in a strongly compact closed category we have two involutive functors, namely a contravariant one $(\ )^{*}:{\bf C}\to{\bf C}$ and a covariant one $(\ )_{*}:{\bf C}\to{\bf C}$ which coincide in their action on objects. Recall that $(\ )_{*}$ being compact closed functor means that it preserves the monoidal structure strictly, and unit and counit i.e.

where $u_{\rm I}:{\rm I}^{*}\simeq{\rm I}$. This in particular implies that $(\ )_{*}$ commutes with $(\ )^{*}$ since $(\ )^{*}$ is definable in terms of the monoidal structure, $\eta$ and $\epsilon$ — in [Abramsky and Coecke LiCS‘04] we only assumed commutation of $(\ )_{*}$ and $(\ )^{*}$ instead of the stronger requirement of equations (4).

For each morphism $f:A\to B$ in a strongly compact closed category we can define an adjoint — as in linear algebra — as

It turns out that we can also define strong compact closure by taking the adjoint to be a primitive.

A strongly compact closed category can be equivalently defined as a symmetric monoidal category ${\bf C}$ which comes with

a monoidal involutive assignment $A\mapsto A^{*}$ on objects,

an identity-on-objects, contravariant, strict monoidal, involutive functor $f\mapsto f^{\dagger}$, and,

for each object $A$ a unit $\eta_{A}:{\rm I}\to A^{*}\otimes A$ with $\eta_{A^{*}}=\sigma_{A^{*}\!,A}\circ\eta_{A}$ and such that either the diagram

commutes, where $\sigma_{A,A}:A\otimes A\simeq A\otimes A$ is the twist map.

While diagram (5) is the analogue to diagram (1) with $\eta_{A}^{\dagger}\circ\sigma_{A,A^{*}}$ playing the role of the coname, diagram (6) expresses yanking with respect to the canonical trace of the compact closed structure. We only need one commuting diagram as compared to diagrams (1) and (2) in the definition of compact closure and hence in Definition 2.1 since due to the strictness assumption (i.e. $A\mapsto A^{*}$ being involutive) we were able to replace the second diagram by $\eta_{A^{*}}=\sigma_{A^{*}\!,A}\circ\eta_{A}$.

Returning to the main issue of this paper, we are now able to construct a bipartite projector (i.e. a projector on an object of type $A\otimes B$) as

from bipartite elements to bipartite projectors. Note that the use of $(\ )_{*}$ is essential in order for ${\rm P}_{f}$ to be endomorphic.

We can normalize these projectors ${\rm P}_{f}$ by considering $s_{f}\bullet{\rm P}_{f}$ for $s_{f}:=(\llcorner f_{*}\lrcorner\circ\ulcorner f\urcorner)^{-1}$ (provided this inverse exists in ${\bf C}({\rm I},{\rm I})$), yielding

Any compact closed category in which $(\ )^{\ast}$ is the identity on objects is trivially strongly compact closed. Examples include relations and finite-dimensional real inner-product spaces, and also the interaction category SProc from [].

So, importantly, are finite-dimensional complex Hilbert spaces and linear maps $({\bf FdHilb},\otimes)$. We take ${\cal H}^{*}$ to be the conjugate space, that is, the Hilbert space with the same elements as ${\cal H}$ but with the scalar multiplication and the inner-product in ${\cal H}^{*}$ defined by

where $\bar{\alpha}$ is the complex conjugate of $\alpha$. Hence we can still take $\epsilon_{\cal H}$ to be the sesquilinear inner-product.

Conversely, an abstract notion of inner product can be defined in any strongly compact closed category. Given ‘elements’ $\psi,\phi:{\rm I}\to A$, we define

As an example, the inner-product in $(\mathbf{Rel},\times)$ is, for $x,y\subseteq\{*\}\times X$,

with $1_{{\rm I}}:=\{*\}\times\{*\}\subseteq\{*\}\times\{*\}$ and $0_{{\rm I}}:=\emptyset\subseteq\{*\}\times\{*\}$. When defining unitarity of an isomorphism $U:A\to B$ by $U^{-1}=U^{\dagger}$ we can prove the defining properties both of inner-product space adjoints and inner-product space unitarity:

for $\psi,\varphi:{\rm I}\to A$, $\phi:{\rm I}\to B$, $f:B\to A$ and $U:A\to B$. As shown in [Abramsky and Coecke LiCS‘04], an alternative way to define the abstract inner-product is {diagram} where $u_{\rm I}:{\rm I}\simeq{\rm I}^{*}$ and $\rho_{\rm I}:{\rm I}\simeq{\rm I}\otimes{\rm I}$. Here the key data we use is the coname $\epsilon_{A}:A\otimes A^{*}\to{\rm I}$ , and also $(\ )_{*}$: cf. also the above examples of both real and complex inner-product spaces where $\epsilon_{A}:=\langle-\mid-\rangle$. Hence it is fair to say that

Finally, note that abstract bipartite projectors ${\rm P}_{f}$ have two components: a ‘name’-component and a ‘coname’-component. While in most algebraic treatments involving projectors these are taken to be primitive, in our setting projectors are composite entities, and this decomposition will carry over to their crucial properties (see below). We depict names, conames, and projectors as follows:

In this representation, diagrams (1) and (6) can be expressed as the respective pictures

being equal to the identity. Below we will express equalities in this manner.

Information-flow through projectors

for $A\rTo^{f}B\rTo^{g}C$, $\rho_{A}:A\simeq A\otimes{\rm I}$ and $\lambda_{C}:C\simeq{\rm I}\otimes C$, i.e.,

Following [Abramsky and Coecke LiCS‘04, Coecke 2003] we can think of the information flowing along the grey line in the diagram below, being acted on by the morphisms which label the coname and the name respectively.

We refer to this as the information-flow interpretation of compact closure. Many variants can also be derived [Abramsky and Coecke LiCS‘04, Coecke 2003]. The pictures expressing the non-trivial branches of diagrams (1) and (6) become

Lemma 2 of [Abramsky and Coecke CTCS‘02], which states that we can realize any linear map $g:V\to W$ using only $({\bf FdHilb},\otimes)$-projectors, follows trivially by setting $f:=1_{V}$ while viewing both $\llcorner 1_{V\!\!}\lrcorner$ and $\ulcorner g\urcorner$ as being parts of projectors — all this is up to a scalar multiple which depends on the input of ${\rm P}_{g}$. Note that by functoriality $1_{V^{*}}=(1_{V})_{*}$ and hence ${\rm P}_{(1_{V})_{*}}\!\!={\rm P}_{1_{V^{*}}}$. As discussed in [Coecke 2003] this feature constitutes the core of logic-gate teleportation, which is a fault-tolerant universal quantum computational primitive [Gottesman and Chuang 1999]. Explicitly,

In a strongly compact closed category ${\bf C}$ for $f:A\to B$,

where $s(f,\xi)\in{\bf C}({\rm I},{\rm I})$ is a scalar, $\sigma_{A,B}:A\otimes A^{*}\!\otimes B\to B\otimes A^{*}\!\otimes A$ is symmetry, $\xi:A^{*}\!\to B^{*}$ is arbitrary, and $s(f,f_{*})=1_{\rm I}$.

Lemma 1 of [Abramsky and Coecke CTCS‘02], that is, we can realize the $({\bf FdHilb},\otimes)$-trace by means of projectors trivially follows from eq.(3), noting that $\eta=\ulcorner 1\urcorner$ and $\epsilon=\llcorner 1\lrcorner$ and again viewing these as parts of projectors. Explicitly:

In a strongly compact closed category ${\bf C}$ for $f:A\otimes C\to B\otimes C$,

where $s(\xi)\in{\bf C}({\rm I},{\rm I})$ is a scalar, $\xi:C\to C$ is arbitrary, and $s(1_{C})=1_{\rm I}$.

Indeed, since $\sigma_{A^{*}\!,A}\circ\ulcorner 1_{A}\urcorner=\ulcorner(1_{\!A})^{\!*\!}\urcorner=\ulcorner 1_{\!A^{*}\!}\!\!\urcorner$ by functoriality, eq.(3) is

Interestingly, using the information-flow interpretation of compact closure, provided $f$ itself admits an information-flow interpretation, this construction admits one too, and can be regarded as a feed-back construction. As an example, for $f:=(g_{1}\otimes g_{2})\circ\sigma\circ(f_{1}\otimes f_{2})$, we have (use naturality of $\sigma$, the definition of (co)name and compositionality)

When taking $f$ itself to be a projector ${\rm P}_{g}=\ulcorner g\urcorner\circ\llcorner g_{*}\!\lrcorner$ we have

using $\sigma\circ\ulcorner f\urcorner=\ulcorner f^{\!*\!}\urcorner$, naturality of $\sigma$ and compositionality. Note that the information-flow in the loop is in this case ‘forward’ as compared to ‘backward’ in the previous example. For $f$ of type $A\otimes(C_{1}\otimes\ldots\otimes C_{n})\to B\otimes(C_{1}\otimes\ldots\otimes C_{n})$ we can have multiple looping:

Note the resemblance between this behavior and that of additive traces [Abramsky 1996, Abramsky, Haghverdi and Scott 2002] such as the one on $({\bf Rel},+)$ namely

for $R\subseteq X+Z\times Y+Z$. In this case we can think of a particle traveling trough a network where the elements $x\in X$ are the possible states of the particle. The morphisms $R\subseteq X\times Y$ are processes that impose a (non-deterministic) change of state $x\in X$ to $y\in R(x)$, emptyness of $R(x)$ corresponding to undefinedness. The sum $X+Y$ is the disjoint union of state sets and $R+S$ represents parallel composition of processes. The trace ${\rm Tr}_{X,Y}^{Z}(R)$ is feedback, that is, entering in a state $x\in X$ the particle will either halt, exit at $y\in Y$ or, exit at $z_{1}\in Z$ in which case it is fed back into $R$ at the $Z$ entrance, and so on, until it halts or exits at $y\in Y$.

For a more conceptual view of the matter, note that the examples illustrated above all live in the free compact closed category generated by a suitable category in the sense of [Kelly and Laplaza 1980]. Indeed our diagrams, which are essentially ‘proof nets for compact closed logic’ [Abramsky and Duncan 2004], give a presentation of this free category. Of course, these diagrams will then have representations in any compact closed category. For a detailed discussion of free contsructions for traced and strongly compact closed categories, see the forthcoming paper [Abr05].

(𝐅𝐑𝐞𝐥,×,Tr)({\bf FRel},\times,{\rm Tr}) from (𝐅𝐝𝐇𝐢𝐥𝐛,⊗,Tr)({\bf FdHilb},\otimes,{\rm Tr})

(using distributivity and ${\rm I}\otimes{\rm I}\simeq{\rm I}$), and

where $\phi^{T}$ denotes the transpose of $\psi$. In the case of $({\bf FRel},\times)$, this yields the strong compact closed structure described above. If the abelian semiring ${\bf C}({\rm I},{\rm I})$ also admits a non-trivial involution $(\ )_{*}$, an alternative compact closed structure arises by defining $\epsilon::(\psi,\phi)\mapsto(\phi^{T})_{*}\circ\psi$, where $(\ )_{*}$ is applied pointwise. The corresponding strong compact closed structure involves defining the adjoint of a matrix $M$ to be $M^{T}_{*}$, i.e. the involution is applied componentwise to the transpose of $M$. In this way we obtain (up to categorical equivalence) the strong compact closed structure on $({\bf FdHilb},\otimes)$ described above, taking $(\ )_{*}$ to be complex conjugation.

References