In recent years, many fruitful interactions have emerged between entanglement and non-locality in quantum systems, on one hand, and the theory of operator algebras and operator systems, on the other. At a high level, this connection stems from the laws of quantum mechanics, which dictate that the input-output behaviour of local measurements on (bipartite) quantum systems is encoded by non-commutative operator algebras of observables and their state spaces. This provides powerful means to translate between questions of a physical nature and questions formulated in the language of non-commutative analysis. At the base of these developments lie the work of Junge, Navascues, Palazuelos, Perez-Garcia, Scholz and Werner [29], where the relation between the Tsirelson Problem in quantum physics and the Connes Embedding Problem in operator algebra theory was first noticed (see also [44]), and that of Paulsen, Severini, Stahlke, Winter and the third author [46], where the notion of synchronous no-signalling correlation was first defined and characterised. The fruitfulness of these connections has been borne out by many recent works; see [44,35,37,36,39,38,1,40,9] for an incomplete list. We specifically single out Sloftsra's ground-breaking work [50,49], which injected ideas from geometric group theory into the theory of non-local games, showing that the set of bipartite quantum correlations is not closed, and the work of Helton, Meyer, Paulsen and Satriano [26], in which an algebraic approach to non-local games was formulated. All of these ideas recently culminated in the resolution of the weak Tsirelson problem and Connes Embedding problem in the preprint [28] by Ji, Natarajan, Vidick, Wright and Yuen.
In the present work, we are primarily interested in investigating the structure of quantum input-quantum output bipartite correlations which generalise the bisynchronous correlations introduced by Paulsen and Rahaman in [47]. Recall that a no-signalling bipartite correlation over the quadruple (X, X, A, A), where X and A are finite sets, is a family of conditional probability distributions p = {p(a, b|x, y) : (x, y) ∈ X × X, (a, b) ∈ A × A} that has well-defined marginals (see e.g. [35]). Operationally, in the commuting operator model of quantum mechanics, p describes the input-output behaviour of a bipartite quantum system, given by a Hilbert space H in state À, interpreted as a unit vector in H, on which local measurements are jointly performed: for each x, y ∈ X, two non-communicating parties Alice and Bob have access to mutually commuting local measurement systems E x = (E x,a ) a∈A ¦ B(H) (for Alice) and F y = (F y,b ) b∈A ¦ B(H) (for Bob). Given input x, Alice uses the system E x to measure À, and similarly, given y, Bob uses F y to measure À; the resulting outcomes of Alice and Bob's measurements are (a, b) ∈ A × A with probability p(a, b|x, y) = ïE x,a F y,b À, Àð.
We say that a correlation p is synchronous if p(a, b|x, x) = 0 for all x ∈ X and a ̸ = b. Heuristically, Alice and Bob's behaviour is synchronised in that they appear to invoke the same "virtual function" X → A to obtain their outputs, depending on the given inputs. A correlation p is called bisynchronous [47] if it is synchronous and has the additional property that p(a, a|x, y) = 0 for all a ∈ A and x ̸ = y. In this case, the "virtual function" X → A behaves as though it were in addition injective.
Using the language of operator algebras and non-commutative geometry, one can make the intuition, highlighted in the previous paragraph, precise. Let A X,A = ⋆ |X| ℓ ∞ (A) be the unital free product of |X| copies of the |A|dimensional abelian C*-algebra ℓ ∞ (A). The C*-algebra A X,A is a C*-cover of the universal operator system S X,A with generators e x,a , where x ∈ X and a ∈ A, subject to the relations e x,a = e 2
x,a = e * x,a and a∈A e x,a = 1, x ∈ X. Within the framework of non-commutative geometry, A X,A can be regarded as a quantisation of the finite-dimensional C * -algebra C(F(X, A)) of complex-valued functions on the set F(X, A) of functions f : X → A. It was shown in [46] that a no-signalling correlation p of quantum commuting type is synchronous if and only if there is a tracial state Ä on A X,A such that p(a, b|x, y) = Ä (e x,a e y,b ), x, y ∈ X, a, b ∈ A. (1) If the correlation p is bisynchronous (and |X| = |A|), then [47] p arises via (1) from a tracial state Ä on the C*-algebra C(S + X ) of the quantum permutation group [56]. Similarly to A X,A , the C*-algebra C(S + X ) is the universal unital C*-algebra with generators e x,a , x, a ∈ X, further satisfying the additional relations x∈X e x,a = 1, a ∈ A. Note that C(S + X ) is a free analogue of the algebra C(S X ) of complex functions on the permutation group S X of X, and is itself a C * -algebraic quantum group [56].
Bisynchronous correlations arise in the analysis of certain classes of nonlocal games, most notably the graph isomorphism game [1,36,38,9] and the related metric isometry game [22]. Here, deep and unexpected connections emerged between quantum permutation groups, no-signalling correlations and graph theory. At the same time, connections were established between graph isomorphism games and quantum graphs [40,41,9]. In particular, in the aforementioned works, a natural (operator) algebraic notion of a quantum isomorphism between quantum graphs was introduced.
One of the main motivations behind the present work is the desire to provide an operational characterisation of quantum isomorphisms between quantum graphs in terms of bipartite correlations. As the term suggests, the description of a quantum graph (in any of its many guises [51,40,9,11]) requires a suitable quantum version of the notion of a vertex or edge, using the language of bipartite quantum systems. Hence one is naturally led to consider bipartite no-signalling correlations which allow quantum states as inputs and outputs.
Quantum input-quantum output no-signalling (QNS) correlations were introduced by Duan and Winter [20], and subsequently systematically studied in [52,7,11]. Given finite sets X and A, and denoting by M X (resp. M A ) the full matrix algebra over the |X|-dimensional Hilbert space, a QNS correlation over the quadruple (X, X, A, A) is a quantum channel Γ : M X ¹ M X → M A ¹ M A satisfying a pair of additional constraints, equivalent to the existence of marginal channels (see equations (5) and (6), and the article [20] for further details). Since any classical no-signalling correlation p over (X, X, A, A) can be regarded as a QNS correlation Γ p that preserves the corresponding diagonal subalgebras, QNS correlations constitute a genuine generalisation of their classical counterparts (see also equation ( 8)).
The main purpose of the present work is to develop a notion, and find (operational and operator algebraic) characterisations, of bisynchronicity in the quantum input-output setting. In parallel with the classical setting, here we focus our attention on the case where the input and output systems are of the same size, that is, |A| = |X|. In this case, it is natural to consider "bistochastic" correlations Γ : M X ¹ M X → M A ¹ M A , that is, unital QNS correlations with the additional property that the dual channels Γ * are also QNS correlations; these channels are referred to as QNS bicorrelations (see Definition 5.1). A quantisation of bisynchronicity must involve a suitable quantum counterpart of the property of sending identical inputs to identical outputs. In bipartite quantum systems, this is naturally captured by how Γ (and Γ * ) acts on the canonical maximally entangled state. More precisely, if (ϵ x,y ) x,y∈X is the canonical matrix unit system of M X , and J X = 1
x,y∈X ϵ x,y ¹ ϵ x,y is the maximally entangled state, then it is natural to impose the condition Γ(J X ) = J A .
(2) Condition (2) on a QNS correlation Γ was introduced and studied in detail in our previous work [11], where it was called concurrency. For a QNC bicorrelation Γ, its concurrency is equivalent to concurrency for Γ * (see Remark 6.2). From an operational viewpoint, concurrent bicorrelations Γ are characterised by the property that Γ and Γ * preserve the perfect correlation of local measurements in both directions: the input state J X is characterised by the property that local measurements performed on J X in any fixed basis are always perfectly correlated with uniformly random outcomes. Concurrent bicorrelations thus respect this perfect correlative structure, and hence rightfully can be interpreted as fully quantum versions of bisynchronous correlations.
We study the various types of QNS bicorrelations (quantum commuting, quantum approximate, quantum and local) in detail, providing operator system/algebra characterisations thereof. After providing necessary preliminaries in Section 2, in Section 3 we exhibit operator bistochastic matrices, which can be viewed as quantum and operator-valued generalisations of classical bistochastic matrices. Operator bistochastic matrices turn out to be the suitable mathematical objects encoding each of the parties of a QNS bicorrelation. We characterise concretely the universal operator system T X of an operator bistochastic matrix as the subspace spanned by natural order two products associated with the entries of a universal block operator bi-isometry V : C |X| ¹ H → C |X| ¹ K (that is, an isometry V for which the transpose V t is also an isometry). We further identify the dual operator system of T X and establish several properties of T X and its universal C*-algebra C X . At the heart of our arguments is a factorisation result for bistochastic operator matrices (Theorem 3.2). Our results should be compared to those of [52], where a similar development was undertaken for the univeral operator system T X,A of a block operator isometry, and the corresponding C*-algebra C X,A .
The diagonal expectations (intuitively, the classical components) of bistochastic operator matrices coincide with quantum magic squares, introduced by De Las Cuevas, Drescher and Netzer in [16]; contrapositively, bistochastic operator matrices can be viewed as quantum versions of quantum magic squares. In Section 4, we build up on this connection and rephrase some of the results of [16] in the language of operator systems. Indeed, one of the main results in [16] is the fact that not every quantum magic square admits a dilation to a quantum permutation. In Theorem 4.5, we characterise the dilatability of a quantum magic square in terms of the complete positivity of natural maps, associated with the given quantum magic square, and defined on the operator system P X ¦ C(S + X ) spanned by the coefficients of a quantum permutation matrix. We demonstrate that the non-dilatability of quantum magic squares is due to the distinction between different operator system structures.
In Section 5, we introduce the types of quantum no-signalling bicorrelations, corresponding to different physical models (local, quantum, approximately quantum, quantum commuting and general no-signalling), and characterise them in terms of states on the various operator system structures, with which the algebraic tensor product T X ¹ T X can be endowed. Here we rely on the tensor product theory developed in [32]. We pay a separate attention to classical no-signalling bicorrelations, showing that their corresponding encoding operator system S X is the universal operator system spanned by the entries of an X × X-quantum magic square studied in Section 4, and obtaininig similar characterisations in terms of states on operator system tensor products on the algebraic tensor product S X ¹ S X .
In Section 6, we focus our attention on concurrent bicorrelations, establishing in Theorem 6.7 a characterisation of concurrent quantum commuting bicorrelations in terms of tracial states. We show that the C*-algebra, whose tracial states are of interest here, is the C*-algebra C(PU + X ) of functions on projective free unitary quantum group. Recall that the C*-algebra of the free unitary quantum group C(U + X ) is the universal unital C*-algebra generated by the entries u x,a of an X × X bi-unitary matrix U = (u x,a ) x,a . The C*-algebra C(PU X + ) is the C*-subalgebra of C(U + X ), generated length two words of the form u *
x,a u x ′ ,a ′ . Note that the C*-algebra C(U + X ) is the free analogue of C(U X ), the C*-algebra of continuous complex functions on the unitary group U X . Similarly, C(PU + X ) is the free analogue of the algebra of continuous complex functions on the projective unitary group PU X = U X /T. Recall that the natural action of U X on M X by conjugation induces an isomorphism of PU X and the group Aut(M X ) of * -automorphisms of the matrix algebra M X . In this way, C(PU X ) can be regarded as the quantum version of the automorphism group of M X . In fact, using quantum group theory, this reasoning can be made precise as, by [3,Corollary 4.1] and [2, Theorem 1], C(PU + X ) is the quantum automorphism group of the tracial C*-algebra M X in the sense of Wang [56].
Thus, from an operator algebraic point of view, Theorem 6.7 provides yet another justification for our definition of concurrent bicorrelations as the appropriate quantum versions of bisynchronous correlations; indeed, at a correlation level, quantisation of bisynchronicity amounts to replacing classical channels on D X ¹ D X with quantum channels on M X ¹ M X . At the level of tracial states encoding these channels, Theorem 6.7 shows that this quantisation amounts to replacing C(S + X ) (that is, quantum automorphisms of D X ) with C(PU + X ) (that is, quantum automorphisms of M X ). We remark here that the C * -algebras C(S + X ) and C(PU + X ) are indeed distinct C * -algebras, as can be seen from the K-theory computations in [54,Theorem 4.5]. In summary, the operational and the algebraic notions of quantisation are in agreement. Our results complement a series of operator characterisations in the literature, part of which we summarise in the following table : as symmetric skew subspaces U ¦ C X ¹ C X [8,51,19,52,11]. We define quantum isomorphisms between quantum graphs in terms of perfect QNS strategies for a suitable quantum graph isomorphism game, building up on the approach to quantum graph homomorphisms followed in [52]. In Theorem 7.4, we characterise quantum commuting isomorphisms between quantum graphs U , V ¦ C X ¹ C X in terms of the existence of a bi-unitary matrix U = (u x,a ) x,a ∈ M X (B(H)) such that C(PU X + ) admits a tracial state Ä , and
where SU and SV are the traceless, symmetric subspaces, canonically associated to U and V, respectively. Note that condition (3) is a quantum counterpart of the characterisation [1] of quantum isomorphisms of classical graphs in terms of quantum permutations matrices that intertwine the relevant adjacency matrices, through the replacement of quantum permutations by bi-unitaries (see Remark 7.6). We further formalise the relations (3) in Theorem 7.10, where we introduce a natural game algebra A P,Q whose tracial states encode the perfect quantum commuting strategies for the (U , V)isomorphism game. We note, in particular, that when U = V, the algebra A P,Q admits the structure of a compact quantum group, which seems to generalise the quantum automorphism group of a classical graph. We leave the study of these quantum groups for future work.
Finally, in Section 8, we compare the operational notion of quantum graph isomorphism of Section 7 to the operator algebraic notions that have appeared previously in the literature, and which have been based mainly on adjacency matrices [40,41,9,15]. We show, in Theorem 8.9, that the algebraic quantum isomorphisms considered in the aforementioned works fit into our framework as special cases. The arguments and ideas for the proof of this theorem rely on the recent work of Daws on quantum graphs [15]. In Theorem 8.14, we establish a partial converse, exhibiting the precise conditions, under which the algebraic and the operational notions of quantum graph isomorphism coincide.
In this section, we collect basic preliminaries on quantum no-signalling correlations, set notation and introduce terminology. Let H be a Hilbert space. As usual, we denote by B(H) the space of all bounded linear operators on H and sometimes write L(H) if H is finite dimensional. We denote by I H the identity operator on H and, if À, ¸∈ H, we let À¸ * be the rank one operator given by (À¸ * )(•) = ï•, ¸ðÀ. In addition to inner products, ï•, •ð will denote the duality between a vector space and its dual. We let B(H) + be the cone of positive operators in B(H), and further denote by T (H) its ideal of trace class operators and by Tr -the trace functional on T (H).
An operator system is a selfadjoint subspace S ¦ B(H), for some Hilbert space H, containing I H . If S is an operator system, the universal C*-cover of S [34] is a pair (C * u (S), º), where C * u (S) is a unital C*-algebra and º : S → C * u (S) is a unital complete order embedding, such that º(S) generates C * u (S) as a C*-algebra and, whenever K is a Hilbert space and ϕ : S → B(K) is a unital completely positive map, there exists a *-representation
If S is a finite dimensional operator system then its Banach space dual S d can be viewed as an operator system [14,Corollary 4.5]. We refer the reader to [45] for information and background on operator systems and completely positive maps.
We denote by |X| the cardinality of a finite set X, let H X = • x∈X H and write M X for the space of all complex matrices of size |X| × |X|; we identify M X with L(C X ) and set
. We write (e x ) x∈X for the canonical orthonormal basis of C X , (ϵ x,x ′ ) x,x ′ ∈X for the canonical matrix unit system in M X , and denote by D X the subalgebra of M X of all diagonal matrices with respect to the basis (e x ) x∈X . If V is a vector space, we write M X (V) for the space of all X × X matrices with entries in V; we note that there is a canonical linear identification between M X (V) and M X ¹ V. Here, and in the sequel, we use the symbol ¹ to denote the algebraic tensor product of vector spaces.
For an element É ∈ M X , we denote by É t the transpose of É in the canonical basis, and write É for the complex conjugate of É; thus, É = (É t ) * . The canonical complete order isomorphism from M X onto its dual operator system M d X maps an element É ∈ M X to the linear functional f É : M X → C given by f É (T ) = Tr(T É t ); see e.g. [48,Theorem 6.2]. We will thus consider M X as self-dual with the pairing (4) (Ä, É) → ïÄ, Éð := Tr(ÄÉ t ).
On the other hand, note that the Banach space predual B(H) * can be canonically identified with T (H); every normal functional ϕ : B(H) → C thus corresponds to a (unique) operator S ϕ ∈ T (H) such that ϕ(T ) = Tr(T S ϕ ), T ∈ B(H). In the case where X is a fixed finite set (which will sometimes come in the form of a Cartesian product), we will use a mixture of the two dualities just discussed: if É, Ä ∈ M X , S ∈ T (H) and T ∈ B(H), it will be convenient to continue writing ïÄ ¹ T, É ¹ Sð = Tr(ÄÉ t ) Tr(T S).
If X and Y are finite sets, we identify M X ¹ M Y with M X×Y and write M XY in its place. Similarly, we set D XY = D X ¹ D Y . For an element É X ∈ M X and a Hilbert space H, we let L É X : M X ¹ B(H) → B(H) be the linear map given by L
and a similar formula holds for L É Y . We let Tr X :
Let X, Y , A and B be finite sets. A quantum channel from M X into M A is a completely positive trace preserving map Φ : M X → M A . A quantum correlation over (X, Y, A, B) (or simply a quantum correlation if the sets are understood from the context) is a quantum channel Γ :
We denote by Q ns the set of all QNS correlations. A stochastic operator matrix over (X, A), acting on a Hilbert space H, is a positive block operator matrix Ẽ = (E x,x ′ ,a,a ′ ) x,x ′ ,a,a ′ ∈ M XA (B(H)) such that Tr A Ẽ = I. A QNS correlation Γ : M XY → M AB is quantum commuting if there exist a Hilbert space H, a unit vector À ∈ H and stochastic operator matrices Ẽ = (E x,x ′ ,a,a ′ ) x,x ′ ,a,a ′ and F = (F y,y ′ ,b,b ′ ) y,y ′ ,b,b ′ on H such that
for all x, x ′ ∈ X and all y, y ′ ∈ Y . Quantum QNS correlations are defined as in (7), but requiring that H has the form H A ¹ H B , for some finite dimensional Hilbert spaces H A and H B , and
We write Q qc (resp. Q qa , Q q , Q loc ) for the (convex) set of all quantum commuting (resp. approximately quantum, quantum, local) QNS correlations, and note the inclusions
(see e.g. [35,46]). We denote the (convex) set of all NS correlations by C ns . With a correlation p ∈ C ns , we associate the classical information channel Γ p : D XY → D AB , given by
The subclasses C t of C ns , for t ∈ {loc, q, qa, qc}, are defined as in the previous paragraph, but using classical stochastic operator matrices, that is, stochastic operator matrices of the form E = x∈X a∈A ϵ x,x ¹ ϵ a,a ¹ E x,a . Note that the condition for E being stochastic is equivalent to the requirement that (E x,a ) a∈A is a positive operator-valued measure (POVM) for all x ∈ X. We note the inclusions
all of which are strict: C loc ̸ = C q is the Bell Theorem [4], C q ̸ = C qa is a negative answer to the weak Tsirelson Problem [49] (see also [21,50]), and [25,29,44], a negative answer to the announced solution of the Connes Embedding Problem [28].
In this section we define and examine bistochastic operator matrices, which constitute a specialisation of stochastic operator matrices [52,Section 3] to the new context to be considered herein. Let X be a finite set, and set A = X. The distinct symbols X and A will continue to be used to indicate the variable with respect to which a partial trace is taken; the symbol X usually refers to the domain of a quantum channel, while A -to its codomain. Definition 3.1. Let H be a Hilbert space. A block operator matrix
Tr A E = I X ¹ I H and Tr X E = I A ¹ I H .
A block operator matrix V = (V a,x ) a,x∈X , where V a,x ∈ B(H, K) for some Hilbert spaces H and K, will be called a bi-isometry if V and V t := (V x,a ) a,x∈X are isometries as operators in B(H X , K X ). Theorem 3.2. Let H be a Hilbert space and E ∈ (M XA ¹ B(H)) + . The following are equivalent:
(i) E is a bistochastic operator matrix;
(ii) there exist a Hilbert space K and operators V a,x ∈ B(H, K), x, a ∈ X, such that (V a,x ) a,x∈X is a bi-isometry and
be the linear map, given by Φ(ϵ a,a ′ ) = E a,a ′ , a, a ′ ∈ A. By Choi's Theorem, Φ is a unital completely positive map and, by Stinespring's Theorem, there exist a Hilbert space K, an isometry V : C X ¹ H → K and a unital *-homomorphism à : M A → B( K) such that Φ(T ) = V * Ã(T )V , T ∈ M A . Up to unitary equivalence, K = C A ¹ K for some Hilbert space K and Ã(T ) = T ¹ I K , T ∈ M A . Write V a,x : H → K, a ∈ A, x ∈ X, for the entries of V , when V is considered as a block operator matrix. As in [52, Theorem 3.1], we conclude that
On the other hand, writing Ä = (Ä a,a ′ ) a,a ′ ∈X , we have
The latter equality holds for every É ∈ T (H); thus,
that is, V t is an isometry. □ 3.2. The universal operator system. Recall [27,58] that a ternary ring is a complex vector space V, equipped with a ternary operation [•, •, •] : V × V × V → V, linear on the outer variables and conjugate linear in the middle variable, such that
A ternary representation of V is a linear map ¹ : V → B(H, K), for some Hilbert spaces H and K, such that
We call ¹ non-degenerate if span{¹(u) * ¸: u ∈ V, ¸∈ K} is dense in H. A (concrete) ternary ring of operators (TRO) [58] is a subspace U ¦ B(H, K) for some Hilbert spaces H and K such that S, T, R ∈ U implies ST * R ∈ U . We refer the reader to [6,Section 4.4] for details about TRO's and their abstract versions that will be used in the sequel. Let V 0 X be the ternary ring, generated by elements v a,x , a, x ∈ X, satisfying the relations (11) a∈X
for all x, x ′ , x ′′ , a, a ′ , a ′′ ∈ X. Note that relations (11) are equivalent to (12)
for all x, x ′ , a, a ′ ∈ X and all u ∈ V 0 X . Conditions (12) imply that the non-degenerate ternary representations ¹ : V 0 X → B(H, K) correspond to bi-isometries V = (V a,x ) a,x via the assignment V a,x = ¹(v a,x ); in this case, we write ¹ = ¹ V . Following [52, Section 5], we let 1 = • V ¹ V , where in the direct sum we have chosen one representative from each unitary equivalence class of bi-isometries and the cardinality of the underlying Hilbert spaces are bounded by that of V. The assignment ∥u∥ := ∥ 1(u)∥ defines a semi-norm on V 0 X ; we set V X := V 0 X / ker 1, observe that V X is a TRO, and continue to write v a,x for the images of the canonical generators of V 0 X under the quotient map q : V 0 X → V X . The maps 1 and ¹ V (for a bi-isometry V ) give rise to corresponding ternary representations of V X , which we denote in the same way.
Let C X be the right C*-algebra of the TRO V X (so that, up to a *isomorphism,
T X = span{e x,x ′ ,a,a ′ : x, x ′ , a, a ′ ∈ X}, viewed as an operator subsystem of C X . It is immediate that
and that the relations
hold true. For a bi-isometry V , acting on the Hilbert space H, we write à V : C X → B(H) for the *-representation of C X , given by (15)
Lemma 3.3. The following hold true: (i) Every non-degenerate ternary representation of V X has the form ¹ V , for some bi-isometry V . (ii) The map 1 is a faithful ternary representation of V X . (iii) Every unital *-representation à of C X has the form à V , for some bi-isometry V .
Proof. The arguments are similar to the ones in [52,Lemma 5.1] where a version of our current setup is considered for isometries (that are not necessarily bi-isometries). We address (iii) for the convenience of the reader. Let à : C X → B(H) be a unital *-representation. Then there exists a ternary representation ¹ : V X → B(H, K) such that Ã(S * T ) = ¹(S) * ¹(T ), S, T ∈ V X,A (see e.g. [5,Theorem 3.4] and [23, p. 1636]). Since à is unital, ¹ is non-degenerate. By the universality of V X described in (i), there exists an operator matrix V = (V a,x ), whose entries satisfy the relations (11), such that ¹ = ¹ V , and hence à = à V . □ Let V X,A be the universal TRO of an isometry (ṽ a,x ) a,x∈X , defined similarly to the TRO V X [52, Section 5]. Thus, the TRO V X,A arises from a ternary ring, whose canonical generators ṽa,x , x, a ∈ X, are required to satisfy only the first of the relations (11). We let C X,A be the right C*-algebra of T X,A . Letting ẽx,x ′ ,a,a ′ = ṽ * a,x ṽa ′ ,x ′ , x, x ′ , a, a ′ ∈ X, we write (16) T X,A = span{ẽ x,x ′ ,a,a ′ : x, x ′ , a, a ′ ∈ X}, viewed as an operator subsystem of C X,A [52]. It was shown in [52,Theorem 5.2] that, for a Hilbert space H, the unital completely positive maps ϕ : T X,A → B(H) correspond to stochastic operator matrices (E x,x ′ ,a,a ′ ) x,x ′ ,a,a ′ via the assignment ϕ(e x,x ′ ,a,a ′ ) = E x,x ′ ,a,a ′ . We next provide a bistochastic version of this fact, to be used subsequently.
Then (i)ô(ii)ô(iii) and (i')ô(ii'). Thus, the pair (C X , º), where º is the inclusion map of T X into C X , is the universal C*-cover of T X . Moreover, if E x,x ′ ,a,a ′ x,x ′ ,a,a ′ is a bistochastic operator matrix acting on a Hilbert space H then there exists a (unique) unital completely positive map ϕ : T X → B(H) such that ϕ(e x,x ′ ,a,a ′ ) = E x,x ′ ,a,a ′ for all x, x ′ , a, a ′ . Proof. (i)⇒(ii) By Arveson's Extension Theorem and Stinespring's Theorem, there exist a Hilbert space K, a *-representation à : C X → B(K) and an isometry W ∈ B(H, K), such that ϕ(u) = W * Ã(u)W , u ∈ T X . By Lemma 3.3, à = à V for some bi-isometry V = (V a,x ) a,x . By (13), E := Ã(e x,x ′ ,a,a ′ ) x,x ′ ,a,a ′ ∈ (M XA ¹ B(K)) + , and hence
that is, the operator matrix ϕ(e x,x ′ ,a,a ′ ) x,x ′ ,a,a ′ is bistochastic.
(ii)⇒(iii) By Theorem 3.2, there exist a Hilbert space K and a bi-isometry
and hence the *-representation à V of C X is an extension of ϕ. (iii)⇒(i) is trivial. (i')⇒(ii') is a direct consequence of ( 13) and the fact that T X is an operator subsystem of C X .
(ii')⇒(i') Let T = ϕ(1) and note that, for any x, a ∈ X, we have Assume first that T is invertible. Following the proof of [52, Proposition 5.4], let È : T X → B(H) be the map given by ( 18)
Setting F = È(e x,x ′ ,a,a ′ ) x,x ′ ,a,a ′ , we have that
and (17) shows that F is a bistochastic operator matrix. By the implication (ii)⇒(i), È is completely positive, and hence so is ϕ, as ϕ(•) = T 1/2 È(•)T 1/2 . Now relax the assumption that T be invertible. Using the implication (ii)⇒(i), let f : T X → C be the state given by f (e x,x ′ ,a,a ′ ) = 1 |X| ¶ x,x ′ ¶ a,a ′ and, for ϵ > 0, let ϕ ϵ : T X → B(H) be given by ϕ ϵ (u) := ϕ(u) + ϵf (u)I. Then ϕ ϵ (e x,x ′ ,a,a ′ ) x,x ′ ,a,a
and ϕ ϵ (I) = T +ϵI is invertible. By the previous paragraph, ϕ ϵ is completely positive and, since ϕ ϵ → ϵ→0 ϕ in the point-norm topology, we conclude that ϕ is completely positive. Finally, suppose that E = E x,x ′ ,a,a ′ x,x ′ ,a,a ′ is a bistochastic operator matrix acting on H. Letting V be the bi-isometry, associated with E via Theorem 3.2, we have that the completely positive map ϕ := Ã V | T X satisfies the equalities ϕ(e x,x ′ ,a,a ′ ) = E x,x ′ ,a,a ′ for all x, x ′ , a, a ′ . □
We note that, if S is an operator system, its Banach space dual S d can be equipped with a natural matricial order structure. To this end, we recall [14, Section 4] that any matrix ϕ = (ϕ i,j ) n i,j=1 ∈ M n (S d ) gives rise to a linear map F ϕ : S → M n , defined by letting
and set
It was shown in [14,Corollary 4.5] that, if S is a finite dimensional operator system then the (matrix ordered) dual S d is an operator system, when equipped with a suitable faithful state as an Archimedean order unit. It is straightforward to verify that, in this case, S dd ∼ = c.o.i. S.
We identify an element T ∈ M XA with its matrix (¼ x,x ′ ,a,a ′ ) x,x ′ ,a,a ′ , where
and consider L X,A as an operator subsystem of M XA . It was shown in [52,Proposition 5.5] that the linear map Λ :
Proposition 3.6. The linear map Λ : T d X → L X , given by (20) Λ(ϕ) = ϕ(e x,x ′ ,a,a ′ ) x,x ′ ,a,a ′ ∈X is a well-defined complete order isomorphism.
Proof. The arguments follow the proof of [52, Proposition 5.5], and we only highlight the required modifications. Using Theorem 3.4, we see that the map Λ + :
, is well-defined; by additivity and homogeneity, Λ + extends to a (C-)linear map Λ : T d X → L X . A further application of Theorem 3.4, combined with Theorem 3.2, shows that Λ is completely positive and bijective.
Let
. Thus, Λ -1 is completely positive, and the proof is complete. □ Corollary 3.7. The linear map f : T X → T X , given by f(e x,x ′ ,a,a ′ ) = e x ′ ,x,a ′ ,a , is a complete order automorphism.
Proof. The map Φ :
, is a (unitarily implemented) complete order automorphism. Further, Φ(L X ) = L X , and hence Φ induces a complete order automorphism Φ 0 : L X → L X . Using Proposition 3.6, we have that its dual Φ * 0 a complete order automorphism of T X . For x, x ′ , a, a ′ ∈ X and T = (¼ x,x ′ ,a,a ′ ) ∈ L X , we have
thus, J X is a linear subspace of the operator system T X,A defined in (16).
Let JX be the closed ideal of C X,A , generated by J X . Write q X for the quotient map from T X,A onto T X,A /J X .
Recall that, if S is an operator system, a subspace J ¦ S is called a kernel [33, Definition 3.2] if there exist an operator system R and a unital completely positive map (equivalently, a completely positive map) ϕ : S → R such that J = ker(ϕ).
Proposition 3.8. The space J X is a kernel in T X,A and the linear map º, given by (22) º q X ẽx,x ′ ,a,a ′ = e x,x ′ ,a,a ′ , x, x ′ , a, a ′ ∈ X, is a well-defined complete order isomorphism from T X,A /J X onto T X . In addition, C X,A / JX ∼ = C X , up to a canonical *-isomorphism.
Proof. Let ³ : L X → L X,A be the inclusion map. Since L X and L X,A are operator subsystems of M XX , we have that ³ is a complete order embedding. By [24, Proposition 1.15], [52, Proposition 5.5] and Proposition 3.6, its dual
Consider the canonical linear mappings
of which the first two are surjective linear maps whose composition is completely positive, while the third is a complete order isomorphism (note that the quotient T X,A /J X is linear algebraic). Dualising and using Proposition 3.6, we obtain the chain of maps ( 23)
By the definition of J X (see (21)), the elements of (T X,A /J X ) d correspond, via the last of the three maps in (23), to elements of the subspace L X of L X,A . It now follows that the middle map in ( 23) is a linear isomorphism, and hence ker(³ * ) = J X . In particular, J X is a kernel in T X,A and (T X,A /J X ) d ∼ = L X complete order isomorphically. Dualising, we see that T X,A /J X ∼ = T X complete order isomorphically via the map º defined in (22). By the universal property of C X , there exists a unital *-epimorphism à :
The block operator matrix ẽx,x ′ ,a,a ′ + JX x,x ′ ,a,a ′ is bistochastic, and hence it gives rise, via Theorem 3.4, to a canonical unital surjective *homomorphism à ′ : C X → C X,A / JX . We thus have a chain of unital *homomorphisms
whose composition is the identity. It follows that J = JX , and the proof is complete. □
In the sequel, write qX : C X,A → C X for the quotient map arising from Proposition 3.8, and continue to write q X for the quotient map from T X,A onto T X . Before formulating the next corollary, we recall that an operator system S is said to possess the local lifting property [33,Section 8] if for every finite dimensional operator subsystem S 0 ¦ S, C*-algebra A, and closed ideal J ¦ A, every unital completely positive map ϕ 0 : S 0 → A/J admits a lifting to a completely positive map ϕ : S 0 → A (that is, if q : A → A/J denotes the quotient map, the identity q • ϕ = ϕ 0 holds).
Corollary 3.9. The operator system T X has the local lifting property.
Proof. By [52, Corollary 5.6], T X,A is an operator system quotient of M XX while, by Proposition 3.8, T X is an operator system quotient of T X,A . It follows that T X is an operator system quotient of M XX . The statement is now a consequence of [31,Theorem 6.8].
□
Realising the commuting tensor product of operator systems as an operator subsystem of maximal tensor products has been of importance from the beginning of the tensor product theory in the operator system category [32]. By Theorem 3.4 and [32,Theorem 6.4], for an arbitrary operator system R, we have
; the next proposition establishes a stronger inclusion. Proposition 3.10. Let R be an operator system. Then
Proof. Let º : T X → C X be the inclusion map. By the functioriality of the commuting tensor product and the fact that the commuting and the maximal tensor products coincide provided one of the terms is a C*-algebra [32, Theorem 6.7], º ¹ id :
let H be a Hilbert space, and ϕ : T X → B(H) and È : R → B(H) be unital completely positive maps with commuting ranges. By Theorem 3.4, ϕ extends to a *-homomorphism à :
and hence w ∈ M n (T X ¹ c R) + . It follows that º ¹ id is a complete order embedding. □
In [16], the concept of a quantum magic square was defined and studied, exhibiting examples which show that not every quantum magic square dilates to a magic unitary. The aim of this section is to present an operator system viewpoint on this result, linking the dilation properties of a quantum magic square to complete positivity of canonical maps, associated with it. The universal operator system of a quantum magic square and its properties will further be used in Section 5.
Recall [16] that a block operator matrix E = (E x,a ) x,a∈X , where
The quantum magic square E is called a magic unitary (or a quantum permutation
Two subclasses of quantum magic squares were singled out in [16] (see [16,Definition 5 and Example 8]). We will call a quantum magic square (E x,a ) x,a , acting on a Hilbert space H, dilatable if there exists a Hilbert space K, an isometry V : H → K, and a quantum permutation (P x,a ) x,a acting on K, such that
The quantum magic square (E x,a ) x,a will be called locally dilatable if (24) holds for a commuting family {P x,a } x,a that forms a quantum permutation.
It is clear that, up to unitary identifications, condition ( 24) can be replaced by the conditions E x,a = QP x,a Q, where we have assumed that H ¦ K, and Q : K → H is the orthogonal projection. For x, a ∈ X, we set e x,a := e x,x,a,a and S X := span{e x,a : x, a ∈ X}, viewed as an operator subsystem of T X .
Theorem 4.1. Let H be a Hilbert space and ϕ : S X → B(H) be a linear map. Consider the conditions (i) ϕ is a unital completely positive map;
(ii) (ϕ(e x,a )) x,a is a quantum magic square, and
x,a is a quantum magic square acting on a Hilbert space H then there exists a (unique) unital completely positive map ϕ : S X → B(H) such that ϕ(e x,a ) = E x,a for all x, a ∈ X.
Proof. (i)⇒(ii) Let ϕ : S X → B(H) be a unital completely positive map, for some Hilbert space H. By Arveson's Extension Theorem, ϕ has a completely positive extension φ : T X → B(H). Setting E x,x ′ ,a,a ′ := φ(e x,x ′ ,a,a ′ ), Theorem 3.4 implies that (E x,x ′ ,a,a ′ ) x,x ′ ,a,a ′ is a bistochastic matrix. In particular, ( φ(e x,a )) x,a , that is, (ϕ(e x,a )) x,a , is a quantum magic square. (ii)⇒(i) Set E x,a := ϕ(e x,a ) and Ẽx,x ′ ,a,a ′ := ¶ x,x ′ ¶ a,a ′ E x,a , x, x ′ , a, a ′ ∈ X. Then ( Ẽx,x ′ ,a,a ′ ) x,x ′ ,a,a ′ is a bistochastic operator matrix and, by Theorem 3.4, there exists a (unital) completely positive map φ :
x,a is a quantum magic square; by the implication (ii)⇒(i), the linear map È : S X → B(H), given by È(e x,a
u ∈ S X , the map ϕ is completely positive. If T is not invertible, we fix a state f : S X → C and, for ϵ > 0, consider the map ϕ ϵ : S X → B(H), given by ϕ ϵ (u) = ϕ(u)+ϵf (u)I. The proof now proceeds similarly to the proof of the implication (ii')⇒(i') of Theorem 3.4.
The last statement in the theorem follows from the proof of the implication (ii)⇒(i).
considered as an operator subsystem of D XX . Since every operator system is spanned by its positive elements, M X is the operator system spanned by the scalar bistochastic matrices in D XX .
Corollary 4.2. We have that S d X ∼ = M X , up to a canonical unital complete order isomorphism.
Proof. Let M + X,1 be the convex set of all scalar bistochastic matrices, that is, matrices
X,1 then the map µ(T ) : S X → C, given by µ(T )(e x,a ) = t x,a , is a (well-defined) state on S X . Writing an arbitrary element T ∈ M X as a linear combination
The map µ is (linear and) well-defined: if
x,a = 0 for all x, a ∈ X, which implies that k
+ and, using the canonical shuffle, write E = (E x,y ) x,y , where E x,y ∈ M n , x, y ∈ X, are such that (25)
Using Theorem 4.1, we see that there exists a completely positive map ϕ : S X → M n such that ϕ(e x,y ) = E x,y , x, y ∈ X. On the other hand, the element µ (n) (E) of M n (S d X ) gives rise, via (19), to a linear map F µ (n) (E) : S X → M n . We have that
is completely positive, and it follows that the map µ is completely positive.
It follows from Theorem 4.1 that the (linear) map µ is surjective; thus, it is injective. We show that µ -1 is completely positive. Assume that W ∈ M n (S d X ) + ; this means that the linear map (25) are satisfied for the matrices E x,y , we have that, in fact, (µ -1 ) (n) (W ) ∈ (M n ¹ M X ) + , and the proof is complete. □
X is a linear subspace of the operator system T X .
Proposition 4.3. The space J ̸ = X is a kernel in T X and, up to a unital complete order isomorphism, S X ∼ = T X /J ̸ = X . Proof. By Theorem 3.4, there exists a unital completely positive map
´:
On the other hand, by Proposition 3.6 and Corollary 4.2, we have a chain of four canonical linear maps ( 26)
of which the first, the second and the fourth are completely positive. In addition, the image of M X in L X under the composition of these maps coincides with itself; thus, ker(´) ¦ J ̸ = X and hence J ̸ = X is a kernel in T X . Dualising the second map in (26), we further obtain a chain
of completely positive maps, whose composition is the identity map on T X /J ̸ = X . On the other hand, we have a chain of canonical completely positive maps S X → T X → T X /J ̸ = X → S X , whose composition is the identity map on S X . It follows that S X ∼ = T X /J ̸ = X , up to a canonical complete order isomorphism. □
In Theorem 4.5 below, we characterise the dilatable and locally dilatable quantum magic squares in operator system terms. Let C(S + X ) be the universal C*-algebra generated by projections p x,a , x, a ∈ X, with the properties b∈X p x,b = y∈X p y,a = 1, x, a ∈ X (thus, C(S + X ) is the universal C * -algebra of functions on the quantum permutation group on X; see e.g. [9]). Write P X = span{p x,a : x, a ∈ X}, viewed as an operator subsystem of C(S + X ). Recall [48, Section 3] that the minimal operator system based on P X has matricial cones M n (OMIN(P X )) + , given by
and that the corresponding maximal operator system based on P X has matricial cones M n (OMAX(P X )) + generated, as cones with an Archimedean order unit, by the elementary tensors of the form T ¹ u, where T ∈ M + n and u ∈ P + X .
Proposition 4.4. There exist canonical unital completely positive maps
Proof. By Theorem 4.1, the linear map q : S X → P X , given by q(e x,a ) = p x,a , x, a ∈ X, is (unital and) completely positive. Suppose that ϕ ∈ (S d X ) + ; by Proposition 4.3, ϕ can be canonically identified with a matrix (¼ x,a ) x,a in M + X . By Birkhoff's Theorem and the argument in the proof of Corollary 4.2, we can further assume that there exists a permutation f : X → X such that ¼ x,a = ¶ f (x),a , x, a ∈ X. By the universal property of C(S + X ), the permutation f gives rise to a canonical *-representation à : C(S + X ) → C. It follows that Ã| P X : P X → C is (completely) positive. We thus obtain a canonical positive map r : S d X → P d X which, by the universal property of the minimal operator system structure, gives rise to a canonical completely positive map S d X → OMIN(P d X ); dualising, we have a canonical completely positive map OMAX(P X ) → S X .
Note that the composition of the maps in ( 27) is the identity map on P X ; hence q is invertible. Since q -1 = r, we have that q -1 is positive, completing the proof. □ Theorem 4.5. Let H be a Hilbert space and E = (E x,a ) x,a be a quantum magic square acting on H. Then (i) E is dilatable if and only if there exists a completely positive map ϕ : P X → B(H), such that ϕ(p x,a ) = E x,a , x, a ∈ X; (ii) E is locally dilatable if and only if there exists a completely positive map ϕ : OMIN(P X ) → B(H), such that ϕ(p x,a ) = E x,a , x, a ∈ X.
Proof. (i) Let P = (P x,a ) x,a be a magic unitary on a Hilbert space K containing H such that, if Q is the projection from K onto H, then E x,a = QP x,a Q, x, a ∈ X. By the universal property of C(S + X ), there exists a unital *homomorphism à : C(S + X ) → B(K) such that Ã(p x,a ) = P x,a , x, a ∈ X. Let ϕ : P X → B(H) be the linear map, defined by ϕ(u) = QÃ(u)Q, u ∈ P X . As a compression of a completely positive map, ϕ is completely positive; by construction, ϕ(p x,a ) = E x,a , x, a ∈ X.
For the converse direction, let φ : C(S + X ) → B(H) be a unital completely positive extension of ϕ, whose existence is guaranteed by Arveson's Extension Theorem. Using Stinespring's Theorem, let K be a Hilbert space, Ã : C(S + X ) → B(K) be a unital *-representation, and V : H → K be an isometry, such that φ(u) = V * Ã(u)V , u ∈ C(S + X ). Letting P x,a = Ã(p x,a ), we have that (P x,a ) x,a is a magic unitary that dilates E.
(ii) We first consider the case where n := dim(H) is finite. Identifying B(H) with M n , suppose that ϕ : OMIN(P X ) → M n is a unital completely positive map. Let
be the canonical functional, associated with ϕ as in [45,Chapter 6]; thus,
By [
Assume that the representation (28) has the form f ϕ ≡ ³ ¹ ´, where ³ ∈ M X and ´∈ M n . In this case, ϕ is given by
In particular, if P ¹ is the permutation unitary corresponding to the permutation ¹ on X, and f ϕ ≡ P ¹ ¹ ´, where ´∈ M n , then
Returning to the representation (28), use Birkhoff's Theorem to write
¹ P ¹ , where the summation is over the permutation group of X, the coefficients ¼ (l) ¹ are non-negative. Thus, (29)
where µ ¹ ∈ M + n and the summation is over the permutation group of X. By the previous paragraph,
Now [16, Theorem 12 and Remark 7] implies that (ϕ(p x,a )) x,a is locally dilatable, after noticing that the matrix convex hull of the set denoted CP (|X|) therein coincides with the locally dilatable magic quantum squares over M n . The converse direction follows by reversing the given arguments.
We now relax the assumption on the finite dimensionality of H. For simplicity, we consider only the case where H is separable. Fix a sequence (Q n ) n∈N of projections of finite rank such that Q n → n→∞ I in the strong operator topology. Assuming that E is locally dilatable, so is (I X ¹ Q n )E(I X ¹ Q n ) for every n ∈ N and hence, by the assumption, the map ϕ n : OMIN(P X ) → B(Q n H), given by ϕ n (p x,a ) = Q n E x,a Q n , x, a ∈ X, i ∈ I, is completely positive. Since ϕ(u) = lim n→∞ ϕ n (u), in the weak operator topology, u ∈ P X , we have that ϕ is completely positive.
Conversely, assuming that ϕ : OMIN(P X ) → B(H) is completely positive, let ϕ n : OMIN(P X ) → B(Q n H) be the (completely positive) map, given by
Since ∥E x,y ∥ f 1 for every x, y ∈ X, we therefore have that ∥µ (n) ¹ ∥ f 1 for every n ∈ N. We can now choose successively weak* cluster points of the sequences µ
, and assume that
where µ ¹ ∈ B(H) + for every permutation ¹ of X, in the weak* topology of M X ¹ B(H). We further have that E x,y = {µ ¹ : ¹(x) = y}. The proof of the implication (a)⇒(b) of [16,Theorem 12] implies, after replacing the identity operator denoted I s therein with I H , that E is locally dilatable. □
In this section, we define the notion of a bicorrelation and obtain representations of the different bicorrelation types in terms of operator system tensor products. We will use the main operator system tensor products, introduced in [32]: the minimal (min), the commuting (c), and the maximal (max). If Ä ∈ {min, c, max} and ϕ i : S i → T i are completely positive maps between operator systems, i = 1, 2, we write ϕ 1 ¹ Ä ϕ 2 for the corresponding tensor product map from S 1 ¹ Ä S 2 into T 1 ¹ Ä T 2 (note that this map is well-defined by [32, Theorems 4.6, 5.5. and 6.3]).
We fix throughout this section finite sets X and Y , and let A = X and B = Y . The symbols A and B will continue to be used for clarity, as needed.
We let Q bi ns be the set of all QNS bicorrelations. We next define different types of QNS bicorrelations, motivated by the analogous definitions of QNS correlation types. A QNS bicorrelation Γ : M XY → M XY is quantum commuting if there exist a Hilbert space H, a unit vector À ∈ H and bistochastic operator matrices Ẽ = (E x,x ′ ,a,a ′ ) x,x ′ ,a,a ′ and F = (F y,y ′ ,b,b ′ ) y,y ′ ,b,b ′ on H with mutually commuting entries, such that the Choi matrix of Γ coincides with
For t ∈ {loc, q, qa, qc}, we let Q bi t be the set of all QNS bicorrelations of type t.
Remark 5.2. If t ∈ {loc, q, qa, qc, ns} and Γ ∈ Q bi t then Γ * ∈ Q bi t . The claim is part of the definition in the case where t = ns and straightforward in the case where t = loc. For the case t = qc, suppose that E = (E x,x ′ ,a,a ′ ) x,x ′ ,a,a ′ and F = (F y,y ′ ,b,b ′ ) y,y ′ ,b,b ′ are bistochastic operator matrices with mutually commuting entries, such that the Choi matrix of Γ coincides with (30). Let Ẽa,a ′ ,x,x ′ := E x,x ′ ,a,a ′ and Fb,b ′ ,y,y
a,a ′ and hence Ẽ is a unitary conjugation of E, implying that Ẽ g 0; similarly, F g 0. The claim now follows from the fact that the Choi matrix of Γ * is equal to Ẽa,a ′ ,x,x ′ Fb,b ′ ,y,y ′ À, À b,b ′ ,y,y ′ a,a ′ ,x,x ′ . The case t = q is analogous, while t = qa is a consequence of the continuity of taking the dual channel.
we conclude that the representation (31) can be chosen with the property that Φ i and Ψ i are unital quantum channels, i = 1, . . . , k, that is, Γ is automatically a local bicorrelation.
We write f y,y ′ ,b,b ′ (resp. fy,y ′ ,b,b ′ ), y, y ′ , b, b ′ ∈ Y , for the canonical generators of the operator system T Y (resp. T Y,B ). If s is a linear functional on T X ¹ T Y or on C X ¹ C Y , we write Γ s : M XY → M XY for the linear map, given by ( 32)
We note that Γ * s is given by the identities
Clearly, the correspondence s → Γ s is a linear map from the vector space dual (T X,A ¹ T Y,B ) d into the space L(M XY ) of all linear transformations on M XY .
Theorem 5.4. Let X and Y be finite sets and Γ : M XY → M XY be a linear map. The following are equivalent:
(i) Γ is a QNS bicorrelation;
(ii) there exists a state s :
is the quotient map (see the paragraph of equation ( 21)); we have that s is a state of T X,A ¹ max T Y,B . Since Γ = Γ s, by [52, Theorem 6.2], Γ ∈ Q ns . In addition,
We verify that Γ * is no-signalling: for any É X = (¼ a,a ′ ) a,a ′ ∈ M X and any (33) we have
x,x ′ ,y,y ′ be the Choi matrix of Γ; thus, the entries of C are given by
Observe that the equalities Cx
The claim follows by setting E x,x ′ ,a,a ′ = Ã X (e x,x ′ ,a,a ′ ) and F x,x ′ ,a,a ′ = Ã Y (f y,y ′ ,b,b ′ ), and appealing to Theorem 3.4. □ Theorem 5.6. Let X and Y be finite sets and Γ : M XY → M XY be a linear map. The following are equivalent:
Proof. (ii)ô(iii) follows from the injectivity of the minimal tensor product.
(i)⇒(iii) Given ε > 0, let E and F be bistochastic operator matrices acting on finite dimensional Hilbert spaces H X and H Y , respectively, and À ∈ H X ¹ H Y be a unit vector, such that
and s be a cluster point of the sequence {s 1/n } n in the weak* topology. Then
x ′ ¹ e y e * y ′ ), e a e a ′ ¹ e b e * b ′ , giving Γ = Γ s .
(iii)⇒(i) Let s be a state satisfying (iv) and ε > 0. By [30, Corollary 4.3.10], there exist faithful *-representations à X : C X → B(H X ) and
´) be a net of finite rank projections on H X (resp. H B ), converging to the identity in the strong operator topology. Set
∥(Pα¹Q β )À∥ (P ³ ¹ Q ´)À (note that À ³,´i s eventually welldefined). Then E ³ and F ´are bistochastic operator matrices acting on P ³ H and Q ´K, respectively, and the QNS correlation associated with the the triple (E ³ , F ´, À ³,´) is a quantum bicorrelation. □ Remark 5.7. By Remark 5.2, (34)
We do not know if equality holds in (34). The problem reduces to a question about the equality of canonical operator system structures. Indeed, it is not difficult to verify that the subspace J XY := T X,A ¹ J Y + J X ¹ T Y,B of the operator system T X,A ¹ c T Y,B is a kernel, and that the states on (T X,A ¹ c T Y,B )/J XY correspond precisely to the elements of Q qc ∩ Q bi ns . However, while there is a canonical bijective unital completely positive map (T X,A ¹ c T Y,B )/J XY → T X ¹ c T Y , it is unclear whether its inverse is completely positive. If this is the case then Theorem 5.5 will imply the reverse inclusion in (34). Further, for a given classical information channel E : D XY → D XY , let Γ E : M XY → M XY be the quantum channel, given by
and set Γ p = Γ Ep for brevity. In the reverse direction, given a quantum channel Γ :
Proposition 5.9. Let p be an NS bicorrelation over (X, Y, X, Y ). Then
Proof. For x, a ∈ X and y, b ∈ Y , we have
For t ∈ {loc, q, qa, qc}, let
It is straightforward to verify that an NS bicorrelation p over (X, Y, X, Y ) belongs to C bi qc precisely when there exist a Hilbert space H, a unit vector À ∈ H and quantum magic squares (E x,a ) x,a∈X and (F y,b ) y,b∈Y with commuting entries, such that (35) p(a, b|x, y
Similarly, p ∈ C bi q precisely when the representation ( 35) is achieved for
loc precisely when p is the convex combinations of correlations of the form p (1) (a|x)p (2) (b|y), where (p (1) (a|x)) x,a and (p (2) (b|y)) y,b are (scalar) bistochastic matrices.
For a linear functional s : S X ¹ S Y → C, let p s : X × Y × X × Y → C be the function given by p s (a, b|x, y) = s(e x,a ¹ e y,b ), x, a ∈ X, y, b ∈ Y. Theorem 5.10. Let X and Y be finite sets and p be an NS correlation over (X, Y, X, Y ). Consider the statements (i) p is an NS bicorrelation;
(ii) there exists a state s :
Proof. (i)ô(ii) By Proposition 4.3 and [24, Proposition 1.16], the states of the maximal tensor product S X ¹ max S Y correspond in a canonical fashion to the elements of M X ¹ min M Y . The proof of the claim can now be completed using a straightforward modification of the proof of Theorem 5.4.
(i')⇒(ii') Write º X : S X → T X and º Y : S Y → T Y for the inclusion maps and let p ∈ C bi qc . By Theorem 5.5, there exists a state s :
; then s is a state on S X ¹ c S Y for which p = p s.
(ii')⇒(i') Let s : S X ¹ c S Y → C be such that p = p s , and let ´X : T X → S X (resp. ´Y : T Y → S Y ) be the quotient map, as defined in the proof of Proposition 4.3. We have that
is a state. By Theorem 5.5, the map Γ s : M XY → M XY , corresponding to s via (32), is a quantum commuting QNS bicorrelation. Since Γ s = Γ p , we have that p ∈ C bi qc . (i")ô(ii") follows in a similar way as the equivalence (i')ô(ii'), using Theorem 5.6 in the place of Theorem 5.5. □
Throughout the section, let X be a finite set and
x,y∈X ϵ x,y ¹ ϵ x,y be the canonical maximally entangled state in M XX . We specialise the definition of a concurrent QNS correlation from [11]:
For t ∈ {loc, q, qa, qc, ns}, we let Q bic t be the set of all concurrent bicorrelations that belong to Q bi t . Remark 6.2. Note that if Γ ∈ Q bic ns , then Γ * ∈ Q bic ns as well. Indeed, since Γ is unital, its dual map Γ * : M AA → M XX is trace-preserving; thus, Tr(Γ * (J A )) = 1. Therefore
The equality clause in the Cauchy-Schwarz inequality now implies that Γ
The universal C*-algebra generated by the entries of a unitary matrix (ũ a,x ) a,x∈X (known as the Brown algebra) was first studied by L. G. Brown [12]. We will introduce a subquotient of the Brown algebra, whose traces will be shown to represent concurrent bicorrelations of different types. First, set ũx,x ′ ,a,a ′ = ũ * a,x ũa ′ ,x ′ , x, x ′ , a, a ′ ∈ X, and let U X,A be the C * -subalgebra of the Brown algebra, generated by the set {ũ x,x ′ ,a,a ′ : x, x ′ , a, a ′ ∈ X}. Lemma 6.3. If à : U X,A → B(H) is a unital *-representation then there exists a block operator unitary U = (U a,x ) a,x such that Ã(ũ x,x ′ ,a,a ′ ) = U * a,x U a ′ ,x ′ , x, x ′ , a, a ′ ∈ X.
Proof. Let V X,A be the universal TRO of an isometry (v a,x ) a,x , as defined in [52, Section 5]. In the sequel, we will consider products v
, where ε i is either the empty symbol or * , and ε i ̸ = ε i+1 for all i, as elements of either V X,A , V * X,A , C X,A or the left C*-algebra corresponding to the TRO V X,A . Let J be the closed ideal of C X,A , generated by the elements By [11,Lemma 4.2], the map Ä : ẽx,x ′ ,a,a ′ → ũx,x ′ ,a,a ′ , x, x ′ , a, a ′ ∈ X extends to a surjective *-homomorphism Ä : C X,A → U X,A with ker Ä = J . Let à : U X,A → B(H) be a *-representation. Then à • Ä : C X,A → B(H) is a *representation that annihilates J . By [52, Lemma 5.1], there exists a block operator isometry U = (U a,x ) a,x∈X , where U a,x ∈ B(H, K) for some Hilbert space K, x, a ∈ X, such that (à • Ä)(ẽ x,x ′ ,a,a ′ ) = U * a,x U a ′ ,x ′ , x, x ′ , a, a ′ ∈ X. By the definition of V X,A , the operator matrix U gives rise to a canonical ternary representation ¹ U : V X,A → B(H, K). Without loss of generality, we can assume that
Since U U * f I, we have that I -x∈X U a,x U * a,x g 0, and hence (36) reads
showing further that
By polarisation, we have x∈X U a,x U * a,x = I, a ∈ X. As I-U U * is a positive block-diagonal operator with the zero diagonal, I -U U * = 0; thus, U is unitary. Since U * a,x U b,y = Ã(ũ x,y,a,b ), x, y, a, b ∈ X, the proof is complete. □ Recall that ẽx,x ′ ,a,a ′ are the canonical generators of the C*-algebra C X,A (so that the matrix ẽx,x ′ ,a,a ′ x,x ′ ,a,a ′ is a universal stochastic operator matrix). Let gx,x ′ y,z,b,c = ¶ x,x ′ ẽy,z,b,c - Proof. Denote by J 0 2 the closed ideal of C X,A , generated by the elements ha,a y,y,b,b , where a, b, y ∈ X. It was shown in [11,Lemma 4.2] that C X,A / J 0 2 ≃ U X,A . Let Ä : C X,A → B(K) be a unital *-representation that annihilates J 0 2 , with the property that the corresponding induced representation of C X,A / J 0 2 is faithful. By Lemma 6.3, there exists a unitary Ũ = ( Ũa,x ) a,x∈X such that, if Ũx,x ′ ,a,a ′ = Ũ * a,x Ũa ′ ,x ′ , then
But then, since Ũ is unitary,
Ũc,z = 0. Thus, Ä automatically annihilates J2 . The proof is complete. □
We say that a block operator matrix U = (u a,x ) a,x ∈ M X (B(H)) is a bi-unitary if both U and U t are unitary. Let C(U + X ) be the universal C*algebra, generated by the entries of a bi-unitary (u a,x ) a,x∈X , and C(PU + X ) be the subalgebra of C(U + X ) generated by the length two words of the form u x,x ′ ,a,a ′ := u * a,x u a ′ ,x ′ , x, x ′ , a, a ′ ∈ X. Further, recall that e x,x ′ ,a,a ′ , x, x ′ , a, a ′ ∈ X, denote the canonical generators of the C*-algebra C X (so that (e x,x ′ ,a,a ′ ) x,x ′ ,a,a ′ is a universal bistochastic operator matrix), set and let J 1 (resp. J 2 ) be the closed ideal of C X , generated by the elements g x,x ′ y,z,b,c (resp. h a,a ′ y,z,b,c ), where y, z, b, c, x, x ′ ∈ X (resp. y, z, b, c, a, a ′ ∈ X). We note that the universal C * -algebra C(U + X ) and its subalgebra C(PU + X ) have been well-studied in the compact quantum group literature. The C *algebra C(U + X ) was introduced by Wang in [55], where it was shown to have the structure of a C * -algebraic compact quantum group. In particular, C(U + X ) comes equipped with a co-associative comultiplication making it into a non-commutative analogue of the C * -algebra of continuous functions of the unitary group U X . The structure of the quantum group C(U + X ) was later studied in detail by Banica in [2]. On the other hand, the subalgebra C(PU + X ) ¦ C(U + X ) can be naturally interpreted as a non-commutative version of the space of continuous functions on the projective unitary group PU X /T. In the classical setting, the conjugation action of U + X on M X induces a group isomorphism PU X ∼ = Aut(M X ), where Aut(M X ) is the group of * -automorpohisms of M X .
In the quantum setting, it is natural to expect that a similar identification between PU + X and quantum automorphisms of M X should hold, and indeed this is the case: In [56], the quantum automorphism group Aut + (M X ) was introduced by Wang (via an abstract universal C * -algebra C(Aut + (M X )) with generators and relations), and later Banica showed in [3] that the natural quantum group C * -algebra morphism C(Aut + (M X )) → C(PU + X ) is actually an isomorphism. In Lemma 6.5 below, we extend Banica's result by showing that in fact any "concrete" quantum automorphism of M X (that is, a * -homomorphism à :
) is implemented by a "concrete" conjugation of M X by a bi-unitary (that is, Ã is the restriction of a representation C(U + X ) → B(H)). Lemma 6.5.
(i) We have
Proof. (i) Set J = J 1 + J 2 , recall that JX is the closed ideal of C X,A generated by the elements y∈X ẽy,y,a,a ′ - ¶ a,a ′ 1, a, a ′ ∈ X (see the paragraph containing equation ( 21)) and, recalling the ideals J1 and J2 of C X,A defined before Lemma 6.4, let (39) J = JX + J1 + J2 .
According to Proposition 3.8, C X,A / JX ≃ C X ; thus, C X,A / J ≃ C X /J . Recall that U X,A is the universal C * -algebra with generators ũx,x ′ ,a,a ′ := ũ * a,x ũa ′ ,x ′ , x, x ′ , a, a ′ ∈ X, where the matrix (ũ a,x ) a,x is unitary. By Lemma 6.4, we have the canonical *-isomorphism C X,A / J2 ≃ U X,A .
We have that C X,A / J ≃ (C X,A / J2 )/( J / J2 ). Using the identification in Lemma 6.4, we have that J / J2 is generated by the elements y∈X ũy,y,a,a ′ - ¶ a,a ′ 1, a, a ′ ∈ X, and a∈X ũy,x,b,a ũx ′ ,z,a,c - ¶ x,x ′ ũy,z,b,c , y, z, b, c, x, x ′ ∈ X.
Let Ä : U X,A ≃ C X,A / J2 → B(K) be a unital *-representation that annihilates J / J2 . By Lemma 6.3, there exists a unitary Ũ = ( Ũa,x ) a,x such that
y∈X Ũ * a,y Ũa ′ ,y = ¶ a,a ′ I, a, a ′ ∈ X, and
By (40), Ũ t = ( Ũy,a ) a,y is an isometry. But then Ũ t ( Ũ t ) * f I, implying, by comparing the (x, x)-entries of the matrices, that a∈X Ũa,x Ũ * a,x f I, x ∈ X. On the other hand, (41)
Multiplying ( 43) by Ũ * b,y ¹ I on the right and adding up along the variable y, we obtain Ũ t Ũ t * = I; thus, U t is unitary. Therefore, U gives rise to a unital *-representation of C(U + X ) and, after restriction, to a unital *-representation of C(PU + X ). We have thus shown that every unital * -representation Ä : C X,A / J2 → B(K) that annihilates J / J2 induces a unital * -homomorphism from C(PU + X ) to B(K). By [52,Theorem 5.2], there exists a * -homomorphism φ : C X,A → C(PU + X ), such that φ(ẽ x,x ′ ,a,a ′ ) = u x,x ′ ,a,a ′ , x, x ′ , a, a ′ ∈ X. A straightforward verification shows that φ annihilates J2 and hence gives rise to a * -homomorphism φ : C X,A / J2 → C(PU + X ), ẽx,x ′ ,a,a ′ + J2 → u x,x ′ ,a,a ′ . It is easy to see that J / J2 ¦ ker φ. The previous paragraph shows that if T ∈ C X,A / J2 then
giving the inclusion ker( φ) ¦ J / J2 and hence the equality ker( φ) = J / J2 . As φ is surjective we obtain the statement.
(ii) Let à : C(PU + X ) → B(H) be a unital *-representation. Letting Ä : C X,A → C X,A / J be the quotient map, the proof of (i) allows us to consider Ä as a *-epimorphism from C X,A onto C(PU + X ). It further exhibits a bi-unitary Ũ = ( Ũa,x ) a,x such that (Ã
x ′ , a, a ′ ∈ X, and the proof is complete.
□
We recall that the opposite C*-algebra A op of a C*-algebra A has the same set, linear structure and involution as A, and multiplication given by u op v op = (vu) op , where u op denotes the element u ∈ A when viewed as an element of A op . Given a Hilbert space H, let H d denote its dual Banach space and, for an operator T ∈ B(H), let T d : H d → H d be its dual. We note the identity (44) (
given by à op (u op ) = Ã(u) d , is a faithful *-representation.
The following result can be proved using the existence of the antipode for compact quantum groups together with the fact that PU + X , the antipode is known to be a * -anti-automorphism of C(PU + X ) (see e.g., [42, Proposition 1.7.9]). For the sake of those unacquainted with quantum group technicalities, we supply a self-contained proof. Lemma 6.6. Let X be a finite set. The map
We observe that V := (V a,x ) a,x is a bi-unitary. Indeed, using (44), we have
that is, V * V = I and V t * V t = I; the relations V V * = I and V t V t * = I follow analogously. It follows that there exists a *-representation Ä :
Before formulating the next theorem, we introduce some notation and terminology. If Φ : M X → M X is a quantum channel, we write Φ q : M X → M X for the quantum channel given by
We call a channel Φ : M X → M X a unitary channel if there exists a unitary
Theorem 6.7. Let X be a finite set and Γ : M XX → M XX be a QNS bicorrelation. Then
(ii) Γ ∈ Q bic q if and only if (45) holds for a trace of C(PU + X ) that factors through a finite dimensional C*-algebra; (iii) Γ ∈ Q bic loc if and only if (45) holds for an abelian trace of C(PU + X ), if and only if there exist unitary channels Φ i , i = 1, . . . , k, such that Γ = k i=1 ¼ i Φ i ¹ Φ q i as a convex combination. Proof. (i) Let U := (u a,x ) a,x be the universal bi-unitary and Γ : M XX → M XX be given via (45). There exists a state ¿ : C(PU + X ) ¹ max C(PU + X ) op → C, given by ( 46)
implying that Γ = Γ s . By Lemma 6.5 (i) and Theorem 5.5, Γ ∈ Q bi qc . Since U is unitary, by the proof of [11,Theorem 4.3], Γ is concurrent.
Conversely, let Γ ∈ Q bic qc . By Theorem 5.5, there exists a state s : C X ¹ max C X → C such that Γ = Γ s . Let V = (v a,x ) a,x be a universal bi-isometry (see Subsection 3.2) and denote by f y,y ′ ,b,b ′ the canonical generators of the second copy of C X in the tensor product. The concurrency of Γ implies the validity of the condition (47)
Let Ä : C X → C be the functional, given by Ä (u) = s(u ¹ 1), u ∈ C X . By [11,Lemma 4.2], there exists a canonical *-epimorphism à : C X,A → C X ; let Ä = Ä •Ã. Letting s : C X,A ¹ max C X,A → C be given by s(w) = (s•(ùÃ))(w), we have that and that Ä is a tracial state.
Recalling notation ( 37) and ( 38), set
We claim that
x,x ′ g 0, implying (49), along with the relations a∈X v a,x v * a,x f 1, x ∈ X. Identity (49) now shows that G y,y,b,b ∈ M X (C X ) + , and hence
x,y∈X a,b∈X
By ( 47), ( 52) and ( 53 Thus the diagonal entries of Ä (X) (G y,y,b,b ) are zero; the positivity condition (50) implies that the off-diagonal entries of Ä (X) (G y,y,b,b ) are also zero. Now the positivity condition (49) implies that
Condition (49) and the Cauchy-Schwarz inequality imply Ä (2X) Q G1/2 y,z,b,c = 0, for all Q ∈ M 2 (M X (C X )), and hence Ä (2X) annihilates the closed ideal of M 2 (M X (C X )) generated by G1/2 y,z,b,c . In particular, Ä (2X) annihilates the closed ideal of M 2 (M X (C X )) generated by Gy,z,b,c ; since C X is unital, this implies that Ä annihilates the closed ideal of C X generated by the elements
Similarly, observe that It follows that Ä annihilates the ideal J 2 , generated by h a,a ′ y,z,b,c , where a, a ′ , y, z, b, c ∈ X, and hence it annihilates J 1 + J 2 . Hence Ä induces a tracial state (denoted in the same fashion) on the quotient C X /J . An application of Lemma 6.5 (i) completes the proof.
(ii) Suppose that Γ : M XX → M XX is a quantum concurrent QNS bicorrelation. By [11,Theorem 4.3], there exists a finite dimensional C*algebra A, a trace t on A, and a *-homomorphism ³ : U X,A → A, such that Γ = Γ t•³ . After taking a quotient, we may assume that t is faithful. Let Ä : C X,A → U X,A be the canonical quotient map, whose existence is guaranteed by [11,Lemma 4.2]. Let Ä : C X,A → C be the functional, given by Ä (u) = (t • ³ • Ä)(u), u ∈ C X,A ; clearly, Ä is a trace on C X,A . Note, further, that Γ = Γ Ä (for brevity here, and in the sequel, Γ Ä is used to denote Γ s τ , where s Ä is the state, canonically associated with the trace Ä ). By the proof of (i), Ä annihilates the ideal J defined in (39); thus, as t is faithful, (³ • Ä)( J ) = 0 and hence we get a * -homomorphism Ä : C(PU + X ) → A and the trace Ä = t • Ä on C(PU + X ) which factors through A. Conversely, suppose that B is a finite dimensional C*-algebra. Let à : C(PU + X ) → B be a unital *-homomorphism and Ä : B → C be a trace such that, if Ä = Ä • Ã, then Γ = Γ Ä . By Lemma 6.5 (ii), there exists a finite dimensional Hilbert space K and a bi-
By [11,Theorem 4.3 (iii)], there exists an abelian C*-algebra A, a *-homomorphism à : U X,A → A and a state ϕ : A → C such that, if Ä = ϕ • à then (Ä is a trace on U X,A such that) Γ = Γ Ä . Realise A = C(Ω) for some compact Hausdorff space Ω and let µ be a regular Borel measure on Ω such that ϕ(h) = Ω hdµ. Writing Ũx,x ′ ,a,a ′ = Ã(ũ x,x ′ a,a ′ ), x, x ′ a, a ′ ∈ X, we have
As µ can be approximated by convex combinations of point mass evaluations, Γ can be approximated by convex combinations k
Since the matrices M i give rise to (one-domensional) *-representations of U X,A , by Lemma 6.3, they admit factorisations of the form µ
, where Φ i is the (unital) quantum channel with Choi matrix µ
x,x ′ ,a,a ′ . By the Carathéodory Theorem and compactness, we have that Γ is itself a convex combination of this form. We further have that
Thus, Φ ¹ Φ q is a concurrent correlation and, since Φ is unital, it is a concurrent bicorrelation. Since Q bic loc is convex, we have that all convex combinations of elementary tensors of the form Φ ¹ Φ q belong to Q bic loc . Now assume that Γ = k i=1 ¼ i Φ i ¹ Φ q i as a convex combination, where Φ i is a unitary channel, i = 1, . . . , k. Assume that Φ i (É) = U * i ÉU i , É ∈ M X , where U i ∈ M X is a unitary. Since U i has scalar entries, it is automatically a bi-unitary, and hence gives rise to a canonical (one-dimensional) unital *-representation of C(PU + X ). A standard argument now shows that Γ = Γ Ä for a trace on the (finite dimensional) abelian C*-algebra D k .
Finally, if Γ = Γ Ä , where Ä factors through an abelian C*-algebra then the argument in the first paragraph of (iii) shows that Γ ∈ Q bic loc . □ Remark 6.8. Assume that Ä is an amenable trace of C(PU + X ). By [13, Theorem 6.2.7], the functional µ : C(PU + X ) ¹ min C(PU + X ) op → C, given by µ(u ¹ v op ) = Ä (uv), is a well-defined state. Letting s = µ • (id ¹∂) (a state on C(PU + X )¹ min C(PU + X ) op ), one can proceed similarly to the first paragraph of the proof of Theorem 6.7 to conclude that Γ ∈ Q bic qa . We do not know if, conversely, every Γ ∈ Q bic qa arises from an amenable trace on C(PU + X ). Recall [47] that an NS correlation p over (X, X, X, X) is called bisynchronous if p(a, b|x, x) ̸ = 0 =⇒ a = b and p(a, a|x, y) ̸ = 0 =⇒ x = y.
It was shown in [47, Remark 2.1] that bisynchrounous correlations of type t ̸ = ns are (classical) bicorrelations. The next statement describes the relation between bisynchronicity and concurrency. Proposition 6.9. Let t ∈ {loc, q, qc}. If p ∈ C t is a bisynchronous NS correlation over the quadruple (X, X, X, X) then there exists
Proof. We consider first the case t = qc. Let p ∈ C qc be a bisynchronous correlation. By [47, Theorem 2.2], there exists a tracial state Ä : C(S + X ) → C such that (55) p(a, b|x, y) = Ä (p a,x p b,y ), x, y, a, b ∈ X.
Let p x,x ′ a,a ′ := p * a,x p a ′ ,x ′ = p a,x p a ′ ,x ′ , x, x ′ , a, a ′ ∈ X, and let C(PS + X ) be the subalgebra of C(S + X ), generated by the elements of the form p x,x ′ ,a,a ′ , x, x ′ , a, a ′ ∈ X. Since every quantum permutation is a bi-unitary, there exists a unital *-homomorphism à :
Let Ä = Ä • Ã; thus, Ä is a tracial state on C(PU + X ) and hence, by Theorem 6.7, Γ Ä is a quantum commuting concurrent QNS bicorrelation. Moreover, if x, y ∈ X then
The cases t = q and t = loc are similar. □
In this section, we view the concurrent bicorrelations studied in Section 6 as strategies for the non-commutative graph isomorphism game. This allows us to define quantum information versions of quantum isomorphisms of non-commutative graphs of different types, which we characterise in terms of relations arising from the underlying graphs.
7.1. Quantum commuting isomorphisms. Several related concepts of quantum graphs have been studied in the literature (see [9,15,20]). Here we work with the notion that is used in [52], [51] and [11]. Let X be a finite set, H = C X , and recall that H d stands for the dual (Banach) space of H. Note that, as an additive group, H d can be identified with H; we write • for the element of H d , corresponding to the vector • in H (so that • :
For a subspace U ¦ C X ¹ C X , set
We let ∂ X : (C X ) d → C X be the linear mapping given by ∂ X (ē x ) = e x , x ∈ X, and we set SU := S U ∂ -1 X ; thus, SU ¦ L(C X ). We denote by m :
Let also f : C X ¹C X → C X ¹C X be the flip operator, given by f(À¹¸) = ¸¹À.
In the sequel, for a subspace U ¦ C X ¹ C X , we denote by P U the orthogonal projection from C X ¹ C X onto U ; thus, P U ∈ M XX . For a classical (simple, undirected) graph G with vertex set X, we use ∼ (or ∼ G when a clarification is needed) to denote the adjacency relation of G. The graph G gives rise to the quantum graph U G = span{e x ¹ e y : x ∼ y}, and we write P G = P U G ; note that P G ∈ D XX , and that SU G = span{ϵ x,y : x ∼ y} is a traceless self-adjoint subspace of M X . More generally, SU ¦ M X is always a traceless transpose-invariant subspace for any quantum graph U ; this is the suitable version arising in our setting of Stahlke's quantum graphs [51], where tracelessness and self-adjointness are assumed as part of the definition.
To motivate Definition 7.2 below, we first recall the graph isomorphism game [1] for graphs G and H, both with vertex set X. For elements x, y ∈ X, we denote by rel G (x, y) the element of the set {=, ∼, ̸ ≃}, which describes the adjacency relation in the pair (x, y), in the graph G. A correlation p ∈ C t is said to be a perfect t-strategy for the (G, H)-isomorphism game, provided p is bisynchronous and
We note that, for a given correlation type t, two graphs G and H with vertex set X are t-isomorphic [1] if and only if there exists a bisynchronous bicorrelation p of type t over the quadruple (X, X, X, X), such that 58) is equivalent to requiring that p(a, b|x, y) = 0 if x ∼ G y but a ̸ ∼ H b, while (59) is equivalent to requiring that p(a, b|x, y) = 0 if a ∼ H b but x ̸ ∼ G y, in conjunction, these two conditions are equivalent to (57).
Recall [52,11] that, if U ¦ C X ¹ C X and V ¦ C X ¹ C X are quantum graphs, and P = P U and Q = P V , then the perfect strategies for the quantum homomorphism game U → V are the QNS correlations Γ :
XX and É = P ÉP =⇒ Γ(É) = QΓ(É)Q. Definition 7.2. Let t ∈ {loc, q, qa, qc, ns}. We say that U and V are tisomorphic, and write U ∼ = t V, if there exists Γ ∈ Q bic t such that (i) Γ is a perfect strategy for U → V, and (ii) Γ * is a perfect strategy for V → U.
Remark 7.3. Although our main interest in this section lies in quantum graphs, it is important to note, for the development in Section 8, that Definition 7.2 can be stated in a greater generality, involving subspaces U and V of C X ¹ C X that are not necessarily quantum graphs.
In the next theorem, we give an operator algebraic characterisation of the relation U ∼ = qc V. We recall the leg numbering notation: if
x,y,a,b∈X
For the formulation of the next theorem, we set Ā = A t * , and call a von Neumann algebra tracial if it admits a tracial state. If H is a Hilbert space and N ¦ B(H) is a von Neumann algebra, an operator matrix U = (U a,x ) a,x∈X will be called N -aligned if U * a,x U b,y ∈ N for all x, y, a, b ∈ X.
Theorem 7.4. Let U and V be quantum graphs in C X ¹C X , and set P = P U and Q = P V .
The following are equivalent:
(ii) there exists a tracial von Neumann algebra N ¦ B(H) and an Naligned bi-unitary U = (U a,x ) a,x ∈ M X (B(H)) such that
Proof. (i)⇒(ii) For a vector À = x,y∈X ³ x,y e x ¹ e y ∈ C X ¹ C X , let À =
x,y∈X ³ x,y e x ¹ e y and set
x,y∈X ³ x,y ϵ x,y ; note that Y À ∈ M X (and that the use of the notation À agrees, up to a canonical identification, with the definition in the beginning of Subsection 7.1).
Let Γ : M XX → M XX be a concurrent quantum commuting bicorrelation satisfying conditions (i) and (ii) in Definition 7.2. By Theorem 6.7, there exists a tracial state Ä :
Let Ã Ä be the *-representation, associated with Ä via the GNS construction, and let • be the corresponding cyclic vector. Then N = Ã Ä (C(PU + X )) ′′ is a finite von Neumann algebra, on which the vector state corresponding to • is faithful and tracial.
Let E = (Ã Ä (u x,x ′ ,a,a ′ )) x,x ′ ,a,a ′ . As in the proof of [11,Theorem 5.5], we have that
implying, by the faithfulness of Ä , that
By Lemma 6.5 (ii), there exists a bi-unitary U = (U a,x ) a,x , such that E = (U * a,x U a ′ ,x ′ ) x,x ′ ,a,a ′ . Writing À = x,y∈X ³ x,y e x ¹ e y and ¸= a,b∈X ´a,b e a ¹ e b , we calculate
.
. By (61), the operator F satisfies the conditions ïF (¸¹ h), À ¹ gð = 0, h, g ∈ H,
Setting F := U 1,3 Ū2,3 =
x,y,a,b∈X ϵ a,x ¹ ϵ b,y ¹ U a,x U * b,y ,
we similarly obtain that
and hence
Let t : M X → M X be the map, given by t(T ) = T t . Since the operators P § and Q are self-adjoint, (t ¹ t)(Q) = Q and (t ¹ t)(P § ) = P § . Thus, applying the map t¹t¹id to the relation (62), we obtain ( P § ¹I)F ( Q¹I) = 0 (ii)⇒(i) Assume that (P ¹I)U t 1,3 U * 2,3 (Q § ¹I) = 0 and ( P § ¹I)U t 1,3 U * 2,3 ( Q¹ I) = 0. By Theorem 6.7 (i), the linear map Γ, given by Γ(ϵ
, is a concurrent quantum commuting bicorrelation. Reversing the arguments from the previous paragraphs and using the proof of [11,Theorem 5.5], we obtain that, if
for all À ∈ U and all ¸∈ V § . Similarly,
Consider U 2,3 Ū1,3 as a linear operator on C XX ¹ B(H) by letting (U 2,3 Ū1,3 )(À ¹ T ):=
x,y,a,b∈X
Fix À ∈ C XX . We have
x,y,a,b∈X
X ¹ I)U * . To see that U ( SU ¹ 1)U * ¦ SV ¹ B(H), let À ∈ U, and fix orthonormal bases (¸i) i∈I and (• j ) j∈J of V and V § , respectively. Then
for some R i , S j ∈ B(H), i ∈ I, j ∈ J. From the previous arguments we obtain
Let É g,h be the vector functional on B(H), given by É g,h (T ) = ïT g, hð and, for ¸∈ C XX , let ℓ ¸be the linear functional on C XX , given by ℓ ¸(À) = ïÀ, ¸ð.
Then (ℓ ¸¹ É g,h )(U 2,3 Ū1,3 (À ¹ I))) =
x,y,a,b∈X ï(ϵ x,a ¹ ϵ y,b )À, ¸ðïU a,x U * b,y g, hð = ïU 2,3 Ū1,3 (À ¹ g), ¸¹ hð,
Taking now ¸= • j we obtain from (63) that
thus, ïS j g, hð = 0. As g and h can be chosen arbitrarily, S j = 0 for all j ∈ J. Therefore
Similar arguments applied to (Q ¹ I) F (P § ¹ I) = 0, where F = U 1,3 Ū2,3 , give U t ( SV ¹ 1)(U t ) * ¦ SU ¹ B(H).
(iii)⇒(ii) follows, using (64), by reversing the arguments in the implication (ii)⇒(iii). □
The arguments in the proof of Theorem 7.4 can be used to conclude that U → qc V if and only if there exists a tracial von Neumann algebra N ¦ B(H) and an N -aligned isometry V = (V a,x ) a,x , V a,x ∈ B(H), such that
This complements the characterisation obtained in [11,Theorem 5.7].
(ii) Similar results to those of Theorem 7.4 hold for U ≃ q V, in which case the space H is finite-dimensional. A treatment of the case U ≃ loc V is presented in Subsection 7.2 below. We can formulate a similar characterisation for types loc and q.
In the case when the bi-unitary U is actually a quantum permutation (that is, the entries u i,j of U are all orthogonal projections), these conditions are equivalent to the condition that U (A G ¹ I)U * = A H ¹ I. Indeed, if U is a quantum permutation satisfying A H c * U (A G ¹ I)U * = 0, then whenever i ̸ = j and i ̸ ∼ H j, we have
Multiplying on the left by u i,k for any fixed k satisfying k ∼ G ℓ, we obtain u i,k u j,ℓ = 0 whenever i ̸ ∼ H j, i ̸ = j and k ∼ G ℓ. Similarly, if i = j and k ∼ G ℓ, then k ̸ = ℓ, so that u i,k u j,ℓ = 0. Next, if we interchange the roles of G and H in the above argument and replace U with the magic unitary U t , the identity A G c * U t (A H ¹ I) Ū = 0 yields u k,i u ℓ,j = 0 whenever i ̸ ∼ G j, i ̸ = j and k ∼ H ℓ or whenever i = j, and k ∼ H ℓ.
It follows that, if i ∼ H j, then (assuming that n = |X|) we have
Similarly, if i ̸ ∼ H j, then either i = j or i ∼ H c j, and we obtain in either case (U (A
It follows that U (A G ¹ I)U * = A H ¹ I. The converse is immediate.
7.2. Local isomorphisms. In this subsection, we restrict our attention to quantum graph isomorphisms of local type.
Proposition 7.7. Let X be a finite set, and U and V be quantum graphs in C X ¹ C X . The following are equivalent:
Proof. (i)⇒(ii) Let Γ ∈ Q bic loc is a correlation satisfying the conditions of Definition 7.2 for quantum graphs U and V. By Theorem 6.7 (iv), Γ = k i=1 ¼ i Φ i ¹ Φ q i as a convex combination, where Φ i : M X → M X is a unitary quantum channel, i = 1, . . . , k. Conditions (i) and (ii) in Definition 7.2 are equivalent to (66) Γ(P U ), P § V = 0 and Γ * (P V ), P § U = 0.
The monotonicity of the trace functional now implies that Φ i ¹ Φ q i satisfies the conditions in Definition 7.2 for every i = 1, . . . , k. We may thus assume that Γ = Φ ¹ Φ q , where Φ : M X → M A is a unitary quantum channel. Let U ∈ M X be a unitary such that Φ(É) = U * ÉU , É ∈ M X . A direct verification shows that
The first condition in (66) now implies that, for every À ∈ U, we have
and arguing by symmetry implies that (U ¹ Ū )(V) ¦ U; thus, (ii) follows.
(ii)⇒(i) Given a unitary U ∈ M X , let Φ(É) = U * ÉU , É ∈ M X , and Γ = Φ ¹ Φ q . Then the arguments in the first part of the proof imply that U ∼ = loc V via Γ. □
Remark. Proposition 7.7 can equivalently be seen as a consequence of Theorem 7.4. Indeed, note that, by Theorem 6.7 (iv) and its proof, Γ ∈ Q bic loc if and only if Γ = k i=1 ¼ i Γ i as a convex combination, where Γ i (e x,x ′ ¹ e y,y ′ ) = (à i (u x,x ′ ,a,a ′ u y ′ ,y,b ′ ,b )) a,a ′ ,b,b ′ for some * -representation à i : C(PU + X ) → C. Using the fact that all Γ i are positive, it can be easily seen that one can assume that k = 1. Let U = (u a,x ) a,x ∈ M X be the unitary that corresponds to à 1 as in the proof of the implication (i)⇒(ii); we have that U satisfies the corresponding conditions (ii) and (iii). In particular, U SU U * ¦ SV and U t SV (U t ) * ¦ SU . As St U = SU and St V = SV , we obtain that U * SV U ¦ SU , which implies U * SV U = SU . This gives in particular that (U ¹ Ū )(U ) = V. Proposition 7.8. Let G and H be graphs with vertex set X.
Proof. A graph isomorphism φ : X → X between G and H gives rise to a permutation unitary operator U φ : C X → C X ; letting Φ : M X → M A be the conjugation by U φ , we have that the correlation Φ ¹ Φ q implements an isomorphism U G ∼ = loc U H .
Conversely, suppose that U G ∼ = loc U H . By Proposition 7.7, there exists a unitary U ∈ M X such that (U ¹ Ū )(U G ) = U H . Letting S G = span{ϵ x,y : x ∼ y or x = y}, we now have that U S G U * = S H . By [43,Proposition 3.1], G ∼ = H. □ Corollary 7.9. There exist quantum graphs U and V such that U ∼ = q V but U ̸ ∼ = loc V.
Proof. By [1, Theorem 6.4], there exists graphs G and H such that G ∼ = q H but G ̸ ∼ = loc H. By Proposition 7.8, U G ̸ ∼ = loc U H ; to complete the proof, we show that U G ∼ = q U H . By [36, Theorem 2.1], there exists a quantum permutation matrix (P x,a ) x,a , acting on a finite dimensional Hilbert space H, such that
3. The quantum isomorphism algebra. Let X be a finite set, and U ¦ C XX and V ¦ C XX be quantum graphs. We will introduce a C*algebra whose tracial properties reflect the properties of the isomorphism game U ∼ = V. Let P (resp. Q) be the projection from C XX onto U (resp. from C XX onto V). For matrices S, T ∈ M XX , define a linear map
, and let
be the closed ideal in C(PU + X ), generated by the elements µ P,Q § (W ¹ W op ) and µ P § ,Q (W ¹ W op ). Set A P,Q = C(PU + X )/I P,Q . We write u for the image of an element u ∈ C(PU + X ) in A P,Q under the quotient map.
, and hence
, where in the last line we have used relation (69) for V to insert the extra copy of (P ¹ I ¹ I) in the middle. This shows that the first relation in (69) holds for Ṽ . The second relation in ( 69) is verified similarly.
Finally, we note that A P,P is, by construction, the C * -subalgebra of B generated by order two elements of B of the form v *
x,a v x ′ ,a ′ , x, x ′ , a, a ′ ∈ X. The natural co-multiplication ∆ P on A P,P is then the restriction of ∆ B to A P,P (note that ∆ B (A P,P ) ¦ A P,P ¹ A P,P ). Remark 7.13. Note that, by Proposition 7.7, any character on A P,P corresponds to a unitary U ∈ U X such that (U ¹ Ū )U = U . In other words, the abelianisation of A P,P corresponds via Gelfand duality to the classical compact group of unitary matrices
The pair (A P,P , ∆ P ) is therefore the quantisation of this very natural matrix group of automorphisms of U .
The purpose of this section is to clarify the connection between the notion of a quantum graph isomorphism defined and characterised in Section 7 and the notion, defined and studied in [9]. Our main reference for the latter concept will be [15], and we follow its notation as closely as possible.
8.1. Algebraic isomorphism as a tighter equivalence. We fix throughout the section a finite set X and let n = |X|. We denote by tr the normalised trace on M X ; thus, tr = 1 |X| Tr. In order to simplify the notation, we will write 1 in the place of I X .
Denote by L 2 (M X ) the Hilbert space with underlying linear space M X and inner product arising from the GNS construction applied to the pair (M X , tr). More specifically, if Λ : M X → L 2 (M X ) is the GNS map, we set ïΛ(a), Λ(b)ð = tr(a * b) (note that the inner product is linear in the second variable). In what follows, we view M X as a subalgebra of B(L 2 (M X )), where an element a ∈ M X gives rise to the operator (denoted in the same way and given by)
) be the multiplication map, that is, the map, defined by letting m(Λ(a)¹Λ(b)) = Λ(ab), and m * : L 2 (M X ) → L 2 (M X ) ¹ L 2 (M X ) be its Hilbert space adjoint. For notational simplicity, we will often suppress the use of Λ, and consider m (resp. m * ) as a map from M X ¹ M X to M X (resp. from M X to M X ¹ M X ). We note that
Indeed, for p, q, s, t = 1, . . . , n, we have (71) ïm * (ϵ i,j ), ϵ p,q ¹ ϵ s,t ð = ïϵ i,j , ϵ p,q ϵ s,t ð = tr(ϵ j,i ϵ p,q ϵ s,t ), while
= n tr(ϵ s,i ϵ p,q ) tr(ϵ j,t ).
The right hand sides of (71) and (72) are thus equal, establishing (70) which, further, implies that
Let ¸: C → L 2 (M X ) be the map, given by ¸(¼) = ¼Λ(1). Recall [15, Definition 2.4] that a selfadjoint linear map A : L 2 (M X ) → L 2 (M X ) is called a quantum adjacency matrix if it has the following properties:
(1) m(A ¹ A)m * = A;
(
(3) m(A ¹ 1)m * = 0. We stress that condition (3) reflects the fact that we work with a quantum version of graphs without loops (graphs with loops are quantised in this context by requiring the condition m(A ¹ 1)m * = 1 instead of (3) [15, p. 6]). A triple G = (M X , tr, A), where A is a quantum adjacency matrix, is called in [9,15] a quantum graph. In order to distinguish this notion from the one used in the present paper, we will hereafter refer to it as an algebraic quantum graph.
We fix an algebraic quantum graph G = (M X , tr, A). We associate with G the M X -bimodule S ′ in B(L 2 (M X )) generated by A (its dependence on G is suppressed for notational simplicity); thus, recalling that the elements of M X are viewed as operators on L 2 (M X ), we have that (74)
If x, y ∈ M X , we write Θ Λ(x),Λ(y) for the rank one operator, given by ϵ i,j ¹ A(ϵ j,i ).
Lemma 8.1. Let G = (M X , tr, A) be an algebraic quantum graph. Then (i) Ψ(A) = e, (ii) e = e * , and
and the claim now follows from (75).
(ii
where f is the flip map. By linearity, we obtain
and therefore by (i) and condition ( 2), e = f(e).
Furthermore,
and therefore
giving e = e * = f(e).
(iii) The claim follows from the fact that
we note that, in the case G is classical, the space U G is closely related to, although not identical, to the space denoted in the same way in Section 7). Throughout this section, we fix an orthonormal basis {Λ(
and set ŨG = (∂ ¹1)(U G ). We next record the properties of the spaces of the form ŨG , akin to the properties of quantum graphs in the sense of Definition 7.1. We write d for the conjugate-linear map on L 2 (M X ) ¹ L 2 (M X ), given by
and recall that f is the flip map on L 2 (M X ) ¹ L 2 (M X ). We note that the definitions of the maps ∂ and d depend on the basis, but the concrete basis we are working with will be fixed or clear from the context. The same comment applies for the notion we define next.
The following are equivalent:
Therefore,
giving the equivalence (i)ô(ii). As
we obtain the equivalence (ii)ô(iii). □ Proposition 8.4. Let G = (M X , tr, A) be an algebraic quantum graph. Then ŨG is a quantum pseudo-graph.
Proof. As A is selfadjoint, there exist
and hence, for all y ∈ M X , we have
Therefore, n 2 j=1 ¼ j x j x * j = 0. By the previous paragraph, we have
showing that ŨG is skew. □ Remark 8.5. Proposition 8.4 shows that an algebraic quantum graph G = (M X , tr, A) gives rise to a canonical quantum pseudo-graph ŨG ¦ L 2 (M X )¹ L 2 (M X ). The reason we are led to work with quantum pseudo-graphs instead of quantum graphs in the sense of our Definition 7.1 lies in the setup of QNS correlations, which is borrowed from [20]. In defining QNS correlations, instead of no-signalling quantum channels Γ : M X ¹M Y → M A ¹M B , one could start with no-signalling quantum channels Γ ′ :
For the class of quantum commuting no-signalling correlations, this would lead to Choi matrices of the form (Ä (e x,x ′ ,a,a ′ e y,y ′ ,b,b ′ )), as opposed to the matrices (Ä (e x,x ′ ,a ′ ,a e y ′ ,y,b ′ ,b )) that arise through the current setup. As we will shortly see, in order to obtain a neat connection between the two note that by [9,Corollary 4.8], this is equivalent to (the seemingly weaker) assumption that O(G 1 , G 2 ) ̸ = 0. We assume, unless specified otherwise, that G 1 ≃ qc G 2 . Let H be the Hilbert space, arising from the GNS construction applied to Ä and, by abuse of notation, continue to write p i,j for the image of the corresponding canonical generator of O(G 1 , G 2 ) under the * -representation arising from Ä . By (81), we have (82) A 2 ¹ I H = P (A 1 ¹ I H )P * .
We view P = (p i,j ) n 2 i,j=1 as an operator on L 2 (M X ) ¹ H and note that, by (78), we have The statements now follow by linearity from the definition of U G 1 . □
Let N ¦ B(H) be a von Neumann algebra, equipped with a faithful trace Ä , and let U = (u i,j ) i,j ∈ M n 2 (N ) be a bi-unitary block operator matrix (with entries in N ). Suppose that Γ : M n 2 ¹ M n 2 → M n 2 ¹ M n 2 is a QNS correlation, given by (85) Γ(ϵ i,i ′ ¹ ϵ j,j ′ ) = (Ä (u * k,i u k ′ ,i ′ u * l ′ ,j ′ u l,j )) k,k ′ ,l,l ′ . We let Γ : M n 2 ¹ M n 2 → M n 2 ¹ M n 2 be the unital completely positive map, given by Γ(ϵ k,k ′ ¹ ϵ l,l ′ ) = (Ä (u * l,j u k,i u * k ′ ,i ′ u l ′ ,j ′ )) i,i ′ ,j,j ′ . If f k,k ′ ,i,i ′ = u k,i u * k ′ ,i ′ then Γ has Choi matrix (Ä (f k,k ′ ,i,i ′ f l ′ ,l,j ′ ,j )) and is hence a quantum commuting QNS correlation. We remark that, as can be verified in a straightforward way, if à : M n 2 ¹ M n 2 → M n 2 ¹ M n 2 is the map, given by Ã(ϵ k,k ′ ¹ ϵ l,l ′ ) = ϵ k ′ ,l ¹ ϵ l ′ ,k , then Γ = à • Γ * • Ã.
We call two quantum pseudo-graphs W 1 and W 2 qc-pseudo-isomorphic if there exists Γ ∈ Q bic qc of the form described in the previous paragraph, such that (i) Γ is a perfect strategy for W 1 → W 2 , and (ii) Γ is a perfect strategy for W 2 → W 1 .
Theorem 8.9. Let G r = (M X , tr, A r ), r = 1, 2, be algebraic quantum graphs with G 1 ≃ qc G 2 . Then the quantum pseudo-graphs ŨG 1 and ŨG 2 are qcpseudo-isomorphic.
Proof. Set Ũr = ŨGr for brevity, r = 1, 2. By assumption, the C*-algebra O(G 1 , G 2 ) has a tracial state, say Ä . Let N ¦ B(H) be the von Neumann algebra associated with Ä via the GNS construction, and Ä be the (faithful) trace on N , corresponding to Ä . Write u i,j for the images of the canonical generators p i,j under the Gelfand map, and let U and Ũ be the matrices, corresponding to P and P , respectively. Let Γ be the QNS correlation given by (85). Note that, by ( 84 We now show that Γ is a perfect strategy for Ũ2 → Ũ1 . Let À = n 2 k,l=1 ³ k,l f k ¹ f l ∈ Ũ2 and ¸= n 2 i,j=1 ´i,j f i ¹ f j ∈ Ũ § 1 ; then
Writing R À,¸= n 2 k,l,i,j=1 ³ k,l ´i,j u * k,i u l,j , we have ï Γ(ÀÀ * )¸, ¸ð = Ä (R * À,¸R À,¸) , and using the fact that Ä is faithful, this implies that ï Γ(ÀÀ * )¸, ¸ð = 0 ⇐⇒ R À,¸= 0.
Taking into account (60), we now have ïR À,¸f , hð = ï Ū1,3 U 2,3 (¸¹ f ), À ¹ hð, f, h ∈ H, and therefore (P Ũ2 ¹ 1) Ū1,3 U 2,3 (P § Ũ1 ¹ 1) = 0 ⇐⇒ Γ is a perfect strategy for Ũ2 → Ũ1 .
The proof is complete in view of (88). □ Remark 8.10. For a classical graph G with vertex set X, let A G : M X → M X be Schur multiplication map against the adjacency matrix of G. Then (M X , tr, A G ) is an algebraic quantum graph. Let
Then W G is a quantum pseudo-graph in L 2 (M X ) ¹ L 2 (M X ).
Let G 1 , G 2 be classical graphs with vertex set X. We have the following three types of quantum commuting isomorphism for the graphs G 1 and G 2 :
(a) quantum commuting isomorphism in the sense of classical non-local games [1]; (b) quantum commuting isomorphism of the algebraic quantum graphs (M X , tr, A G 1 ) and (M X , tr, A G 2 ); (c) quantum commuting isomorphism in the sense of quantum non-local games (Section 7), employing the quantum pseudo-graphs W 1 and W 2 .
Remark 8.12. We remark that reversing the arguments of Lemmas 8.1 and 8.11, we can easily see that any projection e ∈ M op X ¹ M X , such that e = f(e), gives rise to selfadjoint operator A : L 2 (M X ) → L 2 (M X ) satisfying the conditions (1) and (2) of quantum adjacency matrix and linked to e through the identity (75).
Let J : L 2 (M X ) → L 2 (M X ) be the conjugate-linear map, given by J(Λ(a)) = Λ(a * ), and the map » : B(L 2 (M X )) → B(L 2 (M X )) be given by »(x) = Jx * J. We have that » is an anti- * -homomorphism such that » 2 = id; writing à : L 2 (M X ) → L 2 (M X ) for the * -homomorphism given by Ã(x)Λ(a) = Λ(xa), we have that »(Ã(M X )) = Ã(M X ) ′ . Proposition 8.13. Let Ũ be a quantum pseudo-graph such that Ψ -1 ((∂ -1 ¹ 1)( Ũ )) is an M X -bimodule. Then there exists an algebraic quantum graph G = (M X , tr, A) such that Ũ = ŨG .
Proof. Let U = (∂ -1 ¹ 1)( Ũ ) and S ′ = Ψ -1 (U ). By assumption, S ′ is an M X -bimodule and hence »(S ′ ) is a Ã(M X ) ′ -bimodule. Under the canonical bijection between B(L 2 (M X )) and L 2 (M X ) d ¹ L 2 (M X ), the Ã(M X ) ′bimodule »(S ′ ) corresponds to the (Ã(M X ) ′ ) op ¹ Ã(M X ) ′ -invariant subspace U ′ . Thus it gives rise to the projection e ∈ M op X ¹ M X onto U ′ . By Lemma 8.3, S ′ is selfadjoint and hence so is »(S ′ ), which implies, again by Lemma 8.3, that e = f(e) and J 0 (U ′ ) = U ′ .
Let A : L 2 (M X ) → L 2 (M X ) be the linear map corresponding to e as in Remark 8.12. We have that »(S ′ ) is the Ã(M X ) ′ -bimodule generated by A. It follows that S ′ is the Ã(M X )-bimodule generated by A. In fact, since »(Ã(M X ) ′ ) = Ã(M X ), it suffices to verify that JA * J = A. Write A = m i=1 ¼ i Θ Λ(x i ),Λ(x i ) , ¼ i ∈ R, x i ∈ M X , i = 1, . . . , m. Then e = Ψ(A) = m i=1 ¼ i x * i ¹ x i . On the other hand,
Thus Ψ(JA * J) = m i=1 ¼ i x i ¹ x * i = f(e). As e = f(e), we get Ψ(JA * J) = Ψ(A), implying that JA * J = A.
Finally, reversing arguments in Proposition 8.4 we see that skewness of Ũ implies that m(A ¹ 1)m * = 0, showing that A is a quantum adjacency matrix. Letting G = (M X , A, tr), we have that Ũ = ŨG . □
We now fix a quantum pseudo-graph Ũr in L 2 (M X ) ¹ L 2 (M X ), for which the corresponding space S ′ r is an M X -bimodule, and let U r := (∂ -1 ¹ 1)( Ũr ), r = 1, 2. We assume that Ũ1 and Ũ2 are qc-pseudo-isomorphic, and let N be a von Neumann algebra with trace Ä , and U = (u k,i ) n 2 k,i=1 be a bi-unitary, with u k,i ∈ N , k, i = 1, . . . , n 2 , such that U gives rise, via (85), to a QNS correlation implementing a qc-pseudo-isomorphism between ŨG 1 and ŨG 2 . The proof of Theorem 8.9 implies that From the definition of U , we have Observe that V = (F -1 ¹ 1)U (F ¹ 1) (96) where F : H d → H is the unitary given by F Λ(x) = Λ(x * ). Indeed, to establish (96), we note that F -1 = F * and, for À ∈ K and i = 1, . . . , n 2 , we compute:
By (96), and the identities F (Λ(1)) = Λ(1) and F -1 (Λ(1)) = Λ(1), we have (97) V (Λ(1) ¹ À) = Λ(1) ¹ À.