Quantum Relaxations of CSP and Structure Isomorphism

The fundamental structures of computation –graphs, strings, databases, programs, etc. all find a convenient mathematical representation in terms of (finite) logical structures, known as relational structures. It is not surprising then that many of the most important challenges and achievements of theoretical computer science can be phrased in terms of the properties of these structures, and how they interact with one another. We will focus on two decision problems about relational structures that are of central importance in theoretical computer science. The first is known as the constraint satisfaction problem¹¹1This problem is also known as structure homomorphism problem. We shall use the two terms interchangeably. (CSP). In modern terms, it can be phrased as follows.

Constraint Satisfaction Problem: Given as input a pair of relational structures $𝒳,𝒴$ over the same signature, decide if there exists a homomorphism $𝒳\to 𝒴$.

The importance of CSP is underscored by the fact that instances of it arise naturally in practically every area of modern science. For example, in bioinformatics, CSPs arise in protein folding, where the challenge is to determine a protein’s 3D structure while satisfying constraints related to chemical bonds and angles. In database theory, CSPs capture the problem of query evaluation, where determining whether a query can be satisfied involves finding a homomorphism between the query structure and a database. In robotics, the path planning problem, in which a robot aims to navigate from some starting position to a goal position while avoiding obstacles can be formulated as a CSP.

The second problem is known as structure isomorphism.

Structure isomorphism: Given as input a pair of relational structures $𝒳,𝒴$ over the same signature, decide if there exists an isomorphism $𝒳\cong 𝒴$.

The study of structure isomorphism is of central importance in computational complexity theory. It is clear that this problem is in NP, however, structure isomorphism is not known to be solvable in polynomial time nor to be NP-complete. Babai’s recent breakthrough [5] places the problem in quasi-polynomial time which lends some support to the idea that structure isomorphism might be an NP-intermediate problem.

Ever since the pioneering works of Bell [6] and Kochen-Specker [19] in the 1960s physicists have known that a system which operates according to the laws of quantum physics is capable of producing correlations that a system operating according to classical physics cannot. Today, this phenomenon is referred to as quantum advantage and is being extensively studied with the hope that it will allow us to build devices such as quantum computers that can perform information processing tasks which are out of reach for classical computers.

An important theoretical tool for understanding quantum advantage is the framework of non-local games. In these games, two collaborating players (usually called Alice and Bob) are placed in separate rooms so that they are unable to communicate with each other. A referee then asks each of them some questions and compares their answers. The two players win the game if the referee is satisfied that their answers agree with some pre-defined winning conditions. The remarkable feature of these games is that if the players are allowed to share an entangled quantum state between them, they can sometimes win games that they would have otherwise lost. In these cases we say that the players have a quantum winning strategy but no classical winning strategy. The study of non-local games has led to tremendous advances in our understanding of quantum theory, and has even helped solve a major open problem in mathematics, known as the Connes embedding question [18].

Over the past few decades, it has become clear that many standard decision problems studied in theoretical computer science, which are special instances of CSP, can be rephrased in the language of non-local games. This prompted the authors of [1] to recast CSP as a non-local game. For the purposes of this introduction, we aim to convey some intuition for the game by describing its operation in the special case where the relational structures in question are graphs.

We say that Alice and Bob have a perfect strategy in the above game if they can always win the game regardless of what questions the verifier decides to ask them. If only classical (and non-signalling) strategies are allowed then Alice and Bob have a perfect strategy precisely when CSP$(𝒳,𝒴)$ is solvable. In other words, they win the game perfectly if and only if there exists a graph homomorphism $𝒳\to 𝒴$. However, when the players are allowed to use quantum resources, they can sometimes win this game perfectly even if $𝒳\to ̸𝒴$. Based on these facts, we can say that there exists a quantum homomorphism from $𝒳$ to $𝒴$ and write $𝒳\stackrel{𝑞}{\to }𝒴$ whenever Alice and Bob have a perfect quantum strategy in the $(𝒳,𝒴)$-CSP game. Clearly, every classical homomorphism is also a quantum homomorphism. This is why we are justified to say that quantum homomorphisms are a relaxation of classical homomorphisms.

A further important step taken in [1] was the introduction of a graded monad on $ℛ(\sigma )$, which they refer to as the quantum monad. We denote the functor component of this monad (which is parameterised by some Hilbert space $𝐇$) by ${\mathbb{Q}}_{𝑯}$. As with any monad ${\mathbb{Q}}_{𝑯}$ has a Kleisli category associated to it. The objects of this category are the objects of $ℛ(\sigma )$ while morphisms between objects $𝒳$ and $𝒴$ are maps in $ℛ(\sigma )$ of the form $𝒳\to {\mathbb{Q}}_{𝑯}𝒴$. The authors of [1] prove the following theorem which shows that such Kleisli morphisms are precisely quantum homomorphisms.

In this sense, ${\mathbb{Q}}_{𝑯}$ provides a categorical abstraction which perfectly captures the notion of quantum homomorphism.

In this paper we will solidify and extend the results of [1] by answering several open questions mentioned in their work. After introducing preliminary material in Section 2, we shall study the non-local CSP game in Section 3. Our first contribution in this section will be a comparison of the two alternative definitions of quantum graph homomorphisms introduced in [23] and [1]. We show that there exists a pair of graphs which are quantum homomorphic under the definition given in [23] but not under the definition in [1]. Our next contribution is to extend the characterisation of quantum homomorphisms in [1] which only holds in the tensor product framework to the commuting operator framework. In Section 4 we shall introduce a non-local structure isomorphism game, and show that much like the CSP game perfect quantum strategies in this game have a very special form. This will allow us to define the concept of quantum structure isomorphism. Finally, in Section 5 we explore categorical characterisations of quantum homomorphisms and quantum isomorphisms. As we have mentioned, it was already observed in [1] that quantum homomorphisms coincide with Kleisli morphisms of the graded quantum monad ${\mathbb{Q}}_{𝑯}$. Perhaps surprisingly we shall show that Kleisli isomorphism for this graded monad corresponds to classical isomorphism rather than quantum isomorphism. Thus, we shall adopt a different approach to provide a categorical account of quantum isomorphism. Namely, we will show that the functor ${\mathbb{Q}}_{𝑯}$ can be equipped with the structure of a “monad” with a partial multiplication operation. We will then show that Kleisli isomorphisms for this partial quantum monad coincide with quantum isomorphisms. This construction is motivated by the importance of partial algebraic structures in quantum information, which was first noticed in the seminal work of Kochen and Specker [19]. Detailed proofs are provided in the appendix.

A finite relational signature $\sigma$ is a set of relation symbols $\sigma =\{R_1,\mathrm{\dots },R_n\}$ where each symbol $R\in \sigma$ has an associated non-negative integer $ar(R)$ called its arity. A relational structure $𝒳$ with signature $\sigma$ is then a tuple $(X,R_1^{𝒳},\mathrm{\dots },R_n^{𝒳})$ where $X$ is a set known as the universe of $𝒳$ and for each $R\in \sigma ,R^{𝒳}\subseteq X^{ar(R)}$ is a relation of length $ar(R)$. A relational structure is said to be finite if its universe is finite.

Let $𝒳$ and $𝒴$ be two relational structures over the same signature $\sigma$. A function $f:X\to Y$ is said to preserve a relation $R\in \sigma$ with arity $k$ if $\forall 𝒙=(x_1,\mathrm{\dots },x_k)\in X^k:𝒙\in R^{𝒳}⟹𝒇\mathbf{(}𝒙\mathbf{)}=(f(x_1),\mathrm{\dots },f(x_k))\in R^{𝒴}$. Here we have adopted the convention that boldface lowercase letters denote tuples $𝒙=(x_1,\mathrm{\dots },x_k)\in X^k$. Moreover, whenever we use the notation $x_i$ we are implicitly implying that $x_i$ is the element at position $i$ of a tuple $𝒙$. We say that $f$ reflects a relation if the above holds with the implication reversed. $f$ is said to be a homomorphism if it preserves every $R\in \sigma$. If $f$ is bijective and reflects every relation it is called an isomorphism. A partial homomorphism is a partial function $g\subseteq X\times Y$ which preserves all relations. The category $ℛ(\sigma )$ has $\sigma$-structures as objects and $\sigma$-structure homomorphisms as morphisms.

We write ${ℬ}^{+}(𝐇)$ for the set of positive bounded operators on a Hilbert space $𝐇$ and $\mathrm{𝖯𝗋𝗈𝗃}(𝐇)$ for the set of (orthogonal) projectors on $𝐇$. We refer to two projectors $M,N$ as being orthogonal to each other if $MN=\mathrm{𝟎}$. We write $M\le N$ iff $N-M$ is positive semi-definite. $M$ and $N$ commute iff $MN-NM=\mathrm{𝟎}$. The product of two projectors is a projector iff they commute. For any family of projectors ${\{P_i\}}_i$ it holds that ${\sum }_i{P}_i\le I_{𝑯}$ iff $P_i{P}_j=\mathrm{𝟎}$ whenever $i\ne j$.

We recall two mathematical formalisms for studying different types of measurements on physical system. The first is known as a projection valued measurement (PVM). A PVM is a function $P:O\to \mathrm{𝖯𝗋𝗈𝗃}(𝐇)$ which satisfies ${\sum }_{o\in O}p(o)=I_{𝐇}$. Here, the elements of $O$ represent the possible outcomes of a measurement. We shall also consider positive operator-valued measurements (POVMs). A POVM is a function $P:O\to {ℬ}^{+}(𝐇)$ which satisfies ${\sum }_{o\in O}p(o)=I_{𝐇}$. As $\mathrm{𝖯𝗋𝗈𝗃}(𝐇)$ is contained in ${ℬ}^{+}(𝑯)$, it is clear that every PVM is a POVM. If a POVM $P:O\to {ℬ}^{+}(𝐇)$ is performed on a pure state $\psi \in 𝐇$ outcome $o\in O$ will be observed with probability ${\psi }^{†}p(o)\psi$. A set of POVMs ${\{P_i:O_i\to {ℬ}^{+}(𝐇)\}}_i\in [n]$ is commeasurable²²2Also known as compatible or jointly measurable. iff there exists a POVM $𝐏:{\prod }_{i\in [n]}{O}_i\to {ℬ}^{+}(𝐇)$ which marginalises to each of the $P_i$. A remarkable feature of quantum theory (one which is in fact necessary for quantum advantage [36]) is that not all observations are commeasurable. We will write $P_1\odot P_2$ whenever $P_1$ and $P_2$ are commeasurable. We remark that it is possible to have POVMs $P_1,P_2,P_3$ which are pairwise commeasurable but not triplewise commeasurable [15]. Two POVMs are said to commute iff every element of their image commutes. If we restrict our attention to PVMs then commeasurability has particularly nice characteristics summarised by the following lemma (see e.g. [14]).

Non-locality and its generalisation in the form of contextuality are important non-classical features of quantum mechanics. These phenomena have been extensively studied as a source of quantum advantage beginning with the pioneering works of Bell [6] and Kochen-Specker [19].

A (bipartite) non-local game is a cooperative game played between a verifier and two players, usually referred to as Alice and Bob. Formally, following [9] a non-local game is defined as $G=(X_a,X_b,Y_a,Y_b,\pi ,V)$ where $X_a,X_b$ are finite input sets, $Y_a,Y_b$ are finite output sets, $\pi$ is a probability distribution on $X_a\times X_b$, and $V:X_a\times X_b\times Y_a\times Y_b\to ℝ$ is called the payoff function. For our purposes, it suffices to think of $V$ as a $\{0,1\}$ valued boolean predicate. We will also assume that $\pi$ has full support. The game proceeds according to the following protocol:

1. 1.

   The verifier samples a pair $(x_a,x_b)\in X_a\times X_b$ using $\pi$ and sends $x_a$ to Alice and $x_b$ to Bob.

2. 2.

   Without communicating, Alice and Bob respond with $y_a\in Y_a$ and $y_b\in Y_b$ respectively.

3. 3.

   The players win the game if $V(x_a,x_b,y_a,y_b)=1$.

We focus on cases where the game consists of one round of the above protocol.

The goal of Alice and Bob is to maximise their winning probability. To achieve this goal they are allowed to agree on a fixed strategy S for the game beforehand. A correlation³³3Also known as a behaviour or empirical model. $p(y_a,y_b|x_a,x_b)$ represents the joint conditional probability of Alice and Bob responding with $y_a$ and $y_b$ on inputs $x_a$ and $x_b$ respectively.

There are several classes of strategies that Alice and Bob can employ in a non-local game. We are interested in three of these classes.

1. 1.

   A deterministic classical strategy $S_c=(f_a,f_b)$ is defined by two functions $f_a:X_a\to Y_a$ and $f_b:X_b\to Y_b$ which map inputs to outputs for each of Alice and Bob respectively. Hence we have $p(f_a(x_a),f_b(x_b)|x_a,x_b)=1$.

2. 2.

   A quantum tensor strategy $S_{\ast }=(\psi ,E,F)$ consists of a shared state $\psi \in {𝑯}_{𝑨}\otimes {𝑯}_{𝑩}$ for finite dimensional complex Hilbert spaces ${𝑯}_{𝑨},{𝑯}_{𝑩}$, and two sets, $E=\{E_x\}$ and $F=\{F_x\}$ where $E_x=\{E_{xy}:y\in Y_a\}$ for each $x\in X_a$ and $F_x=\{F_{xy}:y\in Y_b\}$ for each $x\in X_b$ are POVMs over ${𝑯}_{𝑨}$ and ${𝑯}_{𝑩}$ respectively. Upon receiving $x_a\in X_a$ and $x_b\in X_b$ Alice and Bob perform the measurements $E_{x_a}$ and $F_{x_b}$ respectively and return the results. Hence we have $p(y_a,y_b|x_a,x_b)={\psi }^{†}(E_{x_a{y}_a}\otimes F_{x_b{y}_b})\psi$.

3. 3.

   A quantum commuting strategy $S_{co}=(\psi ,E,F)$ consists of a shared state $\psi \in 𝒳$ for some potentially infinite dimensional Hilbert space $𝒳$, and two sets of POVMs $E$ and $F$, representing Alice and Bobs measurements as above. Note that in these strategies all of Alice’s measurement operators must commute with all of Bob’s measurement operators. Then we have $p(y_a,y_b|x_a,x_b)={\psi }^{†}{E}_{x_a{y}_a}{F}_{x_b{y}_b}\psi$.

For $t\in \{c,\ast ,co\}$ we will often refer to a $t$-strategy for a non-local game. Here $t$ describes the type of strategy being used, $c$ for classical, $\ast$ for tensor, and $co$ for commuting. We focus exclusively on perfect strategies, where the game is won with probability 1. In this case we must have $p(y_a,y_b|x_a,x_b)=0\text{ when }V(x_a,x_b,y_a,y_b)=0.$

Any $c$-strategy is a $\ast$-strategy since we can simply ignore entanglement in the latter case. Remarkably, it can be shown that in some cases a perfect $\ast$-strategy for a non-local game exists even when a perfect $c$-strategy cannot exist. In such cases, we say that a non-local game exhibits pseudotelepathy. Moreover, it can be straightforwardly shown that any $\ast$-strategy is a $co$-strategy. A non-trivial result of Tsirelson shows that if we restrict to finite-dimensional Hilbert spaces these two classes of strategies coincide [35, 34]. A recent breakthrough result [18] shows that $co$-strategies form a strictly larger set than $\ast$-strategies.

A non-local game is said to be synchronous if Alice and Bob have the same question set $X$, the same answer set $Y$, and the equation $V(y,y^{\prime }|x,x)=0\forall x\in X,y\ne y^{\prime }\in Y$ is satisfied.

This means that given the same inputs Alice and Bob must always respond with the same outputs to win the game. we write $G_s=(X,Y,V)$ to denote synchronous games. Perfect strategies for these games have nice properties which make them easier to analyse. In particular variations of the following lemmas have appeared throughout the literature (see e.g. [4, 31]).

We now recall the characterisation of $\ast$-strategies for the CSP game that was derived in [1]. Our first observation is that if a perfect $\ast$-strategy for the CSP game exists, then there must exist a (possibly different) perfect $\ast$-strategy which exhibits some very strong properties.

The authors then note that this theorem shows that all the information determining the strategies is contained in Alice’s operators $E$. Hence, they define projectors $P_{x,y}:=E_{𝒙}^i$ whenever $x={𝒙}_i$. These projectors are well-defined since we have $E_{𝒙,y}^i=P_{x,y}=E_{{𝒙}^{\mathbf{\prime }}}^j$ whenever $x={𝒙}_i={𝒙}_{𝒋}^{{}^{\mathbf{\prime }}}$. Moreover, for each $𝒙\in R^{𝒳}$ we have PVMs $\{P_{{𝒙}_i}\}$ which are jointly measurable by the PVM $E_{𝒙}$. Thus, $E_{𝒙}$ is equivalent to the PVM $P_{𝒙}$ given by $P_{𝒙\mathbf{,}𝒚}=P_{{𝒙}_1,{𝒚}_1},\mathrm{\dots },P_{{𝒙}_k,{𝒚}_k}.$

Based on the above observations the authors define the notion of a $\ast$-homomorphism as follows:

This definition is justified by the following theorem:

In this section, we restrict our attention to the case where the relational structures $𝒳$ and $𝒴$ are both graphs. As we saw in example 1 the CSP game restricts to a graph homomorphism game when the relational structures $𝒳$ and $𝒴$ are both graphs. There is however an alternative non-local game for graph homomorphisms, due to Mančinska and Roberson which was introduced in [23]. We refer to this game as the MR graph homomorphism game. It is played as follows:

This variant of the graph homomorphism game gives rise to an alternative notion of quantum graph homomorphism.

Clearly, every quantum homomorphism is an MR quantum homomorphism. We now set out to answer the following question from [1].

We answer this question in the negative by explicitly constructing graphs $G$ and $H$ such that an MR quantum homomorphism from $G$ to $H$ exists but where a quantum homomorphism does not exist. Our separation will be achieved by studying the $k$-colouring game which is a special case of the graph homomorphism game (Obtained by taking $H$ to be the complete graph of size $k$.). Restricting the above definitions to this specific case we have:

We now consider the case where $G=G_{14}$ is the 14 vertex graph from [24]. To construct this first consider the following family of vectors in ${ℝ}^3$:
$V:=$ $\{\left(\begin{array}{c}1\\ 0\\ 0\end{array}\right),\left(\begin{array}{c}0\\ 1\\ 0\end{array}\right),\left(\begin{array}{c}0\\ 0\\ 1\end{array}\right)\}\cup \{\left(\begin{array}{c}1\\ 1\\ 0\end{array}\right),\left(\begin{array}{c}1\\ -1\\ 0\end{array}\right),\left(\begin{array}{c}1\\ 0\\ 1\end{array}\right),\left(\begin{array}{c}1\\ 0\\ -1\end{array}\right),\left(\begin{array}{c}0\\ 1\\ 1\end{array}\right),\left(\begin{array}{c}0\\ 1\\ -1\end{array}\right)\}\cup \{\left(\begin{array}{c}1\\ 1\\ 1\end{array}\right),\left(\begin{array}{c}1\\ 1\\ -1\end{array}\right),\left(\begin{array}{c}1\\ -1\\ 1\end{array}\right),\left(\begin{array}{c}-1\\ 1\\ 1\end{array}\right)\}.$

We then define a graph $G_{13}$ from this set by assigning a node to every vertex and an edge between any two nodes which represent orthogonal vectors⁵⁵5It is worth noting that the graph $G_{13}$ has also appeared in a somewhat different context in [37], where it was used to provide a proof of the state-independent Kochen-Specker theorem with only 13 rays. This has since been shown to be the minimum number of vectors necessary for such a proof [8].. This graph is drawn in figure 1.

The graph $G_{14}$ is obtained by adding an apex node to $G_{13}$ which we denote by $\mathrm{\Omega }$. The following results were already shown in [24].

Thus, this graph provides an example of quantum advantage in the MR graph colouring game. In fact, in [24] they conjecture that $G_{14}$ is the smallest graph with this property. A recent preprint claims a computational proof of this conjecture [21]. We prove the following theorem, which separates MR quantum homomorphisms from quantum homomorphisms.

We now aim to analyse commuting operator strategies in the CSP game. For the case of the MR graph homomorphism game, such strategies have been explored in [33, 32, 31]. The following result is known:

To derive these results the authors rely heavily on the fact that the MR graph homomorphism game is synchronous. We wish to derive an analogue of the above result for the CSP game. Unfortunately, this game is not synchronous so we cannot immediately make use of Lemma 5. Our first step is thus to define a synchronous version of the CSP game and show that its perfect strategies coincide with the original game of [1].

Thus, any result that applies to perfect strategies in the synchronous CSP game also applies to the original game.

We now prove a commuting operator framework analogue of Theorem 10.

As before we can verify that perfect classical strategies are isomorphisms.

We now turn our attention to $\ast$-strategies in the isomorphism game. Our goal is to characterise such strategies in a manner analogous to what was done for the homomorphism game in [1]. We begin by showing that strategies can be assumed to have a special form.

We note that using the synchronous nature of the game allows us to simplify some of the steps in the corresponding proof of Theorem 8 in [1]. Now let us once again define projectors $P_{x,y}=E_{𝒙,y}^i$ whenever $x=x_i$ for some $i\in [k]$. Item (6) in Theorem 25 shows that these are well-defined projectors. As in the homomorphism case we then have for each $𝒙\in R^{𝒳}$ PVMs $\{P_{x_i}\}$ which are jointly measurable. Hence $E_{𝒙}$ is equivalent to the PVM $P_{𝒙}$ given by $P_{𝒙\mathbf{,}𝒚}=P_{x_1,y_1}.,\mathrm{\dots },.P_{x_k,y_k}.$ We can then define a $\ast$-isomorphism as follows.

To justify this definition we prove the following:

As in the case of the homomorphism game, we can provide a characterisation of perfect $co$-strategies as follows. We omit a detailed proof as this makes use of Lemma 5 and then follows exactly the same argument as Theorem 27.

We start by describing the graded quantum monad introduced in [1]. Let us define graded monads.

Now let ${\mathbb{N}}^{+}$ denote the monoid of natural numbers under the usual multiplication operation. The graded quantum monad of [1] is defined as follows.

The following result links the graded quantum monad to quantum homomorphisms.

We now point out that one can define an alternative version of the quantum monad which can be used to study representations of graph homomorphisms over any Hilbert space, not just those which are finite-dimensional. For this purpose, consider the monoidal category $({\mathrm{𝐇𝐢𝐥𝐛}}^{𝐔},\otimes ,ℂ)$, which has Hilbert spaces as objects, unitary maps as morphisms, the tensor product of Hilbert spaces as its monoidal product, and the Hilbert space $ℂ$ as its unit object.

We then have the following analogue of our previous theorem:

So far we have introduced suitable definitions for quantum homomorphisms and quantum isomorphisms of relational structures. Moreover, we have described a graded quantum monad ${\mathbb{Q}}_{𝑯}$ whose Kleisli morphisms correspond precisely to quantum homomorphisms. Given these results, one might expect that Kleisli isomorphisms of ${\mathbb{Q}}_{𝑯}$ coincide with quantum isomorphisms. Our next result shows that this is not the case.

Therefore, even though Kleisli morphisms of ${\mathbb{Q}}_{𝑯}$ correspond to quantum homomorphisms we see that Kleisli isomorphisms coincide with classical isomorphisms.

We now describe a method for overcoming this limiting result. Recall that the set $\mathrm{𝖯𝗋𝗈𝗃}(𝑯)$ admits the structure of a partial semiring whereby the operation $+$ is only defined when two projectors are orthogonal and . is only defined when two projectors commute. Based on this observation we now define an alternative partial notion of Kleisli composition for the functor ${\mathbb{Q}}_{𝑯}$ where we use the matrix product instead of the Kronecker product. To explain this in more detail recall from [1] that given two Kleisli morphisms $f:𝒳\to {\mathbb{Q}}_{𝑯}𝒴$ and $g:𝒴\to {\mathbb{Q}}_{{𝑯}^{\mathbf{\prime }}}𝒵$ their composition $g\circ f:𝒳\to {\mathbb{Q}}_{𝑯\otimes {𝑯}^{\mathbf{\prime }}}𝒵$ can be explicitly described by the formula

Now consider instead two morphisms $𝒳\to {\mathbb{Q}}_{𝑯}𝒴$ and $𝒴\to {\mathbb{Q}}_{𝑯}𝒵$. If these morphisms satisfy the condition that for all $x\in 𝒳,y\in 𝒴,z\in 𝒵:f(x)(y)\odot g(y)(z)$ we can define a composite morphism $g\bullet f:𝒳\to {\mathbb{Q}}_{𝑯}𝒵$ given by

Moreover, for any Hilbert space $𝑯$ there is a natural notion of Kleisli identity map given by ${\eta }_{𝒳}^{𝑯}:𝒳\to {\mathbb{Q}}_{𝑯}𝒳$ which sends $x\in X$ to ${\delta }_x\in {\mathbb{Q}}_{𝑯}X$ where for $x\ne x^{\prime }:\{\begin{array}{cc}{\delta }_x(x)=I_d\hfill & \\ {\delta }_x(x^{\prime })={\mathrm{𝟎}}_d\hfill & \end{array}$. It is straightforward to verify that whenever the composition of morphisms under $\bullet$ is well-defined the associativity and unitality axioms of a category are satisfied. Thus we almost have a category, except that composition operation $\bullet$ is a partial rather than total operation. These observations prompt us to define the concept of a partial category.

The partial category we have described above then arises as the Kleisli category of a partial version of the quantum monad which we now describe.

Note that ${\mu }^{}$ here fails to be a natural transformation since the morphism ${\mu }_{𝒳}^{}$ assigned to each object is a partial rather than a total homomorphism. Nevertheless, whenever compositions are well-defined this operation does satisfy the naturality axiom. From this point onwards we shall write $\mathrm{𝐊𝐥}({\stackrel{\bullet }{\mathbb{Q}}}_{𝑯})$ and $\mathrm{𝐊𝐥}({\stackrel{\otimes }{\mathbb{Q}}}_{𝑯})$ to distinguish the (partial) kleilsi categories of the partial and graded version of the quantum monad respectively.

We can now explore what a suitable notion of isomorphism in $\mathrm{𝐊𝐥}({\stackrel{\bullet }{\mathbb{Q}}}_{𝑯})$ would look like. In a Kleisli category, the identity map is given by the monad unit. Thus, let us write $𝒳\stackrel{\mathrm{𝐊𝐥}{({\mathbb{Q}}_{𝑯})}^{\bullet }}{\cong }𝒴$ whenever there exists a pair of Kleisli morphisms $f:𝒳\to {\mathbb{Q}}_{𝑯}𝒴$ and $g:𝒴\to {\mathbb{Q}}_{𝑯}𝒳$ satisfying:

• $\mathrm{■}$

  $\forall x\in 𝒳,y\in 𝒴f(x)(y)\odot g(y)(x)$,

• $\mathrm{■}$

  $g\bullet f={\eta }_{𝒳}^{}$,

• $\mathrm{■}$

  $f\bullet g={\eta }_{𝒴}^{}$.

Our next theorem shows that such isomorphisms are precisely quantum isomorphisms.

This theorem shows that by replacing the Kronecker product with matrix multiplication we can overcome the collapse of Kleisli isomorphisms for ${\mathbb{Q}}_{𝑯}$ to classical isomorphism.

Our final result is a method for overcoming the partiality inherent in $\mathrm{𝐊𝐥}({\stackrel{\bullet }{\mathbb{Q}}}_{𝑯})$ to derive a (total) category where morphisms are quantum homomorphisms and isomorphisms are quantum isomorphisms. The idea is to change the objects of $\mathrm{𝐊𝐥}({\stackrel{\bullet }{\mathbb{Q}}}_{𝑯})$ so that they contain more fine-grained type information. In this way, we will be able to limit the morphisms in and out of each object to precisely those morphisms which are composable via $\bullet$. Our approach to formalising this idea is based on a refinement of the notion of specification structures introduced in [2].

Note that our definition of a specification structure is not the same as in [2]. In particular, since they assume that $𝐂$ is a category they do not need to enforce a totality condition.

Given $𝐂$ and $S$ as above one can define a (total) category ${𝐂}_S$. The objects are pairs $(A,p_A)$ with $A\in \mathrm{Ob}(𝐂)$ and $p_A\in PA$. A morphism $f:(A,p_A)\to (B,p_B)$ is a morphism $f:A\to B$ such that $(p_A,f,p_B)\in R_{A,B}$. The composition of $f$ and $g$ is simply $g{\bullet }_{𝐂}f$. Our next result verifies that this construction indeed yields a valid category.

We now describe the specification structure that shall be placed on $\mathrm{𝐊𝐥}({\stackrel{\bullet }{\mathbb{Q}}}_{𝑯})$. For this purpose, it will be helpful to think of a morphism $𝒳\to 𝒴$ for finite structures $𝒳,𝒴\in ℛ(\sigma )$ as $|Y|\times |X|$ column stochastic matrices with entries in $\mathrm{𝖯𝗋𝗈𝗃}(𝑯)$. Column stochastic means that each column of the corresponding matrix must sum to $I$ (and hence represents a PVM). In this case, the composition operation $\bullet$ is simply the usual notion of matrix multiplication with addition and multiplication given by the corresponding operations in the partial semiring $\mathrm{𝖯𝗋𝗈𝗃}(𝑯)$. Moreover, a PVM with outcomes in $X$ can be thought of as a vector indexed by elements of $X$ whose entries are projectors summing to $I$. Given a morphism $f:𝒳\to {\mathbb{Q}}_{𝑯}𝒴$ let us use capital letters $F$ to clarify that we are thinking of it as a matrix in this form. Likewise, given a PVM $m:X\to \mathrm{𝖯𝗋𝗈𝗃}(𝑯)$ we write $\overrightarrow{m}$ to clarify that we are thinking of it as a vector.

Thus, we now have a category $\mathrm{𝐊𝐥}{({\stackrel{\bullet }{\mathbb{Q}}}_{𝑯})}_S$ whose morphisms correspond to quantum homomorphisms and whose isomorphisms correspond to quantum isomorphisms.

As a final point, it is important to make sure that in passing from $\mathrm{𝐊𝐥}({\stackrel{\bullet }{\mathbb{Q}}}_{𝑯})$ to $\mathrm{𝐊𝐥}{({\stackrel{\bullet }{\mathbb{Q}}}_{𝑯})}_S$ we do not lose any quantum homomorphisms. This means we need to make sure that whenever a quantum homomorphism exists between $𝒳$ and $𝒴$ there exist properties $p_{𝒳}$ and $p_{𝒴}$ such that there is a morphism $(𝒳,p_{𝒳})\to (𝒴,p_{𝒴})$.