communicated to us by Vern Paulsen (see [6]).

Remark.  If $G$ is a graph with vertex set $[d]$ and $S\subseteq[d]$ is an
independent set of $G$ then the set $\\{e_{i}:i\in S\\}$ is
$\mathcal{S}_{G}$-independent. Similarly, if $K\subseteq[d]$ is a clique of
$G$ then the set $\\{e_{i}:i\in K\\}$ is $\mathcal{S}_{G}$-full, and hence an
$\mathcal{S}_{G}$-clique. The notion of an $\mathcal{S}$-independent set – and
that of an $\mathcal{S}$-abelian projection – can thus be viewed a non-
commutative version of the notion of an independent set of a graph. Similarly,
$\mathcal{S}$-clique and $\mathcal{S}$-full projections are (distinct) non-
commutative versions of the notion of a clique of a graph.

Recall the following convex $M_{d}$-corners, associated with a non-commu-
tative graph $\mathcal{S}\subseteq M_{d}$ [6]:

  * •

$\mathop{\rm ap}(\mathcal{S})={\rm C}\left(\mathcal{P}_{\rm
a}(\mathcal{S})\right)$, the _abelian projection convex corner_ ;

  * •

$\mathop{\rm cp}(\mathcal{S})={\rm C}\left(\mathcal{P}_{\rm
c}(\mathcal{S})\right)$, the _clique projection convex corner_ ;

  * •

$\mathop{\rm fp}(\mathcal{S})={\rm C}\left(\mathcal{P}_{\rm
f}(\mathcal{S})\right)$, the _full projection convex corner_.

######  Remark 8.2.

Let $\mathcal{S}\subseteq M_{d}$ be a non-commutative graph.

  * (i)

Since every $\mathcal{S}$-full projection is $\mathcal{S}$-clique, we have
$\mathop{\rm fp}(\mathcal{S})\subseteq\mathop{\rm cp}(\mathcal{S})$.

  * (ii)

Since every rank one projection is trivially $\mathcal{S}$-abelian and
$\mathcal{S}$-clique, $\mathcal{A}_{I_{d}}\subseteq\mathop{\rm
ap}(\mathcal{S})\subseteq\mathcal{B}_{I_{d}}$ and
$\mathcal{A}_{I_{d}}\subseteq\mathop{\rm
cp}(\mathcal{S})\subseteq\mathcal{B}_{I_{d}}$.

  * (iii)

The convex corners $\mathop{\rm ap}(\mathcal{S})$ and $\mathop{\rm
cp}(\mathcal{S})$ are standard. This is not always true for $\mathop{\rm
fp}(\mathcal{S})$, which can reduce to $\\{0\\}$.

  * (iv)

If $\mathcal{T}\subseteq M_{d}$ is a non-commutative graph with
$\mathcal{S}\subseteq\mathcal{T}$ then $\mathop{\rm
ap}(\mathcal{T})\subseteq\mathop{\rm ap}(\mathcal{S})$, $\mathop{\rm
cp}(\mathcal{S})\subseteq\mathop{\rm cp}(\mathcal{T})$ and $\mathop{\rm
fp}(\mathcal{S})\subseteq\mathop{\rm fp}(\mathcal{T})$.

Parts (i)-(ii) of the next proposition were established in [6], while
(iii)-(iv) follow after an application of Proposition 5.4.

######  Proposition 8.3.

Let $G$ be a graph. The following hold:

  * (i)

$\mathop{\rm ap}(\mathcal{S}_{G})$ is a non-commutative lift of $\mathop{\rm
vp}(G)$;

  * (ii)

$\mathop{\rm cp}(\mathcal{S}_{G})$ and $\mathop{\rm fp}(\mathcal{S}_{G})$ are
non-commutative lifts of $\mathop{\rm vp}(\bar{G})$;

  * (iii)

$\mathop{\rm ap}(\mathcal{S}_{G})^{\sharp}$ is a non-commutative lift of
$\mathop{\rm fvp}(\bar{G})$;

  * (iv)

$\mathop{\rm cp}(\mathcal{S}_{G})^{\sharp}$ and $\mathop{\rm
fp}(\mathcal{S}_{G})^{\sharp}$ are non-commutative lifts of $\mathop{\rm
fvp}(G)$.

Now Theorem 5.6, Remark 8.2 and Proposition 8.3 imply the following.

######  Corollary 8.4.

Let $G$ be a graph. The following hold:

  * (i)

$\mathop{\rm her}(\mathop{\rm vp}(G))\subseteq\mathop{\rm
ap}(\mathcal{S}_{G})\subseteq(\mathop{\rm vp}(G)^{\flat})^{\sharp}$;

  * (ii)

$\mathop{\rm her}(\mathop{\rm vp}(\bar{G}))\subseteq\mathop{\rm
fp}(\mathcal{S}_{G})\subseteq\mathop{\rm
cp}(\mathcal{S}_{G})\subseteq\mathop{\rm fvp}(G)^{\sharp}$;

  * (iii)

$\mathop{\rm her}(\mathop{\rm vp}(G)^{\flat})\subseteq\mathop{\rm
ap}(\mathcal{S}_{G})^{\sharp}\subseteq\mathop{\rm vp}(G)^{\sharp}$;

  * (iv)

$\mathop{\rm her}(\mathop{\rm fvp}(G))\subseteq\mathop{\rm
cp}(\mathcal{S}_{G})^{\sharp}\subseteq\mathop{\rm
fp}(\mathcal{S}_{G})^{\sharp}\subseteq(\mathop{\rm fvp}(G)^{\flat})^{\sharp}$.

By Lemma 5.5, the outer terms in Corollary 8.4 are distinct whenever $d>1$. We
next examine when the middle terms reduce to their extreme values. We denote
by $K_{d}$ the complete graph with vertex set $[d]$, in which $i\simeq j$ for
all $i,j\in[d]$. Its complement $\bar{K}_{d}$ is thus the empty graph on
$[d]$, in which $i\simeq j$ precisely when $i=j$.

######  Theorem 8.5.

Let $G$ be a graph on $d$ vertices.

  * (i)

$\mathop{\rm her}(\mathop{\rm vp}(G))=\mathop{\rm ap}(\mathcal{S}_{G})$ if and
only if $G$ is empty;

  * (ii)

$\mathop{\rm ap}(\mathcal{S}_{G})=(\mathop{\rm vp}(G)^{\flat})^{\sharp}$ if
and only if $G$ is complete;

  * (iii)

$\mathop{\rm cp}(\mathcal{S}_{G})=\mathop{\rm fvp}(G)^{\sharp}$ if and only if
$G$ is empty;

  * (iv)

$\mathop{\rm cp}(\mathcal{S}_{G})=\mathop{\rm her}(\mathop{\rm vp}(\bar{G}))$
if and only if $G$ is complete;

  * (v)

$\mathop{\rm fp}(\mathcal{S}_{G})=\mathop{\rm her}(\mathop{\rm vp}(\bar{G}))$
for every graph $G$.

###### Proof.

(i) By (40), $\mathop{\rm
ap}\left(\mathcal{S}_{\bar{K}_{d}}\right)=\mathcal{B}_{I_{d}},$ and as
$I_{d}\in\mathop{\rm vp}\left(\bar{K_{d}}\right)$ we have $\mathop{\rm
vp}\left(\bar{K}_{d}\right)=\left\\{M\in M_{d}^{+}\cap\mathcal{D}_{d}:M\leq
I_{d}\right\\}$, giving

(37) $\mathop{\rm her}\left(\mathop{\rm
vp}\left(\bar{K}_{d}\right)\right)=\mathcal{B}_{I_{d}}.$

Conversely, suppose that $G$ is non-empty with $i\sim j$ in $G$. Let
$v=\frac{1}{\sqrt{2}}(e_{i}+e_{j})$; we have that $vv^{*}\in\mathop{\rm
ap}(\mathcal{S}_{G})$. Suppose that $vv^{*}\leq Q\in\mathop{\rm vp}(G)$. Write
$Q=(q_{i,j})_{i,j=1}^{d}=\sum_{k=1}^{m}\mu_{k}P_{k}$, where $P_{k}=\sum_{i\in
S_{k}}e_{i}e_{i}^{*}$ for an independent set $S_{k}$ of $G$ and scalars
$\mu_{k}>0$, $k\in[m]$, with $\sum_{k}\mu_{k}=1$. Then $q_{i,i}\geq 1/2$ and
$q_{j,j}\geq 1/2$. Since no independent set $S_{k}$ contains both $i$ and $j$,
we have $q_{i,i}=q_{j,j}=1/2$. Thus
$\langle(Q-vv^{*})e_{i},e_{i}\rangle=\langle(Q-vv^{*})e_{j},e_{j}\rangle=0$.
By Lemma 3.8 and the fact that $Q$ is diagonal,

$0=\langle(Q-vv^{*})e_{i},e_{j}\rangle=-\langle(vv^{*})e_{i},e_{j}\rangle=-1/2,$

a contradiction. It follows that $vv^{*}\notin\mathop{\rm her}(\mathop{\rm
vp}(G))$ and hence $\mathop{\rm her}(\mathop{\rm vp}(G))\neq\mathop{\rm
ap}(\mathcal{S}_{G})$.

(ii) We have $\mathcal{S}_{K_{d}}=M_{d}$ and so the
$\mathcal{S}_{K_{d}}$-abelian projections are precisely the rank one
projections; thus, $\mathop{\rm ap}(\mathcal{S}_{K_{d}})=\mathcal{A}_{I_{d}}$.
It is clear that $\mathop{\rm
vp}(K_{d})=\\{M\in\mathcal{D}_{d}^{+}:\mathop{\rm Tr}M\leq 1\\}$; by Lemma
5.5,

(38) $\left(\mathop{\rm vp}(K_{d})^{\flat}\right)^{\sharp}=\left\\{M\in
M_{d}^{+}:\Delta(M)\in\mathop{\rm vp}(K_{d})\right\\}=\mathcal{A}_{I_{d}}.$

Conversely, suppose that $k\not\simeq l$ in $G$. Let
$A=(e_{k}+e_{l})(e_{k}+e_{l})^{*}$ and note that $I-A\not\geq 0$. Since
$\mathop{\rm ap}(\mathcal{S}_{G})\subseteq\mathcal{B}_{I_{d}}$, it follows
that $A\notin\mathop{\rm ap}(\mathcal{S}_{G})$. However,
$\Delta(A)=e_{k}e_{k}^{*}+e_{l}e_{l}^{*}\in\mathop{\rm vp}(G)$. By Lemma 5.5,
$A\in(\mathop{\rm vp}(G)^{\flat})^{\sharp}$ and hence $\mathop{\rm
ap}(\mathcal{S}_{G})\neq(\mathop{\rm vp}(G)^{\flat})^{\sharp}$.

(iii) We claim that $\mathop{\rm cp}(\mathcal{S}_{\bar{K}_{d}})=\\{M\in
M_{d}^{+}:\mathop{\rm Tr}M\leq 1\\}.$ To see this note that a projection $P$
lies in $\mathop{\rm cp}(\mathcal{S}_{\bar{K}_{d}})$ if and only if
$\mathop{\rm rank}(P)=1$. To establish the latter assertion, suppose there
exist orthogonal unit vectors $u=(u_{i})_{i=1}^{d}$ and $v=(v_{i})_{i=1}^{d}$
such that $uv^{*}\in\mathcal{S}_{\bar{K}_{d}}=\mathcal{D}_{d}$. Suppose
$u_{i}\neq 0$; then $v_{j}\neq 0$ for some $j\neq i$. Thus $\left\langle
e_{j}e_{i}^{*},uv^{*}\right\rangle\neq 0$, contradicting the fact that
$uv^{*}\in\mathcal{D}_{d}$. By (38), $\mathop{\rm
cp}(\mathcal{S}_{\bar{K}_{d}})=(\mathop{\rm vp}({K_{d}})^{\flat})^{\sharp}$.
Suppose that $k\sim l$ in $G$. As in (ii), let
$A=(e_{k}+e_{l})(e_{k}+e_{l})^{*}$; by Lemma 5.5, $A\in(\mathop{\rm
vp}(\bar{G})^{\flat})^{\sharp}$. On the other hand, since $A\not\leq I$, we
have that $A\notin\mathop{\rm cp}(\mathcal{S}_{G})$.

(iv) By (37) and (40) below, $\mathop{\rm cp}(\mathcal{S}_{K_{d}})=\mathop{\rm
her}(\mathop{\rm vp}(\bar{K}_{d})).$ Suppose that $i\not\simeq j$ and let
$v=\frac{1}{\sqrt{2}}(e_{i}+e_{j})$. Using the argument from (i), we conclude
that $vv^{*}\notin\mathop{\rm her}(\mathop{\rm vp}(\bar{G}))$.

(v) By Corollary 8.4, $\mathop{\rm her}(\mathop{\rm
vp}(\bar{G}))\subseteq\mathop{\rm fp}(\mathcal{S}_{G})$; we show the reverse
inclusion. Let $\\{v_{1},\ldots,v_{r}\\}$ be an $\mathcal{S}_{G}$-full set and
$P=\sum_{i=1}^{r}v_{i}v_{i}^{*}$. Set
$v_{i}=\sum_{j=1}^{d}\lambda_{j}^{(i)}e_{j}$ with
$\lambda_{j}^{(i)}\in\mathbb{C}$, $j\in[d]$, $i\in[r]$. Now
$v_{i}v_{j}^{*}\in\mathcal{S}_{G}$ for all $i,j\in[r]$ and hence, if
$\lambda_{l}^{(i)}\lambda_{k}^{(j)}\neq 0$ for some $i,j\in[r]$ then $l\simeq
k$ in $G$. We conclude that the set $K=\left\\{j\in[d]:\lambda_{j}^{(k)}\neq
0\mbox{ for some }k\right\\}$ is a clique of $G$. Thus, $Q:=\sum_{j\in
K}e_{j}e_{j}^{*}\in\mathop{\rm vp}(\bar{G})$. Note that
$v_{1},\ldots,v_{r}\in\mathop{\rm span}\\{e_{j}:j\in K\\}$; thus,

$\mathop{\rm ran}(P)=\mathop{\rm
span}\left\\{v_{i}:i\in[r]\right\\}\subseteq\mathop{\rm
span}\left\\{e_{j}:j\in S_{Q}\right\\}=\mathop{\rm ran}(Q).$

Hence $P\leq Q$ and so $P\in\mathop{\rm her}(\mathop{\rm vp}(\bar{G}))$. Since
$\mathop{\rm her}\left(\mathop{\rm vp}(\bar{G})\right)$ is closed and convex,
Proposition 3.14 implies that $\mathop{\rm
fp}(\mathcal{S}_{G})\subseteq\mathop{\rm her}\left(\mathop{\rm
vp}(\bar{G})\right)$, as required. ∎

######  Remark 8.6.

Recall that a graph $G$ is called perfect if every induced subgraph has equal
clique and chromatic numbers. It is shown in [7] that a graph $G$ is perfect
if and only if $\mathop{\rm vp}(G)=\mathop{\rm fvp}(G)$. By Proposition 8.3,
$\mathop{\rm vp}(G)=\mathcal{D}_{d}\cap\mathop{\rm ap}(\mathcal{S}_{G})$ and
$\mathop{\rm vp}(\bar{G})=\mathcal{D}_{d}\cap\mathop{\rm
fp}(\mathcal{S}_{G})=\Delta(\mathop{\rm fp}(\mathcal{S}_{G}))$, whence
Propositions 5.4 and 8.3 give

$\mathop{\rm fvp}(G)=\mathop{\rm
vp}(\bar{G})^{\flat}=\mathcal{D}_{d}\cap(\mathop{\rm
fp}(\mathcal{S}_{G})^{\sharp}).$

Thus, $G$ is perfect if and only if $\mathcal{D}_{d}\cap\mathop{\rm
ap}(\mathcal{S}_{G})=\mathcal{D}_{d}\cap\mathop{\rm
fp}(\mathcal{S}_{G})^{\sharp}$. It is worthwhile to note that the latter
condition is not equivalent to $\mathop{\rm ap}(\mathcal{S}_{G})=\mathop{\rm
fp}(\mathcal{S}_{G})^{\sharp}$; in fact, $\mathop{\rm
ap}(\mathcal{S}_{G})=\mathop{\rm fp}(\mathcal{S}_{G})^{\sharp}$ if and only if
$G$ is complete. To see this, note first that, by Proposition 8.3, if
$\mathop{\rm vp}(G)\neq\mathop{\rm fvp}(G)$ then $\mathop{\rm
ap}(\mathcal{S}_{G})\neq\mathop{\rm fp}(\mathcal{S}_{G})^{\sharp}$. Combined
with Theorem 8.5, this means that if $G$ is perfect then $\mathop{\rm
fp}(\mathcal{S}_{G})=\mathop{\rm her}(\mathop{\rm vp}(G)^{\flat})$ and
$\mathop{\rm fp}(\mathcal{S}_{G})^{\sharp}=\mathop{\rm her}(\mathop{\rm
vp}(G)^{\flat})^{\sharp}$. However, by Theorem 8.5, $\mathop{\rm
ap}(\mathcal{S}_{G})=(\mathop{\rm vp}(G)^{\flat})^{\sharp}=\mathop{\rm
her}(\mathop{\rm vp}(G)^{\flat})^{\sharp}$ if and only if $G$ is complete.

Recall [6] that, for any non-commutative graph $\mathcal{S}$, we have

(39) $\mathop{\rm ap}(\mathcal{S})\subseteq\mathop{\rm
cp}(\mathcal{S})^{\sharp}\subseteq\mathop{\rm fp}(\mathcal{S})^{\sharp}.$

Equality in this chain, for graph operator systems, is characterised in the
next proposition.

######  Proposition 8.7.

Let $G$ be a graph on $d$ vertices. The following are equivalent:

  * (i)

$\mathop{\rm ap}(\mathcal{S}_{\bar{G}})=\mathop{\rm
cp}(\mathcal{S}_{G})=\mathop{\rm fp}(\mathcal{S}_{G})$;

  * (ii)

$G=K_{d}$;

  * (iii)

$\mathop{\rm ap}(\mathcal{S}_{G})=\mathop{\rm
cp}(\mathcal{S}_{G})^{\sharp}=\mathop{\rm fp}(\mathcal{S}_{G})^{\sharp}$.

###### Proof.

(ii)$\Rightarrow$(i) It is clear that $\\{e_{1},\ldots,e_{d}\\}$ is an
$\mathcal{S}_{\bar{K_{d}}}$-independent set, an $\mathcal{S}_{K_{d}}$-clique
and an $\mathcal{S}_{K_{d}}$-full set. Thus
$I_{d}=\sum_{i=1}^{d}e_{i}e_{i}^{*}$ is an $\mathcal{S}_{\bar{K_{d}}}$-abelian
projection, an $\mathcal{S}_{K_{d}}$-clique projection and an
$\mathcal{S}_{K_{d}}$-full projection, and hence

(40) $\mathop{\rm ap}(\mathcal{S}_{\bar{K}_{d}})=\mathop{\rm
cp}(\mathcal{S}_{K_{d}})=\mathop{\rm
fp}(\mathcal{S}_{K_{d}})=\mathcal{B}_{I_{d}}.$

(i)$\Rightarrow$(ii) Suppose that $G\neq K_{d}$ and let $i,j\in[d]$ such that
$i\not\simeq j$. Let $v=\frac{1}{\sqrt{2}}(e_{i}+e_{j})$; then
$vv^{*}\in\mathop{\rm ap}(\mathcal{S}_{\bar{G}})$ and $vv^{*}\in\mathop{\rm
cp}(\mathcal{S}_{G})$.

Consider an $\mathcal{S}_{G}$-full set $\\{v_{1},\ldots,v_{k}\\}$ with
associated $\mathcal{S}_{G}$-full projection $P$. Write
$v_{l}=\sum_{r=1}^{d}\alpha_{r}^{(l)}e_{r}$, $l\in[k]$. Now
$v_{l}v_{m}^{*}=\sum_{r,s=1}^{d}\alpha_{r}^{(l)}\overline{\alpha}_{s}^{(m)}e_{r}e_{s}^{*}\in\mathcal{S}_{G}$
for all $l,m\in[k]$. Thus for all $l,m\in[k]$ we have
$\alpha_{i}^{(l)}\overline{\alpha}_{j}^{(m)}=0$, so either
$\alpha_{i}^{(l)}=0$ for all $l\in[k]$, or $\alpha_{j}^{(m)}=0$ for all
$m\in[k]$. Thus, $\left\langle
P,e_{i}e_{j}^{*}\right\rangle=\sum_{l,m\in[k]}\alpha_{i}^{(l)}\overline{\alpha}_{j}^{(m)}=0$.
It follows that $\left\langle A,e_{i}e_{j}^{*}\right\rangle=0$ for all
$A\in\overline{\mathop{\rm conv}}(\mathcal{P}_{\rm f}(\mathcal{S}_{G}))$. On
the other hand, by (39) and Theorem 4.5, $A\in\mathop{\rm
ap}(\mathcal{S}_{G})^{\sharp}$, and hence $\left\langle
e_{i},Ae_{i}\right\rangle+\left\langle e_{j},Ae_{j}\right\rangle\leq 1$,
whenever $A\in\overline{\mathop{\rm conv}}(\mathcal{P}_{\rm
f}(\mathcal{S}_{G}))$. Since $\frac{1}{2}\begin{pmatrix}1&1\\\
1&1\end{pmatrix}\not\leq\frac{1}{2}\begin{pmatrix}1&0\\\ 0&1\end{pmatrix}$, we
have that $vv^{*}\not\leq A$ for all $A\in\overline{\mathop{\rm
conv}}(\mathcal{P}_{\rm f}(\mathcal{S}_{G}))$, and we conclude
$vv^{*}\notin\mathop{\rm fp}(\mathcal{S}_{G}).$

(ii)$\Leftrightarrow$(iii) is immediate from (39) and Remark 8.6. ∎

We now turn to the theta corners of classical and non-commutative graphs. Let
$G$ be a graph with vertex set $[d]$. A family $(a_{i})_{i\in[d]}$ of unit
vectors in a finite dimensional complex Hilbert space is called an _orthogonal
labelling (o.l.)_ of $G$ if

$i\not\simeq j\ \Rightarrow\ a_{i}\perp a_{j}.$

Let

$\mathcal{P}_{0}(G)=\left\\{\left(|\langle
a_{i},c\rangle|^{2}\right)_{i=1}^{d}:(a_{i})_{i=1}^{d}\mbox{ is an o.l. of
}G\mbox{ and }\|c\|\leq 1\right\\},$

viewed as a subset of $\mathcal{D}_{d}$, and set $\mathop{\rm
thab}(G)=\mathcal{P}_{0}(G)^{\flat}$. We note that the original definition of
$\mathop{\rm thab}(G)$ was given in real Hilbert spaces, but inspection of the
proofs shows that the results in [13, 17, 23] are true for complex Hilbert
spaces as well.

Let $\mathcal{S}\subseteq M_{d}$ be an operator system. Set [6]

$\mathfrak{C}(\mathcal{S})=\left\\{\Phi:M_{d}\to M_{k}\ :\
k\in\mathbb{N},\Phi\mbox{ is a quantum channel with
}\mathcal{S}_{\Phi}\subseteq\mathcal{S}\right\\}$

and

$\mathop{\rm th}(\mathcal{S})=\left\\{T\in M_{d}^{+}:\Phi(T)\leq I\mbox{ for
every }\Phi\in\mathfrak{C}(\mathcal{S})\right\\}.$

It was shown in [6] that the set $\mathop{\rm th}(\mathcal{S})$ is a convex
$M_{d}$-corner, which we call the _theta corner_ of $\mathcal{S}$. Note that
if $\mathcal{S},\mathcal{T}\subseteq M_{d}$ are operator systems then

(41) $\mathcal{S}\subseteq\mathcal{T}\ \Rightarrow\mathop{\rm
th}(\mathcal{T})\ \subseteq\mathop{\rm th}(\mathcal{S}).$

It was shown in [6] that, if $G$ is a graph then $\mathop{\rm
th}(\mathcal{S}_{G})$ is a non-commutative lift of ${\rm thab}(G)$. By
Proposition 5.4, $\mathop{\rm th}(\mathcal{S}_{G})^{\sharp}$ is a non-
commutative lift of ${\rm thab}(G)^{\flat}$. Thus, Theorem 5.6 has the
following corollary.

######  Corollary 8.8.

Let $G$ be a graph. Then

  * (i)

$\mathop{\rm her}({\rm thab}(G))\subseteq\mathop{\rm
th}(\mathcal{S}_{G})\subseteq({\rm thab}(G)^{\flat})^{\sharp}$, and

  * (ii)

$\mathop{\rm her}({\rm thab}(G)^{\flat})\subseteq\mathop{\rm
th}(\mathcal{S}_{G})^{\sharp}\subseteq{\rm thab}(G)^{\sharp}$.

We examine when we have equalities in the inclusions of Corollary 8.8.

######  Theorem 8.9.

Let $G$ be a graph. The following hold:

  * (i)

$\mathop{\rm th}(\mathcal{S}_{G})=({\rm thab}(G)^{\flat})^{\sharp}$ if and
only if $G$ is complete;

  * (ii)

$\mathop{\rm th}(\mathcal{S}_{G})=\mathop{\rm her}({\rm thab}(G))$ if and only
if $G$ is empty.

###### Proof.

(i) It is easy to see that $\mathop{\rm
th}(\mathcal{S}_{K_{d}})=\mathcal{A}_{I_{d}}$ and ${\rm
thab}(K_{d})=\mathcal{D}_{d}\cap\mathcal{A}_{I_{d}}$. By Lemma 5.5, we hence
have

$\displaystyle({\rm thab}(K_{d})^{\flat})^{\sharp}$ $\displaystyle=$
$\displaystyle\\{M\in M_{d}^{+}:\Delta(M)\in{\rm thab}(K_{d})\\}$
$\displaystyle=$ $\displaystyle\\{M\in M_{d}^{+}:\mathop{\rm Tr}M\leq
1\\}=\mathop{\rm th}(\mathcal{S}_{K_{d}}).$

Conversely, suppose that $G$ is not complete, and let $k\not\simeq l$. Let
$A=(e_{k}+e_{l})(e_{k}+e_{l})^{*}$. Then $I-A\not\geq 0$ and, since
$\mathop{\rm th}(\mathcal{S}_{G})\subseteq\mathcal{B}_{I_{d}}$, we have that
$A\notin\mathop{\rm th}(\mathcal{S}_{G})$. It is straightforward that
$A\in(\mathop{\rm vp}(G)^{\flat})^{\sharp}$. Since $\mathop{\rm
vp}(G)\subseteq{\rm thab}(G)$, we have $\mathop{\rm
vp}(G)^{\flat}\supseteq{\rm thab}(G)^{\flat}$, and $(\mathop{\rm
vp}(G)^{\flat})^{\sharp}\subseteq({\rm thab}(G)^{\flat})^{\sharp}$. Thus
$A\in({\rm thab}(G)^{\flat})^{\sharp}$ and so $\mathop{\rm
th}(\mathcal{S}_{G})\neq({\rm thab}(G)^{\flat})^{\sharp}$.

(ii) It is easy to see that

$\mathop{\rm her}({\rm thab}(\bar{K}_{d}))=\mathcal{B}_{I_{d}}=\mathop{\rm
th}(\mathcal{S}_{\bar{K}_{d}}).$

Conversely, assume that $i\sim j$ in $G$. Setting
$v=\frac{1}{\sqrt{2}}(e_{i}+e_{j})$ we have $\mathop{\rm Tr}(vv^{*})=1$ and
$vv^{*}\in\mathop{\rm th}(\mathcal{S}_{G})$. Choosing an o.l.
$(a^{(i)})_{i\in[d]}$ with $a^{(i)}=a^{(j)}$ and $\left\langle
a^{(i)},a^{(l)}\right\rangle=0$ when $l\notin\\{i,j\\}$ and letting
$c=a^{(i)}$ gives $e_{i}e_{i}^{*}+e_{j}e_{j}^{*}\in\mathcal{P}_{0}(G).$
Suppose that $vv^{*}\in\mathop{\rm her}(\mathop{\rm th}(G))$, that is
$vv^{*}\leq Q$ for some $Q\in{\rm thab}(G)\subseteq\mathcal{D}_{d}$. This
requires $\left\langle e_{i},Qe_{i}\right\rangle>\frac{1}{2}$ and
$\left\langle e_{j},Qe_{j}\right\rangle>\frac{1}{2}$. (Indeed, note that,
since $Q\in\mathcal{D}_{d}$, we have that $\left\langle
e_{i},(Q-vv^{*})e_{j}\right\rangle=-\frac{1}{2}.$ But if $\left\langle
e_{i},Qe_{i}\right\rangle=\frac{1}{2}$, we have $e_{i}^{*}(Q-vv^{*})e_{i}=0$,
and since $Q\geq vv^{*}$, Lemma 3.8 implies that $\left\langle
e_{i},(Q-vv^{*})e_{j}\right\rangle=0$. A similar argument applies for $j$.)
Thus, $\left\langle Q,e_{i}e_{i}^{*}+e_{j}e_{j}^{*}\right\rangle>1$ and so
$Q\not\in\mathcal{P}_{0}(G)^{\flat}={\rm thab}(G)$, a contradiction. We
conclude $vv^{*}\notin\mathop{\rm her}(\mathop{\rm th}(G))$. ∎

##  9\. Non-commutative graph entropy

In this section, we provide a quantum version of the notion of graph entropy,
introduced by J. Körner in [18] and a non-commutative analogue of the
fractional chromatic number of a graph. We examine the continuity properties
of non-commutative graph entropy and show its connection to the fractional
chromatic number, extending to the non-commutative case a classical
optimisation result from [35].

###  9.1. Entropy and fractional chromatic number

Let $G$ be a graph with vertex set $[d]$ and let $p\in\mathcal{P}_{d}$ be a
probability distribution over its vertices. The entropy $H(G,p)$ of $p$ with
respect to $G$ was defined in [18] as the optimal coding rate of the source
$\left([d],p\right)$ in the presence of ambiguity between the symbols from
$[d]$, captured by the adjacency relation of $G$ (two symbols $i,j\in[d]$ are
distinguishable if $i\sim j$ in $G$). The entropy functional $H(G,p)$ is thus
defined as an asymptotic parameter, whose computation requires knowledge of
the limiting behaviour of a sequence of chromatic numbers of powers of $G$. An
elegant closed formula for $H(G,p)$, reminiscent of the definition of the
classical Shannon entropy of $p$, was obtained in [18]:

$H(G,p)=\min\left\\{\sum_{i=1}^{d}p_{i}\log\frac{1}{v_{i}}:v=(v_{i})_{i=1}^{d}\in\mathop{\rm
vp}(G),v>0\right\\}$

or, equivalently,

(42) $H(G,p)=\min_{v\in\mathop{\rm vp}(G)}-\mathop{\rm Tr}(p\log v).$

Let $\mathcal{S}\subseteq M_{d}$ be a non-commutative graph and $\rho$ be a
state in $M_{d}$. Since $\mathop{\rm ap}(\mathcal{S})$ is a quantum version of
$\mathop{\rm vp}(G)$, taking (42) as a starting point in the non-commutative
case, it is natural to make the following definition.

######  Definition 9.1.

The _entropy_ $H(\mathcal{S},\rho)$ of a non-commutative graph
$\mathcal{S}\subseteq M_{d}$ with respect to a state $\rho\in\mathcal{R}_{d}$
is the quantity $H(\mathcal{S},\rho)=H_{\mathop{\rm ap}(\mathcal{S})}(\rho).$

It follows from Theorem 6.7 and Proposition 8.3 that, if $p\in\mathcal{P}_{d}$
and $\rho=\sum_{i=1}^{d}p_{i}e_{i}e_{i}^{*}$ then
$H(G,p)=H(\mathcal{S}_{G},\rho)$. Thus, the parameter introduced in Definition
9.1 can be viewed as a non-commutative version of classical graph entropy.

######  Remark 9.2.

Let $\mathcal{S}$ be a non-commutative graph in $M_{d}$ and
$\rho\in\mathcal{R}_{d}$. It follows from (26) and Remark 8.2 that $0\leq
H(\mathcal{S},\rho)\leq H(\rho).$ It is clear that

$\mathcal{S}_{1}\subseteq\mathcal{S}_{2}\ \Longrightarrow\
H(\mathcal{S}_{1},\rho)\leq H(\mathcal{S}_{2},\rho).$

Let $G$ be a graph with vertex set $[d]$ and $\mathcal{S}\subseteq M_{d}$ be a
non-commutative graph. Recall that the chromatic number $\chi(G)$ of $G$ is
given by

$\chi(G)=\min\left\\{k\in\mathbb{N}:\ \exists\mbox{ indep. sets
}S_{1},\dots,S_{k}\mbox{ s.t. }\cup_{i=1}^{k}S_{i}=[d]\right\\}.$

Taking into account that the $\mathcal{S}$-abelian projections are the quantum
analogue of independent sets, the following definition of a chromatic number
of $\mathcal{S}$, given in [28], becomes natural:

$\chi(\mathcal{S})=\min\left\\{k\in\mathbb{N}:\
P_{1},\dots,P_{k}\in\mathcal{P}_{\rm a}(\mathcal{S}),\
\sum_{i=1}^{k}P_{i}=I\right\\}.$

It was shown in [28] that, if $G$ is a graph then
$\chi(\mathcal{S}_{G})=\chi(G)$. Recalling the definitions made after
Proposition 4.9, we note that

(43) $\Gamma(\mathop{\rm ap}(\mathcal{S}))\leq\chi(\mathcal{S}).$

Similarly, recall that the _fractional chromatic number_ $\chi_{\rm f}(G)$ of
$G$ is defined by letting

(44) $\chi_{\rm f}(G)=\min\left\\{\sum_{S}\lambda_{S}:\lambda_{S}\geq
0,\sum_{S}\lambda_{S}\chi_{S}\geq 1\right\\},$

where the summation is taken over independent sets $S$ of $G$. By a duality
argument, $\chi_{\rm f}(G)$ coincides with the _fractional clique number_
$\omega_{\rm f}(G)$ of $G$, defined by

$\omega_{\rm f}(G)=\max\left\\{\sum_{i=1}^{d}\mu_{i}:\mu_{i}\geq 0,\sum_{i\in
S}\mu_{i}\leq 1\ \forall\mbox{ independent set }S\right\\}.$

In [6], we defined a non-commutative version of the fractional clique number
by letting, for an operator system $\mathcal{S}\subseteq M_{d}$,

$\omega_{\rm f}(\mathcal{S})=\max\left\\{\mathop{\rm Tr}(A):A\in
M_{d}^{+},\mathop{\rm Tr}(AP)\leq 1\mbox{ for all }P\in\mathcal{P}_{\rm
a}(\mathcal{S})\right\\}.$

It is clear that

(45) $\omega_{\rm f}(\mathcal{S})=\gamma(\mathop{\rm
ap}(\mathcal{S})^{\sharp}),$

and it was shown in [6] that $\omega_{\rm f}(\mathcal{S}_{G})=\omega_{\rm
f}(G)$.

With the definition (44) of the fractional chromatic number of a classical
graph in mind, it is natural to define the _fractional chromatic number_ of a
non-commutative graph $\mathcal{S}\subseteq M_{d}$ by setting

(46) $\chi_{\rm
f}(\mathcal{S})=\inf\left\\{\sum_{i=1}^{k}\lambda_{i}:\lambda_{i}>0\mbox{ and
}\exists\ P_{1},\dots,P_{k}\in\mathcal{P}_{\rm a}(\mathcal{S})\mbox{ s.t.
}\sum_{i=1}^{k}\lambda_{i}P_{i}\geq I\right\\}.$

######  Proposition 9.3.

If $\mathcal{S}$ is a non-commutative graph then $\chi_{\rm
f}(\mathcal{S})=\Gamma_{\rm f}(\mathop{\rm ap}(\mathcal{S}))$.

###### Proof.

Since $\mathcal{P}_{\rm a}(\mathcal{S})\subseteq\mathop{\rm ap}(\mathcal{S})$,
we have that $\Gamma_{\rm f}(\mathop{\rm ap}(\mathcal{S}))\leq\chi_{\rm
f}(\mathcal{S})$. By [6, Remark 2.7], the set $\mathcal{P}_{\rm a}$ is closed.
Carathéodory’s Theorem now implies that $\overline{{\rm
conv}}(\mathcal{P}_{\rm a})={\rm conv}(\mathcal{P}_{\rm a})$. Suppose that
$P\in\mathop{\rm ap}(\mathcal{S})$ is a projection. Then
$P\leq\sum_{i=1}^{k}\lambda_{i}P_{i}$ for some $P_{i}\in\mathcal{P}_{\rm a}$,
$\lambda_{i}>0$, $i=1,\dots,k$, with $\sum_{i=1}^{k}\lambda_{i}=1$. If $\xi$
is a unit vector with $\xi=P\xi$ then $1\leq\sum_{i=1}^{k}\lambda_{i}\langle
P_{i}\xi,\xi\rangle\leq 1$, and hence $\langle P_{i}\xi,\xi\rangle=1$ for each
$i\in[k]$. It follows that $P_{i}\xi=\xi$, and hence $P\leq P_{i}$, for each
$i\in[k]$. Thus, if $I\leq\sum_{j=1}^{l}\mu_{j}Q_{j}$ for some positive
scalars $\mu_{j}$ and some projections $Q_{j}\in\mathop{\rm ap}(\mathcal{S})$
then $I\leq\sum_{r=1}^{m}\nu_{r}P_{r}$, for some positive scalars $\nu_{r}$
and some $P_{r}\in\mathcal{P}_{\rm a}$, with
$\sum_{r=1}^{m}\nu_{r}=\sum_{j=1}^{l}\mu_{j}$, completing the proof. ∎

As noted, if $G$ is a classical graph $G$ then $\chi_{\rm f}(G)=\omega_{\rm
f}(G)$. The non-commutative counterpart of this identity also holds, but is
much deeper and replies on the second anti-blocker theorem we proved in
Section 4.

######  Theorem 9.4.

If $\mathcal{S}\subseteq M_{d}$ is a non-commutative graph then $\omega_{\rm
f}(\mathcal{S})=\chi_{\rm f}(\mathcal{S}).$

###### Proof.

By Proposition 9.3 and Theorem 4.11, $\chi_{\rm f}(\mathcal{S})=M(\mathop{\rm
ap}(\mathcal{S}))$. The claim now follows from (45) and Theorem 4.11. ∎

It was shown in [35, Lemma 4] that

$\max_{p\in\mathcal{P}_{n}}H(G,{p})=\log\chi_{\rm f}(G).$

The next theorem, which is a direct consequence of Proposition 9.3 and
Theorems 6.6 and 4.11 establishes a quantum version of this identity.

######  Theorem 9.5.

Let $\mathcal{S}\subseteq M_{d}$ be an operator system. Then

$\max_{\rho\in\mathcal{R}_{d}}H(\mathcal{S},\rho)=\log\chi_{\rm
f}(\mathcal{S}).$

###  9.2. Further properties

In this subsection, we include observations regarding the continuity,
multiplicativity and extreme value properties of the non-commutative graph
entropy.

######  Theorem 9.6.

Let $\mathcal{S}$ and $\mathcal{S}_{n}$ be non-commutative graphs in $M_{d}$,
$n\in\mathbb{N}$, such that
$\mathcal{S}\subseteq\liminf_{n\in\mathbb{N}}\mathcal{S}_{n}$. Then
$H(\mathcal{S},\rho)\leq\liminf_{n\in\mathbb{N}}H(\mathcal{S}_{n},\rho)$ for
every $\rho\in\mathcal{R}_{d}$.

###### Proof.

We first claim that

(47) $\limsup_{n\in\mathbb{N}}\mathop{\rm
ap}(\mathcal{S}_{n})\subseteq\mathop{\rm ap}(\mathcal{S}).$

Suppose that $(P_{k})_{k\in\mathbb{N}}$ is a sequence of projections such that
$P_{k}\in\mathcal{P}_{\rm a}(\mathcal{S}_{n_{k}})$, $k\in\mathbb{N}$, and
$P_{k}\to_{k\to\infty}P$. Let $A,B\in\mathcal{S}$, and
$(A_{n})_{n\in\mathbb{N}}$ and $(B_{n})_{n\in\mathbb{N}}$ be sequences such
that $A_{n},B_{n}\in\mathcal{S}_{n}$, $n\in\mathbb{N}$, and
$A_{n}\to_{n\to\infty}A$ and $B_{n}\to_{n\to\infty}B$. Then

$\displaystyle(PAP)(PBP)$ $\displaystyle=$
$\displaystyle\lim_{k\to\infty}(P_{k}A_{n_{k}}P_{k})(P_{k}B_{n_{k}}P_{k})$
$\displaystyle=$
$\displaystyle\lim_{k\to\infty}(P_{k}B_{n_{k}}P_{k})(P_{k}A_{n_{k}}P_{k})=(PBP)(PAP);$

thus, $P\in\mathcal{P}_{\rm a}(\mathcal{S})$.

Now suppose that $(A_{k})_{k\in\mathbb{N}}$ is a sequence with
$A_{k}\in\mathop{\rm ap}(\mathcal{S}_{n_{k}})$, $k\in\mathbb{N}$, and
$A_{k}\to_{k\to\infty}A$. Let
$B_{k}=\sum_{j=1}^{m_{k}}\mu_{j}^{(k)}P_{j}^{(k)}$ be a convex combination of
$\mathcal{S}_{n_{k}}$-abelian projections $P_{j}^{(k)}$, $j\in[m_{k}]$,
$k\in\mathbb{N}$, such that $A_{k}\leq B_{k}$. By Carathéodory’s Theorem, we
may assume that $m_{k}=2d^{2}+1$ for all $k\in\mathbb{N}$. Passing to
subsequences, we may assume that $P_{j}^{(k)}\to_{k\to\infty}P_{j}$ and
$\mu_{j}^{(k)}\to_{k\to\infty}\mu_{j}$, $j\in[2d^{2}+1]$. By the previous
paragraph,

$B:=\sum_{j=1}^{2d^{2}+1}\mu_{j}P_{j}\in\mathop{\rm ap}(\mathcal{S}).$

Since $A\leq B$, we conclude that $A\in\mathop{\rm ap}(\mathcal{S})$, and (47)
is proved. The claim now follows from Theorem 6.12. ∎

Let $G$ be a graph with vertex set $[d]$. We note that $H(G,p)=0$ if and only
if there exists $v=(v_{i})_{i=1}^{d}\in\mathop{\rm vp}(G)$ such that
$p_{i}>0\Rightarrow v_{i}=1$. This is equivalent to the condition that
$\\{i\in[d]:p_{i}>0\\}$ is an independent set of $G$. Note that $H(G,p)=0$ for
all $p\in\mathcal{P}_{d}$ if and only if $G=\bar{K}_{d}$. We now address the
analogous questions in the non-commutative setting.

######  Proposition 9.7.

Let $\mathcal{S}\subseteq M_{d}$ be an operator system.

  * (i)

Suppose that $\rho\in\mathcal{R}_{d}$. We have that $H(\mathcal{S},\rho)=0$ if
and only if there exists an orthonormal basis $\\{v_{1},\ldots,v_{d}\\}$ of
$\mathbb{C}^{d}$ such that, if $T=\\{i\in[d]:\left\langle\rho
v_{i},v_{i}\right\rangle>0\\}$ then $\sum_{i\in T}v_{i}v_{i}^{*}\in\mathop{\rm
ap}({\mathcal{S}})$.

  * (ii)

$H(\mathcal{S},\rho)=0$ for all $\rho\in\mathcal{R}_{d}$ if and only if there
exists an orthonormal basis $V$ of $\mathbb{C}^{d}$ such that
$\mathcal{S}\subseteq\mathcal{D}_{V}$.

###### Proof.

(i) Note that $H(\mathcal{S},\rho)=0$ if and only if there exists
$A\in\mathop{\rm ap}(\mathcal{S})$ such that $-\mathop{\rm Tr}(\rho\log A)=0$.
Write $A=\sum_{i=1}^{d}\lambda_{i}v_{i}v_{i}^{*}$ for some orthonormal basis
$\\{v_{1},\ldots,v_{d}\\}$ and $\lambda_{i}\in\mathbb{R}_{+}$, $i\in[d]$. We
have $\sum_{i=1}^{d}\left\langle\rho
v_{i},v_{i}\right\rangle\log\lambda_{i}=0$, and hence $\lambda_{i}=1$ whenever
$\left\langle\rho v_{i},v_{i}\right\rangle>0$. It follows that $P:=\sum_{i\in
T}v_{i}v_{i}^{*}\leq A$ and so $P\in\mathop{\rm ap}(\mathcal{S})$. Conversely,
if $P\in\mathop{\rm ap}(\mathcal{S})$ then $\mathop{\rm Tr}(\rho\log P)=0$ and
hence $H(\mathcal{S},\rho)=0$.

(ii) Choose $\rho>0$. By (i), if $H(\mathcal{S},\rho)=0$ then $I\in\mathop{\rm
ap}(\mathcal{S})$. Thus, for some orthonormal basis
$V=\\{v_{1},\ldots,v_{d}\\}$ of $\mathbb{C}^{d}$, we have that
$v_{i}v_{j}^{*}\in\mathcal{S}^{\perp}$ for all $i\neq j$. We conclude that
$\mathcal{S}$ is diagonal in basis $V$. Conversely, if $\mathcal{S}$ is
diagonal in some orthonormal basis then $I$ is an $\mathcal{S}$-abelian
projection, and (i) gives $H(\mathcal{S},\rho)=0$ for all
$\rho\in\mathcal{R}_{d}$. ∎

We next consider the extremal cases for the values of $H(\mathcal{S},\rho)$;
Propositions 9.8 and 9.9 should be compared to Propositions 6.9 and 6.10.

######  Proposition 9.8.

The following are equivalent for a non-commutative graph $\mathcal{S}\subseteq
M_{d}$:

  1. (i)

$\mathcal{S}$ is diagonal in some orthonormal basis;

  2. (ii)

$H(\mathcal{S},\rho)=0$ for all states $\rho\in\mathcal{R}_{d}$;

  3. (iii)

$\chi_{\rm f}(\mathcal{S})=1$;

  4. (iv)

$I\in\mathop{\rm ap}(\mathcal{S})$;

  5. (v)

$\alpha(\mathcal{S})=d$;

  6. (vi)

$\chi(\mathcal{S})=1$.

###### Proof.

(i)$\Leftrightarrow$(ii) is Proposition 9.7.

(ii)$\Leftrightarrow$(iii)$\Leftrightarrow$(iv)$\Leftrightarrow$(v) Apply
Proposition 6.9, recalling that

$H(\mathcal{S},\rho)=H_{\mathop{\rm ap}(\mathcal{S})}(\rho)$

and using that $\alpha(\mathcal{S})=\gamma(\mathop{\rm ap}(\mathcal{S}))$ and
$\chi_{\rm f}(\mathcal{S})=\gamma(\mathop{\rm ap}(\mathcal{S})^{\sharp}).$

(iv)$\Leftrightarrow$(vi) is clear from the definition of $\chi(\mathcal{S})$.
∎

######  Proposition 9.9.

The following are equivalent for non-commutative graph $\mathcal{S}\subseteq
M_{d}$:

  * (i)

$H(\mathcal{S},\rho)=H(\rho)$ for all states $\rho\in\mathcal{R}_{d}$;

  * (ii)

$\chi_{\rm f}(\mathcal{S})=d$;

  * (iii)

$\chi(\mathcal{S})=d$;

  * (iv)

$\mathop{\rm ap}(\mathcal{S})=\mathcal{A}_{I_{d}}$;

  * (v)

$\alpha(\mathcal{S})=1$.

###### Proof.

(iii)$\Rightarrow$(iv) All rank one projections are trivially
$\mathcal{S}$-abelian. Suppose that $P$ is an $\mathcal{S}$-abelian projection
with $\mathop{\rm rank}(P)\geq 2$. Then $I$ can be expressed as the sum of $P$
and at most $(d-2)$ rank one projections, giving $\chi(\mathcal{S})\leq d-1.$

(ii)$\Rightarrow$(iv) From their respective definitions, it is clear that
$\chi_{\rm f}(\mathcal{S})\leq\chi(\mathcal{S})\leq d$.

(i)$\Leftrightarrow$(ii)$\Leftrightarrow$(iv)$\Leftrightarrow$(v) follow from
Proposition 6.10. ∎

######  Remark 9.10.

Clearly, the equivalent conditions of Proposition 9.9 are satisfied if
$\mathcal{S}=M_{d}$. However, there exist proper operator subsystems of
$M_{d}$ for which these conditions are also satisfied, for example, the
operator system $\mathcal{S}_{d}$ considered in Section 12 for $d\geq 1$ (this
follows from Propositions 9.9 and 12.6).

We finish this section with noting the subadditivity of the entropy.

######  Proposition 9.11.

Let $\mathcal{S}_{i}\subseteq M_{d_{i}}$ be a non-commutative graph, $i=1,2$,
and $\rho\in\mathcal{R}_{d_{1}d_{2}}$. Then

$H(\mathcal{S}_{1}\otimes\mathcal{S}_{2},\rho)\leq
H(\mathcal{S}_{1},\mathop{\rm
Tr}\mbox{}_{1}\rho)+H(\mathcal{S}_{2},\mathop{\rm Tr}\mbox{}_{2}\rho).$

###### Proof.

It is clear that, if $P_{i}\in\mathcal{P}_{\rm a}(\mathcal{S}_{i})$, $i=1,2$,
then $P_{1}\otimes P_{2}\in\mathcal{P}_{\rm
a}(\mathcal{S}_{1}\otimes\mathcal{S}_{2})$. Thus,

(48) $\mathop{\rm ap}(\mathcal{S}_{1})\otimes_{\max}\mathop{\rm
ap}(\mathcal{S}_{2})\subseteq\mathop{\rm
ap}(\mathcal{S}_{1}\otimes\mathcal{S}_{2}).$

The statement now follows from Theorem 7.3. ∎

##  10\. Cliques and clique covering number

In this section, we discuss the non-commutative versions of cliques and the
clique covering number, and their entropic meaning, and provide a bound on the
Shannon capacity of a non-commutative graph. Recall that the clique number
$\omega(G)$ of a graph $G$ is defined as the size of a largest clique of $G$.
In the non-commutative case, clique and full projections both constitute a
legitimate quantum version of a clique, and so we have two versions of
$\omega(G)$ for an operator system $\mathcal{S}\subseteq M_{d}$ [6, Corollary
3.9]: the _clique number_

$\omega(\mathcal{S})=\max\left\\{\mathop{\rm rank}P:P\mbox{ is an
}\mathcal{S}\mbox{-clique projection}\right\\}$

of $\mathcal{S}$, and the _full number_

$\tilde{\omega}(\mathcal{S})=\max\left\\{\mathop{\rm rank}P:P\mbox{ is an
}\mathcal{S}\mbox{-full projection}\right\\}$

of $\mathcal{S}$. Note that

(49) $\omega(\mathcal{S})=\gamma\left(\mathop{\rm cp}(\mathcal{S})\right)\
\mbox{ and }\ \tilde{\omega}(\mathcal{S})=\gamma\left(\mathop{\rm
fp}(\mathcal{S})\right).$

The clique covering number of $G$, on the other hand, is the minimum number of
cliques of $G$ whose union is equal to the vertex set of $G$. It is clear that
the latter parameter coincides with the chromatic number $\chi(\bar{G})$ of
the complement $\bar{G}$ of $G$, which is often denoted by $\bar{\chi}(G)$. We
thus have the following natural non-commutative analogues of $\bar{\chi}(G)$
and its fractional versions:

######  Definition 10.1.

Let $\mathcal{S}\subseteq M_{d}$ be an operator system. We define

  * (i)

the _clique covering number_ of $\mathcal{S}$ by

$\Omega(\mathcal{S})=\min\left\\{k\in\mathbb{N}:\
P_{1},\dots,P_{k}\in\mathcal{P}_{\rm c}(\mathcal{S}),\
\sum_{i=1}^{k}P_{i}=I\right\\};$

  * (ii)

the _full covering number_ of $\mathcal{S}$ by

$\tilde{\Omega}(\mathcal{S})=\min\left\\{k\in\mathbb{N}:\
P_{1},\dots,P_{k}\in\mathcal{P}_{\rm f}(\mathcal{S}),\
\sum_{i=1}^{k}P_{i}=I\right\\}.$

If the condition on the right hand side of the last equation cannot be
satisfied, we set $\tilde{\Omega}(\mathcal{S})=\infty$;

  * (iii)

the _fractional clique covering number_ of $\mathcal{S}$ by

$\Omega_{\rm
f}(\mathcal{S})=\inf\left\\{\sum_{i=1}^{k}\lambda_{i}:k\in\mathbb{N},\
\lambda_{i}>0,\ P_{1},\dots,P_{k}\in\mathcal{P}_{\rm c}(\mathcal{S}),\
\sum_{i=1}^{k}\lambda_{i}P_{i}\geq I\right\\};$

  * (iv)

The _fractional full covering number_ of $\mathcal{S}$ by

$\tilde{\Omega}_{\rm
f}(\mathcal{S})=\inf\left\\{\sum_{i=1}^{k}\lambda_{i}:k\in\mathbb{N},\
\lambda_{i}>0,\ P_{1},\dots,P_{k}\in\mathcal{P}_{\rm f}(\mathcal{S}),\
\sum_{i=1}^{k}\lambda_{i}P_{i}\geq I\right\\}.$

If the condition on the right hand side of the last equation cannot be
satisfied, we set $\tilde{\Omega}_{\rm f}(\mathcal{S})=\infty$.

Similarly to Proposition 9.3, one can show that

(50) $\Omega_{\rm f}(\mathcal{S})=\Gamma_{\rm f}(\mathop{\rm
cp}(\mathcal{S}))\mbox{ and }\ \tilde{\Omega}_{\rm f}(\mathcal{S})=\Gamma_{\rm
f}(\mathop{\rm fp}(\mathcal{S})).$

It now follows from Theorem 4.11 that $\Omega_{\rm f}(\mathcal{S})$ (resp.
$\tilde{\Omega}_{\rm f}(\mathcal{S})$) coincides with the complementary
fractional clique number (resp. the complementary fractional full number)
defined in [6] and denoted therein by $\kappa(\mathcal{S})$ (resp.
$\varphi(\mathcal{S})$).

We collect the main properties of these parameters in the next theorem.

######  Theorem 10.2.

Let $G$ be a graph with vertex set $[d]$, and $\mathcal{S}$ and $\mathcal{T}$
be non-commutative graphs in $M_{d}$ with $\mathcal{S}\subseteq\mathcal{T}$.
The following hold:

  * (i)

$0\leq\tilde{\omega}(\mathcal{S})\leq\omega(\mathcal{S})\leq\omega_{\rm
f}(\mathcal{S})\leq\chi(\mathcal{S})\leq d$.

  * (ii)

$1\leq\Omega_{\rm{f}}(\mathcal{S})\leq\Omega(\mathcal{S})\leq d$ and
$1\leq\tilde{\Omega}_{\rm{f}}(\mathcal{S})\leq\tilde{\Omega}(\mathcal{S})\leq+\infty$;

  * (iii)

$\Omega(\mathcal{S})\leq\tilde{\Omega}(\mathcal{S})$ and
$\alpha(\mathcal{S})\leq\Omega_{\rm f}(\mathcal{S})\leq\tilde{\Omega}_{\rm
f}(\mathcal{S})$;

  * (iv)

$\Omega(\mathcal{S})=1$ $\Leftrightarrow$ $\omega(\mathcal{S})=d$;

  * (v)

$\tilde{\Omega}_{\rm f}(\mathcal{S})=1$ $\Leftrightarrow$
$\tilde{\Omega}(\mathcal{S})=1$ $\Leftrightarrow$
$\tilde{\omega}(\mathcal{S})=d$ $\Leftrightarrow$ $\mathcal{S}=M_{d}$;

  * (vi)

If $\tilde{\omega}(\mathcal{S})=0$ then $\tilde{\Omega}_{\rm
f}(\mathcal{S})=\infty$;

  * (vii)

$\tilde{\Omega}_{\rm f}(\mathcal{S})=\infty$ $\Leftrightarrow$ $\mathop{\rm
fp}(\mathcal{S})^{\sharp}$ is unbounded $\Leftrightarrow$ $\mathop{\rm
fp}(\mathcal{S})$ has empty relative interior;

  * (viii)

$\chi_{\rm f}(\mathcal{S}_{G})=\chi_{\rm f}(G)$;

  * (ix)

$\tilde{\Omega}_{\rm f}(\mathcal{S}_{G})=\Omega_{\rm
f}(\mathcal{S}_{G})=\chi_{\rm f}(\bar{G})$;

  * (x)

$\tilde{\Omega}(\mathcal{S}_{G})=\Omega(\mathcal{S}_{G})=\chi(\bar{G})$;

  * (xi)

If $\zeta\in\\{\Omega_{\rm f},\tilde{\Omega}_{\rm
f},\Omega,\tilde{\Omega}\\}$, then $\zeta(\mathcal{S})\geq\zeta(\mathcal{T})$;

  * (xii)

If $\zeta\in\\{\omega,\tilde{\omega},\omega_{\rm f},\chi\\}$, then
$\zeta(\mathcal{S})\leq\zeta(\mathcal{T})$;

  * (xiii)

$\alpha(\mathcal{S})\chi(\mathcal{S})\geq d$,
$\omega(\mathcal{S})\Omega(\mathcal{S})\geq d$ and, if
$\tilde{\omega}(\mathcal{S})\geq 1$ then
$\tilde{\omega}(\mathcal{S})\tilde{\Omega}(\mathcal{S})\geq d$.

###### Proof.

(i) Theorem 4.5 and (39) give $\mathop{\rm
fp}(\mathcal{S})\subseteq\mathop{\rm cp}(\mathcal{S})\subseteq\mathop{\rm
ap}(\mathcal{S})^{\sharp}\subseteq\mathcal{B}_{I_{d}}$. The assertion follows
from (49) and Theorem 9.4.

(ii) Using (50) and Remark 4.10, we have

$\Omega_{\rm f}(\mathcal{S})=\Gamma_{\rm f}({\rm
cp}(\mathcal{S}))\leq\Gamma({\rm cp}(\mathcal{S}))\leq\Omega(\mathcal{S}).$

The rest of the statements follow from Theorem 4.11 and the fact that
$\mathcal{A}_{I_{d}}\subseteq\mathop{\rm
cp}(\mathcal{S})\subseteq\mathcal{B}_{I_{d}}$ and $\mathop{\rm
fp}(\mathcal{S})\subseteq\mathcal{B}_{I_{d}}$.

(iii) Using (39), (50) and Theorem 4.11, we have

$M({\rm fp}(\mathcal{S}))\geq M({\rm cp}(\mathcal{S}))=\Omega_{\rm
f}(\mathcal{S})\geq M({\rm ap}(\mathcal{S})^{\sharp})=\gamma({\rm
ap}(\mathcal{S}))=\alpha(\mathcal{S}).$

(iv) follows from the fact that $\Omega(\mathcal{S})=1$ if and only if
$I\in\mathcal{P}_{\rm c}(\mathcal{S})$, if and only if
$\omega(\mathcal{S})=d$.

(v) Since $\mathop{\rm fp}(\mathcal{S})\subseteq\mathcal{B}_{I_{d}}$, we have
that $\mathcal{A}_{I_{d}}\subseteq\mathop{\rm fp}(\mathcal{S})^{\sharp}.$
Thus, if $\tilde{\Omega}_{\rm f}(\mathcal{S})=1$ then $\mathop{\rm
fp}(\mathcal{S})^{\sharp}=\mathcal{A}_{I_{d}}$, yielding $\mathop{\rm
fp}(\mathcal{S})=\mathcal{B}_{I_{d}}$ and $\tilde{\omega}(\mathcal{S})=d$. It
follows that $I\in\mathop{\rm fp}(\mathcal{S})$ and so $I$ is an
$\mathcal{S}$-full projection, implying $\mathcal{S}=M_{d}.$ The proof is
completed by noting that if $\mathcal{S}=M_{d}$, then $\mathop{\rm
fp}(\mathcal{S})=\mathcal{B}_{I_{d}}$ and $\tilde{\Omega}_{\rm
f}(\mathcal{S})=\gamma(\mathop{\rm
fp}(\mathcal{S})^{\sharp})=\gamma(\mathcal{A}_{I_{d}})=1.$

(vi) The condition $\tilde{\omega}(\mathcal{S})=0$ holds if and only if
$\mathop{\rm fp}(\mathcal{S})=\\{0\\}$ or, equivalently, $\mathop{\rm
fp}(\mathcal{S})^{\sharp}=M_{d}^{+}$, which yields $\tilde{\Omega}_{\rm
f}(\mathcal{S})=\infty.$

(vii) The second equivalence is immediate from Proposition 3.12. On the other
hand, if $\tilde{\Omega}_{\rm f}(\mathcal{S})<\infty$ then there exist
$\mathcal{S}$-full projections $P_{1},\dots,P_{k}$ such that
$\sum_{i=1}^{k}\lambda_{i}P_{i}\geq I$ for some positive scalars
$\lambda_{1},\dots,\lambda_{k}$. It follows by hereditarity that
$\frac{1}{\sum_{i=1}^{k}\lambda_{i}}I\in\mathop{\rm fp}(\mathcal{S})$, and
hence $\mathop{\rm fp}(\mathcal{S})$ has non-empty relative interior by Lemma
3.10. Conversely, if $\mathop{\rm fp}(\mathcal{S})$ has non-empty relative
interior then, by Lemma 3.10, $rI\in\mathop{\rm fp}(\mathcal{S})$ for some
$r>0$. Thus, there exist $P_{i}\in\mathcal{P}_{\rm f}(\mathcal{S})$ and
$\lambda_{i}\geq 0$, $i\in[k]$, such that $\sum_{i=1}^{k}\lambda_{i}=1$ and
$rI\leq\sum_{i=1}^{k}\lambda_{i}P_{i}$. This implies that $\tilde{\Omega}_{\rm
f}(\mathcal{S})\leq\frac{1}{r}$.

(viii) follows from Theorem 9.4 and the fact that $\omega_{\rm
f}(\mathcal{S}_{G})=\omega_{\rm f}(G)$ [6, Corollary 3.9].

(ix) follows from [6, Corollary 3.9].

(x) If $\\{i_{1},\ldots,i_{k}\\}$ is a clique in $G$, then
$\\{e_{i_{1}},\ldots,e_{i_{k}}\\}$ is an $\mathcal{S}_{G}$-full set and hence
$P=\sum_{j=1}^{k}e_{i_{j}}e_{i_{j}}^{*}$ is an $\mathcal{S}_{G}$-full, and
thus an $\mathcal{S}_{G}$-clique, projection. Thus,
$\Omega(\mathcal{S}_{G})\leq\tilde{\Omega}(\mathcal{S}_{G})\leq\chi(\bar{G})$.

Let $G$ be a graph on $d$ vertices and let $\\{v_{1},\ldots,v_{d}\\}$ be an
orthonormal basis of $\mathbb{C}^{d}$. A standard combinatorial result (see
[28, Lemma 7.28] and [16, Lemma 13]) shows that there exists a permutation
$\sigma$ on $[d]$ such that $\left\langle e_{\sigma(i)},v_{i}\right\rangle\neq
0$ for all $i\in[d]$ and so, for $j,k\in[d]$, we have that

(51) $\left\langle
v_{j}v_{k}^{*},e_{\sigma(j)}e_{\sigma(k)}^{*}\right\rangle=\left\langle
e_{\sigma(k)},v_{k}\right\rangle\left\langle
v_{j},e_{\sigma(j)}\right\rangle\neq 0.$

Let $P=\sum_{i=1}^{k}v_{i}v_{i}^{*}$. If $P$ is an $\mathcal{S}_{G}$-clique,
then $v_{p}v_{q}^{*}\in\mathcal{S}_{G}$ for distinct $p,q\in[k]$ and, by (51),
$e_{\sigma(p)}e_{\sigma(q)}^{*}\notin\mathcal{S}_{G}^{\perp}$. Thus,
$\sigma(p)\sim\sigma(q)$ in $G$ and $\\{\sigma(1),\ldots,\sigma(k)\\}$ is a
clique in $G$. Then, corresponding to any family of $n$
$\mathcal{S}_{G}$-clique projections which sum to $I$, there is a family of
$n$ cliques in $G$ which partition $V(G)$, and
$\chi(\bar{G})\leq\Omega(\mathcal{S}_{G}).$

(xi) Note that $\Omega_{\rm f}(\mathcal{S})=\gamma({\rm
cp}(\mathcal{S})^{\sharp})$ and $\tilde{\Omega}_{\rm
f}(\mathcal{S})=\gamma({\rm fp}(\mathcal{S})^{\sharp})$, and then apply Remark
8.2 to obtain the results for $\Omega_{\rm f}$ and $\tilde{\Omega}_{\rm f}$.
For $\Omega$ and $\tilde{\Omega}$, it suffices to see that if
$\mathcal{S}\subseteq\mathcal{T}$ then $\mathcal{P}_{\rm
c}(\mathcal{S})\subseteq\mathcal{P}_{\rm c}(\mathcal{T})$ and
$\mathcal{P}_{\rm f}(\mathcal{S})\subseteq\mathcal{P}_{\rm f}(\mathcal{T})$.

(xii) The results for $\omega_{\rm f}$, $\omega$ and $\tilde{\omega}$ follow
from Remark 8.2. If $\mathcal{S}\subseteq\mathcal{T}$ then $\mathcal{P}_{\rm
a}(\mathcal{T})\subseteq\mathcal{P}_{\rm a}(\mathcal{S})$ and the result for
$\chi$ follows.

(xiii) The first inequality follows from (43) and Theorem 4.11, and the rest
are similar. ∎

Remark.  Part (xiii) of Theorem 10.2 can be viewed as a non-commutative
version of the inequality $\alpha(G)\chi(G)\geq d$ for classical graphs $G$.
Note that corresponding results for operator anti-systems are considered in
[16, Section 3.1].

The following fact – an immediate corollary of Theorem 6.6 – gives an entropic
significance to the parameters $\Omega_{\rm f}$ and $\tilde{\Omega}_{\rm f}$.

######  Theorem 10.3.

Let $\mathcal{S}\subseteq M_{d}$ be an operator system. Then

$\max_{\rho\in\mathcal{R}_{d}}H_{\mathop{\rm
cp}(\mathcal{S})}(\rho)=\log\Omega_{\rm f}(\mathcal{S})\ \mbox{ and }\
\max_{\rho\in\mathcal{R}_{d}}H_{\mathop{\rm
fp}(\mathcal{S})}(\rho)=\log\tilde{\Omega}_{\rm f}(\mathcal{S}).$

######  Theorem 10.4.

Let $\mathcal{S}$ and $\mathcal{S}_{n}$ be non-commutative graphs in $M_{d}$,
$n\in\mathbb{N}$.

  * (i)

If $\mathcal{S}\subseteq\liminf_{n\in\mathbb{N}}\mathcal{S}_{n}$ then
$\chi_{\rm f}(\mathcal{S})\leq\liminf_{n\in\mathbb{N}}\chi_{\rm
f}(\mathcal{S}_{n})$;

  * (ii)

If $\tilde{\Omega}_{\rm f}(\mathcal{S})<\infty$ and
$\limsup_{n\in\mathbb{N}}\mathcal{S}_{n}\subseteq\mathcal{S}$ then
$\tilde{\Omega}_{\rm
f}(\mathcal{S})\leq\liminf_{n\in\mathbb{N}}\tilde{\Omega}_{\rm
f}(\mathcal{S}_{n})$.

###### Proof.

(i) By (47) and Proposition 4.12, $\mathop{\rm
ap}(\mathcal{S})^{\sharp}\subseteq\liminf_{n\in\mathbb{N}}\mathop{\rm
ap}(\mathcal{S}_{n})^{\sharp}$, and the claim now follows from (45) and the
proof of Corollary 4.13.

(ii) It is straightforward that $\limsup_{n\in\mathbb{N}}\mathop{\rm
fp}(\mathcal{S}_{n})\subseteq\mathop{\rm fp}(\mathcal{S})$. By Theorem 10.2,
$\mathop{\rm fp}(\mathcal{S})$ has non-empty relative interior, and the
statement follows from (50) and Corollary 4.13. ∎

Remark.  Operator systems satisfying the conditions of Theorem 10.2 (vi) are
precisely those for which no unit vector $v$ satisfies $vv^{*}\in\mathcal{S}$
(for example, $\mathop{\rm span}\\{I_{d}\\}$ for $d>1$). Note that the
converse of Theorem 10.2 (vi) does not hold. Indeed, let $d\geq 3$ and
$\mathcal{K}=\mathop{\rm span}\\{I_{d},e_{1}e_{1}^{*}\\}\subseteq M_{d}$. It
is straightforward to see that the only $\mathcal{K}$-full projection is
$e_{1}e_{1}^{*}$. Thus, $\mathop{\rm fp}(\mathcal{K})=\\{M\in M_{d}^{+}:M\leq
e_{1}e_{1}^{*}\\}$ and $\tilde{\omega}(\mathcal{K})=1$. By Lemma 3.18 we have
$\mathop{\rm fp}(\mathcal{K})^{\sharp}=\\{M\in M_{d}^{+}:\mathop{\rm
Tr}(Me_{1}e_{1}^{*})\leq 1\\}$ and so $ke_{2}e_{2}^{*}\in\mathop{\rm
fp}(\mathcal{S})^{\sharp}$ for all $k\in\mathbb{R}_{+}$, giving that
$\tilde{\Omega}_{\rm f}(\mathcal{K})=\infty.$

##  11\. The Witsenhausen rate

In this section, we define the Witsenhausen rate of a non-commutative graph,
extending the well-known Witsenhausen rate of a classical graph [40]. En
route, we examine the multiplicativity of some of the non-commutative graph
parameters discussed earlier. Some of our bounds are more conveniently
expressed in terms of orthogonal complements of non-commutative graphs,
already employed in [36] and [16]. More specifically, a subspace
$\mathcal{T}\subseteq M_{d}$ is called an _operator anti-system_ [6] if there
exists an operator system $\mathcal{S}\subseteq M_{d}$ such that
$\mathcal{T}=\mathcal{S}^{\perp}.$ (Such subspaces are called trace-free non-
commutative graphs in [36].) As was pointed out in [16, Proposition 8], a
subspace $\mathcal{T}\subseteq M_{d}$ is an operator anti-system precisely
when it is self-adjoint and traceless, in the sense that $\mathop{\rm Tr}T=0$
whenever $T\in\mathcal{T}$. Given a graph $G$ with vertex set $[d]$, its
operator anti-system [36, Equation (7)], [16, Definition 6] is the space

$\mathcal{T}_{G}=\mathop{\rm span}\\{e_{i}e_{j}^{*}:i\sim
j\mbox{~{}in~{}}G\\}.$

Note that

(52) $\mathcal{T}_{G}=(\mathcal{S}_{\bar{G}})^{\perp}.$

Let $\mathcal{T}\subseteq M_{d}$ be an operator anti-system. An orthonormal
set $\\{v_{1},\ldots,v_{k}\\}$ in $\mathbb{C}^{d}$ is called _$\mathcal{T}$
-independent_ (resp. _strongly $\mathcal{T}$-independent_) if
$v_{i}v_{j}^{*}\in\mathcal{T}^{\perp}$ for all $i,j\in[k]$ with $i\neq j$
(resp. for all $i,j\in[k]$). It is clear that a set is
$\mathcal{T}$-independent (resp. strongly $\mathcal{T}$-independent) if and
only if it is $\mathcal{T}^{\perp}$-clique (resp. $\mathcal{T}^{\perp}$-full).
The _chromatic number_ $\chi(\mathcal{T})$ and _strong chromatic number_
$\chi_{\rm s}(\mathcal{T})$ of an operator anti-system $\mathcal{T}$ were
introduced in [16] and can be expressed in our terms as follows:

(53) $\chi(\mathcal{T})=\Omega(\mathcal{T}^{\perp})\mbox{ and }\chi_{\rm
s}(\mathcal{T})=\tilde{\Omega}(\mathcal{T}^{\perp}).$

Thus, $\tilde{\Omega}_{\rm f}(\mathcal{S})$ (resp. $\Omega_{\rm
f}(\mathcal{S})$) can be regarded as the fractional version of $\chi_{\rm
s}(\mathcal{S}^{\perp})$ (resp. $\chi(\mathcal{S}^{\perp})$). It was shown in
[16, Corollary 28 and Theorem 14], and follows from (52) and Theorem 10.2,
that

$\chi(\mathcal{T}_{\bar{G}})=\chi_{\rm
s}(\mathcal{T}_{\bar{G}})=\chi(\bar{G}).$

Recall that, if $G_{1}$ and $G_{2}$ are graphs with vertex sets $[d_{1}]$ and
$[d_{2}]$, respectively, their disjunctive product $G_{1}\ast G_{2}$ has
vertex set $[d_{1}]\times[d_{2}]$ and two pairs $(i,k),(j,l)$ of vertices are
adjacent if $i\sim j$ in $G_{1}$ or $k\sim l$ in $G_{2}$. The _co-normal
product_ of operator anti-systems [36] $\mathcal{T}_{i}\subseteq M_{d_{i}}$,
$i=1,2$, is the operator anti-system

$\mathcal{T}_{1}*\mathcal{T}_{2}=\mathcal{T}_{1}\otimes
M_{d_{2}}+M_{d_{1}}\otimes\mathcal{T}_{2}.$

It is straightforward that

$\mathcal{T}_{G_{1}}\ast\mathcal{T}_{G_{2}}=\mathcal{T}_{G_{1}\ast G_{2}}.$

Note that, if $\mathcal{S}_{1}$ and $\mathcal{S}_{2}$ are operator systems
then
$(\mathcal{S}_{1}\otimes\mathcal{S}_{2})^{\perp}=\mathcal{S}_{1}^{\perp}\ast\mathcal{S}_{2}^{\perp}$.

The next theorem collects the submultiplicativity properties of the chromatic,
the fractional chromatic, the clique and the clique covering numbers. Part (i)
answers [6, Question 7.5].

######  Theorem 11.1.

Let $\mathcal{S}_{i}\subseteq M_{d_{i}}$ be a non-commutative graph, and
$\mathcal{T}_{i}\subseteq M_{d_{i}}$ be an operator anti-system, $i=1,2$.

  * (i)

If $\zeta\in\\{\chi,\chi_{\rm f},\tilde{\Omega},\tilde{\Omega}_{\rm f}\\}$
then
$\zeta(\mathcal{S}_{1}\otimes\mathcal{S}_{2})\leq\zeta(\mathcal{S}_{1})\zeta(\mathcal{S}_{2})$;

  * (ii)

$\tilde{\omega}(\mathcal{S}_{1}\otimes\mathcal{S}_{2})\geq\tilde{\omega}(\mathcal{S}_{1})\tilde{\omega}(\mathcal{S}_{2})$;

  * (iii)

$\omega(\mathcal{S}_{1}\otimes\mathcal{S}_{2})\geq\min\\{\omega(\mathcal{S}_{1}),\omega(\mathcal{S}_{2})\\}$;

  * (iv)

If $\tilde{\omega}(\mathcal{S}_{2})\geq 1$ then
$\omega(\mathcal{S}_{1}\otimes\mathcal{S}_{2})\geq\omega(\mathcal{S}_{1}).$
Thus, if $\tilde{\omega}(\mathcal{S}_{i})\geq 1$, $i=1,2$, then
$\omega(\mathcal{S}_{1}\otimes\mathcal{S}_{2})\geq\max\\{\omega(\mathcal{S}_{1}),\omega(\mathcal{S}_{2})\\};$

  * (v)

$\chi_{\rm s}(\mathcal{T}_{1}*\mathcal{T}_{2})\leq\chi_{\rm
s}(\mathcal{T}_{1})\chi_{\rm s}(\mathcal{T}_{2})$.

###### Proof.

(i) Suppose that $\\{P_{i}^{(k)}\\}_{i=1}^{l_{k}}$ is a PVM consisting of
projections in $\mathcal{P}_{\rm a}(\mathcal{S}_{k})$, $k=1,2$. Then
$\\{P_{i}^{(1)}\otimes P_{j}^{(2)}:i\in[l_{1}],j\in[l_{2}]\\}$ is a PVM
consisting of projections in $\mathcal{P}_{\rm
a}(\mathcal{S}_{1}\otimes\mathcal{S}_{2})$; minimising over $l_{1}$ and
$l_{2}$ proves the claim if $\zeta=\chi$. A similar argument shows the claim
for $\zeta=\tilde{\Omega}$. For $\zeta=\chi_{\rm f}$, the statement follows
from Theorems 7.2 and 4.11, Proposition 9.3 and (48). The claims in the case
$\zeta=\tilde{\Omega}_{\rm f}$ follow from the – straightforward to verify –
inclusion

(54) $\mathop{\rm fp}(\mathcal{S}_{1})\otimes_{\max}\mathop{\rm
fp}(\mathcal{S}_{2})\subseteq\mathop{\rm
fp}(\mathcal{S}_{1}\otimes\mathcal{S}_{2}).$

(ii) follows from (54).

(iii) Without loss of generality, let $\omega(\mathcal{S}_{1})=p\leq
q=\omega(\mathcal{S}_{2})$, and choose an $\mathcal{S}_{1}$-clique
$\\{u_{1},\ldots,u_{p}\\}$ and an $\mathcal{S}_{2}$-clique
$\\{v_{1},\ldots,v_{q}\\}$. The set $\\{u_{i}\otimes v_{i}:i\in[p]\\}$ is then
an $\mathcal{S}_{1}\otimes\mathcal{S}_{2}$-clique.

(iv) Since $\tilde{\omega}(\mathcal{S}_{2})\geq 1$, there exists an
$\mathcal{S}_{2}$-full projection $vv^{*}$ of rank one. Let
$\\{u_{1},\ldots,u_{p}\\}$ be an $\mathcal{S}_{1}$-clique, where
$p=\omega(\mathcal{S}_{1})$. We have

$(u_{i}\otimes v)(u_{j}\otimes v)^{*}=u_{i}u_{j}^{*}\otimes
vv^{*}\in\mathcal{S}_{1}\otimes\mathcal{S}_{2},\ \ \ i\neq j,$

and hence the set $\\{u_{i}\otimes v:i\in[p]\\}$ is an
$\mathcal{S}_{1}\otimes\mathcal{S}_{2}$-clique.

(v) Using (53) and (i), we have

$\chi_{\rm
s}(\mathcal{T}_{1}*\mathcal{T}_{2})=\tilde{\Omega}(\mathcal{T}^{\perp}_{1}\otimes\mathcal{T}^{\perp}_{2})\leq\tilde{\Omega}(\mathcal{T}^{\perp}_{1})\tilde{\Omega}(\mathcal{T}^{\perp}_{2})=\chi_{\rm
s}(\mathcal{T}_{1})\chi_{\rm s}(\mathcal{T}_{2}).$

∎

Remark.  It is well-known that the clique number of classical graphs is
multiplicative with respect to strong graph products [12, Chapter 7, Exercise
13]. The same does not hold true for non-commutative graphs; indeed, we will
see in Section 12 that there exist operator systems $\mathcal{S}$ and
$\mathcal{T}$ such that
$\omega(\mathcal{S}\otimes\mathcal{T})<\omega(\mathcal{T})$.

An application of Theorems 10.2 and 11.1 yields the following bound on the
Shannon capacity of a non-commutative graph:

######  Corollary 11.2.

Let $\mathcal{S}\subseteq M_{d}$ be a non-commutative graph. Then
$\Theta(\mathcal{S})\leq\tilde{\Omega}_{\rm f}(\mathcal{S})$.

In [40], Witsenhausen identified the zero-error capacity of noisy channels in
the presence of side information. In this scenario, in addition to a noisy
channel $\mathcal{N}:[d]\rightarrow[m]$, Alice can communicate to Bob using an
identity channel $[k]\rightarrow[k]$ for any $k\in\mathbb{N}$ of her choice,
which she runs in parallel with $\mathcal{N}$ so that Bob can retrieve with
certainty her input $i\in[d]$. Thus, Alice seeks a function
$f:[d]\rightarrow[k]$, such that the output of the channel $\mathcal{N}$
applied to $i\in[d]$, together with the value $f(i)$, completely determine
$i$. The minimum value of $k$ such that these constraints can be satisfied is
denoted $\chi(\mathcal{N})$ and known as the _packing number_ of
$\mathcal{N}$. Witsenhausen showed that $\chi(\mathcal{N})$ coincides with the
chromatic number $\chi(G)$ of the confusability graph $G$ of $\mathcal{N}$.
The zero-error capacity of $\mathcal{N}$ (or, alternatively, of $G$) in the
presence of side information, is the _Witsenhausen rate_

$R(G)=\lim_{n\rightarrow\infty}\sqrt[n]{\chi(G^{\boxtimes n})}.$

The quantum zero-error side information problem was examined in [28, Section
7.3]. Given a quantum channel $\Phi:M_{d}\rightarrow M_{k}$, here we seek an
orthonormal basis $\\{v_{1},\ldots,v_{d}\\}\subseteq\mathbb{C}^{d}$,
$k\in\mathbb{N}$ and a function $f:[d]\rightarrow[k]$ such that the outputs
$(\Phi\otimes\mathcal{I})((v_{i}\otimes e_{f(i)})(v_{i}\otimes e_{f(i)})^{*})$
are perfectly distinguishable for $i=1,\ldots,d$, where $\mathcal{I}$ is the
identity channel and $\\{e_{1},\ldots,e_{k}\\}$ is the canonical orthonormal
basis of $\mathbb{C}^{n}$. The least $k\in\mathbb{N}$ with this property is
the _packing number_ $\chi(\Phi)$ of $\Phi$. It was shown on [28, p. 59] that,
if $\mathcal{S}$ is the confusability graph of $\Phi$ then
$\chi(\Phi)=\chi(\mathcal{S})$. Theorem 11.1 and Fekete’s Lemma now show that
the limit

$R(\mathcal{S}):=\lim_{n\rightarrow\infty}\sqrt[n]{\chi(\mathcal{S}^{\otimes
n})},$

which we call the _Witsenhausen rate_ of $\mathcal{S}$, exists and coincides
with the infimum of the sequence $\left(\sqrt[n]{\chi(\mathcal{S}^{\otimes
n})}\right)_{n\in\mathbb{N}}$. It is immediate that, if $G$ is a graph then
$R(\mathcal{S}_{G})=R(G)$.

Let $\mathcal{T}^{\ast n}$ denote the disjunctive product of $n$ copies of an
operator anti-system $\mathcal{T}$. It follows from Theorem 11.1 and Fekete’s
Lemma that the limit $\lim_{n\rightarrow\infty}\sqrt[n]{\chi_{\rm
s}(\mathcal{T}^{\ast n})}$ exists and is equal to
$\inf_{n\in\mathbb{N}}\\{\sqrt[n]{\chi_{\rm s}(\mathcal{T}^{n})}\\}$. To
appreciate the significance of this limit, recall that, by [31, Corollary
3.4.3],

(55) $\lim_{n\to\infty}\sqrt[n]{\chi(G^{n})}=\chi_{\rm f}(G),$

where $G^{n}$ denotes the disjunctive product of $n$ copies of a graph $G$. An
application of (52) and Theorem 10.2 shows that

$\lim_{n\rightarrow\infty}\sqrt[n]{\chi_{\rm
s}(\mathcal{T}_{G}^{n})}=\tilde{\Omega}_{\rm f}(\mathcal{T}_{G}^{\perp}).$

Since $\tilde{\Omega}_{\rm f}(\mathcal{T}^{\perp})$ is a fractional version of
$\chi_{\rm s}(\mathcal{T})$, the following question about a non-commutative
version of (55) is natural:

######  Question 11.3.

Let $\mathcal{T}$ be an operator anti-system. Is it true that

$\lim_{n\rightarrow\infty}\sqrt[n]{\chi_{\rm
s}(\mathcal{T}^{n})}=\tilde{\Omega}_{\rm f}(\mathcal{T}^{\perp})?$

##  12\. Some examples

In this subsection, we consider some examples of non-commutative graphs and
evaluate the parameters we introduced. For a graph $G$, let

$\theta(G)=\gamma(\mathop{\rm thab}(G))=\max\left\\{\mathop{\rm
Tr}(A):A\in\mathop{\rm thab}(G)\right\\}$

be the _Lovász number_ of $G$ [23]. The non-commutative versions
$\theta(\mathcal{S})$ and $\hat{\theta}(\mathcal{S})$ of the Lovász number
were introduced in [6]; we refer the reader to [6] for their definitions and
note here that, by [6, Corollary 4.8 and Theorem 5.2], if
$\mathcal{S}\subseteq M_{d}$ is an operator system then

(56)
$\alpha(\mathcal{S})\leq\theta(\mathcal{S})\leq\hat{\theta}(\mathcal{S})\leq
d.$

It was shown in [6] that, if $G$ is a graph then
$\theta(\mathcal{S}_{G})=\hat{\theta}(\mathcal{S}_{G})=\theta(G)$. It follows
from (50) and Theorem 4.11 (and was shown in [6]) that $\tilde{\Omega}_{\rm
f}(\mathcal{S})=\gamma(\mathop{\rm fp}(\mathcal{S})^{\sharp})$ and
$\Omega_{\rm f}(\mathcal{S})=\gamma(\mathop{\rm cp}(\mathcal{S})^{\sharp})$.
For completeness, whenever they are known, we include in the following the
values of $\theta$ and $\hat{\theta}$.

######  Proposition 12.1.

Let $d\in\mathbb{N}$. The following hold:

  * (i)

$\alpha(\mathbb{C}I_{d})=\theta(\mathbb{C}I_{d})=\hat{\theta}(\mathbb{C}I_{d})=\Omega_{\rm
f}(\mathbb{C}I_{d})=\Omega(\mathbb{C}I_{d})=d$;

  * (ii)

$\omega(\mathbb{C}I_{d})=\chi_{\rm{f}}(\mathbb{C}I_{d})=\chi(\mathbb{C}I_{d})=1$;

  * (iii)

$\tilde{\Omega}_{\rm f}(\mathbb{C}I_{d})=\tilde{\Omega}(\mathbb{C}I_{d})=1$ if
$d=1$, and $\tilde{\Omega}_{\rm
f}(\mathbb{C}I_{d})=\tilde{\Omega}(\mathbb{C}I_{d})=\infty$ if $d\geq 2$;

  * (iv)

$\tilde{\omega}(\mathbb{C}I_{d})=1$ if $d=1$ and
$\tilde{\omega}(\mathbb{C}I_{d})=0$ if $d\geq 2$;

  * (v)

$H(\mathbb{C}I_{d},\rho)=0\mbox{ for all }\rho\in\mathcal{R}_{d}$;

  * (vi)

$\Theta(\mathbb{C}I_{d})=d\ \mbox{ and }\ R(\mathbb{C}I_{d})=1$.

###### Proof.

(i), (ii) For orthonormal $u,v\in\mathbb{C}^{d}$ we have $\left\langle
u,v\right\rangle=\left\langle uv^{*},I_{d}\right\rangle=0$, and so
$uv^{*}\in\mathbb{C}I_{d}^{\perp}$. It follows that a projection in $M_{d}$ is
$\mathbb{C}I_{d}$-clique if and only if it has rank one. Thus
$\omega(\mathbb{C}I_{d})=1$, whence $\Omega(\mathbb{C}I_{d})=d$. Proposition
9.8 implies $\alpha(\mathbb{C}I_{d})=d$ and $\chi(\mathbb{C}I_{d})=\chi_{\rm
f}(\mathbb{C}I_{d})=1$. It is immediate that $\Omega_{\rm
f}(\mathbb{C}I_{d})=d$, and (56) yields
$\theta(\mathbb{C}I_{d})=\hat{\theta}(\mathbb{C}I_{d})=d$.

(iii), (iv) Note that if $d=1$ we have $e_{1}e_{1}^{*}\in\mathop{\rm
fp}(\mathbb{C}I_{1})$ and $\mathop{\rm fp}(\mathbb{C}I_{1})=[0,1]=\mathop{\rm
fp}(\mathbb{C}I_{d})^{\sharp}$. This gives
$\tilde{\omega}(\mathbb{C}I_{1})=\tilde{\Omega}(\mathbb{C}I_{1})=\tilde{\Omega}_{\rm
f}(\mathbb{C}I_{d})=1$. However, if $d\geq 2$, no unit vector $v$ satisfies
$vv^{*}\in\mathbb{C}I_{d}$. Thus $\mathop{\rm fp}(\mathbb{C}I_{d})=\\{0\\}$
and $\mathop{\rm fp}(\mathbb{C}I_{d})^{\sharp}=M_{d}$, giving
$\tilde{\omega}(\mathbb{C}I_{d})=0$ and
$\tilde{\Omega}(\mathbb{C}I_{d})=\tilde{\Omega}_{\rm
f}(\mathbb{C}I_{d})=\infty.$

(v) This follows from Proposition 9.8.

(vi) We have $\alpha\left((\mathbb{C}I_{d})^{\otimes
n}\right)=\alpha(\mathbb{C}I_{d^{n}})=d^{n}$, giving
$\Theta(\mathbb{C}I_{d})=d.$ Similarly, $\chi\left((\mathbb{C}I_{d})^{\otimes
n}\right)=\chi(\mathbb{C}I_{d^{n}})=1$, and so $R(\mathbb{C}I_{d})=1.$ ∎

Letting $J_{d}$ be the $d\times d$ matrix all of whose entries are equal to
one, we define the operator system
$\mathcal{T}_{d}=\mathbb{C}I_{d}+\mathbb{C}J_{d}$.

######  Proposition 12.2.

Let $d\in\mathbb{N}$. The following hold:

  * (i)

$\alpha(\mathcal{T}_{d})=\theta(\mathcal{T}_{d})=\hat{\theta}(\mathcal{T}_{d})=\Omega_{\rm
f}(\mathcal{T}_{d})=\Omega(\mathcal{T}_{d})=d;$

  * (ii)

$\omega(\mathcal{T}_{d})=\chi_{\rm{f}}(\mathcal{T}_{d})=\chi(\mathcal{T}_{d})=1;$

  * (iii)

$H(\mathcal{T}_{d},\rho)=0\mbox{ for all }\rho\in\mathcal{R}_{d};$

  * (iv)

$\Theta(\mathcal{T}_{d})=d$ and $R(\mathcal{T}_{d})=1$;

  * (v)

$\tilde{\Omega}(\mathcal{T}_{2})=\tilde{\Omega}_{\rm f}(\mathcal{T}_{2})=2$
and $\tilde{\omega}(\mathcal{T}_{2})=1$;

  * (vi)

If $d\geq 3$ then $\tilde{\Omega}(\mathcal{T}_{d})=\tilde{\Omega}_{\rm
f}(\mathcal{T}_{d})=\infty$ and $\tilde{\omega}(\mathcal{T}_{d})=1.$

###### Proof.

(i)-(iii) As $\mathcal{T}_{d}$ is commutative, Proposition 9.8 gives (iii) and
the fact that $\alpha(\mathcal{T}_{d})=d$ and
$\chi_{\rm{f}}(\mathcal{T}_{d})=\chi(\mathcal{T}_{d})=1$. Theorem 10.2 and
(56) give the remaining results.

(iv) That $\Theta(\mathcal{T}_{d})=d$ follows from (i) and the fact that
$\alpha(\mathcal{S})\leq\Theta(\mathcal{S})\leq\hat{\theta}(\mathcal{S})$ (see
[6, Corollary 5.5]). Theorem 11.1 gives $\chi(\mathcal{T}_{d}^{\otimes n})=1$
for all $n\in\mathbb{N}$, whence we have $R(\mathcal{T}_{d})=1.$

(v) Suppose unit vector $v=(v_{i})_{i=1}^{2}\in\mathbb{C}^{2}$ satisfies
$vv^{*}\in\mathcal{T}_{2}$, so that $\\{v\\}$ is $\mathcal{T}_{2}$-full. Then
$|v_{1}|^{2}=|v_{2}|^{2}=1/2$. Since we have
$v_{1}\overline{v_{2}}=v_{2}\overline{v_{1}}$, it follows that $v_{1}=\pm
v_{2}$. Setting $v_{1}=e^{i\theta}/\sqrt{2}=\pm v_{2}$ for
$\theta\in[0,2\pi)$, gives

(57) $vv^{*}=\frac{1}{2}\begin{pmatrix}1&\pm 1\\\ \pm
1&1\end{pmatrix}\in\mathcal{T}_{2},$

and we conclude that the $\mathcal{T}_{2}$-full singleton sets are those of
the form

$\left\\{\frac{e^{i\theta}}{\sqrt{2}}\begin{pmatrix}1\\\ \pm
1\end{pmatrix}\right\\},\ \theta\in[0,2\pi).$

By (ii) and Theorem 10.2,
$\tilde{\omega}(\mathcal{T}_{2})\leq\omega(\mathcal{T}_{2})=1$, and so
$\tilde{\omega}(\mathcal{T}_{2})=1.$ It then follows from Theorem 10.2 that
$\tilde{\Omega}(\mathcal{T}_{2})\geq 2.$ Now let
$u=\frac{1}{\sqrt{2}}\begin{pmatrix}1\\\ 1\end{pmatrix}$,
$v=\frac{1}{\sqrt{2}}\begin{pmatrix}1\\\ -1\end{pmatrix}$, $P_{1}=uu^{*}$ and
$P_{2}=vv^{*}$. Noting that $\\{u\\}$ and $\\{v\\}$ are $\mathcal{T}_{2}$-full
sets and that $P_{1}+P_{2}=I$ yields $\tilde{\Omega}(\mathcal{T}_{2})=2$.

By (57), $P_{1}$ and $P_{2}$ are the only $\mathcal{T}_{2}$-full projections.
Thus by Proposition 3.14, a matrix $M=\begin{pmatrix}a&b\\\
\overline{b}&d\end{pmatrix}\in M_{2}^{+}$ belongs to $\mathop{\rm
fp}(\mathcal{T}_{2})^{\sharp}$ if and only if

$\frac{1}{2}(a+b+\overline{b}+d)\leq 1\ \mbox{ and }\
\frac{1}{2}(a-b-\overline{b}+d)\leq 1.$

It follows that if $M\in\mathop{\rm fp}(\mathcal{T}_{2})^{\sharp}$ then
$\mathop{\rm Tr}M=a+d\leq 2.$ Since $I\in\mathop{\rm
fp}(\mathcal{T}_{2})^{\sharp}$, we have that $\tilde{\Omega}_{\rm
f}(\mathcal{T}_{2})=2$.

(vi) Let unit vector $v=(v_{i})_{i=1}^{d}\in\mathbb{C}^{d}$ satisfy
$vv^{*}\in\mathcal{T}_{d}$. This requires that $|v_{i}|^{2}=1/d$ for all
$i\in[d]$. Letting $i,j,k\in[d]$ be pairwise distinct, we require
$v_{i}\overline{v_{k}}=v_{j}\overline{v_{k}},$ and so $v_{i}=v_{j}$. Then
$v=\frac{e^{i\theta}}{\sqrt{d}}\mathbbm{1}$ for some
$\theta\in\mathbb{[}0,2\pi)$, and

(58) $vv^{*}=\frac{1}{d}J_{d}\in\mathcal{T}_{d}.$

Thus for $d\geq 3$, the $\mathcal{T}_{d}$-full singleton sets are precisely
those of the form $\left\\{\frac{e^{i\theta}}{\sqrt{d}}\mathbbm{1}\right\\}$,
$\theta\in[0,2\pi).$ As in (v), for $d\geq 3$ we have
$\tilde{\omega}(\mathcal{T}_{d})\leq\omega(\mathcal{T}_{d})=1$ and we conclude
that $\tilde{\omega}(\mathcal{T}_{d})=1$. From (58) we see that the only
$\mathcal{T}_{d}$-full projection is $\frac{1}{d}J_{d}.$ Then for $M\in
M_{d}^{+}$ we have $M\in\mathop{\rm fp}(\mathcal{T}_{d})^{\sharp}$ if and only
if $\mathop{\rm Tr}(MJ_{d})\leq d$. Let unit vector
$w=(w_{i})_{i=1}^{d}\in\mathbb{C}^{d}$ satisfy $\sum_{i=1}^{d}w_{i}=0$, and
thus $\left\langle w,\mathbbm{1}\right\rangle=0.$ For $k\in\mathbb{R}_{+}$
form $M=kww^{*}\in M_{d}^{+},$ giving that $\mathop{\rm Tr}M=k$ and
$\mathop{\rm Tr}(MJ_{d})=k|\left\langle w,\mathbbm{1}\right\rangle|^{2}=0.$
Hence we have $M\in\mathop{\rm fp}(\mathcal{T}_{d})^{\sharp}$ for all
$k\in\mathbb{R}^{+}$, and $\tilde{\Omega}_{\rm
f}(\mathcal{T}_{d})=\gamma(\mathop{\rm fp}(\mathcal{T}_{d})^{\sharp})=\infty$.
Finally note by Theorem 10.2 that $\tilde{\Omega}(\mathcal{T}_{d})=\infty$. ∎

######  Example 12.3.

Here we give some quantum channels whose related operator systems are of the
form $\mathcal{T}_{d}$ for some $d\in\mathbb{N}$.

(i) Consider a quantum channel $\Phi:M_{2}\to M_{2}$ with Kraus representation
$\Phi(T)=\sum_{i=1}^{2}A_{i}TA_{i}^{*},\,\rho\in M_{2}$, where

$A_{1}=\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\\ 0&0\end{pmatrix}\mbox{ and
}A_{2}=\frac{1}{\sqrt{2}}\begin{pmatrix}0&0\\\ 1&-1\end{pmatrix}.$

It is easy to verify that $\mathcal{S}_{\Phi}=\mathcal{T}_{2}$.

(ii) The operators

$B_{1}=\frac{1}{\sqrt{2}}\begin{pmatrix}1&0&0\\\ 0&1&0\\\ 0&0&1\\\ 0&0&0\\\
0&0&0\\\ 0&0&0\end{pmatrix},\ \ \
B_{2}=\frac{1}{\sqrt{8}}\begin{pmatrix}0&1&1\\\ 1&0&1\\\ 1&1&0\\\ 1&-1&0\\\
0&1&-1\\\ 1&0&-1\end{pmatrix}$

satisfy $B_{1}^{*}B_{1}=B_{2}^{*}B_{2}=\frac{1}{2}I_{3}$ and
$B_{2}^{*}B_{1}=B_{1}^{*}B_{2}=\frac{1}{4}(J_{3}-I_{3}).$ It follows that the
channel $\Psi:M_{3}\to M_{6}$ given by $\Psi(\rho)=B_{1}\rho
B_{1}^{*}+B_{2}\rho B_{2}^{*},\,\rho\in M_{3}$ is a quantum channel with
$S_{\Psi}=\mathcal{T}_{3}.$

######  Proposition 12.4.

Consider operator systems $\mathcal{R}_{i}\subseteq M_{d_{i}}$ where
$\chi(\mathcal{R}_{i})=1$ for $i=1,\ldots,m$. Then

  * (i)

$\chi(\bigotimes_{i=1}^{m}\mathcal{R}_{i})=\chi_{\rm
f}(\bigotimes_{i=1}^{m}\mathcal{R}_{i})=\omega(\bigotimes_{i=1}^{m}\mathcal{R}_{i})=R(\bigotimes_{i=1}^{m}\mathcal{R}_{i})=1;$

  * (ii)

$\alpha(\bigotimes_{i=1}^{m}\mathcal{R}_{i})=\Omega(\bigotimes_{i=1}^{m}\mathcal{R}_{i})=\Omega_{\rm
f}(\bigotimes_{i=1}^{m}\mathcal{R}_{i})=\theta(\bigotimes_{i=1}^{m}\mathcal{R}_{i})\newline
=\hat{\theta}(\bigotimes_{i=1}^{m}\mathcal{R}_{i})=c(\bigotimes_{i=1}^{m}\mathcal{R}_{i})=d_{1}\ldots
d_{m}.$

###### Proof.

(i) By Theorem 11.1, $\chi(\bigotimes_{i=1}^{m}\mathcal{R}_{i})=1$, whence it
is immediate that $R(\bigotimes_{i=1}^{m}\mathcal{R}_{i})=1$. The remaining
equalities follow from Theorems 9.4 and 10.2.

(ii) By (i) and Proposition 9.8,
$\alpha(\bigotimes_{i=1}^{m}\mathcal{R}_{i})=d_{1}\ldots d_{m}$, which implies
$\Theta(\bigotimes_{i=1}^{m}\mathcal{R}_{i})=d_{1}\ldots d_{m}$. Theorem 10.2
and (56) give the rest of the equalities. ∎

Propositions 12.2 and 12.4 have the following corollary.

######  Corollary 12.5.

We have that

  * (i)

$\chi(\bigotimes_{i=1}^{m}\mathcal{T}_{d_{i}})=\chi_{\rm
f}(\bigotimes_{i=1}^{m}\mathcal{T}_{d_{i}})=\omega(\bigotimes_{i=1}^{m}\mathcal{T}_{d_{i}})=R(\bigotimes_{i=1}^{m}\mathcal{T}_{d_{i}})=1;$

  * (ii)

$\alpha(\bigotimes_{i=1}^{m}\mathcal{T}_{d_{i}})=\Omega(\bigotimes_{i=1}^{m}\mathcal{T}_{d_{i}})=\Omega_{\rm
f}(\bigotimes_{i=1}^{m}\mathcal{T}_{d_{i}})=\theta(\bigotimes_{i=1}^{m}\mathcal{T}_{d_{i}})\newline
=\hat{\theta}(\bigotimes_{i=1}^{m}\mathcal{T}_{d_{i}})=\Theta(\bigotimes_{i=1}^{m}\mathcal{T}_{d_{i}})=d_{1}\ldots
d_{m}.$

Next we discuss an operator system that has been widely considered in the
literature, see for example [16] and [22], namely

$\mathcal{S}_{d}={\rm span}\\{e_{i}e_{j}^{*},I_{d}:i\neq j\\}\subseteq M_{d},\
\ d\in\mathbb{N}.$

For $d\geq 2$, $\mathcal{S}_{d}$ is not commutative, and so it does not reduce
to the rather trivial case of Proposition 9.8, and nor is it equal to
$\mathcal{S}_{G}$ for any graph $G$. In [22] it was shown that
$\alpha(\mathcal{S}_{2})=1$, and in [16, Examples 4, 22] that
$\chi(\mathcal{S}_{d})=\chi_{\rm s}(\mathcal{S}_{d}^{\perp})=d$, while the
parameters $\alpha$, $\omega_{\rm f}$, $\chi$, $\tilde{\omega}$ were
identified in [6, Proposition 3.12]. Here we extend these results by
identifying the values of some of the parameters introduced in Sections 10 and
11.

######  Proposition 12.6.

Let $d_{1},\dots,d_{m}\in\mathbb{N}$. Then

  * (i)

$R(\bigotimes_{i=1}^{m}\mathcal{S}_{d_{i}})=d_{1},\ldots,d_{m};$

  * (ii)

$\tilde{\Omega}(\mathcal{S}_{2})=\tilde{\Omega}_{\rm f}(\mathcal{S}_{2})=2$
and
$\tilde{\Omega}(\bigotimes_{i=1}^{m}\mathcal{S}_{d_{i}})\geq\tilde{\Omega}_{\rm
f}(\bigotimes_{i=1}^{m}\mathcal{S}_{d_{i}})\geq d_{1}\dots d_{m};$

  * (iii)

$\Omega_{\rm f}(\mathcal{S}_{d})=\Omega(\mathcal{S}_{d})=1$.

###### Proof.

(i) In [6, Proposition 3.12] we have
$\chi\left(\bigotimes_{i=1}^{m}\mathcal{S}_{d_{i}}\right)=d_{1}\ldots d_{m}$,
and the result follows.

(ii) It follows from Proposition 3.14 and the expression for $\mathop{\rm
fp}(\bigotimes_{i=1}^{m}\mathcal{S}_{d_{i}})$ given in [6, Proposition 3.12]
that $I_{d_{1}\ldots d_{m}}\in\mathop{\rm
fp}(\bigotimes_{i=1}^{m}\mathcal{S}_{d_{i}})^{\sharp}$. Theorem 10.2 then
gives that
$\tilde{\Omega}(\bigotimes_{i=1}^{m}\mathcal{S}_{d_{i}})\geq\tilde{\Omega}_{\rm
f}(\bigotimes_{i=1}^{m}\mathcal{S}_{d_{i}})\geq d_{1}\dots d_{m}$. As
$\mathcal{T}_{2}\subseteq\mathcal{S}_{2}$, Theorem 10.2 and Proposition 12.2
give $\tilde{\Omega}_{\rm f}(\mathcal{S}_{2})\leq\tilde{\Omega}_{\rm
f}(\mathcal{T}_{2})=2$ and
$\tilde{\Omega}(\mathcal{S}_{2})\leq\tilde{\Omega}(\mathcal{T}_{2})=2$, and we
conclude that $\tilde{\Omega}(\mathcal{S}_{2})=\tilde{\Omega}_{\rm
f}(\mathcal{S}_{2})=2.$

(iii) It is clear that $\\{e_{1},\ldots,e_{d}\\}$ is an
$\mathcal{S}_{d}$-clique. Thus $I_{d}$ is an $\mathcal{S}_{d}$-clique
projection and hence $\Omega(\mathcal{S}_{d})=1$. By Theorem 10.2,
$\Omega_{\rm f}(\mathcal{S}_{d})=1$. ∎

We conclude with an example of an interesting phenomenon pointed out at the
end of Section 11.

######  Example 12.7.

Consider the operator system $\mathbb{C}I_{2}\otimes\mathcal{S}_{2}$. Recall
from [6, Proposition 3.12] that $\omega(\mathcal{S}_{2})=2$ and observe that
$\omega(\mathbb{C}I_{2})=1$ by Proposition 12.1. We claim that
$\omega(\mathbb{C}I_{2}\otimes\mathcal{S}_{2})=1<\omega(\mathcal{S}_{2})$.
Since $\\{u\\}$ is an $\mathbb{C}I_{2}\otimes\mathcal{S}_{2}$-clique for any
unit vector $u\in\mathbb{C}^{4}$, it suffices to show that no
$(\mathbb{C}I_{2}\otimes\mathcal{S}_{2})$-clique has cardinality greater than
1. To establish this, we show that if
$uv^{*}\in\mathbb{C}I_{2}\otimes\mathcal{S}_{2}$, then $u=0$ or $v=0$. We note
that

$\mathbb{C}I_{2}\otimes\mathcal{S}_{2}=\left\\{\begin{pmatrix}\lambda&a&0&0\\\
b&\lambda&0&0\\\ 0&0&\lambda&a\\\ 0&0&b&\lambda\end{pmatrix}:\
\lambda,a,b\in\mathbb{C}\right\\}.$

For $u,v\in\mathbb{C}^{4}$, write $u=(u_{i})_{i=1}^{4}$ and
$v=(v_{i})_{i=1}^{4},$ and suppose that
$uv^{*}=(u_{i}\overline{v}_{j})_{i,j=1}^{4}\in\mathbb{C}I_{2}\otimes\mathcal{S}_{2}.$
This requires
$u_{1}\overline{v}_{3}=u_{1}\overline{v}_{4}=u_{2}\overline{v}_{3}=u_{2}\overline{v}_{4}=0$,
giving $u_{1}=u_{2}=0$ or $v_{3}=v_{4}=0.$ Since for
$uv^{*}\in\mathbb{C}I_{2}\otimes\mathcal{S}_{2}$ we also have

$u_{1}\overline{v}_{1}=u_{2}\overline{v}_{2}=u_{3}\overline{v}_{3}=u_{4}\overline{v}_{4},$

it must then hold that all these terms vanish. Similarly,
$u_{1}\overline{v}_{2}=u_{3}\overline{v}_{4}$ and vanishes because either
$v_{4}=0$ or $u_{1}=0$. Finally, $u_{2}\overline{v}_{1}=u_{4}\overline{v}_{3}$
and vanishes because $u_{2}=0$ or $v_{3}=0$. We then have $uv^{*}=0$, and it
follows that $u=0$ or $v=0$, and $\\{u,v\\}$ is not a
$\mathbb{C}I_{2}\otimes\mathcal{S}_{2}$-clique.

Acknowledgement.  AW acknowledges financial support by the Spanish MINECO
(projects FIS2016-86681-P and PID2019-107609GB-I00) with the support of FEDER
funds, and the Generalitat de Catalunya (project CIRIT 2017-SGR-1127). It is
our pleasure to thank Giannicola Scarpa for fruitful discussions on the topic
of graph entropy, and Péter Vrana for valuable comments concerning convex
corners.

## References

  * [1] C. Aliprantis and K. C. Border, Infinite-dimensional analysis, Springer-Verlag, Berlin, 1999.
  * [2] K. M. R. Audenaert, and J. Eisert, Continuity bounds on the quantum relative entropy, J. Math. Phys. 46 (2005), no. 10, 102104, 21.
  * [3] W. B. Arveson, Subalgebras of C*-algebras, Acta Math. 123 (1969), 141-224.
  * [4] G. Boreland, A lower bound on graph entropy, Math. Proc. R. Ir. Acad. 118A (2018), no. 1, 9-20.
  * [5] G. Boreland, Information theoretic parameters for graphs and operator systems, PhD thesis, Queen’s University Belfast, 2020.
  * [6] G. Boreland, I. G. Todorov and A. Winter, Sandwich theorems and capacity bounds for non-commutative graphs, J. Combin. Theory Ser. A 177 (2021), 105302, 39 pp.
  * [7] I. Csiszár, J. Körner, L. Lovász, K. Marton and G. Simonyi, Entropy splitting for antiblocking corners and perfect graphs, Combinatorica 10 (1990), no. 1, 27-40.
  * [8] T. S. Cubitt, J. Chen and A. W. Harrow, Superactivation of the asymptotic zero-error classical capacity of a quantum channel, IEEE Trans. Inform. Theory 57 (2011), no. 12, 8114-8126.
  * [9] T. S. Cubitt and G. Smith, An extreme form of superactivation for quantum zero-error capacities, IEEE Trans. Inform. Theory 58 (2012), no. 3, 1953-1961.
  * [10] R. Duan, Super-activation of zero error capacity of noisy quantum channels, preprint (2009), arXiv:0906.2527.
  * [11] R. Duan, S. Severini and A. Winter, Zero-error communication via quantum channels, noncommutative graphs, and a quantum Lovász number, IEEE Trans. Inf. Theory 59 (2013), no. 2, 1164-1174.
  * [12] C. Godsil and G. Royle, Algebraic graph theory, Springer-Verlag, New York, 2001.
  * [13] M. Grötschel, L. Lovász and A. Schrijver, Relaxations of vertex packing, J. Combin. Theory Ser. B 40 (1986), 330-343.
  * [14] M. Grötschel, L. Lovász and A. Schrijver, Geometric algorithms and combinatorial optimization, Springer-Verlag, Berlin, 1988.
  * [15] A. Kavruk, V. I. Paulsen, I. G. Todorov and M. Tomforde, Tensor products of operator systems, J. Funct. Anal. 261 (2011), 267-299.
  * [16] S. Kim and A. Metha, Chromatic numbers and a Lovász type inequality for non-commutative graphs, preprint (2017), arXiv:1709.05595.
  * [17] D. E. Knuth, The sandwich theorem, Electron. J. Combin. 1 (1994), 48p..
  * [18] J. Körner, Coding of an information source having ambiguous alphabet and the entropy of graphs, Transactions of the Sixth Prague Conference on Information Theory, Statistical Decision Functions, Random Processes (Tech Univ., Prague (1971), 411-425.
  * [19] J. Körner, Fredman-Komlós bounds and information theory SIAM J. Algebraic Discrete Methods 7 (1986), no. 4, 560-570.
  * [20] J. Körner and G. Simonyi, Graph pairs and their entropies: modularity problems, Combinatorica 20 (2000), no. 2, 227-240.
  * [21] J. Körner, G. Simonyi and Z. Tuza, Perfect couples of graphs, Combinatorica 12 (1992), no. 2, 179-192.
  * [22] R. Levene, V. I. Paulsen and I. G. Todorov, Complexity and capacity bounds for quantum channels, IEEE Trans. Inf. Theory 64 (2018), no. 10, 6917-6928.
  * [23] L. Lovász, On the Shannon capacity of a graph, IEEE Trans. Inf. Theory 25 (1979), no. 1, 1-7.
  * [24] K. Marton, On the Shannon capacity of probabilistic graphs, J. Combin. Theory Ser. B 57 (1993), no. 2, 183-195.
  * [25] M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information, Cambridge University Press, Cambridge, 2000.
  * [26] M. Ohya and D Petz, Quantum entropy and its use, Springer-Verlag, Berlin, 1993.
  * [27] V. I. Paulsen, Completely bounded maps and operator algebras, Cambridge University Press, Cambridge, 2002.
  * [28] V. I. Paulsen, Entanglement and non-locality, Lecture notes, University of Waterloo, 2016.
  * [29] D. Pollard, Minimax theorem, Unpublished notes, University of Yale, 2003.
  * [30] M. B. Ruskai, Inequalities for quantum entropy: a review with conditions for equality, J. Math. Phys. 43 (2002), no. 9 4358-4375.
  * [31] E. R. Scheinerman and D. H. Ullman, Fractional graph theory. A rational approach to the theory of graphs, Dover Publications, New York, 2011.
  * [32] S. Rezaei and E. Chiniforooshan, Symmetric graphs with respect to graph entropy, Electron. J. Combin. 24 (2017), no. 1.
  * [33] C. E. Shannon, The zero error capacity of a noisy channel, Institute of Radio Engineers, Transactions on Information Theory IT-2 (1956), 8-19.
  * [34] G. Simonyi, Graph entropy: a survey, DIMACS Ser. Discrete Math. Theoret. Comput. Sci. 20 (1995), 399-441.
  * [35] G. Simonyi, Perfect graphs and graph entropy. An updated survey, Wiley-Intersci. Ser. Discrete Math. Optim. (2001), 293-328,
  * [36] D. Stahlke, Quantum zero-error source-channel coding and non-commutative graph theory, IEEE Trans. Inform. Theory 62 (2016), no. 1, 554-577.
  * [37] N. Weaver, A “quantum” Ramsey theorem for operator systems, Proc. Amer. Math. Soc. 145 (2017), no. 11, 4595-4605.
  * [38] A. Wehrl, General properties of entropy, Rev. Modern Phys. 50 (1978), no. 2, 221-260.
  * [39] M. M. Wilde, Quantum information theory, Cambridge University Press, Cambridge, 2017.
  * [40] H. S. Witsenhausen, The zero-error side information problem and chromatic numbers, IEEE Trans. Inform. Theory 22 (1976), no. 5, 592-593.


# The Rise of Quantum Internet Computing

Seng W. Loke Seng W. Loke is with the School of Information Technology, Deakin
University, Melbourne, Australia.
E-mail: see https://www.deakin.edu.au/about-deakin/people/seng-loke.Manuscript
received X XX, 20XX; revised X XX, 20XX.

###### Abstract

This article highlights quantum Internet computing as referring to distributed
quantum computing over the quantum Internet, analogous to (classical) Internet
computing involving (classical) distributed computing over the (classical)
Internet. Relevant to quantum Internet computing would be areas of study such
as quantum protocols for distributed nodes using quantum information for
computations, quantum cloud computing, delegated verifiable blind or private
computing, non-local gates, and distributed quantum applications, over
Internet-scale distances.

###### Index Terms:

quantum Internet computing, quantum Internet, distributed quantum computing,
Internet computing, distributed systems, Internet
”This work has been submitted to the IEEE for possible publication. Copyright
may be transferred without notice, after which this version may no longer be
accessible.”

##  1 Introduction

There have been tremendous developments in quantum computing, quantum
cryptography, quantum communications and the quantum Internet, and we have
seen increased investments and intensive research in quantum computing in
recent years [1, 2]. The quantum Internet will not necessarily replace the
(classical) Internet we know and use today, at least not in the near future,
but can complement the current Internet. The quantum Internet aims to enable
robust quantum teleportation (or transmission) of qubits,111A qubit is the
basic unit of quantum information, and can be thought of as a two-state, or
two-levelled, quantum-mechanical system, such as an electron’s spin, where the
two levels are spin up and spin down, or a photon’s polarization, where the
two states are the vertical polarization and the horizontal polarization. and
entanglement among qubits,222Multiple qubits at different sites can share an
entangled state, a superpositon of “specially correlated” states, to be used
in distributed algorithms. over long Internet-scale distances, which are key
to many of the quantum protocols including quantum key distribution, quantum
voting, and others, as well as for non-local control of quantum gates.

There have been efforts to build quantum computers, and it remains to see if
any one paradigm becomes the dominant or best way of building such quantum
computers. At the same time, even as researchers develop more powerful quantum
computers (supporting more qubits for operations, and at lower error rates),
there is an opportunity for connecting multiple quantum computers from
different sites to achieve much more complex quantum computations, i.e.,
inter-linking multiple quantum computers on different sites to perform
distributed computing with a distributed system of quantum computers (or
quantum processing units (QPUs) at different nodes), arriving at the notion of
distributed quantum computing, e.g., [3].

While distributed quantum computing can involve multiple QPUs next to each
other or at the same site, with the quantum Internet, one can envision
distributed quantum computing over nodes geographically far apart. As noted in
[4], the idea is the quantum Internet as the “underlying infrastructure of the
Distributed Quantum Computing ecosystem.”

This article highlights the emerging area of distributed quantum computing
over the quantum Internet, which we refer to as quantum Internet computing,
i.e., the idea of computing using quantumly connected distributed quantum
computers over Internet-scale distances. Hence, quantum Internet computing is
not a new concept in itself but a proposed “umbrella term” used here for the
collection of topics (listed below), from an analogy to (classical) Internet
computing.

Internet computing, where one does distributed computing but over Internet-
scale distances and distributed systems involve nodes connected via the
Internet, is at the intersection of work in (classical) distributed computing
and the (classical) Internet. Analogous to Internet computing, one could ask
the question of what would be at the intersection of work in distributed
quantum computing and work on the quantum Internet, which brings us to the
notion of quantum Internet computing.

Also, while the quantum Internet and distributed quantum computing are still
nascent research areas, there are at least three key topics which can be
considered as relevant to quantum Internet computing:

  * •

distributed quantum computing, including quantum protocols from theoretical
perspectives involving communication complexity studies, and distributed
quantum computing via non-local or distributed quantum gates,

  * •

quantum cloud computing with a focus on delegating quantum computations, blind
quantum computing, and verifying delegated quantum computations, and

  * •

computations and algorithms for the quantum Internet including key ideas such
as quantum entanglement distillation, entanglement swapping, quantum
repeaters, and quantum Internet standards.333For example, see
https://www.ietf.org/archive/id/draft-irtf-qirg-principles-10.html [last
accessed: 1/8/2022]

We briefly discuss the above topics in the following sections.

##  2 Distributed Quantum Computing

Distributed quantum computing problems and quantum protocols have been well-
studied for over two decades, from a theoretical computer science
perspective,444For example, see Buhrman and Röhrig’s paper dating back to
2003: https://link.springer.com/chapter/10.1007/978-3-540-45138-9_1 [last
accessed: 1/8/2022] many of which have their inspiration from classical
distributed computing research. Quantum versions of classical distributed
computing problems and protocols, and new forms of distributed computing using
quantum information, have been explored, e.g., the distributed three-party
product problem, the distributed Deutsch-Jozsa promise problem and the
distributed intersection problem, demonstrating how, for some problems,
quantum information can enable fewer bits of communication to be used for a
solution, and how certain distributed computation problems can be solved with
quantum information, but cannot be solved classically. Many quantum protocols,
including quantum coin flipping, quantum leader election, quantum anonymous
broadcasting, quantum voting, quantum Byzantine Generals, quantum secret
sharing, and quantum oblivious transfer, can be viewed as “quantum versions”
of classical distributed computing problems, and have been studied
extensively.

Another area of study, which has also been considered as distributed quantum
computing, is non-local gates, or the non-local control of quantum gates,
including early work nearly over two decades ago.555For example, see the work
by Yimsiriwattana and Lomonaco Jr. in https://arxiv.org/pdf/quant-
ph/0402148.pdf and a distributed version of Shor’s famous factorization
algorithm https://arxiv.org/abs/2207.05976 [last accessed: 1/8/2022] Key to
performing such non-local control of quantum gates is the use of entanglement,
which can be viewed as a resource for such non-local computations. More recent
work has looked at how to partition the computations of distributed quantum
circuits over multiple QPUs, e.g., [3] as we mentioned earlier - with
considerations including distributing computations in such a way as to
optimize performance and to reduce the requirements on entanglement, since if
the entanglements required are generated at too low a rate, this will hold up
computations. The key motivation here is to inter-link a set of quantum
computers to form effectively a much more powerful quantum computer.

##  3 Quantum Cloud Computing and Delegating Quantum Computations

We have seen big tech companies and startups offering quantum computing as a
service similar to accessing other cloud service offerings, which is a
fantastic resource for experimentation and studies.

More formally, studies into delegating quantum computation from a client
(which can be either classical, or almost classical, i.e., with minimal
capability to perform computations such as teleporting qubits, applying simple
Pauli quantum operations, and doing basic measurements) which is much more
restricted than the server (assumed to be a universal quantum computer) have
been studied, called delegated quantum computing. And when the server is
prevented from knowing the client’s inputs but still can perform delegated
computations, by a technique such as the quantum one-time pad (where the
client applies Pauli operations to add uncertainty from the server’s
perspective, thereby effectively encrypting the quantum inputs it sends to the
server, and keeps track of operations it later needs to decrypt the outputs
from the server), this is called blind quantum computing.

In order to be sure that the server does indeed perform the required quantum
operations delegated to it by the client, the client can embed tests (or test
runs) into the delegated computations, so that the server (not being able to
distinguish between tests and normal computations) can be caught out if it did
not perform the required computations properly. That is, the client can verify
if the server performed the required quantum computations.666An excellent
example is the work by Broadbent at
https://theoryofcomputing.org/articles/v014a011/ [last accessed: 1/8/2022]
Further abstractions for delegating quantum computations with supporting cloud
services continues to be investigated.

##  4 The Quantum Internet

As we mentioned earlier, work on the quantum Internet focuses on how to
efficiently enable robust entanglement shared among qubits over long
geographical distances. If two nodes in different continents share entangled
states, then, this can be a resource to do non-local gates, i.e., to perform
distributed quantum computations, and enable quantum protocols over Internet-
scale distances.

There have been the use of satellites to enable long distance entanglement, as
well as the use of optical fibre cables to demonstrate entanglement. Key to
the quantum Internet are ideas such as entanglement swapping and quantum
repeaters, including ideas such quantum distillation, to achieve high fidelity
distributed entangled states over long distances, and quantum error correction
- this continues to be a research endeavour as mentioned earlier [2].

There are other interesting distributed quantum applications to be considered
including quantum cryptography, quantum sensing, and quantum positioning
systems.

##  5 Distributed Quantum Computing over the Quantum Internet: Quantum
Internet Computing and the Quantum IoT?

Apart from the many quantum computers available over the cloud by big tech and
startups which work at very low temperatures, room temperature quantum
computers have also started to emerge.777See
https://spectrum.ieee.org/nitrogen-vacancy-diamond-quantum-computer-
accelerator-qubits-server-rack and also https://otd.harvard.edu/explore-
innovation/technologies/scalable-room-temperature-solid-state-quantum-
information-processor/ [last accessed: 1/8/2022] This could pave the way for
quantum computers at the fog and at the edge, not just in remote clouds, and
perhaps even mobile quantum computers, or quantum computers embedded into
everyday devices and objects, if ever! Will we then have the quantum Internet
of Things (IoT)? The answer remains to be seen, and “quantum entangled things
across the world” will likely complement the classical IoT. Future
applications and potential of quantum Internet computing remains to be
investigated. Meanwhile, others have begun to look at the connection between
6G networking and the quantum Internet [5].

## References

  * [1] W. Kozlowski and S. Wehner, “Towards large-scale quantum networks,” in _Proceedings of the Sixth Annual ACM International Conference on Nanoscale Computing and Communication_ , ser. NANOCOM ’19. New York, NY, USA: Association for Computing Machinery, 2019. [Online]. Available: https://doi.org/10.1145/3345312.3345497
  * [2] P. P. Rohde, _The Quantum Internet: The Second Quantum Revolution_. Cambridge University Press, 2021.
  * [3] R. Parekh, A. Ricciardi, A. Darwish, and S. DiAdamo, “Quantum algorithms and simulation for parallel and distributed quantum computing,” in _2021 IEEE/ACM Second International Workshop on Quantum Computing Software (QCS)_ , 2021, pp. 9–19.
  * [4] D. Cuomo, M. Caleffi, and A. S. Cacciapuoti, “Towards a distributed quantum computing ecosystem,” _IET Quantum Communication_ , vol. 1, no. 1, pp. 3–8, 2020.
  * [5] C. Wang and A. Rahman, “Quantum-enabled 6g wireless networks: Opportunities and challenges,” _IEEE Wireless Communications_ , vol. 29, no. 1, pp. 58–69, 2022.