# Quantum information theory and
free semialgebraic geometry:
one wonderland through two looking
glasses

Gemma De las Cuevas  Institut für Theoretische Physik, Technikerstr. 21a,
A6020 Innsbruck, Austria  and  Tim Netzer  Institut für Mathematik,
Technikerstr. 13, A6020 Innsbruck, Austria

###### Abstract.

We illustrate how quantum information theory and free (i.e. noncommutative)
semialgebraic geometry often study similar objects from different
perspectives. We give examples in the context of positivity and separability,
quantum magic squares, quantum correlations in non-local games, and positivity
in tensor networks, and we show the benefits of combining the two
perspectives. This paper is an invitation to consider the intersection of the
two fields, and should be accessible for researchers from either field.

Live free or die.
Motto of New Hampshire

##  1\. Introduction

The ties between physics, computer science and mathematics are historically
strong and multidimensional. It has often happened that mathematical
inventions which were mere products of imagination (and thus thought to be
useless for applications) have later played a crucial role in physics or
computer science. A superb example is that of imaginary numbers and their use
in complex Hilbert spaces in quantum mechanics.111Who would have thought that
the square root of $-1$ would have any physical relevance? See [Re21]. Other
examples include number theory and its use in cryptography, or Riemannian
geometry and its role in General Relativity. It is also true that physicists
tend to be only aware of the mathematical tools useful for them — so there are
many branches of mathematics which have not found an outlet in physics.

The relevance of a statement depends on the glass through which we look at it.
There are statements which are mathematically unimpressive but physically very
impressive. A good example is entanglement. Mathematically, the statement that
the positivity cone of the tensor product space is larger than the tensor
product of the local cones is interesting, but not particularly wild or
surprising. Yet, the physical existence of entangled particles is, from our
perspective, truly remarkable. In other words, while the mathematics is easy
to understand, the physics is mind-blowing. This is particularly true
regarding Bell’s Theorem: while it is mathematically not specially deep, we
regard the experimental violation of Bell inequalities [Gi15, He15, Sh15] as
very deep indeed. Another example is the no-cloning theorem — it is
mathematically trivial, yet it has very far-reaching physical consequences. On
the other hand, there are many mathematically impressive statements which are
— so far — physically irrelevant. Finally, there are statements which can be
both mathematically deep and central for quantum information theory, such as
Stinespring’s Dilation Theorem.

Figure 1. Free semialgebraic geometry and quantum information often look at
similar landscapes from different perspectives, as in the fantastic world of
this woodcut by M. C. Escher.

The goal of this paper is to illustrate how two relatively new disciplines in
physics and mathematics — quantum information theory and free semialgebraic
geometry — have a lot in common (Fig. 1). ‘Free’ means noncommutative, because
it is _free of the commutation relation_. So free semialgebraic geometry
studies noncommutative versions of semialgebraic sets. On the other hand,
quantum information theory is (mathematically) a noncommutative generalisation
of classical information theory. So, intuitively, ‘free’ is naturally linked
to ‘quantum’. Moreover, in both fields, positivity plays a very important
role. Semialgebraic geometry examines questions arising from nonnegativity,
like polynomial inequalities. In quantum information theory, quantum states
are represented by positive semidefinite matrices. Positivity also gives rise
to convexity, which is central in both fields, as we will see.

So the two disciplines often study the same mathematical objects from
different perspectives. As a consequence, they often ask different questions.
For example, in quantum information theory, given an element of a tensor
product space, one wants to know whether it is positive semidefinite, and how
this can be efficiently represented and manipulated. In free semialgebraic
geometry, the attention is focused on the geometry of the set of all such
elements (see LABEL:tab:comparison).

Table 1.  Examples of the different approaches of quantum information theory and free semialgebraic geometry in studying essentially the same mathematical objects. The various notions will be explained throughout the paper.  Quantum information theory |  Free semialgebraic geometry
---|---
_Emphasis on the element_ |  _Emphasis on the set_
Given $\rho=\sum_{\alpha}A_{\alpha}\otimes B_{\alpha}$, is it positive semidefinite (psd)? |  Given $\\{A_{\alpha}\\}$, characterise the set of $\\{B_{\alpha}\\}$ such that $\sum_{\alpha}A_{\alpha}\otimes B_{\alpha}$ is psd.
Block positive matrices / Separable psd matrices. |  Largest / smallest operator system over the psd cone.
Every POVM can be dilated to a PVM. |  The free convex hull of the set of PVMs is the set of POVMs.
Can a correlation matrix $p$ be realised by a quantum strategy? |  Is $p$ in the free convex hull of the free independence model?

We believe that much is to be learnt by bridging the gap among the two
communities — in knowledge, notation and perspective. In this paper we hope to
illustrate this point. This paper is thus meant to be accessible for
physicists and mathematicians.

Obviously we are not the first or the only ones to notice these similarities.
In this paper, however, we will mainly concentrate on what we have learnt from
collaborating in recent years, and we will review a few other works. The
selection of other works is not comprehensive and reflects our partial
knowledge. We also remark that quantum information theory and free
semialgebraic geometry are not the only ones studying positivity in tensor
product spaces. _Compositional distributional semantics_ , for example,
represents the meaning of words by positive semidefinite matrices, and the
composition of meanings is thus given by positivity preserving maps — see e.g.
[De20c, Co20].

This article is organised as follows. We will first explain basic concepts in
quantum information theory and free semialgebraic geometry (Section 2) — the
reader familiar with them can skip the corresponding section. Then we will
explain how they are related (Section 3), and we will end with some closing
words (Section 4).

##  2\. Some basic concepts

Here we present some basic concepts in quantum information theory (Section
2.1) and free semialgebraic geometry (Section 2.2).

Throughout the paper we denote the set of $r\times s$ complex matrices by
${\rm Mat}_{r,s}$, the set of $r\times r$ complex matrices by ${\rm Mat}_{r}$,
and we use the identification of ${\rm Mat}_{r}\otimes{\rm Mat}_{s}$ with
${\rm Mat}_{rs}$. We will also often use the real subspace of ${\rm Mat}_{r}$
containing the Hermitian elements, called ${\rm Her}_{r}$, and use that ${\rm
Her}_{r}\otimes{\rm Her}_{s}$ is identified with ${\rm Her}_{rs}$. The
$d$-fold cartesian product of ${\rm Her}_{r}$ is denoted ${\rm Her}_{r}^{d}$.

###  2.1. Basic concepts from quantum information theory

Here we briefly introduce some concepts from quantum information theory. We
focus on finite-dimensional quantum systems of which we do not assume to have
perfect knowledge (in the language of quantum information, these are called
_mixed states_). See, e.g. [wi, Ni00], for a more general overview.

The state of a quantum system is modelled by a normalized positive
semidefinite matrix, i.e. a

$\rho\in{\rm Mat}_{d}\mbox{ with }\rho\succcurlyeq 0\mbox{ and
}\mathrm{tr}(\rho)=1,$

where $\succcurlyeq 0$ denotes positive semidefinite (psd), i.e. Hermitian
with nonnegative eigenvalues, and the trace, $\mathrm{tr}$, is the sum of the
diagonal elements. We reserve the symbol $\geqslant 0$ for nonnegative
numbers. A measurement on the system is modelled by a _positive operator
valued measure_ (POVM), i.e. a set of psd matrices $\tau_{i}$ that sum to the
identity:

$\tau_{1},\ldots,\tau_{n}\in{\rm Mat}_{d}\mbox{ with all }\tau_{i}\succcurlyeq
0\mbox{ and }\sum_{i}\tau_{i}=I_{d}.$

The probability to obtain outcome $i$ on state $\rho$ is given by

(1) $\displaystyle\mathrm{tr}(\rho\tau_{i}).$

Note that these probabilities sum to 1 because of the normalisation condition
on the $\tau_{i}$’s and $\rho$.

When the system is composed of several subsystems, the global state space is
modelled as a tensor product of the local spaces,

(2) $\displaystyle{\rm Mat}_{d}={\rm Mat}_{d_{1}}\otimes\cdots\otimes{\rm
Mat}_{d_{n}},$

where $d=d_{1}\cdots d_{n}$.

A state $\rho$ is called separable (w.r.t. a given tensor product structure)
if it can be written as

$\rho=\sum_{i=1}^{r}\rho_{i}^{(1)}\otimes\cdots\otimes\rho_{i}^{(n)}\quad\mbox{with
all }\rho_{i}^{(j)}\succcurlyeq 0.$

This is obviously a stronger requirement than $\rho$ being psd — not every
$\rho$ is separable. Separable states are not too interesting from a quantum
information perspective: not separable states are called entangled, and
entanglement is necessary for many quantum information tasks.

[width=.5cm,color = darkgray]3

A quantum channel is the most general transformation on quantum states.
Mathematically, it is modelled by a linear trace-preserving map

$T\colon{\rm Mat}_{d}\to{\rm Mat}_{s}$

that is completely positive. Complete positivity means that the maps

${\rm id}_{n}\otimes T\colon{\rm Mat}_{nd}\to{\rm Mat}_{ns}$

are positive (i.e. map psd matrices to psd matrices) for all $n$, where ${\rm
id}_{n}$ is the identity map on ${\rm Mat}_{n}$.

Any linear map $T\colon{\rm Mat}_{d}\to{\rm Mat}_{s}$ is uniquely determined
by its Choi matrix

$C_{T}:=\sum_{i,j=1}^{d}E_{ij}\otimes
T\mathopen{}\mathclose{{}\left(E_{ij}}\right)\in{\rm Mat}_{ds},$

where $E_{ij}$ is the matrix with a 1 in the $(i,j)$-position and 0
elsewhere.222If this is expressed in the so-called computational basis (which
is one specific orthonormal basis), this is written $E_{ij}=|i\rangle\langle
j|$ in quantum information. It is a basic fact that $T$ is completely positive
if and only if $C_{T}$ is psd (see for example [Pau02, Wo11]). Moreover, a
completely positive map $T$ is _entanglement-breaking_ [Ho03] if and only if
$C_{T}$ is a separable matrix, and $T$ is a positive map if and only if
$C_{T}$ is _block positive_ , i.e.

$\mathrm{tr}((\sigma\otimes\tau)C_{T})\geqslant 0\quad\textrm{for all
}\sigma\succcurlyeq 0,\tau\succcurlyeq 0.$

Note that this is weaker than $C_{T}$ being psd, in which case
$\mathrm{tr}(\chi C_{T})\geqslant 0$ for all $\chi\succcurlyeq 0$ (see Table
2). We also remark that this link between positivity notions of linear maps
and their Choi matrices does not involve the normalisation conditions on the
maps (e.g. preserving the trace) or the matrices (e.g. having a given trace).

Linear map | Element in tensor product space
---|---
$T:{\rm Mat}_{d}\to{\rm Mat}_{s}$ | $\rho\in{\rm Mat}_{d}\otimes{\rm Mat}_{s}$
Entanglement-breaking map | Separable matrix
Completely positive map | Positive semidefinite matrix
Positive map | Block positive matrix
Table 2. Correspondence between notions of positivity for linear maps and
their Choi matrices. Entanglement-breaking maps are a subset of completely
positive maps, which are a subset of positive maps. The same is true for the
right column, of course.

###  2.2. Basic concepts from (free) semialgebraic geometry

We now introduce some basic concepts from free (i.e. noncommutative)
semialgebraic geometry. For a slightly more detailed introduction, see [Ne19]
and references therein.

Our setup starts by considering a $\mathbb{C}$-vector space $V$ with an
involution $*$. The two relevant examples are, first, the case where $V$ is
the space of matrices and * is the transposition with complex conjugation —
denoted $\dagger$ in quantum information —, and, second, $\mathbb{C}^{d}$ with
entrywise complex conjugation.

The fixed points of the involution are called self-adjoint, or Hermitian,
elements. We denote the set of Hermitian elements of $V$ by $V_{\rm her}$.
This is an $\mathbb{R}$-subspace of $V$, in which the real things
happen.333Because it is where positivity and other interesting phenomena
happen.

In the _free_ setup, we do not only consider $V$ but also higher levels
thereof. Namely, for any $s\in\mathbb{N}$, we consider the space of $s\times
s$-matrices with entries over $V$,

${\rm Mat}_{s}(V)=V\otimes{\rm Mat}_{s}.$

Recall that ${\rm Mat}_{s}$ refers to $s\times s$-matrices with entries over
$\mathbb{C}$. ${\rm Mat}_{s}(V)$ is a $\mathbb{C}$-vector space with a
‘natural’ involution, consisting of transposing and applying $*$ entrywise.
This thus promotes $V$ and $*$ to an entire hierarchy of levels, namely ${\rm
Mat}_{s}(V)$ for all $s\in\mathbb{N}$ with the just described involution.

We are now ready to define the most general notion of a free real set. This is
nothing but a collection

$\mathcal{C}=\mathopen{}\mathclose{{}\left(C_{s}}\right)_{s\in\mathbb{N}}$

where each $C_{s}\subseteq{\rm Mat}_{s}(V)_{\rm her}=:{\rm Her}_{s}(V)$. We
call $C_{s}$ the set at level $s$.

To make things more interesting, one often imposes conditions that connect the
levels. One important example is free convexity, which is defined as follows.
For any

$\tau_{i}\in C_{t_{i}}\quad\mbox{with}\quad i=1,\ldots,n,$

and

(3) $\displaystyle v_{i}\in{\rm
Mat}_{t_{i},s}\quad\mbox{with}\quad\sum_{i=1}^{n}v_{i}^{*}v_{i}=I_{s},$

it holds that

(4) $\displaystyle\sum_{i=1}^{n}v_{i}^{*}\tau_{i}v_{i}\in C_{s}.$

Note that in (4) matrices over the complex numbers (namely $v_{i}$) are
multiplied with matrices over $V$ (namely $\tau_{i}$). This is defined as
matrix multiplication in the usual way for $v_{i}^{*}\tau_{i}v_{i}$, and using
that elements of $V$ can be multiplied with complex numbers and added. For
example, for $n=1$, $t=2$, $s=1$, $\tau=(\mu_{i,j})$ with $\mu_{i,j}\in V$ for
$i=1,2$, and $v=(\lambda_{1},\lambda_{2})^{t}$ with
$\lambda_{i}\in\mathbb{C}$, we have

$v^{*}\tau v=\sum_{i,j}\bar{\lambda}_{i}\lambda_{j}\mu_{i,j}.$

Note that if free convexity holds, then every $C_{s}$ is a convex set in the
real vector space ${\rm Her}_{s}(V)$. But free convexity is generally a
stronger condition than ‘classical’ convexity, as we will see.

In addition, a conic version of free convexity is obtained when giving up the
normalization condition on the $v_{i}$, i.e. the right hand side of Eq. (3).
In this case, $\mathcal{C}$ is called an abstract operator system (usually
with the additional assumption that every $C_{s}$ is a proper convex cone).

[width=.5cm,color = darkgray]3

Now, free semialgebraic sets are free sets arising from polynomial
inequalities. This will be particularly important for the connection we hope
to illustrate in this paper. In order to define these, take $V=\mathbb{C}^{d}$
with the involution provided by entrywise conjugation, so that $V_{\rm
her}=\mathbb{R}^{d}$. Let $z_{1},\ldots,z_{d}$ denote free variables, that is,
noncommuting variables. We can imagine each $z_{i}$ to represent a matrix of
_arbitrary size_ — later we will substitute $z_{i}$ by a matrix of a given
size, and this size will correspond to the level of the free semialgebraic
set.

Now let $\omega$ be a finite _word_ in the letters $z_{1},\ldots,z_{d}$, that
is, an ordered tuple of these letters. For example, $\omega$ could be
$z_{1}z_{1}z_{4}$ or $z_{4}z_{5}z_{4}$. In addition, let
$\sigma_{\omega}\in{\rm Mat}_{m}$ be a matrix (of some fixed size $m$) that
specifies the coefficients of word $\omega$; this is called the coefficient
matrix. A matrix polynomial in the free variables $z_{1},\ldots,z_{d}$ is an
expression

$p=\sum_{\omega}\sigma_{\omega}\otimes\omega,$

where the sum is over all finite words $\omega$, and where only finitely many
coefficient matrices $\sigma_{\omega}$ are nonzero.

We denote the reverse of word $\omega$ by $\omega^{*}$. For example, if
$\omega=z_{1}z_{2}z_{3}$ then $\omega^{*}=z_{3}z_{2}z_{1}$. In addition,
$(\sigma_{\omega})^{*}$ is obtained by transposition and complex conjugation
of $\sigma_{\omega}.$ If the coefficient matrices fulfill

(5) $\displaystyle(\sigma_{\omega})^{*}=\sigma_{\omega^{*}},$

then for any tuple of Hermitian matrices $(\tau_{1},\ldots,\tau_{d})\in{\rm
Her}_{s}^{d}$ we have that

$p(\tau_{1},\ldots,\tau_{d})=\sum_{\omega}\sigma_{\omega}\otimes\omega(\tau_{1},\ldots,\tau_{d})\in{\rm
Her}_{ms}.$

That is, $p$ evaluated at the Hermitian matrices $\tau_{1},\ldots,\tau_{d}$ is
a Hermitian matrix itself.

So, for a given matrix polynomial $p$ satisfying condition (5), we define the
free semialgebraic set at level $s$ as the set of Hermitian matrices of size
$s$ such that $p$ evaluated at them is psd:

$C_{s}(p):=\mathopen{}\mathclose{{}\left\\{(\tau_{1},\ldots,\tau_{d})\in{\rm
Her}_{s}^{d}\mid p(\tau_{1},\ldots,\tau_{d})\succcurlyeq 0}\right\\}.$

Finally we define the free semialgebraic set as the collection of all such
levels:

$\mathcal{C}(p):=\mathopen{}\mathclose{{}\left(C_{s}(p)}\right)_{s\in\mathbb{N}}.$

For example, let $E_{ii}$ denote the matrix with a 1 in entry $(i,i)$ and 0
elsewhere. Then the matrix polynomial

$p=\sum_{i=1}^{d}E_{ii}\otimes z_{i}$

defines the following free semialgebraic set at level $s$

$C_{s}(p)=\mathopen{}\mathclose{{}\left\\{(\tau_{1},\ldots,\tau_{d})\in{\rm
Her}_{s}^{d}\mid
E_{11}\otimes\tau_{1}+\ldots+E_{dd}\otimes\tau_{d}\succcurlyeq 0}\right\\}.$

The positivity condition is equivalent to $\tau_{i}\succcurlyeq 0$ for all
$i$, which gives this free set the name free positive orthant. Note that for
$s=1$, the ‘free’ variables become real numbers,

$C_{1}(p)=\mathopen{}\mathclose{{}\left\\{(a_{1},\ldots,a_{d})\in\mathbb{R}^{d}\mid
a_{i}\geqslant 0\>\>\forall i}\right\\},$

which defines the positive orthant in $d$ dimensions.

It is easy to see that any free semialgebraic set is closed under direct sums,
meaning that if $(\tau_{1},\ldots,\tau_{d})\in C_{s}(p)$,
$(\chi_{1},\ldots,\chi_{d})\in C_{r}(p)$ then

$(\tau_{1}\oplus\chi_{1},\ldots,\tau_{d}\oplus\chi_{d})\in C_{r+s}(p),$

where $\tau_{i}\oplus\chi_{i}$ denotes the block diagonal sum of two Hermitian
matrices. This is because
$p(\tau_{1}\oplus\chi_{1},\ldots\tau_{d}\oplus\chi_{d})=p(\tau_{1},\ldots\tau_{d})\oplus
p(\chi_{1},\ldots\chi_{d}),$ which is psd if and only if each of the terms is
psd.

Note also that a semialgebraic set is a Boolean combination of $C_{1}(p_{i})$
for a finite set of polynomials $p_{i}$. A ‘free semialgebraic set’ is thus a
noncommutative generalisation thereof, with the difference that usually a
single polynomial $p$ is considered.

[width=.5cm,color = darkgray]3

A very special case of free semialgebraic sets are _free spectrahedra_ , which
arise from linear matrix polynomials. A linear matrix polynomial is a matrix
polynomial where every word $\omega$ depends only on one variable, i.e.

$\ell=\sigma_{0}\otimes 1+\sum_{i=1}^{d}\sigma_{i}\otimes z_{i}$

with 1 being the empty word, and all $\sigma_{i}\in{\rm Her}_{m}$. The
corresponding free set at level $s$ is given by

$C_{s}(\ell)=\mathopen{}\mathclose{{}\left\\{(\tau_{1},\ldots,\tau_{d})\in{\rm
Her}_{s}^{d}\mid\sigma_{0}\otimes
I_{s}+\sum_{i=1}^{d}\sigma_{i}\otimes\tau_{i}\succcurlyeq 0}\right\\}$

and $\mathcal{C}(\ell)$ is called a free spectrahedron. The first level set,

$C_{1}(\ell)=\mathopen{}\mathclose{{}\left\\{(a_{1},\ldots,a_{d})\in\mathbb{R}^{d}\mid\sigma_{0}+a_{1}\sigma_{1}+\cdots+a_{d}\sigma_{d}\succcurlyeq
0}\right\\},$

is known as a classical spectrahedron, or simply, a spectrahedron (see Fig. 2
for some three-dimensional spectrahedra). If all $\sigma_{i}$ are diagonal in
the same basis, then the spectrahedron $C_{1}(\ell)$ becomes a polyhedron.
(Intuitively, polyhedra have flat facets whereas the borders of spectrahedra
can be round, as in Fig. 2.) Thus, every polyhedron is a spectrahedron, but
not vice versa.

While the linear image (i.e. the _shadow_) of a polyhedron is a polyhedron,
the shadow of a spectahedron need not be a spectahedron. The forthcoming book
[NP] presents a comprehensive treatment of spectrahedra and their
shadows.444Shadows can be very different from the actual thing, as this shadow
art by Kumi Yamashita shows.

Figure 2. Some three-dimensional spectrahedra taken from [NP]. Spectrahedra
are convex sets described by a linear matrix inequality, and polyhedra are
particular cases of spectrahedra.

##  3\. One wonderland through two looking glasses

Let us now explain some recent results that illustrate how concepts and
methods from the two disciplines interact. We will focus on positivity and
separability (Section 3.1), quantum magic squares (Section 3.2), non-local
games (Section 3.3), and positivity in tensor networks (Section 3.4).

###  3.1. Positivity and separability

For fixed $d,s\in\mathbb{N}$ consider the set of states and separable states
in ${\rm Mat}_{d}\otimes{\rm Mat}_{s}$, namely ${\rm State}_{d,s}$ and ${\rm
Sep}_{d,s}$, respectively. Both sets are closed in the real vector space ${\rm
Her}_{d}\otimes{\rm Her}_{s}$. Moreover, both are semialgebraic, since ${\rm
State}_{d,s}$ is a classical spectrahedron, and ${\rm Sep}_{d,s}$ can be
proven to be semialgebraic using the projection theorem/quantifier elimination
in the theory of real closed fields (see, e.g., [PD01]).

It has long been known that ${\rm Sep}_{d,s}$ is a strict subset of ${\rm
State}_{d,s}$ whenever $d,s>1$. A recent work by Fawzi [Faw19], building on
Scheiderer’s [Sc18], strengthens this result, by showing that the geometry of
these two sets is significantly different:

######  Theorem 1 ([Faw19]).

If $d+s>5$ then ${\rm Sep}_{d,s}$ is not a spectrahedral shadow.

Recall that a spectahedral shadow is the linear image of a spectrahedron.

Together with the relations of Table 2, it follows from the previous result
that the corresponding sets of linear maps $T:{\rm Mat}_{d}\to{\rm Mat}_{s}$
satisfy that:

  * (i)

Entanglement-breaking maps form a convex semialgebraic set which is not a
spectrahedral shadow,

  * (ii)

Completely positive maps form a spectrahedron, and

  * (iii)

Positive maps form a convex semialgebraic set which is not a spectrahedral
shadow. This follows from (i), the duality of positive maps and entanglement-
breaking maps, and the fact that duals of spectrahedral shadows are also
spectrahedral shadows [NP].

Let us now consider the set of states and separable states as free sets.
Namely, for fixed $d\geqslant 1$ let

${\rm State}_{d}:=\mathopen{}\mathclose{{}\left({\rm
State}_{d,s}}\right)_{s\in\mathbb{N}}\quad\mbox{ and }\quad{\rm
Sep}_{d}:=\mathopen{}\mathclose{{}\left({\rm
Sep}_{d,s}}\right)_{s\in\mathbb{N}}.$

This is a particular case of the setup described above, where $V={\rm
Mat}_{d}$ and the involution is provided by $\dagger$. Moreover, both sets
satisfy the condition of free convexity (Eq. (4)). In addition, ${\rm
State}_{d}$ is a free spectrahedron, whereas ${\rm Sep}_{d}$ is not, since for
fixed $s$ it is not even a classical spectrahedral shadow at level $s$ due to
Theorem 1.

Viewing states as free sets also leads to an easy conceptual proof of the
following result [D19], which was first proven by Cariello [Car].

######  Theorem 2 ([D19, Car]).

For arbitrary $d,s\in\mathbb{N}$, if $\rho\in{\rm State}_{d,s}$ is of tensor
rank $2$, i.e. it can be written as

(6) $\displaystyle\rho=\sigma_{1}\otimes\tau_{1}+\sigma_{2}\otimes\tau_{2},$

where $\sigma_{i}$ and $\tau_{i}$ are Hermitian, then it is separable.

Note that $\sigma_{i}$ and $\tau_{i}$ need not be psd. Let us sketch the proof
of [D19] to illustrate the method.

###### Proof.

Consider the linear matrix polynomial $\ell=\sigma_{1}\otimes
z_{1}+\sigma_{2}\otimes z_{2}$, where $\sigma_{1},\sigma_{2}$ are given in Eq.
(6). The fact that $\rho$ is a state means that the corresponding free set of
level $s$ contains $(\tau_{1},\tau_{2})$:

$(\tau_{1},\tau_{2})\in C_{s}(\ell).$

At level one, the spectrahedron $C_{1}(\ell)$ is a convex cone in
$\mathbb{R}^{2}$. A convex cone in the plane must be a _simplex cone_ , i.e. a
cone whose number of extreme rays equals the dimension of the space. In
$\mathbb{R}^{2}$ this means that the cone is spanned by two vectors,

$C_{1}(\ell)={\rm cone}\\{v_{1},v_{2}\\},$

where $v_{1},v_{2}\in\mathbb{R}^{2}$. When the cone at level one is a simplex
cone, the free convex cone is fully determined [ev, FNT].

In addition, the sets

$T_{s}:=\mathopen{}\mathclose{{}\left\\{v_{1}\otimes\eta_{1}+v_{2}\otimes\eta_{2}\mid
0\preccurlyeq\eta_{i}\in{\rm Her}_{s}}\right\\}$

also give rise to a free convex cone
$\mathopen{}\mathclose{{}\left(T_{s}}\right)_{s\in\mathbb{N}}$, and we have
that $T_{1}=C_{1}(\ell)$.

These two facts imply that $T_{s}=C_{s}(\ell)$ for all $s\in\mathbb{N}$. Using
a representation for $(\tau_{1},\tau_{2})$ in $T_{s}$, and substituting into
Eq. (6) results in a separable decomposition of $\rho$. ∎

The crucial point in the proof is that when the cone at level one is a simplex
cone, the free convex cone is fully determined. This is not a very deep
insight — it can easily be reduced to the case of the positive orthant, where
it is obvious.

Note that the separable decomposition of $\rho$ obtained in the above proof
contains only two terms — in the language of [D19, DN], $\rho$ has separable
rank 2.

[width=.5cm,color = darkgray]3

References [BN1, BN2] also propose to use free spectrahedra to study some
problems in quantum information theory, but from a different perspective.
Given $d$ Hermitian matrices $\sigma_{1},\ldots,\sigma_{d}\in{\rm Her}_{m}$,
one would like to know whether they fulfill

$0\preccurlyeq\sigma_{i}\preccurlyeq I_{m},$

because this implies that each $\sigma_{i}$ gives rise to the binary POVM
consisting of $\sigma_{i},I_{m}-\sigma_{i}$. In addition, one would like to
know whether $\sigma_{1},\ldots,\sigma_{d}$ are jointly measurable, meaning
that these POVMs are the marginals of one POVM (see [BN1] for an exact
definition).

Now use $\sigma_{1},\ldots,\sigma_{d}$ to construct the linear matrix
polynomial

$\ell:=I_{m}\otimes 1-\sum_{i=1}^{d}(2\sigma_{i}-I_{m})\otimes z_{i}$

and consider its free spectrahedron
$\mathcal{C}(\ell)=\mathopen{}\mathclose{{}\left(C_{s}(\ell)}\right)_{s\in\mathbb{N}}.$
Define the matrix diamond as the free spectrahedron
$\mathcal{D}=\mathopen{}\mathclose{{}\left(D_{s}}\right)_{s\in\mathbb{N}}$
with

$D_{s}:=\mathopen{}\mathclose{{}\left\\{(\tau_{1},\ldots,\tau_{d})\in{\rm
Her}_{s}^{d}\mid I_{s}-\sum_{i=1}^{d}\pm\tau_{i}\succcurlyeq 0}\right\\},$

where all possible choices of signs $\pm$ are taken into account. Note that
$D_{1}$ is just the unit ball of $\mathbb{R}^{d}$ in $1$-norm, which explains
the name diamond. Note also that $D_{1}\subseteq S_{1}(\ell)$ is equivalent to
$0\preccurlyeq\sigma_{i}\preccurlyeq I_{m}$ for all $i=1,\ldots,d$. Since
these finitely many conditions can be combined into a single linear matrix
inequality (using diagonal blocks of matrix polynomials), $\mathcal{D}$ is
indeed a free spectrahedron. The following result translates the joint
measurability to the containment of free spectrahedra:

######  Theorem 3 ([BN1]).

$\sigma_{1},\ldots,\sigma_{d}$ are jointly measurable if and only if
$\mathcal{D}\subseteq\mathcal{C}(\ell)$.

That one free spectrahedron is contained in another,
$\mathcal{D}\subseteq\mathcal{C}(\ell)$, means that each of their
corresponding levels satisfy the same containment, i.e. $D_{s}\subseteq
C_{s}(\ell)$ for all $s\in\mathbb{N}$.

The containment of spectrahedra and free spectrahedra has received
considerable attention recently [bental, hecp, hedi, FNT, PSS]. One often
studies inclusion constants for containment, which determine how much the
small spectrahedron needs to be shrunk in order to obtain inclusion. In [BN1,
BN2] this is used to quantify the degree of incompatibility, and to obtain
lower bounds on the joint measurability of quantum measurements.

###  3.2. Quantum magic squares

Let us now look at magic squares and their quantum cousins.

A magic square is a $d\times d$-matrix with positive entries such that every
row and column sums to the same number (see Fig. 3 for two beautiful
examples.) A doubly stochastic matrix is a $d\times d$-matrix with real
nonnegative entries, in which each row and each column sums to $1$. So doubly
stochastic matrices contain a probability measure in each row and each column.
For example, dividing every entry of Dürer’s magic square by 34 results in a
doubly stochastic matrix. Now, the set of doubly stochastic matrices forms a
polytope, whose vertices consist of the permutation matrices, i.e. doubly
stochastic matrices with a single 1 in every row and column and 0 elsewhere
(that is, permutations of the identity matrix). This is the content of the
famous Birkhoff–von Neumann Theorem.

Figure 3. (Left) The magic square on the façade of the Sagrada Família in
Barcelona, where every row and column adds to 33. (Right) The magic square in
Albrecht Dürer’s lithograph _Melencolia I_ , where every row and column adds
to 34.

A ‘quantum’ generalization of a doubly stochastic matrix is obtained by
putting a POVM (defined in Section 2.1) in each row and each column of a
$d\times d$-matrix. This defines a quantum magic square [D20]. That is, in
passing from doubly stochastic matrices to quantum magic squares, we promote
the nonnegative numbers to psd matrices. The normalisation conditions on the
numbers (that they sum to 1) become the normalisations of the POVM (that they
sum to the identity matrix).

What is a quantum generalisation of a permutation matrix? Permutation matrices
only contain 0s and 1s, so in passing to the quantum version, we promote 0 and
1 to orthogonal projectors (given that 0 and 1 are the only numbers that
square to themselves). The relevant notion is thus that of a _projection
valued measure_ (PVM), in which each measurement operator
$\tau_{1},\ldots,\tau_{d}$ is an orthogonal projection,
$\tau_{i}^{2}=\tau_{i}$. Quantum permutation matrices are magic squares
containing a PVM in each row and column [Ba].555 See the closely related
notion of _quantum Latin squares_ [Mu16, Ho20], which in essence are quantum
permutation matrices with rank 1 projectors.

While PVMs are a special case of POVMs, every POVM dilates to a PVM (see,
e.g., [Pau02]):

######  Theorem 4 (Naimark’s Dilation Theorem).

Let $\tau_{1},\ldots,\tau_{d}$ (of size $m\times m$) form a POVM. Then there
exists a PVM $\sigma_{1},\ldots,\sigma_{d}$ (of size $n\times n$, for some
$n$) and a matrix $v\in{\rm Mat}_{n,m}$ such that

$v^{*}\sigma_{i}v=\tau_{i}\mbox{ for all }i=1,\ldots,d.$

In terms of free sets, this theorem states that _the free convex hull of the
set of PVMs is precisely the set of POVMs_. Both sets are free semialgebraic,
and the POVMs even form a free spectrahedron.

Through the glass of free semialgebraic geometry, quantum magic squares form a
free spectrahedron over the space $V={\rm Mat}_{d}$, equipped with entrywise
complex conjugation as an involution. Level $s$ corresponds to POVMs with
matrices of size $s\times s$, and thus level 1 corresponds to doubly
stochastic matrices. We thus recover the magic in the classical world at level
1, and we have an infinite tower of levels on top of that expressing the
quantum case.

Furthermore, quantum permutation matrices form a free semialgebraic set whose
first level consists of permutation matrices. The ‘classical magic’ is thus
again found at level 1, and the quantum magic is expressed in an infinite
tower on top of it.

Now, recall that the Birkoff–von Neumann theorem says that the convex hull of
the set of permutation matrices is the set of doubly stochastic matrices. So
the permutation matrices are the vertices of the polytope of doubly stochastic
matrices. In the light of the towers of quantum magic squares and quantum
permutation matrices, this theorem fully characterises what happens at level
one. We ask whether a similar characterisation is possible for the quantum
levels: _Is the free convex hull of quantum permutation matrices equal to the
set of quantum magic squares?_

This question can be phrased in terms of dilations as follows. By Naimark’s
Dilation Theorem we know that every POVM dilates to a PVM. The question is
whether this also holds for a two-dimensional array of POVMs, i.e. whether
every square of POVMs can dilated to a square of PVMs. The non-trivial part is
that the dilation must work simultaneously for all POVMs in the rows and
columns. The two-dimensional version of Naimark’s Dilation Theorem can thus be
phrased as: _Does every quantum magic square dilate to a quantum permutation
matrix?_

The answer to these questions is ‘no’: these quantum generalisations fail to
be true in the simplest nontrivial case. This means that there must exist very
strange (and thus very interesting) quantum magic squares:

######  Theorem 5 ([D20]).

For each $d\geqslant 3$, the free convex hull of the free semialgebraic set of
$d\times d$ quantum permutation matrices is strictly contained in the free
spectrahedron of quantum magic squares. This strict containment already
appears at level $s=2$.

The latter statement means that there is a $d\times d$-matrix with POVMs of
size $2\times 2$ in each row and column which does not dilate to a matrix with
a PVM in each row and column.

In words, the tower of quantum levels does not admit the same kind of ‘easy’
characterisation as level one or the case of a single POVM — at least not the
natural generalisations we have considered here. This is yet another sign of
the richer structure of the quantum world compared to the classical one.

###  3.3. Non-local games and quantum correlations

Consider a game with two players, Alice and Bob, and a referee. The referee
chooses a question randomly from finite sets $\mathcal{Q}_{A}$ and
$\mathcal{Q}_{B}$ for Alice and Bob, respectively, and sends them to Alice and
Bob. Upon receiving her question, Alice chooses from a finite set
$\mathcal{A}_{A}$ of answers, and similarly Bob chooses his answer from the
finite set $\mathcal{A}_{B}$. They send their answers to the referee, who
computes a winning function

$w\colon\mathcal{Q}_{A}\times\mathcal{Q}_{B}\times\mathcal{A}_{A}\times\mathcal{A}_{B}\to\\{0,1\\}$

to determine whether they win or lose the game (value of $w$ being 1 or 0,
respectively).

During the game, Alice and Bob know both the winning function $w$ and the
probability measure on $\mathcal{Q}_{A}\times\mathcal{Q}_{B}$ used by the
referee to choose the questions. So before the game starts Alice and Bob agree
on a joint strategy. However, during the game Alice and Bob are ‘in separate
rooms’ (or in separate galaxies) so they cannot communicate. In particular,
Alice will not know Bob’s question and vice versa. In order to find the
strategy that maximises the winning probability, Alice and Bob have to solve
an optimisation problem.666Thus, strictly speaking, this is not a game in the
game-theoretic sense, but (just) an optimisation problem.

What kind of strategies may Alice and Bob choose? It depends on the resources
they have. First, in a classical deterministic strategy, both Alice and Bob
reply deterministically to each of their questions, and they do so
independently of each other. This is described by two functions

$c_{A}\colon\mathcal{Q}_{A}\to\mathcal{A}_{A}\quad\mbox{ and }\quad
c_{B}\colon\mathcal{Q}_{B}\to\mathcal{A}_{B},$

which specify which answer Alice and Bob give to each question.

Slightly more generally, in a classical randomised strategy, Alice and Bob’s
answers are probabilistic, but still independent of each other. This is
described by

$r_{A}\colon\mathcal{Q}_{A}\to\mathcal{\rm Pr}(\mathcal{A}_{A})\quad\mbox{ and
}\quad r_{B}\colon\mathcal{Q}_{B}\to\mathcal{\rm Pr}(\mathcal{A}_{B}),$

where ${\rm Pr}(S)$ denotes the set of probability measures on the set $S$.
Namely, if Alice receives question $a$, the probability that she answers $x$
is given by $r_{A}(a)(x)$, where $r_{A}(a)$ is the probability measure on
$\mathcal{A}_{A}$ corresponding to question $a$. Similarly, Bob answers $y$ to
$b$ with probability $r_{B}(b)(y)$. Since Alice and Bob answer independently
of each other, the joint probability of answering $x,y$ upon questions $a,b$
is the product of the two,

(7) $\displaystyle p(x,y\mid a,b)=r_{A}(a)(x)\cdot r_{B}(b)(y).$

Finally, a quantum strategy allows them to share a bipartite state
$\rho\in{\rm State}_{d,s}$. The questions determine which measurement to apply
to their part of the state, and the measurement outcomes determine the
answers. This is described by functions

(8) $\displaystyle q_{A}\colon\mathcal{Q}_{A}\to{\rm
POVM}_{d}(\mathcal{A}_{A})\quad\mbox{ and }\quad
q_{B}\colon\mathcal{Q}_{B}\to{\rm POVM}_{s}(\mathcal{A}_{B})$

whose image is the set of POVMs with matrices of size $d\times d$ and $s\times
s$, respectively, on the respective sets of answers. The probability that
Alice answers $x$ upon receiving $a$ is described by $q_{A}(a)(x)$, which is
the psd matrix that the POVM $q_{A}(a)$ assigns to answer $x$. Similarly,
Bob’s behaviour is modelled by $q_{B}(b)(y)$. Since they act independently of
each other, this is described by the tensor product of the two. Using rule
(1), we obtain that their joint probability is given by

(9) $\displaystyle p(x,y\mid
a,b)=\mathrm{tr}\mathopen{}\mathclose{{}\left(\rho\mathopen{}\mathclose{{}\left(q_{A}(a)(x)\otimes
q_{B}(b)(y)}\right)}\right).$

Now, the table of conditional probabilities

$\mathopen{}\mathclose{{}\left(p(x,y\mid
a,b)}\right)_{(a,b,x,y)\in\mathcal{Q}_{A}\times\mathcal{Q}_{B}\times\mathcal{A}_{A}\times\mathcal{A}_{B}}$

is called the correlation matrix  of the respective strategy. For any given
kind of strategy, the set of correlation matrices is the feasible set of the
optimisation problem that Alice and Bob have to solve. The objective function
of this optimisation problem is given by the winning probability. Since this
objective function is linear in the correlation matrix entries, one can
replace the feasible set by its convex hull.

The important fact is that quantum strategies cannot be reproduced by
classical randomised strategies:

######  Theorem 6 ([Be, Cl69]).

If at least $2$ questions and $2$ answers exist for both Alice and Bob, the
convex hull of correlation matrices of classical randomised strategies is
strictly contained in the set of correlation matrices of quantum strategies.

For classical randomised strategies, passing to the convex hull has the
physical interpretation of including a _hidden variable_. The latter is a
variable whose value is unknown to us, who are describing the system, and it
is usually denoted $\lambda$. However, this mysterious variable $\lambda$ is
shared between Alice and Bob, and it will determine the choice of their POVMs
together with their respective questions $a,b$. This is the physical
interpretation of the convex hull

$p(x,y\mid a,b)=\sum_{\lambda}q_{\lambda}\>r_{A}(a,\lambda)(x)\cdot
r_{B}(b,\lambda)(y),$

where $q_{\lambda}$ is the probability of the hidden variable taking the value
$\lambda$. For example, we can imagine that Alice and Bob are listening to a
radio station which plays songs from a certain list, but this is a ‘private’
radio station to which we have no access. The song at the moment of playing
the game (i.e. receiving the questions) will determine the value of $\lambda$
(i.e. $\lambda$ is an index of that list).

Theorem 6 thus states that quantum strategies cannot be emulated by classical
strategies, even if we take into account ‘mysterious’ hidden variables.

[width=.5cm,color = darkgray]3

Let us now approach these results from the perspective of free sets. Assume
for simplicity that all four sets
$\mathcal{Q}_{A},\mathcal{Q}_{B},\mathcal{A}_{A},\mathcal{A}_{B}$ have two
elements. A quantum strategy consists of a state $\rho\in{\rm State}_{d,s}$
and the following psd matrices for Alice and Bob, respectively, satisfying
this normalisation condition:

(10) $\displaystyle\begin{split}&\sigma_{j}^{(i)}\succcurlyeq 0\mbox{ and
}\tau_{j}^{(i)}\succcurlyeq 0\\\ &\mbox{such that
}\sum_{j}\sigma_{j}^{(i)}=I_{d}\mbox{ and
}\sum_{j}\tau_{j}^{(i)}=I_{s},\end{split}$

where $i,j=1,2$. The superscript refers to the questions and the subscript to
the answers. The correlation matrix is given by

$\mathopen{}\mathclose{{}\left(\mathrm{tr}\mathopen{}\mathclose{{}\left(\rho\>\mathopen{}\mathclose{{}\left(\sigma_{k}^{(i)}\otimes\tau_{l}^{(j)}}\right)}\right)}\right)_{i,j,k,l}.$

Using the spectral decomposition of $\rho=\sum_{r}v_{r}v_{r}^{*}$, it can be
written as

(11)
$\displaystyle\mathopen{}\mathclose{{}\left(\sum_{r}v_{r}^{*}\mathopen{}\mathclose{{}\left(\sigma_{k}^{(i)}\otimes\tau_{l}^{(j)}}\right)v_{r}}\right)_{i,j,k,l},$

where $v_{r}\in\mathbb{C}^{d}\otimes\mathbb{C}^{s}$ and
$\sum_{r}v_{r}^{*}v_{r}=1$. Through the looking glass of free semialgebraic
geometry, this is first level of a free convex hull. To see this, define the
free set $\mathcal{I}$ as

(12) $\displaystyle\mathcal{I}=\bigcup_{d,s\geq
1}\mathopen{}\mathclose{{}\left\\{\mathopen{}\mathclose{{}\left(\sigma_{k}^{(i)}\otimes\tau_{l}^{(j)}}\right)_{i,j,k,l}\in{\rm
Mat}_{4}({\rm Mat}_{d}\otimes{\rm Mat}_{s})\mid\sigma_{k}^{(i)}\mbox{and
}\tau_{l}^{(j)}\mbox{satisfy }\eqref{eq:normsigmatau}}\right\\}$

(Note that the 4 is due the fact that we have 2 questions and 2 answers; more
generally we would have a matrix of size
$|\mathcal{Q}_{A}||\mathcal{Q}_{B}|\times|\mathcal{A}_{A}||\mathcal{A}_{B}|$.
Note also that the ordering of questions and answers of Alice and Bob is
irrelevant for the following discussion.)

If we look at level 1 of this free set, we encounter that $I_{1}$ is the
subset of ${\rm Mat}_{4}(\mathbb{R})$ consisting precisely of the correlation
matrices of classical randomized strategies. In other words, when $d=s=1$, the
formula coincides with that of (7). Furthermore, higher levels of this free
set contain the tensor products of POVMs of Alice and Bob in the corresponding
space ${\rm Mat}_{d}$ and ${\rm Mat}_{s}.$ Since $I_{1}$ is called the
independence model in algebraic statistics [Dr], we call $\mathcal{I}$ the
free independence model, since this is the natural noncommutative
generalisation of independent strategies.

Let us now consider the free convex hull of $\mathcal{I}$. First of all,
computing the conditional probabilities of a pair of POVMs with a given state
$\rho$ corresponds to compressing to level 1 with the vectors $\\{v_{r}\\}$
given by the spectral decomposition of $\rho$, as in (11). So _the set of
quantum correlations is the first level of the free convex hull of the free
independence model._

We thus encounter an interesting phenomenon: the free convex hull of a free
set can be larger than the classical convex hull at a fixed level.
Specifically, the convex hull of $I_{1}$ is the set of classical correlations,
whereas the free convex hull of $\mathcal{I}$ at level 1 is the set of quantum
correlations, which are different by Theorem 6. In fact, wilder things can
happen: fractal sets can arise in the free convex hull of free semialgebraic
sets [al]. We wonder what these results imply for the corresponding quantum
information setup.

Now, in the free convex hull of $\mathcal{I}$, what do higher levels
correspond to? Compressing to lower levels (i.e. with smaller $ds$)
corresponds to taking the partial trace with a psd matrix of size smaller than
$ds$. This results in 4 psd matrices (one for each $i,j,k,l$), each of size
$<ds$, and which not need be an elementary tensor product.

What about ‘compressing’ to higher levels? Any compression to a higher level
can be achieved by direct sums of the POVMs of Alice and Bob and a compression
to a lower level as we just described. The number of elements in this direct
sum is precisely $n$ in (4). Another way of seeing that the direct sum is
needed is by noting that, if $n=1$, the matrices $v_{i}$ cannot fulfill the
normalisation condition on the right hand side of (4). In quantum information
terms, this says that a POVM in a given dimension cannot be transformed to a
POVM in a larger dimension by means of an isometry, because the terms will sum
to a projector instead of the identity.

Let us make two final remarks. The first one is that $\mathcal{I}$ is not a
free semialgebraic set, for the simple reason that it is not closed under
direct sums (which is a property of these sets, as we saw in Section 2.2), as
is easily checked.

The second remark is that the free convex hull of the free independence model
is not closed. This follows from the fact that, at level 1, this free convex
hull fails to be closed, as shown in [sl] and for smaller sizes in [dy].

######  Theorem 7 ([sl, dy]).

For at least $5$ questions and $2$ answers, the set of quantum correlation
matrices is not closed.

In our language, this implies that the level $ds$ — which is to be compressed
to level 1 in the construction of the free convex hull — cannot be upper
bounded. That is, the higher $ds$ the more things we will obtain in its
compression to level 1.

In the recent preprint [Fu21] the membership problem in the closure of the set
of quantum correlations is shown to be undecidable, for a fixed (and large
enough) size of the sets of questions and answers.

[width=.5cm,color = darkgray]3

A computational approach to quantum correlations, comparable to sums-of-
squares and moment relaxation approaches in polynomial optimisation [blek,
NP], is the NPA-hierarchy [NPA1, NPA2, NPA3]. We briefly describe the approach
here, omitting technical details. Assume one is given a table

$p=\mathopen{}\mathclose{{}\left(p(x,y\mid
a,b)}\right)_{(a,b,x,y)\in\mathcal{Q}_{A}\times\mathcal{Q}_{B}\times\mathcal{A}_{A}\times\mathcal{A}_{B}},$

and the task is to check whether it is the correlation matrix of a quantum
strategy. The NPA hierarchy provides a family of necessary conditions, each
more stringent than the previous one, for $p$ to be a quantum strategy.

In order to understand the NPA hierarchy, we will first _assume_ that $p$ is a
correlation matrix, i.e. there is a state $\rho$ and strategies such that (9)
holds. We will use this state and strategies to define a positive functional
on a certain algebra. Namely, we consider the game $*$-algebra

$\mathcal{G}:=\mathbb{C}\langle\mathcal{Q}_{A}\times\mathcal{A}_{A},\mathcal{Q}_{B}\times\mathcal{A}_{B}\rangle.$

This is an algebra of polynomials in certain noncommuting variables.
Explicitly, for each question and answer pair from Alice and Bob, $(a,x)$ and
$(b,y)$, there is an associated self-adjoint variable, $z_{(a,x)}$ and
$z_{(b,y)}$, respectively. $\mathcal{G}$ consists of all polynomials with
complex coefficients in these variables; for example, the monomial
$z_{(a,x)}z_{(b,y)}\in\mathcal{G}$. Now, _if we had the strategy
$\rho,q_{A},q_{B}$_ we could construct a linear functional

$\varphi\colon\mathcal{G}\to\mathbb{C}$

by evaluating the variables $z_{(a,x)}$ and $z_{(b,y)}$ at the psd matrices
$q_{A}(a)(x)\otimes I_{s}$ and $I_{d}\otimes q_{B}(b)(y)$, respectively, and
computing the trace inner product with the state $\rho$. So, in particular,
evaluating $\varphi$ at the monomial $z_{(a,x)}z_{(b,y)}$ would yield

(13) $\displaystyle\varphi(z_{(a,x)}z_{(b,y)})$ $\displaystyle={\rm
tr}\mathopen{}\mathclose{{}\left(\rho\mathopen{}\mathclose{{}\left(\mathopen{}\mathclose{{}\left(q_{A}(a)(x)\otimes
I_{s}}\right)\cdot\mathopen{}\mathclose{{}\left(I_{d}\otimes
q_{B}(b)(y)}\right)}\right)}\right)$ (14) $\displaystyle=p(x,y\mid a,b).$

The crucial point is that $\varphi$ evaluated at this monomial needs to have
the value $p(x,y\mid a,b)$ _for any strategy_ realising $p$. In other words,
the linear constraint on $\varphi$ expressed in Equation (14) must hold even
if we do not know the strategy. This functional must satisfy other nice
properties independently of the strategy too, such as being positive.

This perspective is precisely the one we now take. Namely, we assume that the
strategy $\rho,q_{A},q_{B}$ is not given (since our question is whether $p$ is
a quantum strategy at all), and we search for a functional on $\mathcal{G}$
that has the stated properties (or other properties, depending on the kind of
strategies one is looking for). When restricted to a finite-dimensional
subspace of $\mathcal{G}$, this becomes a semidefinite optimisation problem,
as can be easily checked. The dimension of this subspace will be the parameter
indicating the level of the hierarchy, which is gradually increased.
Solvability of all these semidefinite problems is thus a necessary condition
for $p$ to be a quantum correlation matrix. In words, the levels of the NPA
hierarchy form an outer approximation to the set of correlations. Conversely,
if all/many of these problems are feasible, one can apply a (truncated)
Gelfand-Naimark-Segal (GNS) construction (see for example [Pau02]) to the
obtained functional, and thereby try to construct a quantum strategy that
realises $p$. This is the content of the NPA hierarchy from the perspective of
free semialgebraic geometry.

###  3.4. Positivity in tensor networks

Let us finally explain some results about positivity in tensor networks. The
results are not as much related to free semialgebraic geometry as to
positivity and sums of squares, as we will see.

Since the state space of a composite quantum system is given by the tensor
product of smaller state spaces (Eq. (2)), the global dimension $d$ grows
exponentially with the number of subsystems $n$. Very soon it becomes
infeasible to work with the entire space — to describe $n=270$ qubits
$d_{i}=2$, we would need to deal with a space dimension $d\sim 2^{270}\sim
10^{80}$, the estimated number of atoms in the Universe. To describe anything
at the macro-scale involving a mole of particles, $\sim 10^{23}$, we would
need a space dimension of $\sim 2^{{10}^{23}}$, which is much larger than a
googol ($10^{100}$), but smaller than a googolplex ($10^{10^{100}}$). These
absurd numbers illustrates how quickly the Hilbert space description becomes
impractical — in practice, it works well for a few tens of qubits.777The lack
of scalability of this description is far from being a unique case in physics
— most theories are not scalable. One needs to find the new relevant degrees
of freedom at the new scale, which will define an emergent theory.

Fortunately, many physically relevant states admit an efficient description.
The ultimate reason is that physical interactions are local (w.r.t. a
particular tensor product decomposition; this decomposition typically reflects
spatial locality). The resulting relevant states admit a description using
only a few terms for every local Hilbert space. The main idea of tensor
networks is precisely to use a few matrices for every local Hilbert space
${\rm Mat}_{d_{i}}$ (Eq. (2); see, e.g., [Or18, Ci20]).

Now, this idea interacts with _positivity_ in a very interesting way (Fig. 4).
Positivity is a property in the global space ${\rm Mat}_{d}$ which cannot be
easily translated to positivity properties in the local spaces. As we will
see, there is a ‘tension’ between using a few matrices for each local Hilbert
space and representing the positivity locally. This mathematical interplay has
implications for the description of quantum many-body systems, among others.

Figure 4. The notion of positivity gives rise to convexity, which gives rise
to many surprising effects when interacting with the multiplicity of systems,
as in this lithograph by M. C. Escher.

Let us see one example of a tensor network decomposition where this
_positivity problem_ appears. To describe a mixed state in one spatial
dimension with periodic boundary conditions we use the matrix product density
operator form (MPDO) of $\rho$,

$\rho=\sum_{i_{1},\ldots,i_{n}=1}^{r}\rho_{i_{1},i_{2}}^{(1)}\otimes\rho_{i_{2},i_{3}}^{(2)}\otimes\cdots\otimes\rho_{i_{n},i_{1}}^{(n)}.$

The smallest such $r$ is called the operator Schmidt rank of $\rho$ [Ve04b,
Zw04]. Clearly, every state admits an MPDO form, and the ones with small $r$
can be handled efficiently. But how is the positivity of $\rho$ reflected in
the local matrices? Clearly, if all local matrices are psd (i.e.
$\rho_{ij}^{(k)}\succcurlyeq 0$) then $\rho$ will be psd. But some sums of
non-psd matrices will also give rise to a global psd matrix, since negative
subspaces may cancel in the sum. Can one easily characterise the set of local
matrices whose sum is psd? The short answer is ‘no’.

For further reference, if all local matrices are psd, so that $\rho$ is
separable, the corresponding $r$ is called the separable rank  of $\rho$ [DN,
DHN].

To obtain a local certificate of positivity, we first express
$\rho=\xi\xi^{*}$ (which is possible only if $\rho$ is psd) and then apply the
tensor network ‘philosophy’ to $\xi$, i.e. express $\xi$ as an MPDO:

$\rho=\xi\xi^{*}\quad\mbox{ with
}\quad\xi=\sum_{i_{1},\ldots,i_{n}=1}^{r}\xi_{i_{1},i_{2}}^{(1)}\otimes\xi_{i_{2},i_{3}}^{(2)}\otimes\cdots\otimes\xi_{i_{n},i_{1}}^{(n)}.$

This is the local purification form of $\rho$. Note that there are many $\xi$
that satisfy $\rho=\xi\xi^{*}$, as $\xi$ need not be Hermitian or a square
matrix (it could be a column vector). The smallest $r$ among all such $\xi$ is
called the purification rank of $\rho$.

The interesting point for the purposes of this paper is that the purification
rank is a _noncommutative generalisation_ of the positive semidefinite rank of
a nonnegative matrix. There are many more such connections: the separable
rank, the translational invariant (t.i.) purification rank, and the t.i.
separable rank are noncommutative generalisations of the nonnegative rank, the
cpsd rank and the cp rank of nonnegative matrices, respectively [DN]. As a
matter of fact, this connection holds in much greater generality, as we will
explain below. In all of these cases, the ranks coincide for quantum states
that are diagonal in the computational basis.

From our perspective, this connection is beneficial for both sides. For
example, for quantum many-body systems, this insight together with the results
by [GPT] leads to the following result:

######  Theorem 8 ([DSPC, DN]).

The purification rank cannot be upper bounded by a function of the operator
Schmidt rank only. The separable rank cannot be upper bounded by a function of
the purification rank only.

(It is worth noting these separations are not robust, as they disappear in the
approximate case for certain norms [De20].)

Conversely, the quantum perspective provides a natural and well-motivated path
for generalisation of the ‘commutative’ results about cpsd rank, cp rank, etc.
For example, in [GPT] it is shown that the extension complexity of a polytope
w.r.t. a given cone is given by the rank of the slack matrix of that polytope
w.r.t. that cone. We wonder whether this result could be generalisation to the
noncommutative world. This would give a _geometric_ interpretation of the
purification rank, the separable rank and their symmetric versions, perhaps as
extension complexities of some objects.

[width=.5cm,color = darkgray]3

Symmetry is a central property in physics, both conceptually and practically.
Conceptually, symmetry is the other side of the coin of a conserved quantity
(by Noether’s theorem). Practically, it allows for more efficient mathematical
descriptions, as symmetric objects have fewer degrees of freedom. For example,
in the above context, $\rho$ is translational invariant if it remains
unchanged under cyclic permutations of the local systems. This raises the
question: is there an MPDO form that explicitly expresses this symmetry? For
example, the following form does,

$\rho=\sum_{i_{1},\ldots,i_{n}=1}^{r}\rho_{i_{1},i_{2}}\otimes\rho_{i_{2},i_{3}}\otimes\cdots\otimes\rho_{i_{n},i_{1}},$

because it uses the same matrices on every site, and the arrangement of
indices is such that a cyclic permutation of the local systems does not change
$\rho$. But does this hold for other symmetries too?

The existence of such _invariant decompositions_ and their corresponding ranks
has been studied in a very general framework [DHN]. Explicitly, every tensor
decomposition is represented as a simplicial complex, where the individual
tensor product spaces are associated to the vertices, and the summation
indices to the facets. The symmetry is modelled by a group action on the
simplicial complex. The central result is that an invariant decomposition
exists if the group action is free on the simplicial complex [DHN]. Just to
give one example, if $\rho\in{\rm Mat}_{d}\otimes{\rm Mat}_{d}$ is separable
and symmetric, it will in general not admit a decomposition of the type

$\rho=\sum_{\alpha}\rho_{\alpha}\otimes\rho_{\alpha}\quad\mbox{with all
}\rho_{\alpha}\mbox{ psd,}$

but it will have one of the type

$\rho=\sum_{\alpha,\beta}\rho_{\alpha,\beta}\otimes\rho_{\beta,\alpha}\quad\mbox{with
all }\rho_{\alpha,\beta}\mbox{ psd}.$

From the perspective of our framework, this is due the fact that the group
permuting the two end points of an edge does not act freely on the edge
connecting them. But this group action can be made free if the two points are
connected by two edges, leading to the two indices $\alpha,\beta$ in the above
sum. This is one example of a _refinement_ of a simplicial complex, which
makes the action of the group free [DHN].

Finally, we remark that this framework of tensor decompositions with
invariance can not only be applied to quantum-many body systems, but to any
object in a tensor product space. One example are multivariate symmetric
polynomials with positivity conditions [Kl21].

[width=.5cm,color = darkgray]3

A related question is the existence of invariant decompositions _uniform_ in
the system size. Namely, given a tensor
$\rho=\mathopen{}\mathclose{{}\left(\rho_{\alpha,\beta}}\right)_{\alpha,\beta=1,\ldots,r}$
with all $\rho_{\alpha,\beta}\in{\rm Mat}_{d}$, define

$\tau_{n}(\rho):=\sum_{i_{1},\ldots,i_{n}=1}^{r}\rho_{\alpha_{1},\alpha_{2}}\otimes\rho_{\alpha_{2},\alpha_{3}}\otimes\cdots\otimes\rho_{\alpha_{n},\alpha_{1}}\in{\rm
Mat}_{d^{n}}$

for all $n\in\mathbb{N}$. The result, in this case, is very different from the
fixed $n$ case:

######  Theorem 9 ([DCCW]).

Let $d,r\geqslant 7$. Then it is undecidable whether
$\tau_{n}(\rho)\succcurlyeq 0$ for all $n\in\mathbb{N}$.

Using this result it can be shown that a translationally invariant local
purification of $\tau_{n}(\rho)$ _uniform in the system size_ need not exist
[DCCW].

The proof of this theorem uses a reduction from the matrix mortality problem.
In the latter, given a finite set of matrices $M_{\alpha}\in{\rm
Mat}_{d}(\mathbb{Z})$, one is asked whether there is a word $w$ such that
$0=M_{w_{1}}\cdots M_{w_{n}}\in{\rm Mat}_{d}(\mathbb{Z})$. While this problem
is noncommutative (because matrix multiplication is), the problem about
$\tau_{n}(\rho)$ is ‘more’ noncommutative. Intuitively, if all
$\rho_{\alpha,\beta}$ are diagonal, we recover a version of the matrix
mortality problem. Note also that the space where $\tau_{n}(\rho)$ lives grows
with $n$, in contrast to the matrix mortality problem.

The decidability of a similar problem can be studied for more general
algebras. In that case, $\rho_{\alpha,\beta}$ is in a certain algebra, and
$\tau_{n}(\rho)$ is asked to be in a certain cone [Gr21].

[width=.5cm,color = darkgray]3

Let us finally explain a computational approach for the finite case. So
consider $n$ fixed and recall that after specifying some local matrices
$\rho_{i}^{(j)}$, one wants to know whether

$\rho=\sum_{i}\rho_{i}^{(1)}\otimes\cdots\otimes\rho_{i}^{(n)}$

is psd. Since the $n$ is fixed, this problem is decidable, but computing and
diagonalising $\rho$ is impossible for large values of $n$ (in fact it is NP-
hard [Kl14]). So one has to come up with a different idea. What can be
computed are certain moments of $\rho$, i.e. the numbers
$\mathrm{tr}(\rho^{k})$ for small enough $k$. This follows from the
observation that the moments only require local matrix products,

$\mathrm{tr}(\rho^{k})=\sum_{i_{1},\ldots,i_{k}=1}^{r}\mathrm{tr}\mathopen{}\mathclose{{}\left(\rho_{i_{1}}^{(1)}\cdots\rho_{i_{k}}^{(1)}}\right)\cdots\mathrm{tr}\mathopen{}\mathclose{{}\left(\rho_{i_{1}}^{(n)}\cdots\rho_{i_{k}}^{(n)}}\right).$

These few moments can then be used to compute optimal upper and lower bounds
on the distance of $\rho$ to the cone of psd matrices [D20/2]. Specifically,
to compute this distance it suffices to compare $\rho$ with $f(\rho)$, where
$f\colon\mathbb{R}\to\mathbb{R}$ is the function that leaves the positive
numbers unchanged, and sets the negative numbers to zero. We then approximate
$f$ by polynomial functions $q$ of low degree, so that $\mathrm{tr}(q(\rho))$
only uses a few moments of $\rho$. The best results were obtained with certain
sums of squares approximations, which can be computed with a linear or
semidefinite optimisation.

##  4\. Closing words

We have illustrated how quantum information theory and free semialgebraic
geometry often study very similar mathematical objects from different
perspectives. We have given the examples of positivity and separability
(Section 3.1), quantum magic squares (Section 3.2), non-local games (Section
3.3), and positivity in tensor networks (Section 3.4). In all of these cases,
we have tried to illustrate how results can be transferred among the two
fields, and how this can be beneficial for the two perspectives. As mentioned
in the introduction, there are many similar such connections which have not
been covered here.

Going back to New Hampshire’s motto, we conclude that it is undecidable to
determine whether to live free or die, because both the question of whether
matrices generate a free semigroup and the matrix mortality problem are
undecidable.

_Acknowledgements_.— GDLC acknowledges support from the Austrian Science Fund
(FWF) with projects START Prize Y1261-N and the Stand Alone project P33122-N.
TN acknowledges support from the Austrian Science Fund (FWF) with Stand Alone
project P29496-N35.

## References

@article{al}

  * AUTHOR = Alekseev, V., AUTHOR = Netzer, T., AUTHOR= Thom, A., TITLE = Quadratic modules, $C^{*}$-algebras, and free convexity, JOURNAL = Trans. Amer. Math. Soc., FJOURNAL = Transactions of the American Mathematical Society, VOLUME = 372, NUMBER = 11, PAGES = 7525–7539, YEAR = 2019,
@book{arv}

  * AUTHOR = Arveson, W., TITLE = An invitation to $C^{*}$-algebras, NOTE = Graduate Texts in Mathematics, No. 39, PUBLISHER = Springer-Verlag, New York-Heidelberg, YEAR = 1976, PAGES = x+106,
BanicaT.BichonJ.CollinsB.Quantum permutation groups: a surveyNoncommutative
harmonic analysis with applications to probabilityBanach Center Publ.78Polish
Acad. Sci. Inst. Math., Warsaw13–342007@incollection{Ba, author = {Banica,
T.}, author = {Bichon, J.}, author = {Collins, B.}, title = {Quantum
permutation groups: a survey}, booktitle = {Noncommutative harmonic analysis
with applications to probability}, series = {Banach Center Publ.}, volume =
{78}, pages = {13–34}, publisher = {Polish Acad. Sci. Inst. Math., Warsaw},
year = {2007}} @article{Be}

  * AUTHOR = Bell, J. S., TITLE = On the Einstein Podolsky Rosen paradox, JOURNAL = Phys. Phys. Fiz., FJOURNAL = Physics Physique Fizika, VOLUME = 1, YEAR = 1964, NUMBER = 3, PAGES = 195–200,
Ben-TalA.NemirovskiA.On tractable approximations of uncertain linear matrix
inequalities affected by interval uncertaintySIAM J. Optim.SIAM Journal on
Optimization1220023811–833@article{bental, author = {Ben-Tal, A.}, author =
{Nemirovski, A.}, title = {On tractable approximations of uncertain linear
matrix inequalities affected by interval uncertainty}, journal = {SIAM J.
Optim.}, fjournal = {SIAM Journal on Optimization}, volume = {12}, year =
{2002}, number = {3}, pages = {811–833}} @book{blek}

  * TITLE = Semidefinite optimization and convex algebraic geometry, SERIES = MOS-SIAM Series on Optimization, VOLUME = 13, EDITOR = Blekherman, G., EDITOR = Parrilo, P. A., EDITOR =Thomas, R. R., PUBLISHER = SIAM, Philadelphia, PA, YEAR = 2013, PAGES = xx+476,
@article{BN1}

  * AUTHOR = Bluhm, A., AUTHOR =Nechita, I., TITLE = Joint measurability of quantum effects and the matrix diamond, JOURNAL = J. Math. Phys., FJOURNAL = Journal of Mathematical Physics, VOLUME = 59, YEAR = 2018, NUMBER = 11, PAGES = 112202,
@article{BN2}

  * AUTHOR = Bluhm, A., AUTHOR = Nechita, I., TITLE = Compatibility of quantum measurements and inclusion constants for the matrix jewel, JOURNAL = SIAM J. Appl. Algebra Geom., FJOURNAL = SIAM Journal on Applied Algebra and Geometry, VOLUME = 4, YEAR = 2020, NUMBER = 2, PAGES = 255,
ChoiM. D.Positive semidefinite biquadratic formsLinear Algebra Appl.Linear
Algebra and its Applications121975295–100@article{Ch75, author = {Choi, M.\
D.}, title = {Positive semidefinite biquadratic forms}, journal = {Linear
Algebra Appl.}, fjournal = {Linear Algebra and its Applications}, volume =
{12}, year = {1975}, number = {2}, pages = {95–100}} CarielloD.Separability
for weak irreducible matricesQuantum Inf. Comput.1420141308@article{Car,
author = {Cariello, D.}, title = {Separability for weak irreducible matrices},
journal = {Quantum Inf. Comput.}, number = {14}, year = {2014}, pages =
{1308}} author=Perez-Garcia, D. author=Schuch, N. author=Verstraete, F.Cirac,
I.arXiv:2011.12127Matrix Product States and Projected Entangled Pair States:
Concepts, Symmetries, and Theorems2020@article{Ci20, author = {{Cirac, I.}
author={Perez-Garcia, D.} author={Schuch, N.} author={Verstraete, F.}},
journal = {arXiv:2011.12127}, title = {{Matrix Product States and Projected
Entangled Pair States: Concepts, Symmetries, and Theorems}}, year = {2020}}
author=Horne, M. A. author=Shimony, A. author=Holt, R. A.Clauser, J. F.Phys.
Rev. Lett.880Proposed Experiment to Test Local Hidden-Variable
Theories231969@article{Cl69, author = {{Clauser, J. F.} author={Horne, M. A.}
author={Shimony, A.} author={Holt, R. A.}}, journal = {Phys. Rev. Lett.},
pages = {880}, title = {{Proposed Experiment to Test Local Hidden-Variable
Theories}}, volume = {23}, year = {1969}} author= Meichanetzidis, K.Coecke,
B.arXiv:2001.00862Meaning updating of density matrices2020@article{Co20,
author = {{Coecke, B.} author= {Meichanetzidis, K.}}, journal =
{arXiv:2001.00862}, title = {{Meaning updating of density matrices}}, year =
{2020}} De las CuevasG.SchuchN.Perez-GarciaD.CiracJ. I.Purifications of
multipartite states: limitations and constructive methodsNew J.
Phys.151230212013@article{DSPC, author = {De las Cuevas, G.}, author =
{Schuch, N.}, author = {Perez-Garcia, D.}, author = {Cirac, J.\ I.}, title =
{Purifications of multipartite states: limitations and constructive methods},
journal = {New J.\ Phys.}, volume = {15}, pages = {123021}, year = {2013}} De
las CuevasG.CubittT. S.CiracJ. I.WolfM. M.Pérez-GarcíaD.Fundamental
limitations in the purifications of tensor networksJ. Math. Phys.Journal of
Mathematical Physics5720167071902@article{DCCW, author = {De las Cuevas, G.},
author = {Cubitt, T.\ S.}, author = {Cirac, J.\ I.}, author = {Wolf, M.\ M.},
author = {P\'{e}rez-Garc\'{\i}a, D.}, title = {Fundamental limitations in the
purifications of tensor networks}, journal = {J. Math. Phys.}, fjournal =
{Journal of Mathematical Physics}, volume = {57}, year = {2016}, number = {7},
pages = {071902}} De las CuevasG.DrescherT.NetzerT.Separability for mixed
states with operator schmidt rank twoQuantum32019203@article{D19, author = {
De las Cuevas, G.}, author = { Drescher, T.}, author = {Netzer, T.}, title =
{Separability for Mixed States with Operator Schmidt Rank Two}, journal =
{Quantum}, number = {3}, year = {2019}, pages = {203}} De las
CuevasG.DrescherT.NetzerT.Quantum magic squares: Dilations and their
limitationsJ. Math. Phys.J. Math. Phys.61202011111704@article{D20, author =
{De las Cuevas, G.}, author = {Drescher, T.}, author = {Netzer, T.}, title =
{Quantum magic squares: {D}ilations and their limitations}, journal = {J.
Math. Phys.}, fjournal = {J. Math. Phys.}, volume = {61}, year = {2020},
number = {11}, pages = {111704}} De las CuevasG.FritzT.NetzerT.Optimal bounds
on the positivity of a matrix from a few momentsComm. Math.
Phys.Communications in Mathematical Physics37520201105–126@article{D20/2,
author = {De las Cuevas, G.}, author = { Fritz, T.}, author = {Netzer, T.},
title = {Optimal bounds on the positivity of a matrix from a few moments},
journal = {Comm. Math. Phys.}, fjournal = {Communications in Mathematical
Physics}, volume = {375}, year = {2020}, number = {1}, pages = {105–126}}
@article{Gr21}

  * author=De las Cuevas, G., author = Graf, J., author=Netzer, T., journal = In preparation, title = Computational complexity of algebras in a chain, year = 2021
De las CuevasG.Hoogsteder RieraM.NetzerT.Tensor decompositions on simplicial
complexes with invariancearXiv:1909.017372019@article{DHN, author = {De las
Cuevas, G.}, author = {Hoogsteder Riera, M.}, author = {Netzer, T.}, title =
{Tensor decompositions on simplicial complexes with invariance}, journal =
{arXiv:1909.01737}, year = {2019}} @article{De20c}

  * author = De las Cuevas, G author=Klingler, A. author=Lewis, M. author=Netzer, T., journal = arXiv:2005.14134, mendeley-groups = Biblio-IST, title = Cats climb entail mammals move: preserving hyponymy in distributional semantics, year = 2020
@article{De20}

  * arxivId = 2004.10219, author = De las Cuevas, G. author =Klingler, A. author=Netzer, T., journal = arXiv:2004.10219, title = Approximate tensor decompositions: disappearance of many separations, year = 2020
De las CuevasG.KlinglerA.NetzerT.In preparationGeneral polynomial
decompositions with invariance and positivity2021@article{Kl21, author = {De
las Cuevas, G.}, author = {Klingler, A.}, author = {Netzer, T.}, journal = {In
preparation}, title = {{General polynomial decompositions with invariance and
positivity}}, year = {2021}} @article{DN}

  * AUTHOR = De las Cuevas, G., AUTHOR = Netzer, T., TITLE = Mixed states in one spatial dimension: decompositions and correspondence with nonnegative matrices, JOURNAL = J. Math. Phys., FJOURNAL = Journal of Mathematical Physics, VOLUME = 61, YEAR = 2020, NUMBER = 4, PAGES = 041901,
@book{Dr}

  * AUTHOR = Drton, M., AUTHOR=Sturmfels, B., AUTHOR=Sullivant, S., TITLE = Lectures on algebraic statistics, SERIES = Oberwolfach Seminars, VOLUME = 39, PUBLISHER = Birkhäuser Verlag, Basel, YEAR = 2009, PAGES = viii+171,
@article{dy}

  * AUTHOR = Dykema, K., AUTHOR=Paulsen, V. I., AUTHOR=Prakash, J., TITLE = Non-closure of the set of quantum correlations via graphs, JOURNAL = Comm. Math. Phys., FJOURNAL = Communications in Mathematical Physics, VOLUME = 365, YEAR = 2019, NUMBER = 3, PAGES = 1125–1142,
@article{ev}

  * AUTHOR = Evert, E. AUTHOR = Helton, J. W., AUTHOR=Klep, I., AUTHOR=McCullough, S., TITLE = Extreme points of matrix convex sets, free spectrahedra, and dilation theory, JOURNAL = J. Geom. Anal., FJOURNAL = Journal of Geometric Analysis, VOLUME = 28, YEAR = 2018, NUMBER = 2, PAGES = 1373–1408,
FawziH.The set of separable states has no finite semidefinite representation
except in dimension 3x2arXiv:1905.025752019@article{Faw19, author = {Fawzi,
H.}, title = {The set of separable states has no finite semidefinite
representation except in dimension 3x2}, journal = {arXiv:1905.02575}, year =
{2019}} author=Miller, C. A. author=Slofstra, W.Fu, H.arXiv:2101.11087The
membership problem for constant-sized quantum correlations is
undecidable2021@article{Fu21, author = {{Fu, H.} author={Miller, C. A.}
author={Slofstra, W.}}, journal = {arXiv:2101.11087}, title = {{The membership
problem for constant-sized quantum correlations is undecidable}}, year =
{2021}} FritzT.NetzerT.ThomA.Spectrahedral containment and operator systems
with finite-dimensional realizationSIAM J. Appl. Algebra Geom.SIAM Journal on
Applied Algebra and Geometry120171556–574@article{FNT, author = {Fritz, T.},
author = {Netzer, T.}, author = {Thom, A.}, title = {Spectrahedral containment
and operator systems with finite-dimensional realization}, journal = {SIAM J.
Appl. Algebra Geom.}, fjournal = {SIAM Journal on Applied Algebra and
Geometry}, volume = {1}, year = {2017}, number = {1}, pages = {556–574}}
@article{Gi15}

  * author = Giustina, M. author=Versteegh, M. A. M. author=Wengerowsky, S. author=Handsteiner, J. author=Hochrainer, A. author=Phelan, K. author=Steinlechner, F. author=Kofler, J. author=Larsson, J.-Å. author=Abellán, C. author=Amaya, W. author=Pruneri, V. author=Mitchell, M. W. author=Beyer, J. author=Gerrits, T. author=Lita, A. E. authr=Shalm, L. K. author=Nam, S. W. author=Scheidl, T. author=Ursin, R. author=Wittmann, B. author=Zeilinger, A., journal = Phys. Rev. Lett., pages = 250401, title = Significant-Loophole-Free Test of Bell’s Theorem with Entangled Photons, volume = 115, year = 2015
@article{GPT}

  * AUTHOR = Gouveia, J., AUTHOR = Parrilo, P. A., AUTHOR = Thomas, R. R., TITLE = Lifts of convex sets and cone factorizations, JOURNAL = Math. Oper. Res., FJOURNAL = Mathematics of Operations Research, VOLUME = 38, YEAR = 2013, NUMBER = 2, PAGES = 248–264,
HeltonJ. W.KlepI.McCulloughS.The matricial relaxation of a linear matrix
inequalityMath. Program.Mathematical Programming. A Publication of the
Mathematical Programming Society13820131-2, Ser. A401–445@article{hecp, author
= {Helton, J. W.}, author = {Klep, I.}, author = {McCullough, S.}, title =
{The matricial relaxation of a linear matrix inequality}, journal = {Math.
Program.}, fjournal = {Mathematical Programming. A Publication of the
Mathematical Programming Society}, volume = {138}, year = {2013}, number =
{1-2, Ser. A}, pages = {401–445}} HeltonJ.
W.KlepI.McCulloughS.SchweighoferM.Dilations, linear matrix inequalities, the
matrix cube problem and beta distributionsMem. Amer. Math.
Soc.25720191232106@article{hedi, author = {Helton, J. W.}, author = {Klep,
I.}, author = {McCullough, S.}, author = {Schweighofer, M.}, title =
{Dilations, linear matrix inequalities, the matrix cube problem and beta
distributions}, journal = {Mem. Amer. Math. Soc.}, volume = {257}, year =
{2019}, number = {1232}, pages = {106}} author=Bernien, H. author=Dréau, A. E.
author=Reiserer, A. author=Kalb, N. author=Blok, M. S. author=Ruitenberg, J.
author=Vermeulen, R. F. L. author=Schouten, R. N. author=Abellán, C.
author=Amaya, W. author=Pruneri, V. author=Mitchell, M. W. author=Markham, M.
author=Twitchen, D. J. author=Elkouss, D. author=Wehner, S. author=Taminiau,
T. H. author=Hanson, R.Hensen, B.Nature682Loophole-free Bell inequality
violation using electron spins separated by 1.3
kilometres5262015@article{He15, author = {{Hensen, B.} author={Bernien, H.}
author={Dr{\'{e}}au, A. E.} author={Reiserer, A.} author={Kalb, N.}
author={Blok, M. S.} author={Ruitenberg, J.} author={Vermeulen, R. F. L.}
author={Schouten, R. N.} author={Abell{\'{a}}n, C.} author={Amaya, W.}
author={Pruneri, V.} author={Mitchell, M. W.} author={Markham, M.}
author={Twitchen, D. J.} author={Elkouss, D.} author={Wehner, S.}
author={Taminiau, T. H.} author={Hanson, R.}}, journal = {Nature}, pages =
{682}, title = {{Loophole-free Bell inequality violation using electron spins
separated by 1.3 kilometres}}, volume = {526}, year = {2015}}
HorodeckiM.author=Ruskai, M. B.Shor, P. W.Rev. Math. Phys.629Entanglement
breaking channels152003@article{Ho03, author = {Horodecki, M.}, author =
{{Shor, P. W.} author={Ruskai, M. B.}}, journal = {Rev. Math. Phys.}, pages =
{629}, title = {Entanglement Breaking Channels}, volume = {15}, year = {2003}}
author = Rudnicki, Ł. author = Życzkowski, K.Horodecki, P.arXiv:2002.03233Five
open problems in quantum information2020@article{Ho20, author = {{Horodecki,
P.} author = {Rudnicki, {\L}.} author = {\\.{Z}yczkowski, K.}}, journal =
{arXiv:2002.03233}, title = {{Five open problems in quantum information}},
year = {2020}} KlieschM.GrossD.EisertJ.Phys. Rev. Lett.160503Matrix product
operators and states: NP-hardness and undecidability1132014@article{Kl14,
author = {Kliesch, M.}, author = {Gross, D.}, author = {Eisert, J.}, journal =
{Phys. Rev. Lett.}, pages = {160503}, title = {{Matrix product operators and
states: NP-hardness and undecidability}}, volume = {113}, year = {2014}}
author =Vicary, J.Musto, B.Quantum Inf. Comput.1318Quantum Latin squares and
unitary error bases162016@article{Mu16, author = {{Musto, B.} author ={Vicary,
J.}}, journal = {Quantum Inf. Comput.}, pages = {1318}, title = {{Quantum
Latin squares and unitary error bases}}, volume = {16}, year = {2016}}
NavascuésM.PironioS.AcínA.Bounding the set of quantum correlationsPhys. Rev.
Lett.980104012007@article{NPA1, author = {Navascu\'{e}s, M.}, author =
{Pironio, S.}, author = {Ac\'{i}n, A.}, title = {Bounding the set of quantum
correlations}, journal = {Phys. Rev. Lett.}, volume = {98}, pages = {010401},
year = {2007}} NavascuésM.PironioS.AcínA.A convergent hierarchy of
semidefinite programs characterizing the set of quantum correlationsNew J.
Phys.100730132008@article{NPA2, author = {Navascu\'{e}s, M.}, author =
{Pironio, S.}, author = {Ac\'{i}n, A.}, title = {A convergent hierarchy of
semidefinite programs characterizing the set of quantum correlations}, journal
= {New J. Phys.}, volume = {10}, pages = {073013}, year = {2008}}
@article{NPA3}

  * AUTHOR = Navascués, M., AUTHOR = Vértesi, T., TITLE = Bounding the set of finite dimensional quantum correlations, JOURNAL = Phys. Rev. Lett., FJOURNAL = Physical Review Letters, VOLUME = 115, YEAR = 2015, PAGES = 020501,
NetzerT.Free semialgebraic geometryInternat. Math.
Nachrichten24031–412019@article{Ne19, author = {Netzer, T.}, title = {Free
Semialgebraic Geometry}, journal = {Internat. Math. Nachrichten}, number =
{240}, pages = {31–41}, year = {2019}} =Plaumann, D.Netzer, T. AUTHORGeometry
of linear matrix inequalitiesForthcoming2021@book{NP, author = {{Netzer, T.}
AUTHOR ={Plaumann, D.}}, title = {Geometry of Linear Matrix Inequalities},
note = {Forthcoming}, year = {2021}} author=Chuang, I. L.Nielsen, M.
A.Cambridge University PressQuantum Computation and Quantum
Information2000@book{Ni00, author = {{Nielsen, M. A.} author={Chuang, I. L.}},
publisher = {Cambridge University Press}, title = {{Quantum Computation and
Quantum Information}}, year = {2000}} OrúsR.Tensor networks for complex
systemsNat. Rev. Phys.1538–5502019@article{Or18, author = {Or\'us, R.}, title
= {Tensor networks for complex systems}, journal = {Nat. Rev. Phys.}, volume =
{1}, pages = {538–550}, year = {2019}} @article{PSS}

  * AUTHOR = Passer, B., AUTHOR = Shalit, O. M., AUTHOR = Solel, B., TITLE = Minimal and maximal matrix convex sets, JOURNAL = J. Funct. Anal., FJOURNAL = Journal of Functional Analysis, VOLUME = 274, YEAR = 2018, NUMBER = 11, PAGES = 3197–3253,
PaulsenV.Completely bounded maps and operator algebrasCambridge Studies in
Advanced Mathematics78Cambridge University Press2002@book{Pau02, author =
{Paulsen, V.}, title = {Completely bounded maps and operator algebras}, series
= {Cambridge Studies in Advanced Mathematics}, volume = {78}, publisher =
{Cambridge University Press}, year = {2002}} =Delzell, C. N.Prestel, A.
AUTHORPositive polynomialsSpringer Monographs in MathematicsSpringer-Verlag,
Berlin2001@book{PD01, author = {{Prestel, A.} AUTHOR ={Delzell, C.\ N.}},
title = {Positive polynomials}, series = {Springer Monographs in Mathematics},
publisher = {Springer-Verlag, Berlin}, year = {2001}} author=Trillo, D.
author=Weilenmann, M. author=Thinh, L. P. author=Tavakoli, A. author=Gisin, N.
author=Acin, A. author=Navascues, M.Renou, M.-O.arXiv:2101.10873Quantum
physics needs complex numbers2021@article{Re21, author = {{Renou, M.-O.}
author={Trillo, D.} author={Weilenmann, M.} author={Thinh, L. P.}
author={Tavakoli, A.} author={Gisin, N.} author={Acin, A.} author={Navascues,
M.}}, journal = {arXiv:2101.10873}, title = {{Quantum physics needs complex
numbers}}, year = {2021}} ScheidererC.Spectrahedral shadowsSIAM J. Appl.
Algebra Geom.SIAM Journal on Applied Algebra and
Geometry22018126–44@article{Sc18, author = {Scheiderer, C.}, title =
{Spectrahedral shadows}, journal = {SIAM J. Appl. Algebra Geom.}, fjournal =
{SIAM Journal on Applied Algebra and Geometry}, volume = {2}, year = {2018},
number = {1}, pages = {26–44}} @article{Sh15}

  * author = Shalm, L. K., author=Meyer-Scott, E. author=Christensen, B. G. author=Bierhorst, P. author=Wayne, M. A. author=Gerrits, T., author=Glancy, S., author=Hamel, D. R. , author=Allman, M. S. , author=Coakley, K. J. , author=Dyer, S. D. , author=Hodge, C. , author=Lita, A. E. , author=Verma, V. B. , author=Lambrocco, C. , author=Tortorici, E. , author=Migdall, A. L. , author=Zhang, Y. , author=Kumor, D. R. , author=Farr, W. H. , author=Marsili, F. , author=Shaw, M. D. , author=Stern, J. A. , author=Abellán, C. , author=Amaya, W. , author=Pruneri, V. , author=Jennewein, T. , author=Mitchell, M. W. , author=Kwiat, P. G. , author=Bienfang, J. C. , author=Mirin, R. P. , author=Knill, E., author=Nam, S. W. , journal = Phys. Rev. Lett., pages = 250402, title = Strong Loophole-Free Test of Local Realism, volume = 115, year = 2015
@article{sl}

  * AUTHOR = Slofstra, W., TITLE = The set of quantum correlations is not closed, JOURNAL = Forum Math., Pi, VOLUME = 7, YEAR = 2019, PAGES = e1, 41,
@article{Ve04b}

  * author = Verstraete, F. author= Porras, D. author=Cirac, J. I., journal = Phys. Rev. Lett., pages = 227205, title = Density Matrix Renormalization Group and Periodic Boundary Conditions: A Quantum Information Perspective, volume = 93, year = 2004
@article{Wo11}

  * author = Wolf, M. M., title = Quantum Channels & Operations: A Guided Tour, url = https://www-m5.ma.tum.de/foswiki/pub/M5/Allgemeines/MichaelWolf/QChannelLecture.pdf, year = 2011
@book{wi}

  * , AUTHOR = Wilde, M. M., TITLE = Quantum Information Theory, PUBLISHER = Cambridge University Press, YEAR = 2017, PAGES = xvii+757,
@article{Zw04}

  * author = Zwolak, M. author = Vidal, G., journal = Phys. Rev. Lett., pages = 207205, title = Mixed-State Dynamics in One-Dimensional Quantum Lattice Systems: A Time-Dependent Superoperator Renormalization Algorithm, volume = 93, year = 2004