# Magic squares: Latin, Semiclassical and Quantum

Gemma De las Cuevas  Institute for Theoretical Physics, Technikerstr. 21a,
A-6020 Innsbruck, Austria  ,  Tim Netzer  Department of Mathematics,
Technikerstr. 13, A-6020 Innsbruck, Austria  and  Inga Valentiner-Branth
Department of Mathematics, Technikerstr. 13, A-6020 Innsbruck, Austria

###### Abstract.

Quantum magic squares were recently introduced as a ‘magical’ combination of
quantum measurements. In contrast to quantum measurements, they cannot be
purified (i.e. dilated to a quantum permutation matrix)—only the so-called
semiclassical ones can. Purifying establishes a relation to an ideal world of
fundamental theoretical and practical importance; the opposite of purifying is
described by the matrix convex hull. In this work, we prove that semiclassical
magic squares can be purified to quantum Latin squares, which are ‘magical’
combinations of orthonormal bases. Conversely, we prove that the matrix convex
hull of quantum Latin squares is larger than the semiclassical ones. This
tension is resolved by our third result: We prove that the quantum Latin
squares that are semiclassical are precisely those constructed from a
classical Latin square. Our work sheds light on the internal structure of
quantum magic squares, on how this is affected by the matrix convex hull, and,
more generally, on the nature of the ‘magical’ composition rule, both at the
semiclassical and quantum level.

##  1\. Introduction

Magic squares have fascinated mathematicians and non-mathematicians for more
than 2000 years. They are defined as square matrices filled with nonnegative
numbers, so that the entries in each row and column (and sometimes also the
diagonal) sum to the same number (the so-called magic constant of the square).
If the magic constant is one (and there is no condition on the diagonal), they
are sometimes called doubly stochastic matrices. We will use the notions of
magic square and doubly stochastic matrix interchangeably in this work.

A quantum version of magic squares has been introduced in [6] (see also [7]
for an invitation to this work), where the entries are no longer nonnegative
numbers, but positive semidefinite matrices, and every row and column of the
quantum magic square sums to the identity matrix. That is, rows and columns
form a positive operator valued measure (POVM), which is a description of a
quantum measurement. In other words: if we consider the POVMs defined by the
rows, they can be combined into a quantum magic square only if the first
elements of every POVM also define a POVM (i.e. the first column), and
similarly with the second elements, and so on, until the last elements. This
is the ‘magical’ combination which, to the best of our knowledge, does not
correspond to any physical composition (although see the considerations in the
Outlook). Some features of this composition rule are that only POVMs with the
same number of outcomes can be composed into a quantum magic square, and that
the order of outcomes in every POVM matters. Note that the definition of a
quantum magic square is not a construction but a _condition_ —having positive
semidefinite elements that sum to the identity along every row and column.
This work, together with others, attempts to characterise some aspects of the
set of matrices satisfying this condition.

Now, about 300 years ago Latin squares were introduced, among others to help
construct magic squares. A Latin square is an $n\times n$-matrix filled with
the numbers $1,\ldots,n$ such that each number appears exactly once in each
row and column. A special case of Latin squares of size $9$ are known as
Sudokus, for which there are additional constraints. Latin squares have
several applications in mathematics, for example in the design of experiments
[1] and as multiplication tables of quasigroups [20]. Clearly, every Latin
square is a non-normalized magic square.

There are several quantum generalisations of Latin squares. On the one hand, a
quantum version of Sudokus has recently been proposed in [15]. On the other
hand, a quantum version of Latin squares was introduced in [14], where instead
of numbers as entries in the Latin square, (pure) quantum states are used. In
a quantum Latin square, every entry is a unit vector from $\mathbb{C}^{n}$
such that every row and column forms an orthonormal basis. In [14] it is shown
that the so-called quantum shift-and-multiply method can be used to construct
unitary error bases from quantum Latin squares. Unitary error bases are
special bases of the set of complex matrices of size $n\times n$, which are
widely used in quantum information theory [11], the most famous example being
the Pauli matrices.

In this work, we study quantum Latin squares and quantum magic squares from a
unified perspective, and examine their relations. We prove the following:

  1. (1)

Every semiclassical magic square can be purified to a quantum Latin square.
Equivalently, the matrix convex hull of several sets of semiclassical Latin
squares is the set of semiclassical magic squares (Theorem 14).

  2. (2)

The matrix convex hull of all quantum Latin squares is larger than the set of
semiclassical magic squares. This follows from the existence of non-
semiclassical quantum Latin squares of even sizes larger than $2$ (Theorem
15).

  3. (3)

The quantum Latin squares that arise directly from a classical Latin square
are precisely the semiclassical ones (Theorem 11).

From a mathematical perspective, our work provides new insights into quantum
magic squares by leveraging free convexity, and is part of an ongoing effort
to establish synergies between free semialgebraic geometry and quantum
information, see e.g. [7, 3, 10, 2, 4].

From a conceptual perspective, we characterise quantum magic squares by
studying their relation to the ideal world, as the latter admits—presumably—a
simpler description. (See [5] for related conceptual considerations). While in
theoretical physics the ideal world typically involves an infinity (the
thermodynamic limit, zero temperature, ground states, etc), this is not the
case with regard to the description of quantum states, precisely because of
the purification theorem, which expresses the relation to the ideal world as a
relation between the parts and the whole, where this whole is finite (if the
parts are finite). By virtue of this theorem, quantum states, quantum
measurements and quantum channels can be purified, that is to say, related to
their respective ideal quantities (pure states, projective measurements and
unitary maps) of finite dimension (assuming we start from a finite dimension).
Mathematically, these purifications follow from Stinespring’s dilation
theorem, which says that every completely positive map is a multiplicative map
followed by a contraction; the multiplicative maps are easy to characterise
and here play the role of the ideal map, whereas the contraction plays the
opposite role to the purification. In short, purifying corresponds to relating
to the ideal world, whereas taking the matrix convex hull corresponds to a
compression to our (non-idealised, imperfect) world.

The purification theorem applies to every row and column of the quantum magic
square, i.e. it establishes relations to the ideal world for every such ‘one
dimensional’ array of objects. This work investigates the nature of the
purification in ‘two dimensions’, namely we study which quantum magic squares
can be purified, i.e. admit a purification that applies to all rows and
columns _simultaneously_.

Other works related to this study include the quantum generalisations of magic
squares proposed in [13], and the quantum permutation matrices considered in
[12]. The recent resolution of Euler’s officers problem in the quantum case
involves the construction of a special quantum magic square [17].

This paper is structured as follows. In Section 2 we present quantum Latin and
magic squares, in Section 3 we prove our main results, and in Section 4 we
conclude and provide an outlook.

##  2\. Setting the stage

Throughout this work, $\mathrm{Mat}_{n}(S)$ denotes the set of $n\times
n$-matrices with entries from the set $S$. Given a matrix
$A\in\mathrm{Mat}_{n}(\mathbb{C})$, $A^{*}$ denotes the complex conjugate of
$A$, and we denote by
$\mathrm{Her}_{n}(\mathbb{C})=\\{A\in\mathrm{Mat}_{n}(\mathbb{C})\mid
A^{*}=A\\}$ the real vector space of complex Hermitian $n\times n$ matrices.
$A\geqslant 0$ denotes that the Hermitian matrix $A$ is positive semidefinite,
and the convex cone of all positive semidefinite matrices is denoted by ${\rm
Psd}_{n}(\mathbb{C})$. The identity matrix of size $s$ is denoted by $I_{s}$.

We will first revisit quantum magic squares and friends (Section 2.1), then
define and explain the matrix convex hull (Section 2.2), and finally consider
quantum Latin squares (Section 2.3).

###  2.1. Quantum magic squares and friends

Let us start by reviewing some basic definitions and results on quantum magic
squares from [6].

First recall that a _positive operator valued measure_ (POVM) is a set of
positive semidefinite matrices $A_{1},\ldots,A_{n}\in{\rm
Psd}_{s}(\mathbb{C})$ such that $\sum_{i=1}^{n}A_{i}=I_{s}$. If every $A_{i}$
is a projection, i.e. $A_{i}^{2}=A_{i}=A_{i}^{*}$, then the POVM is called a
_projective valued measure_ (PVM).

A quantum magic square is an $n\times n$ grid where every cell contains an
$s\times s$ positive semidefinite matrix such that every row and column sums
to the identity. For this reason we refer to $n$ as the _external size_ and to
$s$ as the _internal size_. A quantum permutation matrix is a quantum magic
square where every element $A_{ij}$ is a projection, and in a commuting
quantum permutation matrix we additionally require that
$A_{ij}A_{k\ell}=A_{k\ell}A_{ij}$ for all $i,j,k,\ell\in\\{1,\ldots,n\\}$.

######  Definition 1 (Quantum magic squares and friends).

Given exterior size $n$ and interior size $s$,

  1. (1)

A _quantum magic square_ is a matrix
$A\in\mathrm{Mat}_{n}(\mathrm{Her}_{s}(\mathbb{C}))$ such that every row and
column of $A$ forms a POVM;

  2. (2)

A _quantum permutation matrix_ is a quantum magic square where every row and
column forms a PVM;

  3. (3)

A _commuting quantum permutation matrix_ is a quantum permutation matrix where
all entries commute.

Fixing the interior size to 1 results in the classical matrices we are
acquainted with. Specifically, quantum magic squares of interior size 1 are
precisely the doubly stochastic matrices. Moreover, quantum permutation
matrices of interior size 1 are the permutation matrices, since the only
projectors in $\mathbb{C}$ are 0 and 1, and the magic square condition ensures
that there is exactly one 1 entry per row and column.

Quantum magic squares with exterior size 1 and 2 are also very simple:

######  Remark 2 (Exterior size 1 and 2).

For exterior size $n=1$, the only possible quantum magic square is
$A=(I_{s})$. For $n=2$ all quantum magic squares have the form

$\begin{pmatrix}A&I_{s}-A\\\ I_{s}-A&A\end{pmatrix}=\begin{pmatrix}1&0\\\
0&1\end{pmatrix}\otimes A+\begin{pmatrix}0&1\\\
1&0\end{pmatrix}\otimes(I_{s}-A),$

where $A\in{\rm Psd}_{s}(\mathbb{C})$ is such that also $I_{s}-A$ is positive
semidefinite.

Note that a quantum permutation matrix is a quantum representation [8] of the
hypergraph obtained by considering a $n\times n$ grid and defining a hyperedge
for every row and column, as shown in Fig. 1. The interior size of the quantum
permutation matrix is precisely the dimension of the Hilbert space in [8,
Definition 7].

Figure 1. A quantum permutation matrix is a quantum representation of the
hypergraph shown here for $n=4$.

We now turn to _semiclassical_ magic squares, which were introduced in [6]. In
Section 3 we will shed light on this notion from a broader perspective. We
denote the permutation group on $n$ elements by $S_{n}$.

######  Definition 3 (Semiclassical).

$A\in\mathrm{Mat}_{n}(\mathrm{Her}_{s}(\mathbb{C}))$ is a _semiclassical magic
square_ if there exists a POVM $\\{Q_{\pi}\\}_{\pi\in S_{n}}$ such that

(1) $A=\sum_{\pi\in S_{n}}P_{\pi}\otimes Q_{\pi},$

where $P_{\pi}\in{\rm Mat}_{n}(\mathbb{C})$ is the permutation matrix
corresponding to permutation $\pi$.

A semiclassical magic square is a quantum magic square, as one can easily
verify.

Semiclassical magic squares are clearly not classical, because they contain
positive semidefinite matrices as its entries, but other than that they are
essentially classical, as they contain positive semidefinite matrices

$Q_{1},\ldots,Q_{n!}$

permuted through all inner positions. Specifically, in a semiclassical magic
square, the elements of a single POVM $\\{Q_{\pi}\\}$ are summed and arranged
according to the permutation matrices $P_{\pi}$, so as to form a quantum magic
square. In this sense semiclassical magic square provide a constructive
‘magical’ combination of POVMs stemming from a single, ‘primary’ POVM.

Now, every magic square (a.k.a. doubly stochastic matrix) is
semiclassical—this is precisely the content of Birkhoff–von Neumann’s Theorem.
Moreover, every quantum magic square of exterior size $n=1,2$ is
semiclassical—this follows from Remark 2.

Let us now consider the union over all internal sizes of the set of quantum
magic squares and their friends. This union is natural in the context of free
semialgebraic geometry.

######  Definition 4 (Sets of quantum magic squares and friends).

We denote the set of

  1. (1)

Quantum magic squares by

$\mathsf{M}_{s}^{(n)}\coloneqq\mathopen{}\mathclose{{}\left\\{A\in{\rm
Mat}_{n}\mathopen{}\mathclose{{}\left({\rm
Psd}_{s}(\mathbb{C})}\right)\mid\sum_{i}A_{ij}=\sum_{j}A_{ij}=I_{s}}\right\\};$

  2. (2)

Quantum permutation matrices by

$\mathsf{P}_{s}^{(n)}\coloneqq\mathopen{}\mathclose{{}\left\\{A\in\mathsf{M}_{s}^{(n)}\mid
A_{ij}^{2}=A_{ij}=A_{ij}^{*}\mbox{ for every }i,j}\right\\};$

  3. (3)

Commuting quantum permutation matrices by

$\mathsf{C}_{s}^{(n)}\coloneqq\mathopen{}\mathclose{{}\left\\{A\in\mathsf{P}_{s}^{(n)}\mid
A_{ij}A_{k\ell}=A_{k\ell}A_{ij}\,\mbox{ for every }i,j,k,\ell}\right\\};$

  4. (4)

Semiclassical magic squares by

$\mathsf{S}_{s}^{(n)}\coloneqq\mathopen{}\mathclose{{}\left\\{A\in\mathsf{M}_{s}^{(n)}\mid
A\mbox{ is semiclassical }}\right\\};$

and the union over all internal sizes, respectively, by

$\mathsf{M}^{(n)}\coloneqq\bigcup_{s\in\mathbb{N}}\mathsf{M}_{s}^{(n)},\
\mathsf{P}^{(n)}\coloneqq\bigcup_{s\in\mathbb{N}}\mathsf{P}_{s}^{(n)},\
\mathsf{C}^{(n)}\coloneqq\bigcup_{s\in\mathbb{N}}\mathsf{C}_{s}^{(n)},\
\mathsf{S}^{(n)}\coloneqq\bigcup_{s\in\mathbb{N}}\mathsf{S}_{s}^{(n)}.$

Note that, by definition,

$\mathsf{C}^{(n)}\subseteq\mathsf{P}^{(n)}\subseteq\mathsf{M}^{(n)}.$

In addition, for exterior size $n=1,2,3$, the commuting requirement makes no
difference, i.e.

$\mathsf{C}^{(n)}=\mathsf{P}^{(n)}.$

For $n=1,2$, this follows from Remark 2, and the case $n=3$ can be found in
[12]. On the other hand, for $n\geqslant 4$, these two sets are different,

$\mathsf{C}^{(n)}\subsetneq\mathsf{P}^{(n)},$

as can be seen by taking block diagonal sums of quantum permutation matrices.
In addition, in [6] it is shown that commuting quantum permutation matrices
are semiclassical,

$\textsf{C}^{(n)}\subseteq\textsf{S}^{(n)}.$

###  2.2. The matrix convex hull

Figure 2. The idea of matrix convexity. The external size $n$ remains fixed
(in this depiction, $n=4$), whereas matrix convexity expresses a relation
between all internal sizes $s$. Specifically, the sets $R_{s}$ at different
internal level must be closed under contractions, which are transformations of
the internal matrices with $\sum_{i}V_{i}^{*}\cdot V_{i}$ where
$\sum_{i}V_{i}^{*}V_{i}=I$.

We now consider a dimension-free notion of convexity, called _matrix
convexity_ , often used in free semialgebraic geometry and operator algebra,
see for example [9, 16]. The matrix convex hull plays a central role in this
work, and the idea is the following (see Fig. 2). We are given a subset of
matrices of external size $n$ and internal size $s$,

$R_{s}\subseteq\mathrm{Mat}_{n}(\mathrm{Her}_{s}(\mathbb{C}))$

for every $s$, and we consider

$R=\bigcup_{s\in\mathbb{N}}R_{s}.$

We want to characterise what it means for $R$ to be matrix convex.
Intuitively, it means that it is closed under a certain notion of
contractions, which we will now explain step by step.

Within a given level $s$, we consider a set of matrices
$A^{(1)},\ldots,A^{(r)}\in R_{s}$ of internal size $s$ and external size $n$.
We then consider the $k,\ell$ entry of each of these matrices, and contract
them as

$A_{k\ell}^{(1)},\ldots,A_{k\ell}^{(r)}\mapsto\sum_{i=1}^{r}V_{i}^{*}A_{k\ell}^{(i)}V_{i}$

where the $V_{i}$s are square matrices of size $s$ (i.e. the same size as
$A_{k\ell}^{(i)}$, which is the internal size of $A$), which satisfy

$\sum_{i=1}^{r}V_{i}^{*}V_{i}=I_{s}.$

The latter condition guarantees that the $V_{i}$s behave like probabilities in
the matrix case, since if $s=1$, we recover the usual notion of convexity.
Matrix convexity requires that, for a given level $s$, for any set
$A^{(1)},\ldots,A^{(r)}\in R_{s}$ (with any $r$), the result of contracting
with any such $V_{i}$s is still in $R_{s}$,

$\sum_{i=1}^{r}V_{i}^{*}A^{(i)}V_{i}\coloneqq\mathopen{}\mathclose{{}\left(\sum_{i=1}^{r}V_{i}^{*}A_{k,\ell}^{(i)}V_{i}}\right)_{k,\ell=1}^{n}\in
R_{s}.$

Note that the contraction is applied to every cell (labeled $k,\ell$)
separately.

Additionally, we can communicate different internal levels $s$. This is
achieved by letting $V_{i}$ be rectangular matrices. Namely, if $R$ is matrix
convex, for any levels $s$ and $t$, and for any matrices

$V_{i}\in\mathrm{Mat}_{s,t}(\mathbb{C})\mbox{ for }i=1,\ldots r\mbox{ with
}\sum_{i}V_{i}^{*}V_{i}=I_{t}$

it must hold that

$\sum_{i=1}^{r}V_{i}^{*}A^{(i)}V_{i}\in R_{t}.$

In words, we can contract the matrices of a given level $s$ to a smaller or a
larger level $t$, and not leave $R$.

Finally, in the most general case, the initial matrices can be taken from
different levels, $A^{(i)}\in R_{s_{i}}$ (with $i$ running from 1 to an
arbitrary $r$), and we take the corresponding matrices $V_{i}$ to match this
initial size $s_{i}$ and result in size $t$,
$V_{i}\in\mathrm{Mat}_{s_{i},t}(\mathbb{C})$.

Note that the external size of the matrices $n$ is fixed through these
operations. It is only the internal size of the matrices $s$ that is asked to
satisfy these closure properties; specifically, every cell of the external
$n\times n$ matrix is asked to satisfy these conditions.

######  Definition 5 (Matrix convex).

  1. (1)

Let

$R=\bigcup_{s\in\mathbb{N}}R_{s}\mbox{ where
}R_{s}\subseteq\mathrm{Mat}_{n}(\mathrm{Her}_{s}(\mathbb{C})).$

$R$ is _matrix convex_ if for all $r,s_{i},t\geqslant 1$, for all $A^{(i)}\in
R_{s_{i}}$, and for all $V_{i}\in\mathrm{Mat}_{s_{i},t}(\mathbb{C})$ with
$i=1,\ldots,r$ and $\sum_{i}V_{i}^{*}V_{i}=I_{t}$, it holds that

$\sum_{i=1}^{r}V_{i}^{*}A^{(i)}V_{i}\in R_{t}.$

  2. (2)

For any set $R$, its _matrix convex hull_ , denoted ${\rm mconv}(R)$, is the
smallest matrix convex superset of $R$, i.e. the intersection of all its
matrix convex supersets.

The matrix convex hull can thus be understood as a ‘free’ version of the
convex hull. Here free can either mean free of the dimension, or free of the
commutation relation—both apply.

One of the main results from [6] states that the matrix convex hull of the
quantum permutation matrices is smaller than the set quantum magic squares,

(2) ${\rm mconv}(\mathsf{P}^{(n)})\subsetneq\mathsf{M}^{(n)}\qquad\mbox{ for
all }n\geqslant 3.$

This is seen as a failure of a matrix version of the Birkoff–von Neumann
theorem, since for internal size $s=1$ the convex hull of the set of
permutation matrices equals the set of doubly stochastic matrices. (2) thus
says that the characterisation of larger interior sizes is more difficult; at
least, quantum magic squares cannot be characterised as the matrix convex hull
of quantum permutation matrices.

On the other hand, the matrix convex hull of the _classical_ (i.e. usual)
permutation matrices is precisely the set of semiclassical magic squares [6],

(3) ${\rm mconv}(\textsf{P}^{(n)}_{1})=\textsf{S}^{(n)}.$

In other words, the semiclassical magic squares (elements $A$ in (1)) are
precisely what we need to add to the usual permutation matrices so that the
set is matrix convex. In this sense, semiclassical magic squares are a free
convex promotion of classical permutation matrices—this is yet another way in
which they are semiclassical.

Overall, we have

${\rm mconv}(\textsf{C}^{(n)})={{\rm
mconv}}(\textsf{P}^{(n)}_{1})=\textsf{S}^{(n)}$

because $\textsf{C}^{(n)}$ is contained in $\textsf{S}^{(n)}$ and contains
$\textsf{P}^{(n)}_{1}$.

###  2.3. Quantum Latin squares

We now turn our attention to (quantum) Latin squares. A Latin square is a
square where each number from $\\{1,\ldots n\\}$ appears exactly once in each
row and column—it is like a solved Sudoku without the condition on the smaller
squares. A Latin square is also a particular kind of (unnormalised) magic
square, as in the latter, the numbers need not be taken from a given set.
Formally, $L\in\mathrm{Mat}_{n}(\\{1,\ldots,n\\})$ is a Latin square if each
number from $\\{1,\ldots,n\\}$ appears exactly once in each row and each
column of $L$.

_Quantum_ Latin squares are defined in [14]; let us now review their
definition.

######  Definition 6 (Quantum Latin squares).

$L\in\mathrm{Mat}_{n}(\mathbb{C}^{n})$ is a _quantum Latin square_ if every
row and column of $L$ forms an orthonormal basis of $\mathbb{C}^{n}$.

######  Example 7 (Easy quantum Latin square).

The easiest way to construct a quantum Latin square is to take a Latin square
and an orthonormal basis of the correct size, and to arrange the basis
according to the indices in the Latin square. For example, given the $4\times
4$ Latin square

$\begin{array}[]{|c|c|c|c|}\hline\cr 1&2&3&4\\\ \hline\cr 2&4&1&3\\\ \hline\cr
3&1&4&2\\\ \hline\cr 4&3&2&1\\\ \hline\cr\end{array}$

and an orthonormal basis $v_{1},\ldots,v_{4}\in\mathbb{C}^{4},$ we obtain the
following quantum Latin square:

$\begin{array}[]{|c|c|c|c|}\hline\cr v_{1}&v_{2}&v_{3}&v_{4}\\\ \hline\cr
v_{2}&v_{4}&v_{1}&v_{3}\\\ \hline\cr v_{3}&v_{1}&v_{4}&v_{2}\\\ \hline\cr
v_{4}&v_{3}&v_{2}&v_{1}\\\ \hline\cr\end{array}$

There are more quantum Latin squares than the easy ones, as this example from
[14] shows:

$\begin{array}[]{|c|c|c|c|}\hline\cr v_{1}&v_{2}&v_{3}&v_{4}\\\
\hline\cr\tfrac{1}{\sqrt{2}}(v_{2}-v_{3})&\tfrac{1}{\sqrt{5}}(iv_{1}+2v_{4})&\tfrac{1}{\sqrt{5}}(2v_{1}+iv_{4})&\tfrac{1}{\sqrt{2}}(v_{2}+v_{3})\\\
\hline\cr\tfrac{1}{\sqrt{2}}(v_{2}+v_{3})&\tfrac{1}{\sqrt{5}}(2v_{1}+iv_{4})&\tfrac{1}{\sqrt{5}}(iv_{1}+2v_{4})&\tfrac{1}{\sqrt{2}}(v_{2}-v_{3})\\\
\hline\cr v_{4}&v_{3}&v_{2}&v_{1}\\\ \hline\cr\end{array}$

Here $v_{1},\ldots,v_{4}\in\mathbb{C}^{n}$ is again a fixed orthonormal basis.
In this square, four different orthonormal bases can be found in the rows and
columns.

##  3\. From quantum Latin squares to quantum magic squares

In this section we investigate the relation between quantum Latin squares and
quantum magic squares. We first explain how quantum Latin squares can be
understood as quantum magic squares (Section 3.1), show that the easy quantum
Latin squares are precisely the semiclassical ones (Section 3.2), study
quantum Latin squares and friends (Section 3.3), as well as these sets under
the matrix convex hull (Section 3.4).

###  3.1. Quantum Latin squares as quantum magic squares

We start by noting that quantum Latin squares are essentially equivalent to
rank one quantum magic squares.

######  Observation 8.

Let $V=(v_{ij})_{i,j=1}^{n}\in\mathrm{Mat}_{n}(\mathbb{C}^{n})$ be a quantum
Latin square. Then

$\mathopen{}\mathclose{{}\left(v_{ij}v_{ij}^{*}}\right)_{i,j=1}^{n}\in\mathrm{Mat}_{n}(\mathrm{Her}_{n}(\mathbb{C}))$

is a quantum magic square. Conversely, given a quantum magic square
$A=(A_{ij})_{i,j=1}^{n}\in\mathrm{Mat}_{n}(\mathrm{Her}_{n}(\mathbb{C}))$ with
$\operatorname{rank}(A_{ij})=1$ for all $i,j$, there exist
$a_{ij}\in\mathbb{C}^{n}$ such that $A_{ij}=a_{ij}a_{ij}^{*}$ and

$(a_{ij})_{i,j=1}^{n}\in\mathrm{Mat}_{n}(\mathbb{C}^{n})$

is a quantum Latin square.

Let us formalize this now, together with another way to construct quantum
magic squares.

######  Definition 9 (Rank one quantum magic squares).

($i$) The set of quantum magic squares of exterior size $n$ and interior size
$s$, where each entry matrix has rank one, is denoted by

$\mathsf{R}_{s}\coloneqq\\{A\in\mathsf{M}_{s}^{(n)}\mid\mathrm{rank}(A_{ij})=1\mbox{
for all }i,j\\}.$

and $\mathsf{R}\coloneqq\bigcup_{s\in\mathbb{N}}\mathsf{R}_{s}$.

($ii$) The set of quantum Latin squares that arise from an easy quantum Latin
square as in Example 7 and applying 8 is denoted by

$\displaystyle\mathsf{L}_{n}:=\mathopen{}\mathclose{{}\left\\{\mathopen{}\mathclose{{}\left(v_{L_{ij}}v_{L_{ij}}^{*}}\right)_{i,j=1}^{n}\mid}\right.$
$\displaystyle L\text{ classical Latin square of size }n,$ $\displaystyle\
\mathopen{}\mathclose{{}\left.v_{1},\ldots,v_{n}\in\mathbb{C}^{n}\text{
orthonormal basis}}\right\\}.$

The set $\textsf{R}_{n}^{(n)}$ is in one-to-one correspondence with the set of
quantum Latin squares of size $n$ (up to a phase in the orthonormal bases, of
course), as shown in 8. For $s>n$ the set $\textsf{R}_{s}^{(n)}$ is empty,
since less than $s$ matrices of rank $1$ cannot sum up to the identity matrix
$I_{s}$.

Every element from $\textsf{R}_{n}^{(n)}$ is a quantum permutation matrix,
since for a unit vector $v\in\mathbb{C}^{n},$ $vv^{*}$ is an orthogonal
projection. For $\textsf{R}_{s}^{(n)}$ with $s<n$ this is not the case, as the
following example shows:

$\displaystyle\begin{array}[]{|c|c|c|}\hline\cr\tfrac{1}{2}e_{1}e_{1}^{*}&\tfrac{1}{2}e_{1}e_{1}^{*}&e_{2}e_{2}^{*}\\\
\hline\cr
e_{2}e_{2}^{*}&\tfrac{1}{2}e_{1}e_{1}^{*}&\tfrac{1}{2}e_{1}e_{1}^{*}\\\
\hline\cr\tfrac{1}{2}e_{1}e_{1}^{*}&e_{2}e_{2}^{*}&\tfrac{1}{2}e_{1}e_{1}^{*}\\\
\hline\cr\end{array}\in\textsf{R}^{(3)}_{2}$

Here $e_{1},e_{2}\in\mathbb{C}^{2}$ is an orthonormal basis.

######  Remark 10.

We have seen that

$\textsf{L}_{n}\subseteq\textsf{R}_{n}^{(n)}\subseteq\textsf{P}_{n}^{(n)}\subseteq\textsf{M}_{n}^{(n)},$

and

$\textsf{L}_{n}\subseteq\textsf{C}_{n}^{(n)}$

because for two orthonormal vectors $v,w$, their associated rank 1 projectors
commute.

###  3.2. Easy quantum Latin square are semiclassical

Our first main result shows that $\textsf{L}_{n}$ is precisely the set of
quantum Latin squares that are semiclassical:

######  Theorem 11.

$\textsf{L}_{n}=\textsf{R}_{n}^{(n)}\cap\textsf{S}_{n}^{(n)}.$

###### Proof.

First note that any element from $\textsf{L}_{n}$ is semiclassical, since
$\textsf{L}_{n}\subseteq\textsf{C}_{n}^{(n)}\subseteq\textsf{S}_{n}^{(n)}$.
Since $\textsf{L}_{n}\subseteq\textsf{R}_{n}^{(n)}$ too, this proves that the
left hand side is included in the right hand side.

For the other inclusion, let $A=\sum_{\pi\in S_{n}}P_{\pi}\otimes Q_{\pi}$ be
a semiclassical magic square of interior and exterior size $n$ such that each
entry has rank 1. Hence every $Q_{\pi}$ has rank at most one, and thus the sum
of two such $Q_{\pi}$ has rank at most one if and only if they are linearly
dependent. Now consider

$\Pi_{ij}\coloneqq\\{\pi\in S_{n}\mid(P_{\pi})_{i,j}=1\\}=\\{\pi\in
S_{n}\mid\pi(j)=i\\}.$

For $\pi,\tilde{\pi}\in\Pi_{ij}$ the above arguments imply that $Q_{\pi}$ and
$Q_{\tilde{\pi}}$ are linearly dependent, so

(4) $\dim({\rm span}\\{Q_{\pi}\mid\pi\in\Pi_{ij}\\})=1\quad\mbox{for all }i,j$

Note that $A_{ij}\neq 0$ for all $i,j$, because each $A_{ij}$ is rank one and
otherwise the corresponding row or column of $A$ could not sum up to $I_{n}$.

Now for every $i\in\\{1,\ldots,n\\}$ choose a $\pi_{i}\in\Pi_{i1}$ with
$Q_{\pi_{i}}\neq 0$. By a similar rank argument as above, we see that
$A_{i1}\notin{\rm span}\\{A_{j1}\\},$ and hence $Q_{\pi_{i}}\notin{\rm
span}\\{Q_{\pi_{j}}\\}$ for $i\neq j$. In view of (4) this implies that each
$\Pi_{k\ell}$ contains at most one of the $\pi_{i}$. So we have found
permutations $\pi_{1},\ldots,\pi_{n}\in S_{n}$ that are completely disjoint,
in the sense that no two of them coincide on some input $\ell$. But then for
each $k,\ell$ there must be some $i$ with $\pi_{i}(\ell)=k$. Hence each
$\Pi_{k\ell}$ contains precisely one of the $\pi_{i}$.

We now claim that $Q_{\pi}=0$ for $\pi\in
S_{n}\setminus\\{\pi_{1},...,\pi_{n}\\}$. For $\ell=\pi(1)$ we have
$\pi\in\Pi_{\ell 1}$, and since $\pi\neq\pi_{\ell}$ there exists some $j\neq
1$ with $\pi(j)\neq\pi_{\ell}(j)$. So $\pi\in\Pi_{\pi(j)j}$ and
$\pi_{\ell}\notin\Pi_{\pi(j)j}$, and by the above considerations we find an
$i\neq\ell$ with $\pi_{i}\in\Pi_{\pi(j)j}$. This implies

$Q_{\pi}\in{\rm span}\\{Q_{\pi_{\ell}}\\}\cap{\rm
span}\\{Q_{\pi_{i}}\\}=\\{0\\},$

as claimed.

Altogether we have shown $A=\sum_{i=1}^{n}P_{\pi_{i}}\otimes Q_{\pi_{i}}$, and
the $Q_{\pi_{i}}$ are all rank 1 squares, i.e. $Q_{\pi_{i}}=q_{i}q_{i}^{*}$
for certain $q_{i}\in\mathbb{C}^{n}$. 8 implies that $q_{1},\ldots,q_{n}$ form
an orthonormal basis, and that $A$ is the quantum Latin square constructed
from this orthonormal basis and the classical Latin square

$\sum_{j=1}^{n}j\,P_{\pi_{j}}.$

∎

###  3.3. Quantum Latin squares and friends

Instead of taking an orthonormal basis to construct an easy quantum Latin
square, we can take a POVM or a PVM, and arrange its elements according to a
classical Latin square of size $n$, similarly to Example 7. These result in a
certain type of quantum magic squares, where there is a _single_ POVM (or PVM)
that is placed in a permuted way in every row and column. We denote them
$\mathsf{POVML}_{s}^{(n)}$ and $\mathsf{PVML}_{s}^{(n)}$, respectively.

######  Definition 12 (Quantum Latin squares and friends).

We define

$\displaystyle\mathsf{POVML}_{s}^{(n)}$
$\displaystyle:=\mathopen{}\mathclose{{}\left\\{\mathopen{}\mathclose{{}\left(P_{L_{ij}}}\right)_{i,j=1}^{n}\mid
P_{1},\ldots,P_{n}\in\mathrm{Her}_{s}(\mathbb{C})\text{ POVM, }L\text{ Latin
square}}\right\\}$ $\displaystyle\mathsf{PVML}_{s}^{(n)}$
$\displaystyle:=\mathopen{}\mathclose{{}\left\\{\mathopen{}\mathclose{{}\left(P_{L_{ij}}}\right)_{i,j=1}^{n}\mid
P_{1},\ldots,P_{n}\in\mathrm{Her}_{s}(\mathbb{C})\text{ PVM, }L\text{ Latin
square}}\right\\}$

as well as

$\mathsf{POVML}^{(n)}\coloneqq\bigcup_{s\in\mathbb{N}}\mathsf{POVML}_{s}^{(n)},\quad\mathsf{PVML}^{(n)}\coloneqq\bigcup_{s\in\mathbb{N}}\mathsf{PVML}_{s}^{(n)}.$

######  Proposition 13.

$\mathsf{POVML}^{(n)}\subseteq\mathsf{S}^{(n)}$ and
$\mathsf{PVML}^{(n)}\subseteq\mathsf{C}^{(n)}\cap\mathsf{POVML}^{(n)}.$

###### Proof.

Let $A\in\mathsf{POVML}_{s}^{(n)}$ be generated by the POVM
$Q_{1},\ldots,Q_{n}\in\mathrm{Her}_{s}(\mathbb{C})$ and the Latin square $L$.
We define permutation matrices $P_{1},\ldots,P_{n}$ by setting for all
$i,k,\ell\in\\{1,\ldots n\\}$:

$\displaystyle(P_{i})_{k,\ell}=\begin{cases}1&\mbox{if }L_{k\ell}=i\\\
0&\mbox{else.}\end{cases}$

Then clearly

$A=\sum_{i=1}^{n}P_{i}\otimes Q_{i},$

which shows that $A$ is semiclassical and proves the first inclusion. The
second inclusion is obvious, since projectors from one PVM always commute. ∎

The inclusions observed so far are shown in Figure 3.

$\textstyle{\mathsf{M}^{(n)}}$$\textstyle{\mathsf{S}^{(n)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathsf{P}^{(n)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathsf{POVML}^{(n)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathsf{C}^{(n)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathsf{R}_{n}^{(n)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathsf{PVML}^{(n)}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathsf{L}_{n}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$
Figure 3. Inclusions between sets of quantum magic squares, where
$\mathsf{A}\to\mathsf{B}$ denotes $\mathsf{A}\subseteq\mathsf{B}$. That easy
quantum Latin squares are PVM Latin squares, which are POVM Latin squares,
$\mathsf{L}_{n}\subseteq\mathsf{PVML}^{(n)}\subseteq\mathsf{POVML}^{(n)}$, is
the case by definition, and $\mathsf{POVML}^{(n)}\subseteq\mathsf{C}^{(n)}$ by
Proposition 13. That commuting quantum permutation matrices are quantum
permutation matrices, which are quantum magic squares,
$\mathsf{C}^{(n)}\subseteq\mathsf{P}^{(n)}\subseteq\mathsf{M}^{(n)}$, is true
by definition. That quantum Latin squares are rank one, which are quantum
permutation matrices,
$\textsf{L}_{n}\subseteq\textsf{R}_{n}^{(n)}\subseteq\textsf{P}_{n}^{(n)}$, is
stated in Remark 10. Finally,
$\textsf{C}^{(n)}\subseteq\textsf{S}^{(n)}\subseteq\textsf{M}^{(n)}$ was shown
in [6], and $\mathsf{POVML}^{(n)}\subseteq\textsf{S}^{(n)}$ by Proposition 13.

###  3.4. Taking the matrix convex hull

Let us now examine the matrix convex hulls of some quantum magic squares.

######  Theorem 14.

$\displaystyle\mathsf{S}^{(n)}$ $\displaystyle={{\rm
mconv}}(\mathsf{C}^{(n)})={{\rm mconv}}(\mathsf{POVML}^{(n)})={{\rm
mconv}}(\mathsf{PVML}^{(n)})={{\rm mconv}}(\mathsf{L}_{n}).$

###### Proof.

In view of the inclusions of Fig. 3 and Eq. (3) it suffices to prove that
$\mathsf{P}_{1}^{(n)}\subseteq{\rm mconv}(\mathsf{L}_{n})$. So let
$P\in\mathsf{P}_{1}^{(n)}$ be a permutation matrix, and denote by $L$ the
classical Latin square obtained from $P$ by replacing its zero entries with
numbers $2,\ldots n$ suitably. Let $v_{1},\ldots,v_{n}$ be an orthonormal
basis of $\mathbb{C}^{n}$, and let $A\in\mathsf{L}_{n}$ be the easy quantum
Latin square constructed from $L$ and this basis. Then
$P=v_{1}^{*}Av_{1}\in{\rm mconv}(\mathsf{L}_{n})$, which finishes the proof. ∎

This shows that the left hand side of Fig. 3 simplifies greatly after taking
the matrix convex hull. Let us now consider what happens to the right hand
side of Fig. 3 under the matrix convex hull.

First note that from $\mathsf{L}_{n}\subseteq\mathsf{R}_{n}^{(n)}$ we
immediately obtain

${\rm mconv}(\mathsf{L}_{n})\subseteq{\rm mconv}(\mathsf{R}_{n}^{(n)}).$

######  Theorem 15.

For even $n\geqslant 4$ we have ${\rm mconv}(\mathsf{L}_{n})\subsetneq{\rm
mconv}(\mathsf{R}_{n}^{(n)})$, and in particular
$\mathsf{L}_{n}\subsetneq\mathsf{R}_{n}^{(n)},$ i.e. there exist quantum Latin
squares which are not semiclassical.

###### Proof.

Write $n=2m$, let $L$ be a classical Latin square of size $m,$ and let
$v_{1},\ldots,v_{m}\in\mathbb{C}^{m},w_{1},\ldots,w_{m}\in\mathbb{C}^{m}$ be
two orthonormal bases such that

$v_{1}v_{1}^{*}w_{1}w_{1}^{*}\neq w_{1}w_{1}^{*}v_{1}v_{1}^{*}.$

Let $A,B\in\mathsf{L}_{m}$ be the quantum magic squares generated by $L$ and
these two bases, respectively. The following block matrix is a quantum
permutation matrix of size $n$:

$A{\oplus}B\coloneqq\begin{pmatrix}A&0\\\
0&B\end{pmatrix}\in\mathsf{P}^{(n)}.$

For example, for $n=4$ and
$L=\mathopen{}\mathclose{{}\left(\begin{array}[]{cc}1&2\\\
2&1\end{array}}\right)$, this is the matrix

$\begin{pmatrix}v_{1}v_{1}^{*}&v_{2}v_{2}^{*}&0&0\\\
v_{2}v_{2}^{*}&v_{1}v_{1}^{*}&0&0\\\ 0&0&w_{1}w_{1}^{*}&w_{2}w_{2}^{*}\\\
0&0&w_{2}w_{2}^{*}&w_{1}w_{1}^{*}\end{pmatrix}.$

By our choice of bases we have that $A{\oplus}B\notin\mathsf{C}^{(n)}$, and
the proof of [6, Corollary 15] shows that $A{\oplus}B\notin\mathsf{S}^{(n)}$.

Now we claim that $A{\oplus}B\in{\rm mconv}(\mathsf{R}_{n}^{(n)})$. To see
this, let

$\iota:\mathbb{C}^{m}\to\mathbb{C}^{n}:v\mapsto\begin{pmatrix}v\\\
0\end{pmatrix}.$

Then $\iota(v_{1}),\ldots,\iota(v_{m})$ and $\iota(w_{1}),\ldots,\iota(w_{m})$
are orthonormal systems in $\mathbb{C}^{n},$ which are both extended to an
orthonormal basis by the standard basis vectors $e_{m+1},\ldots,e_{n}$. Now
let $\iota(A)$ be the matrix constructed from
$\iota(v_{1}),\ldots,\iota(v_{m})$ and $L$ as in Definition 9 ($i$) (except
that $\iota(v_{1}),\ldots,\iota(v_{m})$ only form half of an orthonormal basis
here). In the same way we construct $\iota(B)$ from
$\iota(w_{1}),\ldots,\iota(w_{m})$ and $L$, as well as $E$ from
$e_{m+1},\ldots e_{n}$ and $L$. We then obtain

$C=\begin{pmatrix}\iota(A)&E\\\
E&\iota(B)\end{pmatrix}\in\mathsf{R}_{n}^{(n)},$

since each row and each column contains the rank one squares of an orthonormal
basis of $\mathbb{C}^{n}.$ For $n=4$ this looks like

$\begin{pmatrix}\iota(v_{1})\iota(v_{1})^{*}&\iota(v_{2})\iota(v_{2})^{*}&e_{3}e_{3}^{*}&e_{4}e_{4}^{*}\\\
\iota(v_{2})\iota(v_{2})^{*}&\iota(v_{1})\iota(v_{1})^{*}&e_{4}e_{4}^{*}&e_{3}e_{3}^{*}\\\
e_{3}e_{3}^{*}&e_{4}e_{4}^{*}&\iota(w_{1})\iota(w_{1})^{*}&\iota(w_{2})\iota(w_{2})^{*}\\\
e_{4}e_{4}^{*}&e_{3}e_{3}^{*}&\iota(w_{2})\iota(w_{2})^{*}&\iota(w_{1})\iota(w_{1})^{*}\end{pmatrix}.$

For $V=\begin{pmatrix}I_{m}\\\
0\end{pmatrix}\in\mathrm{Mat}_{n,m}(\mathbb{C})$ we have $V^{*}V=I_{m}$ and

$V^{*}CV=A\oplus B\in{\rm mconv}(\mathsf{R}_{n}^{(n)}),$

which proves the claim. ∎

It follows that, after taking matrix convex hulls, the diagram from Fig. 3
simplifies to Fig. 4.

$\textstyle{\mathsf{M}^{(n)}}$$\textstyle{{\rm
mconv}(\mathsf{P}^{(n)})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{{\rm
mconv}(\mathsf{R}_{n}^{(n)})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathsf{S}^{(n)}={\rm
mconv}(\mathsf{L}_{n})\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$
Figure 4. Inclusions between the matrix convex hulls (compare with Fig. 3).
$\mathsf{S}^{(n)}={\rm mconv}(\mathsf{L}_{n})$ is shown in Theorem 14, and its
inclusion in ${\rm mconv}(\mathsf{R}_{n}^{(n)})$ is strict for even
$n\geqslant 4$ by Theorem 15. The inclusion of ${\rm mconv}(\mathsf{P}^{(n)})$
in $\mathsf{M}^{(n)}$ is strict for all $n\geqslant 3$, as proven in [6]. We
do not know if the inclusion ${\rm mconv}(\mathsf{R}_{n}^{(n)})\subseteq{\rm
mconv}(\mathsf{P}^{(n)})$ is strict.

######  Remark 16.

We thank David E. Roberson for bringing to our attention the following fact.
The statement $\mathsf{L}_{n}\subsetneq\mathsf{R}_{n}^{(n)}$ holds for _all_
$n\geq 4$, not only the even ones as proven in Theorem 15. This follows from
[18, Theorem 4.6], which shows that for each $n$ there are $n!$ quantum Latin
squares of which at most $n(n-1)$ have commuting entries. This implies that
for every $n\geq 4$ there are quantum Latin squares not in $\mathsf{C}^{(n)}$
and thus neither in $\mathsf{L}_{n}$.

##  4\. Conclusions and Outlook

In this work, we have proven three results concerning the structure of the
special types of quantum magic squares. First, every semiclassical magic
square can be purified to a quantum Latin square; equivalently, the matrix
convex hull of several sets of Latin squares is the set of semiclassical magic
squares (Theorem 14). Second, the matrix convex hull of all quantum Latin
squares is larger than the set of semiclassical magic squares; this follows
from the existence of non-semiclassical quantum Latin squares of even sizes
larger than $2$ (Theorem 15). And third, the easy quantum Latin squares (i.e.
those that arise from a classical Latin square) are precisely the
semiclassical ones (Theorem 11).

It would be interesting to define and characterise quantum magic cubes, as
well as the three ‘dimensional’ version of their friends. Quantum permutation
cubes would be represented by the hypergraph of Fig. 5. Not every magic cube
can be expressed as a convex combination of permutation cubes, i.e. the
analogue of Birkhoff–von Neumann theorem fails. Perhaps a quantum version of a
magic cube could recover a behaviour of this type.

Figure 5. The quantum hypergraph corresponding to a quantum magic cube. Nodes
and hypergraphs behind the top layer are now shown.

Quantum magic squares can be seen as ‘magical’ combinations of quantum
measurements, and this work and others investigate when this combination can
be purified, as well as other properties. Positive semidefinite matrices are
intimately related to completely positive maps by the Choi–Jamiołkowski
isomorphism (given a bipartite structure of the former). Yet, we do not know
if any of the investigations on quantum magic squares has any consequences for
‘magical’ combinations of completely positive maps.

Finally, it would be very interesting to establish a correspondence between
(quantum) magic squares and the study of contextuality [19], and to understand
matrix convex hulls of classical magic squares as epistemic restrictions of
classical theories.

## References

  * [1] Bailey, R. A. Design of Comparative Experiments.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2008.
  * [2] Blakaj, V., and Wolf, M. M. Transcendental properties of entropy-constrained sets.  Ann. Henri Poincaré (2022).
  * [3] Bluhm, A., and Nechita, I. Joint measurability of quantum effects and the matrix diamond.  J. Math. Phys. 59 (2018), 112202.
  * [4] Buckley, A. New examples of entangled states on $\mathbb{C}^{3}\otimes\mathbb{C}^{3}$.  arXiv:2112.12643.
  * [5] Cuffaro, M. E., and Hartmann, S. The open systems view.  arXiv:2112.11095 (2021).
  * [6] De las Cuevas, G., Drescher, T., and Netzer, T. Quantum magic squares: Dilations and their limitations.  J. Math. Phys. 61, 11 (2020), 111704.
  * [7] De las Cuevas, G., and Netzer, T. Quantum Information Theory and Free Semialgebraic Geometry: One Wonderland Through Two Looking Glasses.  IMN (2021), 246.
  * [8] Fritz, T. Quantum logic is undecidable.  Arch. Math. Logic 60 (2021), 329.
  * [9] Helton, J. W., Klep, I., and McCullough, S. Matrix convex hulls of free semialgebraic sets.  Trans. Amer. Math. Soc. 368, 5 (2015), 3105.
  * [10] Jivulescu, M. A., Lancien, C., and Nechita, I. Multipartite entanglement detection via projective tensor norms.  Ann. Henri Poincaré (2022).
  * [11] Klappenecker, A., and Rötteler, M. Unitary error bases: Constructions, equivalence, and applications.  In International Symposium on Applied Algebra, Algebraic Algorithms, and Error-Correcting Codes (2003), Springer, p. 139.
  * [12] Lupini, M., Mančinska, L., and Roberson, D. E. Nonlocal Games and Quantum Permutation Groups.  J. Funct. Anal. 279 (2020), 108592.
  * [13] Mendl, C. B., and Wolf, M. M. Unital Quantum Channels – Convex Structure and Revivals of Birkhoff’s Theorem.  Comm. Math. Phys. 289 (2009), 1057.
  * [14] Musto, B., and Vicary, J. Quantum Latin squares and unitary error bases.  Quantum Inf. Comput. 16 (2016), 1318.
  * [15] Nechita, I., and Pillet, J. SudoQ – a quantum variant of the popular game.  arXiv:2005.10862 (2020).
  * [16] Paulsen, V. Completely bounded maps and operator algebras.  Cambridge University Press, 2002.
  * [17] Rather, S. A., Burchardt, A., Bruzda, W., Rajchel-Mieldzioć, G., Lakshminarayan, A., and K.Życzkowski.  Thirty-six entangled officers of Euler: Quantum solution to a classically impossible problem.  Phys. Rev. Lett. 128 (2022), 080507.
  * [18] Roberson, D. E., and Schmidt, S. Quantum symmetry vs nonlocal symmetry.  arxiv:2012.13328 (2020).
  * [19] Schmid, D., Selby, J. H., and Spekkens, R. W. Unscrambling the omelette of causation and inference: The framework of causal-inferential theories.  arXiv:2009.03297 (2020).
  * [20] Smith, J. An Introduction to Quasigroups and Their Representations.  Chapman and Hall, 2006.


Karate Club: An API Oriented Open-Source Python Framework for Unsupervised Learning on Graphs

Benedek Rozemberczki

The University of Edinburgh
United Kingdom

Oliver Kiss

Central European University

Rik Sarkar

The University of Edinburgh
United Kingdom

Graphs encode important structural properties of complex systems. Machine learning on graphs has therefore emerged as an important technique in research and applications. We present Karate Club – a Python framework combining more than 30 state-of-the-art graph mining algorithms. These unsupervised techniques make it easy to identify and represent common graph features. The primary goal of the package is to make community detection, node and whole graph embedding available to a wide audience of machine learning researchers and practitioners.
Karate Club is designed with an emphasis on a consistent application interface, scalability, ease of use, sensible out of the box model behaviour,  standardized dataset ingestion, and output generation. This paper discusses the design principles behind the framework with practical examples. We show Karate Club's efficiency in learning performance on a wide range of real world clustering problems and classification tasks along with supporting evidence of its competitive speed.

§ ACKNOWLEDGEMENTS

Benedek Rozemberczki was supported by the Centre for Doctoral Training in Data Science, funded by EPSRC (grant EP/L016427/1).

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

[Abadi, Barham, Chen, Chen, Davis, Dean, Devin,
Ghemawat, Irving, Isard, et alAbadi et al2016]
authorpersonMartín Abadi, personPaul
Barham, personJianmin Chen, personZhifeng Chen,
personAndy Davis, personJeffrey Dean,
personMatthieu Devin, personSanjay Ghemawat,
personGeoffrey Irving, personMichael Isard,
et al year2016.
Tensorflow: A system for large-scale machine
learning. In booktitle12th $\{$USENIX$\}$ Symposium on
Operating Systems Design and Implementation ($\{$OSDI$\}$ 16).

[Ahmed, Rossi, Lee, Willke, Zhou, Kong, and
EldardiryAhmed et al2019]
authorpersonNesreen K Ahmed, personRyan A
Rossi, personJohn Boaz Lee, personTheodore L Willke,
personRong Zhou, personXiangnan Kong, and
personHoda Eldardiry. year2019.
role2vec: Role-based network embeddings. In
booktitleProc. DLG KDD.

[Bandyopadhyay, Kara, Kannan, and
MurtyBandyopadhyay et al2018]
authorpersonSambaran Bandyopadhyay,
personHarsh Kara, personAswin Kannan, and
personM Narasimha Murty. year2018.
Fscnmf: Fusing structure and content via
non-negative matrix factorization for embedding information networks.
journalarXiv preprint arXiv:1804.05313

[Belkin and NiyogiBelkin and Niyogi2002]
authorpersonMikhail Belkin and
personPartha Niyogi. year2002.
Laplacian eigenmaps and spectral techniques for
embedding and clustering. In booktitleAdvances in neural
information processing systems. pages585–591.

[Buitinck, Louppe, Blondel, Pedregosa, Mueller,
Grisel, Niculae, Prettenhofer, Gramfort, Grobler, Layton, VanderPlas, Joly,
Holt, and VaroquauxBuitinck et al2013]
authorpersonLars Buitinck, personGilles
Louppe, personMathieu Blondel, personFabian
Pedregosa, personAndreas Mueller, personOlivier
Grisel, personVlad Niculae, personPeter
Prettenhofer, personAlexandre Gramfort, personJaques
Grobler, personRobert Layton, personJacob
VanderPlas, personArnaud Joly, personBrian Holt,
and personGaël Varoquaux. year2013.
API design for machine learning software:
experiences from the scikit-learn project.
journalArXiv  volumeabs/1309.0238

[Cao, Lu, and XuCao et al2015]
authorpersonShaosheng Cao, personWei Lu,
and personQiongkai Xu. year2015.
Grarep: Learning graph representations with global
structural information. In booktitleProceedings of the 24th
ACM international on conference on information and knowledge management.
ACM, pages891–900.

[Chen and KogaChen and Koga2019]
authorpersonHong Chen and personHisashi
Koga. year2019.
GL2vec: Graph Embedding Enriched by Line Graphs
with Edge Features. In booktitleInternational Conference on
Neural Information Processing. Springer, pages3–14.

[de Lara and Edouardde Lara and
authorpersonNathan de Lara and
personPineau Edouard. year2018.
A simple baseline algorithm for graph
classification. In booktitleAdvances in Neural Information
Processing Systems.

[Defferrard, Martin, Pena, and
PerraudinDefferrard et al[n.d.]]
authorpersonMichaël Defferrard,
personLionel Martin, personRodrigo Pena, and
personNathanaël Perraudin. year[n.d.].
titlePyGSP: Graph Signal Processing in Python.

[Donnat, Zitnik, Hallac, and LeskovecDonnat
et al2018]
authorpersonClaire Donnat, personMarinka
Zitnik, personDavid Hallac, and personJure
Leskovec. year2018.
Learning structural node embeddings via diffusion
wavelets. In booktitleProceedings of the 24th ACM SIGKDD
International Conference on Knowledge Discovery & Data Mining. ACM,

[Epasto, Lattanzi, and Paes LemeEpasto
et al2017]
authorpersonAlessandro Epasto, personSilvio
Lattanzi, and personRenato Paes Leme.
Ego-Splitting Framework: From Non-Overlapping to
Overlapping Clusters. In booktitleProceedings of the 23rd
ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
(seriesKDD '17). pages145–154.

[Gao, Wolf, and HirnGao
et al2019]
authorpersonFeng Gao, personGuy Wolf, and
personMatthew Hirn. year2019.
Geometric Scattering for Graph Data Analysis. In
booktitleProceedings of the 36th International Conference on
Machine Learning, Vol. volume97. pages2122–2131.

[Hagberg, Swart, and S ChultHagberg
et al2008]
authorpersonAric Hagberg, personPieter
Swart, and personDaniel S Chult.
booktitleExploring network structure, dynamics, and
function using NetworkX.
typeTechnical Report. institutionLos
Alamos National Lab.(LANL), Los Alamos, NM (United States).

[Henderson, Gallagher, Eliassi-Rad, Tong, Basu,
Akoglu, Koutra, Faloutsos, and LiHenderson et al2012]
authorpersonKeith Henderson, personBrian
Gallagher, personTina Eliassi-Rad, personHanghang
Tong, personSugato Basu, personLeman Akoglu,
personDanai Koutra, personChristos Faloutsos, and
personLei Li. year2012.
Rolx: structural role extraction & mining in large
graphs. In booktitleProceedings of the 18th ACM SIGKDD
international conference on Knowledge discovery and data mining.

[Jundong LiJundong Li2019]
authorpersonHuan Liu Jundong Li, Liang Wu.
Multi-Level Network Embedding with Boosted Low-Rank
Matrix Approximation. In booktitleProceedings of the 2019
IEEE/ACM International Conference on Advances in Social Networks Analysis and
Mining 2019. ACM, pages50–56.

[Kuang, Ding, and ParkKuang
et al2012]
authorpersonDa Kuang, personChris Ding,
and personHaesun Park. year2012.
Symmetric nonnegative matrix factorization for
graph clustering. In booktitleProceedings of the 2012 SIAM
international conference on data mining. SIAM, pages106–117.

[Leskovec and KrevlLeskovec and
authorpersonJure Leskovec and personAndrej
Krevl. year2014.
titleSNAP Datasets: Stanford Large Network Dataset

[Li, Huang, Wang, and LaiLi
et al2019]
authorpersonPei-Zhen Li, personLing Huang,
personChang-Dong Wang, and personJian-Huang Lai.
EdMot: An Edge Enhancement Approach for Motif-aware
Community Detection. In booktitleProceedings of the 25th
ACM SIGKDD International Conference on Knowledge Discovery & Data Mining
(seriesKDD '19). pages479–487.

[Narayanan, Chandramohan, Venkatesan, Chen, and
LiuNarayanan et al2017]
authorpersonAnnamalai Narayanan,
personMahinthan Chandramohan, personRajasekar
Venkatesan, personLihui Chen, and personYang Liu.
graph2vec: Learning distributed representations of

[Ou, Cui, Pei, Zhang, and ZhuOu
et al2016]
authorpersonMingdong Ou, personPeng Cui,
personJian Pei, personZiwei Zhang, and
personWenwu Zhu. year2016.
Asymmetric transitivity preserving graph
embedding. In booktitleProceedings of the 22nd ACM SIGKDD
international conference on Knowledge discovery and data mining.

[Paszke, Gross, Massa, Lerer, Bradbury, Chanan,
Killeen, Lin, Gimelshein, Antiga, et alPaszke
et al2019]
authorpersonAdam Paszke, personSam Gross,
personFrancisco Massa, personAdam Lerer,
personJames Bradbury, personGregory Chanan,
personTrevor Killeen, personZeming Lin,
personNatalia Gimelshein, personLuca Antiga,
et al year2019.
PyTorch: An imperative style, high-performance deep
learning library. In booktitleAdvances in Neural
Information Processing Systems. pages8024–8035.

[Pedregosa, Varoquaux, Gramfort, Michel,
Thirion, Grisel, Blondel, Prettenhofer, Weiss, Dubourg,
et alPedregosa et al2011]
authorpersonFabian Pedregosa, personGaël
Varoquaux, personAlexandre Gramfort, personVincent
Michel, personBertrand Thirion, personOlivier
Grisel, personMathieu Blondel, personPeter
Prettenhofer, personRon Weiss, personVincent
Dubourg, et al year2011.
Scikit-learn: Machine learning in Python.
journalJournal of machine learning research
volume12, numberOct (year2011),

authorpersonTiago P Peixoto.
The graph-tool python library.
journalfigshare (year2014).

[Perozzi, Al-Rfou, and SkienaPerozzi
et al2014]
authorpersonBryan Perozzi, personRami
Al-Rfou, and personSteven Skiena.
Deepwalk: Online learning of social
representations. In booktitleProceedings of the 20th ACM
SIGKDD international conference on Knowledge discovery and data mining.
ACM, pages701–710.

[Perozzi, Kulkarni, Chen, and SkienaPerozzi
et al2017]
authorpersonBryan Perozzi, personVivek
Kulkarni, personHaochen Chen, and personSteven
Skiena. year2017.
Don't Walk, Skip!: online learning of multi-scale
network embeddings. In booktitleProceedings of the 2017
IEEE/ACM International Conference on Advances in Social Networks Analysis and
Mining 2017. ACM, pages258–265.

[Prat-Pérez, Dominguez-Sal, and
Larriba-PeyPrat-Pérez et al2014]
authorpersonArnau Prat-Pérez,
personDavid Dominguez-Sal, and personJosep-Lluis
Larriba-Pey. year2014.
High quality, scalable and parallel community
detection for large real graphs. In booktitleProceedings of
the 23rd international conference on World wide web.

[Qiu, Dong, Ma, Li, Wang, and TangQiu
et al2018]
authorpersonJiezhong Qiu, personYuxiao
Dong, personHao Ma, personJian Li,
personKuansan Wang, and personJie Tang.
Network embedding as matrix factorization: Unifying
deepwalk, line, pte, and node2vec. In booktitleProceedings
of the Eleventh ACM International Conference on Web Search and Data Mining.
ACM, pages459–467.

[Raghavan, Albert, and KumaraRaghavan
et al2007]
authorpersonUsha Nandini Raghavan,
personRéka Albert, and personSoundar Kumara.
Near Linear Time Algorithm to Detect Community
Structures in Large-scale Networks.
journalPhysical review E volume76,
number3 (year2007), pages036106.

[Rehurek and SojkaRehurek and Sojka2011]
authorpersonRadim Rehurek and personPetr
Sojka. year2011.
Gensim—statistical semantics in python.
journalRetrieved from genism. org

[Rozemberczki, Allen, and SarkarRozemberczki
et al2019a]
authorpersonBenedek Rozemberczki, personCarl
Allen, and personRik Sarkar.
Multi-scale Attributed Node Embedding.
journalarXiv preprint arXiv:1909.13021

[Rozemberczki, Davies, Sarkar, and
SuttonRozemberczki et al2019b]
authorpersonBenedek Rozemberczki, personRyan
Davies, personRik Sarkar, and personCharles
Sutton. year2019b.
GEMSEC: Graph Embedding with Self Clustering. In
booktitleProceedings of the 2019 IEEE/ACM International
Conference on Advances in Social Networks Analysis and Mining 2019. ACM,

[Rozemberczki, Kiss, and SarkarRozemberczki
et al2020]
authorpersonBenedek Rozemberczki,
personOliver Kiss, and personRik Sarkar.
Little Ball of Fur: A Python Library for Graph
Sampling. In booktitleProceedings of the 29th ACM
International Conference on Information and Knowledge Management (CIKM
'20). ACM.

[Rozemberczki and SarkarRozemberczki and
authorpersonBenedek Rozemberczki and
personRik Sarkar. year2018.
Fast Sequence-Based Embedding with Diffusion
Graphs. In booktitleInternational Workshop on Complex
Networks. Springer, pages99–107.

[Rozemberczki and SarkarRozemberczki and
authorpersonBenedek Rozemberczki and
personRik Sarkar. year2020.
Characteristic Functions on Graphs: Birds of a
Feather, from Statistical Descriptors to Parametric Models. In
booktitleProceedings of the 29th ACM International on
Conference on Information and Knowledge Management (CIKM '20). ACM.

authorpersonRik Sarkar.
Low distortion delaunay embedding of trees in
hyperbolic plane. In booktitleInternational Symposium on
Graph Drawing. Springer, pages355–366.

[Sun, Shen, Gao, Ouyang, and ChengSun
et al2017]
authorpersonBing-Jie Sun, personHuawei
Shen, personJinhua Gao, personWentao Ouyang, and
personXueqi Cheng. year2017.
A non-negative symmetric encoder-decoder approach
for community detection. In booktitleProceedings of the
2017 ACM on Conference on Information and Knowledge Management. ACM,

[Sun and FevotteSun and Fevotte2014]
authorpersonDennis L Sun and personCedric
Fevotte. year2014.
Alternating direction method of multipliers for
non-negative matrix factorization with the beta-divergence. In
booktitle2014 IEEE international conference on acoustics,
speech and signal processing (ICASSP). IEEE, pages6201–6205.

[Tsitsulin, Mottin, Karras, Bronstein, and
MüllerTsitsulin et al2018]
authorpersonAnton Tsitsulin, personDavide
Mottin, personPanagiotis Karras, personAlexander
Bronstein, and personEmmanuel Müller.
Netlsd: hearing the shape of a graph. In
booktitleProceedings of the 24th ACM SIGKDD International
Conference on Knowledge Discovery & Data Mining.

[Verbeek and SuriVerbeek and Suri2014]
authorpersonKevin Verbeek and
personSubhash Suri. year2014.
Metric embedding, hyperbolic space, and social
networks. In booktitleProceedings of the thirtieth annual
symposium on Computational geometry. pages501–510.

[Verma and ZhangVerma and Zhang2017]
authorpersonSaurabh Verma and personZhi-Li
Zhang. year2017.
Hunt for the unique, stable, sparse and fast
feature learning on graphs. In booktitleAdvances in Neural
Information Processing Systems. pages88–98.

[Virtanen, Gommers, Oliphant, Haberland, Reddy,
Cournapeau, Burovski, Peterson, Weckesser, Bright, et alVirtanen
et al2019]
authorpersonPauli Virtanen, personRalf
Gommers, personTravis E Oliphant, personMatt
Haberland, personTyler Reddy, personDavid
Cournapeau, personEvgeni Burovski, personPearu
Peterson, personWarren Weckesser, personJonathan
Bright, et al year2019.
SciPy 1.0–fundamental algorithms for scientific
computing in Python.
journalarXiv preprint arXiv:1907.10121

[Walt, Colbert, and VaroquauxWalt
et al2011]
authorpersonStéfan van der Walt,
personS Chris Colbert, and personGael Varoquaux.
The NumPy array: a structure for efficient
numerical computation.
journalComputing in Science & Engineering
volume13, number2 (year2011),

[Wang, Cui, Wang, Pei, Zhu, and YangWang
et al2017]
authorpersonXiao Wang, personPeng Cui,
personJing Wang, personJian Pei,
personWenwu Zhu, and personShiqiang Yang.
Community Preserving Network Embedding. In
booktitleProceedings of the Thirty-First AAAI Conference on
Artificial Intelligence (seriesAAAI'17).

[Yanardag and VishwanathanYanardag and
authorpersonPinar Yanardag and
personS.V.N. Vishwanathan. year2015.
Deep Graph Kernels. In
booktitleProceedings of the 21th ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining.

[Yang, Liu, Zhao, Sun, and ChangYang
et al2015]
authorpersonCheng Yang, personZhiyuan Liu,
personDeli Zhao, personMaosong Sun, and
personEdward Chang. year2015.
Network representation learning with rich text
information. In booktitleTwenty-Fourth International Joint
Conference on Artificial Intelligence.

[Yang, Sun, Liu, and TuYang
et al2017]
authorpersonCheng Yang, personMaosong Sun,
personZhiyuan Liu, and personCunchao Tu.
Fast network embedding enhancement via high order
proximity approximation.. In booktitleIJCAI.

[Yang, Rosso, Li, and Cudre-MaurouxYang
et al2019]
authorpersonDingqi Yang, personPaolo Rosso,
personBin Li, and personPhilippe Cudre-Mauroux.
NodeSketch: Highly-Efficient Graph Embeddings via
Recursive Sketching. In booktitleProceedings of the 25th
ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.

[Yang, Pan, Zhang, Chen, Lian, and ZhangYang
et al2018]
authorpersonHong Yang, personShirui Pan,
personPeng Zhang, personLing Chen,
personDefu Lian, and personChengqi Zhang.
Binarized attributed network embedding. In
booktitle2018 IEEE International Conference on Data Mining
(ICDM). IEEE, pages1476–1481.

[Yang and LeskovecYang and Leskovec2013]
authorpersonJaewon Yang and personJure
Leskovec. year2013.
Overlapping community detection at scale: a
nonnegative matrix factorization approach. In
booktitleProceedings of the sixth ACM international
conference on Web search and data mining. ACM, pages587–596.

[Yang and YangYang and Yang2018]
authorpersonShuang Yang and personBo
Yang. year2018.
Enhanced Network Embedding with Text Information.
In booktitle2018 24th International Conference on Pattern
Recognition (ICPR). IEEE, pages326–331.

[Ye, Chen, and ZhengYe et al2018]
authorpersonFanghua Ye, personChuan Chen,
and personZibin Zheng. year2018.
Deep Autoencoder-like Nonnegative Matrix
Factorization for Community Detection. In
booktitleProceedings of the 27th ACM International
Conference on Information and Knowledge Management
(seriesCIKM '18). pages1393–1402.

authorpersonWayne W Zachary.
An information flow model for conflict and fission
in small groups.
journalJournal of anthropological research
volume33, number4 (year1977),

[Zhang, Yin, Zhu, and ZhangZhang
et al2018]
authorpersonDaokun Zhang, personJie Yin,
personXingquan Zhu, and personChengqi Zhang.
SINE: Scalable Incomplete Network Embedding. In
booktitle2018 IEEE International Conference on Data Mining
(ICDM). IEEE, pages737–746.