# Transformations of Stabilizer States in Quantum Networks

Matthias Englbrecht  Institute for Theoretical Physics, University of
Innsbruck, Technikerstraße 21A, 6020 Innsbruck, Austria  Tristan Kraft
Institute for Theoretical Physics, University of Innsbruck, Technikerstraße
21A, 6020 Innsbruck, Austria  Barbara Kraus  Institute for Theoretical
Physics, University of Innsbruck, Technikerstraße 21A, 6020 Innsbruck, Austria

###### Abstract

Stabilizer states and graph states find application in quantum error
correction, measurement-based quantum computation and various other concepts
in quantum information theory. In this work, we study party-local Clifford
(PLC) transformations among stabilizer states. These transformations arise as
a physically motivated extension of local operations in quantum networks with
access to bipartite entanglement between some of the nodes of the network.
First, we show that PLC transformations among graph states are equivalent to a
generalization of the well-known local complementation, which describes local
Clifford transformations among graph states. Then, we introduce a mathematical
framework to study PLC equivalence of stabilizer states, relating it to the
classification of tuples of bilinear forms. This framework allows us to study
decompositions of stabilizer states into tensor products of indecomposable
ones, that is, decompositions into states from the entanglement generating set
(EGS). While the EGS is finite up to $3$ parties [Bravyi et al., J. Math.
Phys. 47, 062106 (2006)], we show that for $4$ and more parties it is an
infinite set, even when considering party-local unitary transformations.
Moreover, we explicitly compute the EGS for $4$ parties up to $10$ qubits.
Finally, we generalize the framework to qudit stabilizer states in prime
dimensions not equal to $2$, which allows us to show that the decomposition of
qudit stabilizer states into states from the EGS is unique.

##  1 Introduction

The pursuit of building large-scale quantum networks to implement a quantum
internet [1, 2] has recently attracted much interest from the experimental and
the theoretical perspective [3, 4, 5]. In particular, several important
building blocks of quantum networks have been demonstrated experimentally [6,
7]. Such networks open interesting possibilities for advanced quantum
information processing tasks, which include distributed quantum computing [8],
quantum metrology [9], and, most prominently, long-distance quantum
communication [10]. Beyond future applications, the strong correlations in
quantum networks also open new possibilities for fundamental tests of quantum
mechanics (cf. Ref. [11]). As technology progresses it becomes more and more
relevant to understand quantum networks from the theoretical point of view.
The fundamental building block of these networks are entangled quantum
systems. Entanglement itself is quite well understood in the bipartite case,
but understanding multipartite entanglement, despite many efforts, still
remains to be an extremely challenging task [12, 13, 14, 15]. In particular,
our understanding of network entanglement is still quite limited, even in the
case of a few qubits only, which is due to its complicated structure. Indeed,
recent results demonstrate that its characterization requires new mathematical
tools to be explored [16, 17, 18].

In this regard, so-called _stabilizer states_ constitute an interesting
subclass of multipartite entangled pure states. These states are defined as
the unique simultaneous eigenstate of a maximal set of commuting Pauli
observables, the so-called _stabilizer_ [20, 19]. The stabilizer formalism was
originally introduced by Gottesman in the realm of quantum error correction
codes [21]. Nowadays, stabilizer states are known to be important to many
aspects of quantum information processing such as, e.g., measurement based
quantum computing [22] or the classical simulation of quantum circuits [23].
_Graph states_ [20, 19] admit a simple description in terms of mathematical
graphs 111In the context of quantum error correction graph states were first
considered in Ref. [24].. It is known that any stabilizer state is equivalent
to a graph state under a certain class of local operations, the so-called
local _Clifford operations_ , which map the set of stabilizer states onto
itself. Due to their relevance, as outlined above, gaining a deeper
understanding of entanglement in stabilizer states is an important goal.

In this paper we study stabilizer states in quantum networks. Creating
bipartite entanglement in quantum networks is considerably less demanding than
the distribution of large entangled states. In particular, well connected
nodes can share a large amount of bipartite entanglement at basically no cost.
This bipartite entanglement can be used, for instance, to implement non-local
transformations of stabilizer states via gate teleportation [25]. Here,
Clifford operations turn out to be particularly important as they can be
implemented deterministically. Thus, well connected nodes having access to the
additional bipartite entanglement can be viewed as a single party. We call the
operations that can be applied on those parties _party-local Clifford_ (PLC)
operations. In case each party only holds a single qubit it is known that two
stabilizer states are equivalent under local Cliffords if and only if their
corresponding graph states are connected by a series of _local
complementations_ [26].

If all qubits of a stabilizer state are grouped into two parties the bipartite
stabilizer state can be converted into multiple independent copies of the
maximally entangled state $\ket{\phi^{+}}$, and locally separable states
$\ket{0}$ using PLC transformations [27]. For tripartite stabilizer states it
was shown in Ref. [28] that any state can be converted to multiple independent
copies of the Greenberger-Horne-Zeilinger (GHZ) state $\ket{GHZ}$ between the
three parties, the Bell state $\ket{\phi^{+}}$ between pairs of parties, and
locally separable states $\ket{0}$, see Figure 1. The fact that these
decompositions are unique, even under more general party local unitary (PLU)
transformations, motivated the authors of Ref. [28] to call these sets
_entanglement generating sets_. These results were later generalized to
tripartite qudit graph states in Ref. [29].

Figure 1: Top: A stabilizer state is distributed over two parties. Under party
local unitary transformations the state can be converted to multiple
independent copies of the Bell state, and locally separable states. Bottom:
The same state, when grouped into three parties, can be decomposed into a GHZ
state, a Bell state and locally separable states.

Furthermore, Ref. [28] provides criteria for the PLC equivalence of stabilizer
states. In Ref. [30] homological invariants of stabilizer states under local
Clifford operations are studied, and were linked to the GHZ extraction
condition of Ref. [28]. The extraction of GHZ states from random stabilizer
states was investigated in Refs. [31, 32, 33]. However, a systematic approach
to study the extraction of arbitrary stabilizer states in the multipartite
scenario was missing. Putting forward such an approach that allows us to gain
a deeper insight into the structure of entanglement in multipartite stabilizer
states is precisely the aim of this work.

In this paper we study PLC transformations and state extraction of stabilizer
states. First, we introduce notations and definitions relevant in the context
of PLC transformations of stabilizer states in Section 2.1. Then we study how
PLC transformations between graph states alter the corresponding graphs in
Section 2.3, generalizing the concept of local complementation. As any
stabilizer state is LC equivalent to a graph state this characterizes the
action of any PLC operations on an arbitrary stabilizer state. In Section 2.4
we put forward a complete characterization of PLC equivalence classes based on
PLC invariant polynomials which seems computationally not very practical. Then
we recall previous works on PLC transformations of stabilizer states (Section
2.5). We mainly focus on the results of Ref. [28] which solves the
classification of PLC classes for the $3$-partite case and introduces the
notion of the entanglement generating set. In Section 3, we introduce one of
our main results, namely, a new mathematical formalism, that we call the
_commutation matrix formalism_ , that allows us to systematically study PLC
transformations and state extraction of stabilizer states shared between an
arbitrary number of parties. In this formalism we associate a tuple of
alternating bilinear forms to every stabilizer state. We show that the
classification of PLC classes is equivalent to the classification of
commutation matrices up to simultaneous congruence. This type of problem was
studied in linear algebra and we demonstrate how these results can be utilized
in the commutation matrix formalism in Sections 3.1 and 3.2. In particular
this leads to necessary and sufficient conditions for a state to be contained
in the EGS. In Section 3.3, using the commutation matrix formalism, we derive
another main result by showing that the EGSM is an infinite set for $M\geq 4$,
even with respect to party-local unitary transformations (PLU). Moreover, the
new formalism allows us to compute the EGS4 up to $10$ qubits. Going beyond
the EGS4 we provide evidence that the structure of the EGS becomes rapidly
more complex. In Section 4 we show that the commutation matrix formalism
extends to qudit stabilizer states of prime dimension. As the commutation
matrices in this case are defined over the field $\mathbb{Z}_{d}$ for $d\geq
3$, the results of Ref. [34] imply that every qudit stabilizer states admits a
unique decomposition into a tensor product of states in the EGS. Whether or
not the uniqueness of the decomposition extends to all qubit stabilizer states
is unclear. Finally, in case one considers more general states or operations
it happens that the decomposition is not unique anymore, which we discuss in
Section 4.2.

##  2 Party-local operations

###  2.1 Preliminaries

Let us introduce some notation and recall some important definitions relevant
in the context of PLC transformations of stabilizer states. We denote by
$X,Y,Z$ the single-qubit Pauli operators

$X=\begin{pmatrix}0&1\\\ 1&0\end{pmatrix},\ \ Y=\begin{pmatrix}0&-i\\\
i&0\end{pmatrix},\ \ Z=\begin{pmatrix}1&0\\\ 0&-1\end{pmatrix},$ (1)

and by $\mathcal{P}_{n}$ the $n$-qubit Pauli group, i.e., the group generated
by $n$-fold tensor products of single-qubit Pauli operators. A stabilizer
$\mathcal{S}$ is an abelian subgroup of the Pauli group $\mathcal{P}_{n}$,
which does not contain $-\mathds{1}$. A maximal abelian subgroup of
$\mathcal{P}_{n}$ is generated by $n$ independent commuting Pauli operators.
The operators of a stabilizer forming a maximal abelian subgroup admit a
unique, common $+1$ eigenstate, which is called a stabilizer state. Examples
of stabilizer states are the Bell state
$\ket{\phi^{+}}=1/\sqrt{2}(\ket{00}+\ket{11})$ and the $n$-qubit GHZ state
$\ket{GHZ}=1/\sqrt{n}(\ket{0\ldots 0}+\ket{1\ldots 1})$.

It follows from the definition of stabilizer states that the density matrix
$\outerproduct{\psi}{\psi}$ of a $n$-qubit stabilizer state $\ket{\psi}$ with
stabilizer $\mathcal{S}$ can we written as

$\rho=\outerproduct{\psi}{\psi}=\frac{1}{2^{n}}\sum_{s\in\mathcal{S}}s.$ (2)

Using this relation together with the fact that Pauli operators are traceless,
one finds that the reduced state on a subset of qubits $\alpha$ is given by

$\rho_{\alpha}=\frac{1}{2^{|\alpha|}}\sum_{s\in\mathcal{S}_{\alpha}}s,$ (3)

where $\mathcal{S}_{\alpha}$ contains those elements of $\mathcal{S}$ which
act trivially on all qubits not in $\alpha$. Here, and in the following,
$|\alpha|$ denotes the cardinality of the set $\alpha$. The rank of the
reduced state $\varrho_{\alpha}$ depends on how many qubits in $\alpha$ are
entangled with qubits outside of $\alpha$, e.g., if all qubits are entangled
$\mathcal{S}_{\alpha}$ only contains the identity operator and
$\varrho_{\alpha}$ has full rank.

The unitary normalizer (modulo $U(1)$) of the Pauli group $\mathcal{P}_{n}$ is
called the $n$-qubit Clifford group $\mathcal{C}_{n}$, i.e.,
$\mathcal{C}_{n}=\\{U\in U(2^{n})|UPU^{\dagger}\in\mathcal{P}_{n}\forall
P\in\mathcal{P}_{n}\\}\backslash U(1)$. For any $n$, the Clifford group
$\mathcal{C}_{n}$ is generated by single and two qubit gates, e.g.,

$\begin{split}H&=\frac{1}{\sqrt{2}}\begin{pmatrix}1&1\\\ 1&-1\end{pmatrix},\
P=\begin{pmatrix}1&0\\\ 0&i\end{pmatrix},\\\ CZ&=\begin{pmatrix}1&0\\\
0&0\end{pmatrix}\otimes\mathds{1}+\begin{pmatrix}0&0\\\
0&1\end{pmatrix}\otimes Z.\end{split}$ (4)

A subgroup of the Clifford group $\mathcal{C}_{n}$ is the local Clifford group
$\mathcal{C}_{n}^{L}$, which consists of those elements of $\mathcal{C}_{n}$
which can be written as a tensor product of elements of $\mathcal{C}_{1}$.

Every stabilizer state is local Clifford (LC) equivalent to a graph state
[26]. A graph state $\ket{G}$ is the unique stabilizer state associated to a
simple (no loops, undirected) graph $G=(V,E)$ with vertices
$V=\\{1,2,\ldots,n\\}$ and edges $E\subset\\{\\{i,j\\}|i,j\in V\\}$. Its
stabilizer $\mathcal{S}_{G}=\left<g_{1},\ldots,g_{n}\right>$ is generated by
the _canonical generators_

$g_{i}=X_{i}\bigotimes_{j\in N_{i}}Z_{j},$ (5)

where $N_{i}=\\{k\in V|\\{k,i\\}\in E\\}$ is the neighbourhood of vertex $i$
in $G$. A local Clifford transformation which maps a graph state to another
graph state corresponds to a sequence of local complementations on the level
of the graphs [26]. A local complementation with respect to (w.r.t.) the
vertex $j\in E$ removes all edges between neighbours of vertex $j$ and adds
all edges between neighbours of vertex $j$, which where previously not present
in the graph. That is, it removes the edges in $\\{\\{k,l\\}\in E|k,l\in
N_{j}\\}$ and adds all edges in $\\{\\{k,l\\}\not\in E|k,l\in N_{j}\\}$ to the
graph $G$. This corresponds to the application of the operator
$\exp(-i\pi/4X)$ on qubit $j$, and $\exp(i\pi/4Z)$ on each of its neighbours.
Let us mention here that counting the number of local Clifford equivalent
graph states is #P-Complete [35]. Note that the graphical description of local
Clifford transformations between graph states has also been studied for qudit
systems [36, 37]. A particularly useful way of representing an $n$-qubit graph
state $\ket{G}$ is by its _adjacency matrix_ $\Gamma_{G}\in M_{n\times n}$,
defined by

$(\Gamma_{G})_{i,j}=\begin{cases}1,&\text{if $i$ and $j$ are connected}\\\
0,&\,\text{otherwise.}\end{cases}$ (6)

For a graph state $\ket{G}$ any element of its stabilizer $\mathcal{S}$ is a
local symmetry. However, the state $\ket{G}$ can have more local symmetries
than those in $\mathcal{S}$ (see Ref. [38]). For example, consider a graph
state $\ket{G}$ where qubit $1$ is only connected to qubit $2$. Then qubit $1$
is called a _leaf_ , qubit $2$ is called its _parent_ and for any
$\alpha\in\mathbb{C}$ the operator

$e^{i\alpha X}\otimes e^{-i\alpha Z}\otimes\mathds{1}$ (7)

is a local symmetry of $\ket{G}$ (see Ref. [39]). In Ref. [38] some of the
authors of the current work studied, among other things, all local symmetries
of stabilizer states. While preparing the current work, we became aware of
Ref. [40] (and Ref. [41]), which studies equivalence of graphs under local
complementation. In this context, Ref. [40] also derives the local Clifford
symmetries of graph states.

In this work we are interested in a superset of local Clifford
transformations, so called party-local Clifford transformations (PLC). To
define these transformations, consider a partition $P(M,n)$ of the set
$[n]:=\\{1,\ldots n\\}$ into $M$ subsets. In the following, we refer to the
elements of $P(M,n)$ as parties. We call operators of the form

$\bigotimes_{\alpha\in P(M,n)}C_{\alpha}\ \text{ with }\
C_{\alpha}\in\mathcal{C}_{|\alpha|},$ (8)

party-local Clifford operators and we denote the subgroup generated by these
operators by $\mathcal{C}^{P(M,n)}$. Note that
$\mathcal{C}^{P(M,n)}\subset\mathcal{C}_{n}$ and equality only holds for
$M=1$. We say that an $n$-qubit stabilizer state is $M$-partite if its qubits
are distributed among $M$ parties. In the following we denote by
$\text{Stab}(P(M,n))$ the set of $n$-qubit stabilizer states that are
distributed according to the partition $P(M,n)$.

As we will discuss in Section 2.1, the Pauli group can be represented as a
vector space over a finite field. We denote by $\mathbb{Z}_{d}$ the finite
field of order $d$ for any prime number $d$. Over this field addition and
multiplication are carried out modulo $d$.

###  2.2 Motivation

In this section we explain our motivation for studying PLC transformation of
stabilizer states in quantum networks. We argue that PLC transformations are a
physically motivated extension of local operations.

As experimental techniques progress, the distribution of bipartite
entanglement between well connected nodes in a quantum network will no longer
be an expensive resource. For instance, if two nodes are spatially close they
might be considered as well connected. Nevertheless, two nodes can be not
spatially close and well connected if they can establish a large amount of
entanglement over long distances, e.g., via a satellite [42]. One can use this
bipartite entanglement to implement non-local gates. This setting effectively
breaks the network down into several parties, within which non-local
operations are possible.

Figure 2: Local complementation (LC) on the parties highlighted in green
compared to local complementation and edge removal/addition (LCE) on the
parties highlighted in grey.

Clifford operations play a special role in such a setting as they can be
implemented deterministically via gate teleportation (see Refs. [25, 43]).
Indeed, to apply a non-local gate $U\in\mathcal{C}_{2}$ to two qubits held by
spatially separated parties, we can distribute the Choi state
$U\otimes\mathds{1}\ket{\phi^{+}}^{\otimes 2}$ among the parties. After
performing a Bell measurement in each of the parties (each involving one qubit
of the Choi state and the one originally held by the party), the state of the
two unmeasured qubits is

$UP\varrho P^{\dagger}U^{\dagger}=UPU^{\dagger}(U\varrho
U^{\dagger})UP^{\dagger}U^{\dagger},$ (9)

where $P\in\mathcal{P}_{n}$ depends on the measurement result and $\rho$
denotes the initial state of the two qubits originally held by the parties. As
Clifford operators map the Pauli group onto itself, local Pauli corrections
suffice to invert $UPU^{\dagger}$. As the Clifford group is generated by
single and two-qubit gates (see Section 2.1), the above well-known
construction allows to implement any non-local Clifford gate. For other non-
local gates, which are not Clifford gates, the correction $UPU^{\dagger}$ will
not be local in general and thus a deterministic local correction is not
possible.

In this work we only consider PLC transformations among special types of
states, namely stabilizer states. This is, on the one hand, due to the
outstanding importance of these states for quantum information protocols. On
the other hand, Clifford operations map stabilizer states to stabilizer states
and thus these states are a natural candidate to study in the setting we
consider. Additionally, the experimental requirements to implement party-local
Clifford gates on stabilizer states are actually significantly less than what
we described above. For stabilizer states, the distribution of Bell states,
local $Z$ basis measurements and the application of Clifford gates, which act
locally on the nodes of the network, suffice to implement any party-local
Clifford gate. Indeed, it is easy to see that after distributing the Bell
state between two parties both parties can apply a $CZ$ between the qubits of
the stabilizer state and the Bell state, perform local complementation on the
qubits of the Bell state and then measure them in the $Z$ basis to implement a
non-local $CZ$ gate up to local Pauli corrections.

Motivated by the above, it is the goal of this work to approach a complete
characterization of PLC equivalence classes of stabilizer states.

###  2.3 Generalized local complementation

In this section, we study how party-local Clifford transformations from graph
states to graph states alter the corresponding graphs. We mentioned in Section
2.1 that local Clifford transformations which map a graph state to another
graph state correspond to a sequence of local complementations on the level of
the graphs [26]. We analyze how these results generalize to party-local
Clifford transformations in the following theorem.

######  Theorem 1.

Let $\ket{G}$ and $\ket{G^{\prime}}$ be $n$-qubit graph states distributed
among the parties $P(M,n)$. Then $\ket{G}$ is PLC equivalent to
$\ket{G^{\prime}}$ if and only if the graphs $G$ and $G^{\prime}$ are related
via a sequence of local complementations and edge additions/removals within
parties (LCE).

Let us compare Theorem 1 to the results of [26] for local Clifford operations.
We see that the only additional power party-local Clifford transformations
have over local Clifford transformations is the possibility of adding and
removing edges within parties. However, note that adding and removing edges
within parties and local complementations are non-commuting operations and
thus LCE generates larger orbits. The proof of Theorem 1 makes use of Lemma 2,
which is stated and proven in Appendix A . Here, we state only an informal
version of it, as this is sufficient to understand the reason for the validity
of Theorem 1.

######  Lemma 2 (informal version).

The action of any two-qubit Clifford gate on a graph state is equivalent to
the action of a suitable sequence of LCE up to local Clifford corrections.

Using Lemma 2 and the fact that $\mathcal{C}_{n}$ is generated by single and
two-qubit Clifford operators (see Section 2.1) we can then show Theorem 1. The
proof can be found in Appendix A.

###  2.4 Classification of PLC classes via invariant polynomials

The characterization of equivalence classes of states under certain operations
is a common task in quantum information theory. In the context of stochastic
local operations assisted by classical communication (SLOCC), invariant
polynomials proved to be a fruitful approach [44]. Motivated by this, we study
the use of invariant polynomials in the classification of PLC classes of
stabilizer states.

Consider a stabilizer state $\ket{\psi}\in\text{Stab}(P(M,n))$. We want to
identify all states in the PLC class of $\ket{\psi}$. To this end, let us
choose a set of generators $g_{1}^{\psi},\ldots,g_{n}^{\psi}$ for the
stabilizer $\mathcal{S}$ of $\ket{\psi}$ and define the polynomial

$I_{\ket{\psi}}(\ket{\phi})=\sum_{C\in\mathcal{C}_{n}^{P(M,n)}}\prod_{j=1}^{n}\innerproduct*{\phi}{C^{\dagger}g_{j}^{\psi}C|\phi}^{2}.$
(10)

Observe that this polynomial is obviously PLC invariant, i.e., for all
$C\in\mathcal{C}^{P(M,n)}$ it holds that
$I_{\ket{\psi}}(C\ket{\phi})=I_{\ket{\psi}}(\ket{\phi})$, and that
$I_{\ket{\psi}}=I_{C\ket{\psi}}$. Moreover, for any stabilizer state
$\ket{\phi}$ this polynomial is nonzero if and only if $\ket{\phi}$ is PLC
equivalent to $\ket{\psi}$, as we show in the following. Using the fact that
any stabilizer state can be written in terms of its stabilizer as in Equation
(2), and that every $P\in\mathcal{P}_{n}$ not equal to the identity is
traceless, a term in the polynomial in Equation (10) is nonzero if and only if
$\\{C^{\dagger}g_{i}^{\psi}C\\}_{i=1}^{n}$ generate the stabilizer of
$\ket{\phi}$ for some $C\in\mathcal{C}^{P(M,n)}$. Hence, the polynomial is
nonzero if and only if $\ket{\psi}$ and $\ket{\phi}$ are PLC equivalent. We
will see in Section 2.5 that it follows from the results of Ref. [28] that the
polynomial $I_{\ket{\psi}}$ only depends on the commutation relations of the
generators $g_{1}^{\psi},\ldots,g_{n}^{\psi}$ on the individual parties.

While each PLC equivalence class can be characterized by a polynomial as in
Equation (10), this characterization is not very practical. To our knowledge,
the only way to compute the value of such a polynomial (with the possible
exception of a small number of parties) for a given stabilizer state is to
explicitly perform the sum over all terms. If that is the case, computing the
polynomial is not more efficient than directly checking PLC equivalence by
computing the full PLC orbit.

Let us remark that invariants have been used previously to study PLC
equivalence of stabilizer states. Ref. [45] introduces a finite set of
invariants that completely characterize local Clifford equivalence of
stabilizer states. That is, two states are local Clifford equivalent if and
only if they agree in these invariants. Ref. [30] takes a similar approach,
defining so called homological invariants of stabilizer states, which apply to
arbitrary party sizes, and even qudit stabilizer states. These are used to
rederive the results on the extraction of GHZ states from Ref. [28] (see
Section 2.5).

###  2.5 Previous results

In this section we summarize the main results obtained in the context of PLC
transformations of stabilizer states, focusing on those that we use in the
following.

The classification of $3$-partite PLC equivalence classes of stabilizer states
was completely solved in Ref. [28]. There, it is shown that every $3$-partite
stabilizer state is PLC equivalent to a tensor product of a unique number of
copies of the states $\ket{0}$, $\ket{\phi^{+}}$ and $\ket{GHZ}$, see Figure 1
for an example. That is, two stabilizer states are PLC equivalent if and only
if their unique decompositions coincide. In the following we make use of some
of the techniques developed in Ref. [28]. Therefore, let us briefly introduce
some of the notation that was being used and discuss the content of the paper
in more detail. First, recall that the Pauli group $\mathcal{P}_{n}$ modulo
phases is isomorphic to the vector space $\mathbb{Z}_{2}^{2n}$. To see that,
one identifies the single-qubit Pauli operators and the identity operator with
elements of $\mathbb{Z}_{2}^{2}$ as

$\sigma_{0,0}=\mathds{1},\ \sigma_{1,0}=X,\ \sigma_{1,1}=Y,\ \sigma_{0,1}=Z.$
(11)

Then, one can define a map
$\sigma:\mathbb{Z}_{2}^{2n}\rightarrow\mathcal{P}_{n}$ via

$\sigma((a_{1},b_{1},\ldots,a_{n},b_{n}))=\sigma_{a_{1},b_{1}}\otimes\ldots\otimes\sigma_{a_{n},b_{n}}.$
(12)

From this relation one sees that the multiplication of Pauli operators
corresponds to the addition of their corresponding vectors in
$\mathbb{Z}_{2}^{2n}$, i.e.,

$\sigma(\bm{f})\sigma(\bm{g})\propto\sigma(\bm{f}+\bm{g})\ \ \
\bm{f},\bm{g}\in\mathbb{Z}_{2}^{2n}.$ (13)

The commutation relations of the Pauli operators define a symplectic bilinear
form $\omega:\mathbb{Z}_{2}^{2n}\rightarrow\mathbb{Z}_{2}$ by

$\sigma(\bm{f})\sigma(\bm{g})=e^{i\pi\omega(\bm{f},\bm{g})}\sigma(\bm{g})\sigma(\bm{f}).$
(14)

Indeed, writing $\bm{f}=(a_{1},b_{1}\ldots,a_{n},b_{n})$ and
$\bm{g}=(a_{1}^{\prime},b_{1}^{\prime},\ldots,a_{n}^{\prime},b_{n}^{\prime})$
the above definition implies that

$\displaystyle\begin{split}&\omega(\bm{f},\bm{g})\\\
&=(a_{1},\ldots,a_{n},b_{1},\ldots b_{n})\begin{pmatrix}0&\mathds{1}\\\
\mathds{1}&0\end{pmatrix}(a_{1}^{\prime},\ldots,a_{n}^{\prime},b_{1}^{\prime},\ldots
b_{n}^{\prime})^{T}.\end{split}$ (15)

Thus, the bilinear form $\omega$ satisfies $\omega(\bm{f},\bm{f})=0$, and is
non-degenerate, i.e., $\omega(\bm{f},\bm{g})=0$ for all $\bm{g}$ implies that
$\bm{f}=0$. We conclude that $\mathbb{Z}^{2n}_{2}$ together with $\omega$ is a
symplectic vector space. A brief introduction to symplectic vector spaces can
be found in Appendix B.

Every stabilizer $\mathcal{S}\subset\mathcal{P}_{n}$ can be written as
$\mathcal{S}=\\{\epsilon(\bm{f})\sigma(\bm{f})|\bm{f}\in V^{\mathcal{S}}\\}$
where $V^{\mathcal{S}}$ is a maximally isotropic subspace of
$\mathbb{Z}^{2n}_{2}$ and $\epsilon:V^{\mathcal{S}}\rightarrow\\{\pm 1\\}$ is
a suitable sign choice. A maximally isotropic subspace is a subspace which is
equal to its orthogonal complement defined via the symplectic form $\omega$
(for details see Appendix B). A set of generators of $\mathcal{S}$ corresponds
to a basis of $V^{\mathcal{S}}$ via the map $\sigma$. Choosing a different set
of generators of $\mathcal{S}$ is equivalent to a basis change in
$V^{\mathcal{S}}$ via Equation (13) and it is described by an invertible
matrix. Note that subspaces which are isotropic but not maximally isotropic,
i.e., which are contained in their orthogonal complement but not necessarily
equal to it, correspond to stabilizer codes.

Any Clifford operator $C\in\mathcal{C}_{n}$ defines a linear map
$u:\mathbb{Z}_{2}^{2n}\rightarrow\mathbb{Z}_{2}^{2n}$ via

$C\sigma(\bm{f})C^{\dagger}\propto\sigma(u(\bm{f})).$ (16)

As $C$ is unitary, $u$ is invertible and preserves the symplectic form
$\omega$, i.e., it is an isometry. In fact, one can show that any isometry on
$\mathbb{Z}_{2}^{2n}$ corresponds to a $C\in\mathcal{C}_{n}$ via the above
relation. This correspondence is unique up to phases.

Consider a set of parties $P(M,n)$. For every $\bm{f}\in\mathbb{Z}_{2}^{2n}$
and $\alpha\in P(M,n)$ we denote by
$\bm{f}_{\alpha}\in\mathbb{Z}_{2}^{2|\alpha|}$ the restriction of $\bm{f}$ to
party $\alpha$. For every party $\alpha\in P(M,n)$, we consider two subspaces,
the local subspace

$V^{\mathcal{S}}_{\alpha}=\\{\bm{f}\in V^{\mathcal{S}}|\bm{f}_{\beta}=0\
\forall\beta\in M,\beta\neq\alpha\\}$ (17)

and the colocal subspace

$V_{\hat{\alpha}}^{\mathcal{S}}=\\{\bm{f}\in
V^{\mathcal{S}}|\bm{f}_{\alpha}=0\\}.$ (18)

That is, while $V^{\mathcal{S}}_{\alpha}$ contains those vectors of
$V^{\mathcal{S}}$ that vanish on every party but $\alpha$, the subspace
$V^{\mathcal{S}}_{\alpha}$ contains those vectors that vanish on party
$\alpha$. Note that the dimension of $V_{\alpha}^{\mathcal{S}}$ is related to
rank of the reduced state via ${\rm rk}(\rho_{\alpha})=2^{|\alpha|-{\rm
dim}(V_{\alpha}^{\mathcal{S}})}$ (see Equation (3)). In this context, it is
helpful to define the support of a vector
$\bm{f}=(a_{1},b_{1},\ldots,a_{n},b_{n})\in\mathbb{Z}_{2}^{2n}$ as

$\text{supp}(\bm{f})=\\{i\in[n]|a_{i}=1\lor b_{i}=1\\}.$ (19)

Similarly, the support of a Pauli operator $P\propto\sigma(\bm{f})$ is given
$\text{supp}(P)=\text{supp}(\bm{f})$, i.e., the support of $P$ is where it
acts non-trivially.

With all the definitions in place let us recall the findings of Ref. [28] that
we will use here. There are two types of results in Ref. [28]. On the one
hand, the authors provide necessary and sufficient conditions for PLC
equivalence of stabilizer states. On the other hand, they use those conditions
to find the exact number of $M$-qubit, $M$-partite GHZ states one can extract
from an $M$-partite stabilizer state. Using this result, as well as the
conditions for PLC equivalence, they provide a complete solution to the
problem of PLC equivalence for $3$-partite stabilizer states. We start by
summarizing the necessary and sufficient conditions for PLC equivalence
derived in Ref. [28].

It is shown in Ref. [28] that the PLC equivalence of two stabilizer states
solely depends on how elements of their stabilizers commute on the individual
parties, as stated in the following theorem.

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

Let $\ket{\psi},\ket{\phi}\in\text{Stab}(P(M,n))$. Then, $\ket{\psi}$ and
$\ket{\phi}$ are PLC equivalent if and only if there exists a basis
$\bm{g}_{1},\ldots,\bm{g}_{n}$ of $V^{{\mathcal{S}}_{\psi}}$ and a basis
$\bm{f}_{1},\ldots,\bm{f}_{n}$ of $V^{{\mathcal{S}}_{\phi}}$ such that

$\omega((\bm{f}_{i})_{\alpha},(\bm{f}_{j})_{\alpha})=\omega((\bm{g}_{i})_{\alpha},(\bm{g}_{j})_{\alpha})$
(20)

for all $\alpha\in P(M,n)$ and $i,j\in[n]$.

That is, two stabilizer states are PLC equivalent iff there exist sets of
generators for $\mathcal{S}_{\psi}$ and $\mathcal{S}_{\phi}$ whose respective
commutation relations on all parties agree. In Ref. [28], this theorem is only
stated for stabilizer states of maximal local rank, i.e., states for which
$\text{dim}(V_{\alpha}^{\mathcal{S}})=0$ for all $\alpha\in P(M,n)$. However,
the authors mention that it extends to general stabilizer states. In Appendix
G we provide a proof for the general statement in the case of qudit systems of
prime dimension, as we use it in Section 4 where we study qudit systems of
prime dimension.

Moreover, Ref. [28] provides a theorem which gives necessary and sufficient
conditions for when a stabilizer state $\ket{\phi}$ can be extracted from a
stabilizer state $\ket{\psi}$ via PLC. We say a state
$\ket{\phi}\in\text{Stab}(P(M,m))$ can be extracted from a state
$\ket{\psi}\in\text{Stab}(P(M,n))$ with $n\geq m$ if there exists a PLC
transformation $C\in\mathcal{C}^{P(M,n)}$ and a $(n-m)$-qubit stabilizer state
$\ket{\phi^{\prime}}$ such that
$C\ket{\psi}=\ket{\phi}\otimes\ket{\phi^{\prime}}$. In this case, we say
$\ket{\psi}$ decomposes into $\ket{\phi}$ and $\ket{\phi^{\prime}}$.

######  Theorem 4 ([28]).

Let $\ket{\psi}\in\text{Stab}(P(M,n))$ and $\ket{\phi}\in\text{Stab}(P(M,m))$
with $n\geq m$. The state $\ket{\phi}$ can be extracted from $\ket{\psi}$ if
and only if there exists a linear injective map
$T:V^{\mathcal{S}_{\phi}}\rightarrow V^{\mathcal{S}_{\psi}}$ such that

  1. (i)

$\omega(T(\bm{f})_{\alpha},T(\bm{g})_{\alpha})=\omega(\bm{f}_{\alpha},\bm{g}_{\alpha})\
\forall\bm{f},\bm{g}\in V^{\mathcal{S}_{\phi}}\ \alpha\in P(M,n)$

  2. (ii)

$[T(V^{\mathcal{S}_{\phi}})]_{\hat{\alpha}}=T(V^{\mathcal{S}_{\phi}}_{\hat{\alpha}})$
for all $\alpha\in P(M,n)$.

Condition $(i)$ in Theorem 4 guarantees that the map $T$ preserves commutation
relations on every party. Condition $(ii)$ enforces that the party support of
$f$ and $T(f)$ is the same for all $\bm{f}\in V^{\mathcal{S}_{\phi}}$. This
condition is necessary as PLC transformations cannot change the party support
of Pauli operators. Note that Theorem 3 considers an extremal case of Theorem
4 where $n=m$. One can show that condition $(ii)$ in Theorem 4 becomes
obsolete in this case.

A simple case of extractability occurs if there exists a party $\alpha\in
P(M,n)$ such that $\text{dim}(V^{\mathcal{S}}_{\alpha})=d_{\alpha}>0$. It
follows directly from Theorem 4 that then $\ket{\psi}$ is PLC equivalent to a
state $\ket{\phi}\otimes\ket{0}^{\otimes d_{\alpha}}$. Note that an analogous
reasoning also applies to the qudit case (see Appendix G).

Using, in particular, Theorem 4 one can determine the maximum number of
$M$-qubit GHZ states shared among all parties that can be extracted from a
state $\ket{\psi}\in\text{Stab}(P(M,n))$ via PLC. This number is given by the
minimum number of generators of $\mathcal{S}_{\psi}$ which are truly
$M$-partite. To be more precise, let us consider the subspace

$V_{loc}=\text{span}\bigcup_{\alpha\in P(M,n)}V^{S}_{\hat{\alpha}}.$ (21)

It is shown in Ref. [28] that the maximum number of $M$-qubit GHZ states
distributed among all $M$ parties that can be extracted from $\ket{\psi}$ via
PLC is given by $\Delta=n-\text{dim}(V_{loc})$.

In the $3$-partite case, this result in combination with Theorem 4 leads to a
complete characterization of all PLC equivalence classes of stabilizer states
of arbitrary qubit number. As we have mentioned before, it is shown in Ref.
[28], that every $3$-partite stabilizer state decomposes into a tensor product
of $k_{1}$ copies of the $\ket{0}$ state, $k_{2}$ copies of the
$\ket{\phi^{+}}$ state, and $k_{3}$ copies of the $\ket{GHZ}$ state under PLC.
The number of copies of each of those states is unique and can be computed
efficiently. Two stabilizer states are PLC equivalent if and only if their
decompositions coincide, i.e., if the numbers of copies in the decompositions
of each of the states coincides. This statement still holds if one considers
party-local unitary operations (PLU) instead of PLC operations. Conversely,
any tensor product of the states $\ket{0},\ket{\phi^{+}}$ and $\ket{GHZ}$
uniquely characterizes a PLC class (of three parties), and also a PLU class
(Ref. [28]).

The authors of Ref. [28] therefore suggest to call
$\\{\ket{0},\ket{\phi^{+}},\ket{GHZ}\\}$ the entanglement generating set (EGS)
for $3$-partite stabilizer states. In this work, we use the EGS w.r.t. PLC
operations to characterize PLC equivalence classes for an arbitrary number of
parties. The entanglement generating set (EGS) for $M$-partite stabilizer
states under PLC is a minimal set EGSM of indecomposable $M$-partite
stabilizer states such that every $M$-partite stabilizer state decomposes
under PLC into a tensor product of the states contained in EGSM. It follows
directly from its definition that the EGS is unique up to PLC transformations
of the individual states it contains. In particular, it contains one
representative of every PLC class, which consists of indecomposable stabilizer
states. Note that there are stabilizer states which are LU equivalent but not
LC equivalent (see Ref. [46]). Therefore, the EGS, as we define it, can be
overcomplete regarding PLU transformations. Moreover, the EGSM is defined for
a fixed number of parties $M$ but an unbounded number of qubits. Thus, it is
possible that it contains infinitely many states.

The results of Ref. [28] imply that $3$-partite stabilizer states decompose
uniquely into states from the EGS3. Note that the results of [28] were also
partially extended to $2$\- and $3$-partite qudit systems, with $d$ such that
its prime decomposition only contains primes of power $0$ or $1$ in Ref. [29].
More precisely, the authors show that any $2$\- and $3$-partite qudit
stabilizer state, with $d$ as defined above, decomposes into a tensor product
of the states $\ket{0}$,
$\ket{\phi_{d}^{+}}=\frac{1}{\sqrt{d}}\sum_{j}\ket{jj}$ and
$\ket{GHZ^{d}}=\frac{1}{\sqrt{d}}\sum_{j}\ket{jjj}$.

In the light of the above summary let us briefly outline the rest of the
paper. In the following sections we introduce the commutation matrix formalism
as a powerful tool to study PLC equivalence of stabilizer states. This allows
us to use results from the classification theory of bilinear forms to study
the structure of the EGSM for qubits and qudits. Particularly, we derive
necessary and sufficient conditions for when a state is decomposable. While we
do not know whether or not qubit stabilizer state decompose uniquely into
states from the EGS, we prove that for qudit stabilizer states of prime
dimension the decomposition is indeed unique.

##  3 PLC transformations of stabilizer states and the commutation matrix
formalism

As we saw in the previous section, whether or not two stabilizer states are
PLC equivalent solely depends on the local commutation relations of operators
in their stabilizers (Theorem 3 shown in [28]). In this section, we introduce
a new formalism to exploit these findings in studying the PLC transformations
of stabilizer states.

Let $\ket{\psi}\in\text{Stab}(P(M,n))$ with stabilizer $\mathcal{S}$ and let
$\\{\bm{f}_{1},\ldots,\bm{f}_{n}\\}$ be a basis of its corresponding maximally
isotropic subspace $V^{\mathcal{S}}$. As we are only interested in the
subspace $V^{\mathcal{S}}$, we define the linear map
$R:V^{\mathcal{S}}\rightarrow\mathbb{Z}^{n}_{2}$ via $R\bm{f}_{i}=\bm{e}_{i}$
for all $i\in[n]$, where $\\{\bm{e}_{i}\\}$ denotes the standard basis of
$\mathbb{Z}_{2}^{n}$ 222This representation of the maximally isotropic
subspace $V^{\mathcal{S}}$ is equivalent to the representation of any element
$g\in\mathcal{S}$ as $g=g_{1}^{x_{1}}g_{2}^{x_{2}}\cdots g_{n}^{x_{n}}$, where
$\bm{x}\in\mathbb{Z}_{2}^{n}$.. The map $R$ is invertible and therefore
describes an isomorphism. For every party $\alpha\in P(M,n)$ we define a
bilinear form
$C_{\alpha}:\mathbb{Z}_{2}^{n}\times\mathbb{Z}_{2}^{n}\rightarrow\mathbb{Z}_{2}$
via

$C_{\alpha}(\bm{k},\bm{l})=\omega((R^{-1}\bm{k})_{\alpha},(R^{-1}\bm{l})_{\alpha}).$
(22)

As $\omega$ is a symplectic form, the bilinear forms $(C_{\alpha})_{\alpha}$
are _alternating_ , that is,
$C_{\alpha}(\bm{k},\bm{l})=-C_{\alpha}(\bm{l},\bm{k})$, and
$C_{\alpha}(\bm{k},\bm{k})=0$ for all $\bm{k},\bm{l}\in\mathbb{Z}_{2}^{n}$. As
we operate over the field $\mathbb{Z}_{2}$ we also have that
$C_{\alpha}(\bm{k},\bm{l})=C_{\alpha}(\bm{l},\bm{k})$. Note that they are not
symplectic in general as they can be degenerate, i.e., if
$C_{\alpha}(\bm{k},\bm{l})=0$ for all $\bm{l}\in\mathbb{Z}_{2}^{n}$, then this
does not imply that $\bm{k}=0$.

In slight abuse of notation we use $C_{\alpha}$ also to denote the matrix
representation of the respective bilinear form w.r.t. to the basis
$\\{\bm{e}_{i}\\}_{i\in[n]}$. Let us now make the following definition.

######  Definition 5.

Let $\ket{\psi}$ be an $M$-partite stabilizer state. We call the matrices
$(C_{\alpha})_{\alpha\in P(M,n)}$, describing the bilinear forms defined in
Equation (22) w.r.t. to the basis choice $\\{\bm{f}_{i}\\}$ of
$V^{\mathcal{S}}$, commutation matrices.

A commutation matrix $C_{\alpha}$ contains all information about the
commutation relations of the Pauli operators $\sigma(\bm{f}_{j})$ on the party
$\alpha$. More precisely, $(C_{\alpha})_{ij}=0$ iff $\sigma(\bm{f}_{i})$ and
$\sigma(\bm{f}_{j})$ commute on party $\alpha$, i.e.,
$[\sigma(\bm{f}_{i})_{\alpha},\sigma(\bm{f}_{j})_{\alpha}]=0$. Moreover, by
replacing the field $\mathbb{Z}_{2}$ with a finite field $\mathbb{Z}_{d}$ for
$d\geq 3$, commutation matrices can also be defined for qudit systems of prime
dimension, which we discuss in Section 4.

Let us discuss some properties of commutation matrices. Commutation matrices
are alternating as they describe alternating forms. Moreover they satisfy

$\sum_{\alpha\in P(M,n)}C_{\alpha}=0,$ (23)

where addition is performed modulo $2$. This condition is a direct consequence
of the fact that all generators globally commute, i.e., that $V^{\mathcal{S}}$
is isotropic. Indeed, as $[\sigma(\bm{f}_{i}),\sigma(\bm{f}_{j})]=0$ for all
$i,j$, the operators $\sigma(\bm{f}_{i})$ and $\sigma(\bm{f}_{j})$ anti-
commute on an even number of parties. Therefore
$\sum_{\alpha}(C_{\alpha})_{ij}=0$ for all $i,j$. Moreover, for two parties
$\alpha_{i},\alpha_{j}\in P(M,n)$ one finds that

$C_{\alpha_{1}}+C_{\alpha_{2}}=C_{\alpha_{1}\cup\alpha_{2}}.$ (24)

As noted in the definition, the commutation matrices depend on the chosen
basis $\\{\bm{f}_{1},\ldots,\bm{f}_{n}\\}$. A basis change in
$V^{\mathcal{S}}$, which is equivalent to choosing a different set of
generators for $\mathcal{S}$, is described by an invertible matrix $Q\in
M_{n\times n}(\mathbb{Z}_{2})$ on $\mathbb{Z}_{2}^{n}$. As commutation
matrices represent bilinear forms, the commutation matrices with respect to
the new basis are given by

$(Q^{T}C_{\alpha}Q)_{\alpha\in M}.$ (25)

In order to illustrate the formalism, let us present some examples of
commutation matrices that are relevant in the following. For the state
$\ket{\phi^{+}}$ distributed among the parties $P(2,2)=\\{\\{1\\},\\{2\\}\\}$
the commutation matrices w.r.t the canonical generators $g_{1}=X_{1}Z_{2}$ and
$g_{2}=Z_{1}X_{2}$, defined by Equation (5), are

$C_{\\{1\\}}=\begin{pmatrix}0&1\\\
1&0\end{pmatrix}\,\text{and}\,C_{\\{2\\}}=\begin{pmatrix}0&1\\\
1&0\end{pmatrix}.$ (26)

For the state $\ket{GHZ}$ distributed among the parties
$P(3,3)=\\{\\{1\\},\\{2\\},\\{3\\}\\}$ the commutation matrices w.r.t the
canonical generators $g_{1}=X_{1}Z_{2}$, $g_{2}=Z_{1}X_{2}Z_{3}$ and
$g_{3}=Z_{2}X_{3}$ are

$\displaystyle C_{\\{1\\}}$ $\displaystyle=\begin{pmatrix}0&1&0\\\ 1&0&0\\\
0&0&0\end{pmatrix},C_{\\{2\\}}=\begin{pmatrix}0&1&0\\\ 1&0&1\\\
0&1&0\end{pmatrix},$ $\displaystyle C_{\\{3\\}}$
$\displaystyle=\begin{pmatrix}0&0&0\\\ 0&0&1\\\ 0&1&0\end{pmatrix}.$ (27)

It can be easily verified that they satisfy all the requirements listed above,
i.e., they are alternating, and sum up to zero.

If we instead choose the generators $g_{1},g_{2},g_{2}g_{3}$, the associated
tuple of commutation matrices is

$\displaystyle\tilde{C}_{\\{1\\}}$ $\displaystyle=\begin{pmatrix}0&1&1\\\
1&0&0\\\ 1&0&0\end{pmatrix},\tilde{C}_{\\{2\\}}=\begin{pmatrix}0&1&1\\\
1&0&1\\\ 1&1&0\end{pmatrix},$ $\displaystyle\tilde{C}_{\\{3\\}}$
$\displaystyle=\begin{pmatrix}0&0&0\\\ 0&0&1\\\ 0&1&0\end{pmatrix}.$ (28)

Again, it is straightforward to verify that these commutation matrices result
from the original ones by a congruence transformation with the invertible
matrix

$Q=\begin{pmatrix}1&0&0\\\ 0&1&0\\\ 0&1&1\\\ \end{pmatrix}.$ (29)

In fact, the states that we have just discussed are graph states, as the
generators of their stabilizers correspond to the canonical generators in
Equation 5. For these states there exists a simple way to compute a tuple of
commutation matrices from the adjacency matrix $\Gamma_{G}$. One finds that if
$\Gamma_{G}(i)$ denotes the matrix that agrees with $\Gamma_{G}$ in row and
column $i$ and is zero everywhere else, then

$C_{\alpha}=\sum_{i\in\alpha}\Gamma_{G}(i).$ (30)

However, not every tuple of alternating matrices which satisfies Equation (23)
corresponds to a stabilizer state, i.e., a maximally isotropic subspace. As we
show in the following Theorem, the ranks of the matrices in tuples
corresponding to stabilizer states are constrained.

######  Theorem 6.

Let $(C_{\alpha})_{\alpha\in P(M,n)}$, $C_{\alpha}\in M_{n\times
n}(\mathbb{Z}_{2})$ be a tuple of alternating matrices such that
$\sum_{\alpha}C_{\alpha}=0$ for some partition $P(M,n)$. Then there exists a
$\ket{\psi}\in\text{Stab}(P(M,n))$ such that $(C_{\alpha})_{\alpha}$ are the
corresponding commutation matrices if and only if

$2\,{\rm rk}([C_{\alpha}]_{\alpha})=\sum_{\alpha}{\rm rk}(C_{\alpha}).$ (31)

Here, $[C_{\alpha}]_{\alpha}$ denotes the $n\times(nm)$ matrix obtained by
concatenating all matrices $C_{\alpha}$, and the rank is taken over the field
$\mathbb{Z}_{2}$.

To explain this condition let us note that the rank of a commutation matrix is
related to the rank of the reduced stabilizer state as
$2^{\text{rk}(C_{\alpha})/2}=\text{rk}(\rho_{\alpha})$. Therefore,
$\text{rk}(C_{\alpha})/2$ coincides with the number of qubits in party
$\alpha$ that are effectively entangled to another party (see discussion in
Appendix C). Observe that ${\rm rk}([C_{\alpha}]_{\alpha})={\rm
rk}([QC_{\alpha}Q^{T}]_{\alpha})$ for any invertible matrix $Q$. Therefore,
$n-{\rm rk}([C_{\alpha}]_{\alpha})$ is the maximum number of generators that
locally commute with all other generators of $\mathcal{S}$. As $\mathcal{S}$
is a maximally abelian subgroup it follows that those generators can be chosen
to have support only on one party, and thus correspond to extractable qubits
in the state $\ket{0}$. Thus, the rank condition in Equation (31) states the
following. The sum over the number of qubits in each party which are
effectively entangled to another one outside the party has to be equal to the
difference between $n$ and the total number of qubits in the state $\ket{0}$
that can be extract from $\ket{\psi}$. The latter number is precisely given by
$n-{\rm rk}([C_{\alpha}]_{\alpha})$.

For general alternating matrices $(C_{\alpha})_{\alpha\in P(M,n)}$ which sum
up to zero, Equation (31) becomes an inequality

$2\,{\rm rk}([C_{\alpha}]_{\alpha})\leq\sum_{i=1}^{M}{\rm rk}(C_{i}).$ (32)

Commutation matrices are precisely those sets of matrices that saturate this
bound. For the details of the proof of this inequality and for the proof of
Theorem 6 see Appendix C and the discussion below. Note that one can show that
tuples of alternating matrices which do not satisfy Equation (31) are
associated to stabilizer codes. Thus, one can also use this formalism to study
PLC equivalence of stabilizer codes. However, in this case the condition for
PLC equivalence is more complicated. Addressing this task is beyond the scope
of this paper.

Given a tuple of commutation matrices one can construct a corresponding
stabilizer state, as we show in the following. The idea is to go through all
parties and transform the respective commutation matrix to a form where it is
easy to choose a correct form for the generators. Finally, the transformations
are reversed. More precisely, one proceeds as follows. Let us first consider
first the case ${\rm rk}([C_{\alpha}]_{\alpha})=n$ and then deal with the case
${\rm rk}([C_{\alpha}]_{\alpha})<n$.

  * –

Initialize the operators $g_{1},\ldots,g_{n}$ to $\mathds{1}$.

  * –

For each party $\alpha$ proceed as follows:

    * $\rightarrow$

Assign ${\rm rk}(C_{\alpha})/2$ qubits to party $\alpha$. For this iteration
of the loop, these qubits are labeled from $1$ to ${\rm rk}(C_{\alpha})/2$.

    * $\rightarrow$

Find an invertible matrix $P\in M_{n\times n}(\mathbb{Z}_{2})$ such that
$PC_{\alpha}P^{T}$ is of the form described in Theorem 18, i.e., a direct sum
of the blocks

$\begin{pmatrix}0\end{pmatrix},\text{ and }\begin{pmatrix}0&1\\\
1&0\end{pmatrix}.$

    * $\rightarrow$

Let $\tilde{g}_{1},\ldots,\tilde{g}_{n}$ be this new set of generators
(obtained as products of the old generators). For all $j\in[n-1]$, if
$(PC_{\alpha}P^{T})_{j,j+1}=1$, set $(\tilde{g}_{j})_{\alpha}=X_{(j+1)/2}$ and
$(\tilde{g}_{j+1})_{\alpha}=Z_{(j+1)/2}$.

    * $\rightarrow$

Then undo the change of generators according to $P^{-1}$.

  * –

After determining all operators $g_{j}$ check whether $g_{j}^{2}=+\mathds{1}$
or $-\mathds{1}$. In the latter case replace $g_{j}$ by $ig_{j}$.

First, observe that the rank condition in Eq. (31) ensures that the algorithm
defines generators acting on $n$ qubits. It is clear that implementing this
algorithm for every party, the commutation relations of the operators
$g_{1},\ldots,g_{n}$ are described by $(C_{\alpha})_{\alpha}$. Thus, the
$g_{1},\ldots,g_{n}$ commute. Moreover, they are independent as ${\rm
rk}([C_{\alpha}]_{\alpha})=n$ and, due to the last step of the algorithm,
$g_{i}^{2}=\mathds{1}$ for all $i\in[n]$. Therefore, any element of the
generated subgroup is a product of powers zero or one of each generator. If
any of these powers is one, the generated operator is not proportional to
$\mathds{1}$ as the generators are independent. If all powers are zero, then
the operator is equal to $\mathds{1}$ due to the last step of the algorithm.
We conclude that $g_{1},\ldots,g_{n}$ generate an $n$-qubit stabilizer
corresponding to a stabilizer state.

In case ${\rm rk}([C_{\alpha}]_{\alpha})<n$, the construction has to be
slightly modified. First, one finds an invertible matrix $R$ such that the
last $w=n-\text{rk}([C_{\alpha}]_{\alpha})$ rows of
$[RC_{\alpha}R^{T}]_{\alpha}$ are zero. Then, one can assign
$\text{rk}(C_{\alpha})/2$ qubits to party $\alpha$ for every $\alpha\in
P(M,n)$ and determine the generators $g_{1},\ldots,g_{n-w}$ as above. The
remaining $n-{\rm rk}([C_{\alpha}]_{\alpha})$ qubits, which are in the state
$\ket{0}$, can be distributed arbitrarily among the parties. Let us number the
qubits in the state such that those appear last. Then we define $g_{j}=Z_{j}$
for all $j\in\\{n-w+1,\ldots,n\\}$. Finally, we undo the change of generators
according to $R^{-1}$. It is straightforward to verify that the operators
obtained this way define a stabilizer corresponding to a stabilizer state.
Again Eq. (31) ensures that the algorithm defines generators acting on $n$
qubits.

Let us discuss the relevance of commutation matrices in the context of PLC
transformations. Theorem 3 ([28]) states that two stabilizer states are PLC
equivalent if their stabilizers admit sets of generators with the same
commutation relations on each party. In terms of commutation matrices this
Theorem reads as follows.

######  Theorem 7.

Let $\ket{\psi},\ket{\phi}\in\text{Stab}(P(M,n))$. Then $\ket{\psi}$ is PLC
equivalent to $\ket{\phi}$ if and only if they admit the same tuple of
commutation matrices.

As all sets of commutation matrices of a state are related via a congruence
transformation, this theorem is equivalent to the following: $\ket{\psi}$ and
$\ket{\phi}$ are PLC equivalent if any two tuples of commutation matrices
$(C_{\alpha}^{\psi})_{\alpha}$, and $(C_{\alpha}^{\phi})_{\alpha}$ are
congruent to each other. Consequently, a set of commutation matrices and every
congruent set uniquely characterizes a PLC equivalence class. Thus, in order
to characterize all PLC classes we have to find a maximal set of non-congruent
tuples of commutation matrices.

###  3.1 The EGS and commutation matrices

We argued in the previous section that the classification of PLC classes is
equivalent to the classification of commutation matrices up to congruence. A
common approach to classify tuples of matrices under certain operations is to
first establish that these tuples decompose uniquely into indecomposable
blocks (up to reordering and equivalence of the blocks). Then, the
classification task is solved by presenting a complete set of indecomposable
tuples. We show in this section that these two tasks are equivalent to the
ones we want to solve for stabilizer states. Namely, we show that stabilizer
states decompose uniquely into indecomposable states if and only if this is
true for commutation matrices. Moreover, finding the EGS is equivalent to
finding a maximal set of non-congruent indecomposable commutation matrices.

Let us start by making more precise the notion of decomposability of
stabilizer states and their corresponding tuples of commutation matrices. To
that end, consider the tensor product of two stabilizer states
$\ket{\psi}\otimes\ket{\varphi}$, and let $\\{g_{i}\\}_{i}$ be the generators
of $\mathcal{S}_{\psi}$ and $\\{h_{i}\\}_{i}$ the generators of
$\mathcal{S}_{\varphi}$ respectively. Such a state is clearly decomposable.
Observe that the two sets of generators are mutually commuting, globally but
also locally, as they are acting on different qubits. Thus, their commutation
matrices are block-diagonal, where one block corresponds to the generators of
$\ket{\psi}$ and the other to the generators of $\ket{\varphi}$, i.e.,

$C_{\alpha}(\ket{\psi}\otimes\ket{\varphi})=C_{\alpha}(\ket{\psi})\oplus
C_{\alpha}(\ket{\varphi}).$ (33)

To see that the converse is also true the following theorem establishes the
connection between decomposability of stabilizer states and the block-
diagonalizability of their commutation matrices.

######  Theorem 8.

Let $\ket{\psi}\in\text{Stab}(P(M,n))$ and let $(C_{\alpha})_{\alpha\in
P(M,n)}$ be a tuple of commutation matrices. Then $\ket{\psi}$ is decomposable
if and only if there exists an invertible matrix $Q\in M_{n\times
n}(\mathbb{Z}_{2})$, and matrices $B_{\alpha}^{1}\in M_{n_{1}\times
n_{1}}(\mathbb{Z}_{2})$, $B_{\alpha}^{2}\in M_{n_{2}\times
n_{2}}(\mathbb{Z}_{2})$ such that $(QC_{\alpha}Q^{T})_{\alpha\in
M}=(B_{\alpha}^{1}\oplus B_{\alpha}^{2})_{\alpha\in M}$.

###### Proof.

The proof of the only if part follows directly from Theorem 3 and the fact
that all tuples of commutation matrices associated to same state are
congruent.

Next, we prove the if part. Suppose there exists a an invertible matrix $Q\in
M_{n\times n}(\mathbb{Z}_{2})$ such that $(QC_{\alpha}Q^{T})_{\alpha\in
P(M,n)}=(B_{\alpha}^{1}\oplus B_{\alpha}^{2})_{\alpha}$. As
$(B_{\alpha}^{1}\oplus B_{\alpha}^{2})_{\alpha}$ is a tuple of commutation
matrices, it satisfies Equation (31). That is,

$2\,{\rm rk}([B_{\alpha}^{1}+B_{\alpha}^{2}])=\sum_{\alpha}{\rm
rk}(B_{\alpha}^{1}\oplus B_{\alpha}^{2})$ (34)

or equivalently,

$2\,{\rm rk}([B_{\alpha}^{1}])+2\,{\rm rk}([B_{\alpha}^{2}])=\sum_{\alpha}{\rm
rk}(B_{\alpha}^{1})+\sum_{\alpha}{\rm rk}(B_{\alpha}^{2}).$ (35)

As $2\,{\rm rk}([B_{\alpha}^{i}])\leq\sum_{\alpha}{\rm rk}(B_{\alpha}^{i})$
(see Inequality (32)) Equation (35) can hold only if $2\,{\rm
rk}([B_{\alpha}^{i}])=\sum_{\alpha}{\rm rk}(B_{\alpha}^{i})$. Thus,
$(B_{\alpha}^{1})$ and $(B_{\alpha}^{2})$ are tuples of commutation matrices.
Let $\ket{\phi_{1}}$ and $\ket{\phi_{2}}$ be the corresponding $M$-partite
stabilizer states. It follows from Theorem 3 that $\ket{\psi}$ is PLC
equivalent to $\ket{\phi_{1}}\otimes\ket{\phi_{2}}$ and is therefore
decomposable. ∎

This theorem establishes that decomposing stabilizer states into other
stabilizer states is equivalent to decomposing tuples of commutation matrices
into blocks. Therefore, to identify states in the EGS we have to identify
indecomposable tuples of commutation matrices. The question whether or not
stabilizer states decompose uniquely into indecomposable ones is equivalent to
whether or not tuples of commutation matrices uniquely decompose into
indecomposable blocks.

These questions were studied for general tuples of alternating matrices in
linear algebra in the last century. We summarize the main results in the
following. For a more detailed description we refer the reader to Appendix D.
Let us stress that we are only interested in the classification of a special
subset of these tuples, namely those which satisfy Equation (31).

How much is known about the problem very much depends on the field one
considers. For the field $\mathbb{Z}_{2}$, up to our knowledge, both questions
have only been answered for tuples of length $1$ and $2$. The solution for a
single matrix is given by Theorem 18 (see Appendix B), which establishes that
the only indecomposable blocks are given by

$\begin{pmatrix}0\end{pmatrix},\text{ and }\begin{pmatrix}0&1\\\
1&0\end{pmatrix}.$ (36)

Theorem 18 also implies that the decomposition into these blocks is unique.
This follows from the simple fact that a congruence transformation cannot
change the rank of a matrix and therefore the number of blocks of each type is
fixed. Comparing the above result to the commutation matrices of the state
$\ket{\phi^{+}}$ in Equation (26) one sees that this implies that any
bipartite stabilizer state decomposes uniquely into a tensor product of copies
of the state $\ket{\phi^{+}}$ and the state $\ket{0}$.

For tuples of length $2$ Ref. [47] establishes the uniqueness of the
decomposition and states a complete set of indecomposable pairs of alternating
forms. To obtain these results the author shows that the classification of
pairs of alternating forms is equivalent to the classification of the better
known matrix pencils. Due to Equation (23), these results directly apply to
the characterization of the EGS for $3$-partite stabilizer states. In fact,
they precisely reproduce the results of Ref. [28] regarding PLC equivalence
classes. To see this, one starts from the general classification of Ref. [47]
and considers only those indecomposable tuples which satisfy the rank
condition in Equation (31). For a more detailed discussion we refer the reader
to Appendix D.

Up to our knowledge, the solution for tuples of length $\geq 3$ for the field
$\mathbb{Z}_{2}$ is not known. However, for algebraically closed fields of
characteristic $\neq 2$ it is shown in Ref. [48] that the classification of
triples of alternating forms is a _wild_ problem, i.e., it is at least as hard
as classifying pairs of matrices up to simultaneous similarity. The latter
task is considered to be very challenging. This suggests that also in the case
of the field $\mathbb{Z}_{2}$, classifying general triples of alternating
forms is difficult. However, due to Equation (31) we are only interested in
very special triples of matrices and thus a complete characterization of
indecomposables tuples might be possible beyond pairs of matrices.

For the field $\mathbb{Z}_{d}$ with $d\geq 3$ the situation is different.
Here, Ref. [34] establishes the uniqueness of the decomposition for arbitrary
tuples of alternating matrices (cf. Theorem 2 in Ref. [34], see also Appendix
D). As mentioned earlier, the commutation matrix formalism generalizes to
qudit stabilizer states for prime dimension. In this case, the commutation
matrices are defined over the field $\mathbb{Z}_{d}$. Therefore, by
establishing the equivalence between the decomposition of commutation matrices
and the decomposition of stabilizer states (see Section 4) we show via the
results of Ref. [34] that qudit stabilizer states decompose uniquely into
indecomposable ones under PLC (see Section 4).

We comment in Appendix H on our approach to show the uniqueness of the
decomposition for qubit systems. We prove that stabilizer states without PLC
symmetries decompose uniquely. However, these symmetries seem to be common, at
least for four parties (see the states in Figure 4) as many states in the EGS4
up to $10$ qubits contain leafs, which yield additional symmetries.

###  3.2 Necessary and sufficient conditions for decomposability

In this section we introduce useful tools for studying decompositions of
stabilizer states. In particular, we focus on the application of the
commutation matrix formalism. We discuss Fitting’s Lemma (see, e.g., Ref.
[34]), which provides necessary and sufficient conditions for decomposability
of tuples of alternating matrices, and in particular of commutation matrices.

First, let us present a lemma which gives sufficient conditions for the
extraction of the state $\ket*{GHZ_{M-1}}$ or $\ket*{GHZ_{M}}$ from an
$M$-partite stabilizer state.

######  Lemma 9.

Let $P(M,n)=\\{\alpha_{1},\ldots,\alpha_{M}\\}$ be a partition and let
$\ket{\psi}\in\text{Stab}(P(M,n))$ have full local ranks, i.e.,
$\text{dim}(V^{\mathcal{S}}_{\alpha})=0$ for all $\alpha\in P(M,n)$. Then one
can extract either $\ket*{GHZ_{M-1}}$ or $\ket{GHZ_{M}}$ from $\ket{\psi}$ if
and only if there exist elements $f_{1},\ldots,f_{M-2}$ in $\mathcal{S}$ such
that $\text{supp}(f_{j})=\alpha_{1}\cup\alpha_{j+1}$ and
$(f_{j})_{\alpha_{1}}=(f_{k})_{\alpha_{1}}$ for all $j,k\in[M-2]$.

The proof of this lemma can be found in Appendix E. It makes use of the fact
that $\mathcal{S}$ is a maximally isotropic subspace. This fact in combination
with the special operators $f_{j}$ it has to contain is enough to show that
the conditions of Theorem 4 are satisfied and an extraction is possible
333Note that Ref. [30] also contains conditions under which one can extract a
GHZ state from a given stabilizer states, even between less than $M-1$
parties..

Next, let us discuss how one can analyze decompositions of tuples of
commutations (and thereby decompositions of the corresponding stabilizer
states). It is a well-known fact that to study decompositions of a tuples of
alternating matrices into blocks one can equivalently study the ring of self-
adjoint endomorphisms of the corresponding tuple. A self-adjoint endomorphism
of a tuple of alternating matrices $(C_{\alpha})_{\alpha\in P(M,n)}$,
$C_{\alpha}\in M_{n\times n}(\mathbb{Z}_{2})$ is a matrix $E\in M_{n\times
n}(\mathbb{Z}_{2})$ such that

$C_{\alpha}E=E^{T}C_{\alpha}$ (37)

holds for all $\alpha\in P(M,n)$. Self-adjoint endomorphisms enjoy many useful
properties that we will frequently make use of in what follows. It directly
follows from the defining Equation (37) that the set of self-adjoint
endomorphisms is closed under products and additions and therefore forms a
ring. In particular, whenever $E$ is a self-adjoint endomorphism, so are its
powers $E^{m}$. It is straightforward to verify that for any $m\in\mathbb{N}$
it holds that $\text{ran}(E^{m})\supseteq\text{ran}(E^{m+1})$, and
$\text{ker}(E^{m})\subseteq\text{ker}(E^{m+1})$. For invertible endomorphisms
the range coincides with the full vector space for any power of $E$, and for
nilpotent endomorphisms one finds $k\in\mathbb{N}$ such that $E^{k}=0$. For
finite dimensional vector spaces, and in particular over finite fields, one
can always find an $l\in\mathbb{N}$ for which
$\text{ran}(E^{l})=\text{ran}(E^{l+1})$, and
$\text{ker}(E^{l})=\text{ker}(E^{l+1})$, that is $E^{l}$ acts as a bijection
on its range. Over finite fields, $\text{ran}(E^{l})$ is a finite set and,
therefore, $E^{l}$ is a permutation on it. Therefore, there exists a power
$p\geq l$ for which $E^{p}$ acts as the identity on its range and thus
fulfills $(E^{p})^{2}=E^{p}$, i.e., $E^{p}$ is _idempotent_. The existence of
idempotent elements that are neither invertible nor nilpotent plays a crucial
role in deciding if a set of commutation matrices is decomposable. The
following lemma, known as Fitting’s lemma, explains how properties of self-
adjoint endomorphisms relate to the decomposition of $(C_{\alpha})_{\alpha\in
P(M,n)}$ into blocks.

######  Lemma 10 (Fitting’s lemma [34]).

Let $F$ be any field, let $I\subset\mathbb{N}$ be a finite index set and let
$(A_{\alpha})_{\alpha\in I}$, $A_{\alpha}\in M_{n\times n}(F)$ be a tuple of
alternating matrices. Then, $(A_{\alpha})_{\alpha\in I}$ is indecomposable
under congruence if and only if all self-adjoint endomorphisms of
$(A_{\alpha})_{\alpha\in I}$ are either nilpotent or invertible.

Let us include a proof of the lemma for finite fields as it illustrates its
application in the context of commutation matrices.

###### Proof.

Let $(A_{i})_{i}$ be a tuple of alternating $n\times n$ matrices. As $F$ is
finite, for any endomorphism of $(A_{i})_{i}$ there exists a $k\in\mathbb{N}$
such that $E^{2k}=E^{k}$ (see the discussion above Lemma 10). Thus, there
exists an invertible matrix $R$ such that $E^{k}=R^{-1}(\mathds{1}\oplus 0)R$.
It is straightforward to verify that $\mathds{1}\oplus 0$ is a self-adjoint
endomorphism of $(RA_{i}R^{T})$. We conclude that if $\text{ker}(E^{k})\neq
F^{n}$ or $\text{R}(E^{k})\neq F^{n}$, then $(RA_{i}R^{T})_{i}$ is
blockdiagonal. ∎

Hence, they are simultaneously decomposable if and only if there exists an
idempotent endomorphism which is neither invertible nor nilpotent 444Note that
Fitting’s lemma is usually stated for decompositions into blocks under
isomorphisms, i.e., under transformations of the form $QC_{\alpha}R$, where
$Q,R$ are invertible (see for instance Ref. [49]). However, for our purposes
the version presented in Ref. [34] is the relevant one, as it is formulated
for congruence.

Lemma 10 is particularly useful if one wants to numerically decide whether or
not a stabilizer state is decomposable. As Equation (37) is linear in the
entries of $E$, it is efficient to compute a basis of the endomorphism ring.
The endomorphism ring generated by this basis is finite as we work over the
finite field $\mathbb{Z}_{2}$ and there are only finitely many matrices over
$\mathbb{Z}_{2}$. Thus, if the ring is not too large one can check whether
every element is either nilpotent or invertible, or equivalently, if there
exists a idempotent element that is neither invertible nor nilpotent. As we
will see later, this insight is very useful for numerically computing the EGS.

###  3.3 The EGSM for $M\geq 4$

We explained in the previous sections that to characterize the PLC classes of
$M$-partite stabilizer states we can characterize the EGSM and establish that
$M$-partite stabilizer states decompose uniquely into indecomposable ones. In
this section we are concerned with the structure of the EGSM for $M\geq 4$. We
show that the EGS4 and therefore any EGSM for $M\geq 4$ is an infinite set.
This is even the case if we consider PLU instead of PLC transformations.

Let us show that the EGS4 is an infinite set w.r.t. PLC transformations.
Consider the spiral graph states $\ket{G_{n}}$ defined for any
$n\in\mathbb{N}$, $n\geq 4$, in Figure 3. These states are distributed among
the parties $P(4,n)=\\{\alpha_{1},\alpha_{2},\alpha_{3},\alpha_{4}\\}$.

Figure 3: Sequence of the spiral graph states $\ket{G_{n}}$ and their
distribution among four parties
$P(4,n)=\\{\alpha_{1},\alpha_{2},\alpha_{3},\alpha_{4}\\}$; all of these graph
states are indecomposable.

######  Theorem 11.

For any $n\in\mathbb{N}$ the state $\ket{G_{n}}$ is indecomposable.

We show this Theorem in Appendix F. The proof makes use of the fact that if a
tuple of linear combinations of commutation matrices is indecomposable, then
so is the original tuple. Using the complete classification of indecomposable
pairs of alternating forms from Ref. [47] it is straightforward to verify that
if
$(C_{\alpha_{1}}^{(n)},C_{\alpha_{2}}^{(n)},C_{\alpha_{3}}^{(n)},C_{\alpha_{4}}^{(n)})$
are the commutation matrices of the spiral graph state $\ket{G_{n}}$, then
$(C_{\alpha_{1}}^{(n)}+C_{\alpha_{2}}^{(n)},C_{\alpha_{2}}^{(n)}+C_{\alpha_{3}}^{(n)})$
is indecomposable for any $n$. As the EGS4 contains one representative of
every PLC class which only consists of indecomposable states,
$\ket{G_{n}}\in\text{EGS}_{4}$ for any $n$ and thus EGS4 contains infinitely
many states. Moreover, as $\text{EGS}_{4}\subset\text{EGS}_{M}$ for any $M\geq
4$, we have the following corollary.

######  Corollary 12.

The EGSM is infinite for any $M\geq 4$.

Thus, by simply increasing the number of parties from $3$ to $4$ the EGS
changes from a finite set of three states (up to permutation) to an infinite
set.

Let us address the question whether the EGS is infinite only due to
considering PLC operations instead of more general PLU operations. Indeed, it
could be that the EGS is finite when considering PLU operations. The following
discussion, however, shows that this is not the case. By studying which
additional transformations of the spiral graph states $\ket{G_{4n}}$ are
enabled by PLU operations compared to PLC operations one realizes that they
are equally powerful, as stated in the following theorem. A proof can be found
in Appendix F.

######  Theorem 13.

Let $U$ be a PLU transformation such that $U\ket{G_{4n}}=\ket{H_{4n}}$ is a
stabilizer state. Then, there exists a PLC transformation
$C\in\mathcal{C}_{4n}^{P(4,4n)}$ such that $C\ket{G_{4n}}=\ket{H_{4n}}$.

The theorem relies on properties of the PLU symmetry group of the spiral graph
states $\ket{G_{4n}}$. Note that any PLU transformation between stabilizer
states defines a bijection between their respective PLU symmetry groups.
Theorem 13 implies that the spiral graph states $\ket{G_{4n}}$ are
indecomposable under PLU operations and therefore are elements of the EGSM
w.r.t. PLU operations for any $M\geq 4$. Thus, stabilizer states on $M\geq 4$
parties contain infinitely many different types of stabilizer state
entanglement.

###  3.4 The EGS4 up to $10$ qubits

Figure 4: EGS4 for up to $10$ qubits. The first three states generate all
stabilizer states on two- and three-partite qubit stabilizer states [27, 28].
The EGS4 on four qubits contains the GHZ state as well as the linear cluster
state (up to permutations) with different positions of its leaf parent pairs.
For five, six and seven qubits one finds that only the PLC classes of spiral
graphs are indecomposable. For eight qubits, the spiral graph appears three
times with different positions of its leaf parent pairs, while the other two
graphs have a structure different from the spiral graph. Particularly the last
graph for eight qubits has an interesting structure, since it contains three
leaf parent pairs. Finally, for nine and ten qubits only the PLC classes of
the spiral graphs are indecomposable.

The results from the previous section suggest that a complete characterization
of all indecomposable stabilizer states for an arbitrary number of parties is
a difficult task. Nevertheless, let us turn to the simplest non-solved case,
namely EGS4, and present some results on the states it contains. Intuitively,
we expect that not every distribution of qubits among the $4$ parties allows
for the existence of an indecomposable state. Indeed, it can be shown that any
state, where one party contains more than twice the number of qubits of the
party with the smallest number of qubits, is decomposable, as stated by the
following observation.

######  Observation 14.

Let $P(4,n)=\\{\alpha_{1},\alpha_{2},\alpha_{3},\alpha_{4}\\}$ be a partition
such that $|\alpha_{1}|\geq|\alpha_{2}|\geq|\alpha_{3}|\geq|\alpha_{4}|$ and
$\ket{\psi}\in\text{Stab}(P(M,n))$. Then $\ket{\psi}$ is decomposable if
$|\alpha_{1}|>2|\alpha_{4}|$.

The bound is simple consequence of Lemma 9, which gives sufficient conditions
for when one can extract GHZ states from a stabilizer state. Note that this
bound is not tight, as we will see later, i.e., there exist qubit
configurations for which all states are decomposable which is not implied by
the above observation. This is not surprising as Observation 14 does not take
into account whether $4$-partite stabilizer states other than the GHZ state
can be extracted. Now let us compute the EGS4 up to $10$ qubits. We explain in
detail how we utilize the commutation matrix formalism in this computation
555The code is written for Python 3 and can be made available from the authors
upon reasonable request..

From Observation 14 it is clear that for up to $9$ qubits only qubits
distributed among parties specified by the tuples $(1,1,1,1)$, $(2,1,1,1)$,
$(2,2,1,1)$, $(2,2,2,1)$, $(2,2,2,2)$, and $(3,2,2,2)$ can lead to
indecomposable stabilizer states. To find the maximal set of indecomposable
PLC inequivalent set of stabilizer states we proceed as follows. First, for
each configuration containing up to $7$ qubits we generate all possible graph
states and remove the decomposable ones. To this end, we compute a tuple of
commutation matrices for each state and then check decomposability by
computing a basis of the endomorphism ring and checking whether or not there
exists an idempotent element that is neither nilpotent nor invertible.
According to Fitting’s Lemma 10 the existence of such an element is equivalent
to the set of commutation matrices, and hence, the state, being decomposable.

It remains to identify one representative of each PLC equivalence class from
the obtained list of indecomposable graph states. We select a state from the
list and then remove all states which are PLC equivalent to the chosen state.
To check PLC equivalence we proceed as follows. Recall that according to
Theorem 7 two states are PLC equivalent if they admit congruent tuples of
commutation matrices. Thus, given two graph states $\ket{G^{\prime}}$ and
$\ket{G^{\prime}}$ with commutation matrices $(C_{\alpha})_{\alpha}$ and
$(D_{\alpha})_{\alpha}$ respectively, we have to decide whether
$(C_{\alpha})_{\alpha}$ and $(D_{\alpha})_{\alpha}$ are congruent to each
other or not. This can be done by solving the linear system of equations

$(QC_{\alpha})_{\alpha}=(D_{\alpha}P)_{\alpha}$ (38)

for the entries of $Q$ and $P$. Then, we check if any solution satisfies
$Q=(P^{-1})^{T}$. The runtime for both, verifying indecomposability and
removing congruent tuples, can in principle be exponentially large in the
number of qubits. This is due to the fact that the solution space of the
respective linear equation system can have a basis of $O(n^{2})$ elements, and
hence the solution space contains $O(2^{n^{2}})$ elements. Nevertheless, the
algorithm seems to be fast for most graph states in practice.

For the cases $(2,2,2,2)$ and $(3,2,2,2)$ containing eight and nine qubits we
have to follow a different approach as the number of graph states of eight
qubits is already too large ($\approx 268$ million). Therefore, we start from
a complete list of local Clifford inequivalent states of eight and nine qubits
(see [50]) and consider all possible distributions of these states among $4$
parties resulting in the configuration $(2,2,2,2)$, and $(3,2,2,2)$
respectively. Then, we proceed as before by removing all decomposable states
and determining a state for each PLC class.

For $10$ qubits we proceed in a similar way as for eight and nine qubits but
now we have to consider qubits distributed as $(3,3,2,2)$ and $(4,2,2,2)$.
Note, that the latter distribution is not excluded to contain indecomposable
states by Observation 14. Nevertheless, we find that it contains only
decomposable states. For the distribution $(3,3,2,2)$ only the PLC class of
the ten qubit spiral graph state is indecomposable.

In Figure 4 we display all states in the EGS4 up to $10$ qubits up to
relabeling of parties. Remarkably, up to $7$ qubits, the only additions to the
EGS4 besides the $4$-qubit GHZ state are the spiral graph states. For $8$
qubits more complex indecomposable graph states exist. In particular, the last
graph for eight qubits in Figure 4 is different, since it contains three leaf
parent pairs. Finally, for $9$ and $10$ qubits the only additional states are
again the spiral graphs.

Going beyond the EGS4 we find that for $6$ qubits on 5 parties there exist
$19$ different PLC classes (or $10$ different classes up to permutations of
the parties holding a single qubit). This suggests that beyond the EGS4 the
number of different PLC classes increases very quickly, already in the case
where the EGS4 for $5$ qubits still has a very simple structure, i.e., where
it contains only a single PLC class (see Figure 4).

##  4 Qudit systems

In this section, we generalize the commutation matrix formalism to qudit
stabilizer states of prime dimension. Similar to the qubit case, non-local
qudit Clifford operations can be implemented deterministically using gate
teleportation. Consequently, it is again interesting to study the same task of
characterizing PLC equivalence classes of qudit stabilizer states.

We first recall the definition of the Pauli group and stabilizer states for
qudits. We will closely follow Refs. [51, 52]. In the following,
$d\in\mathbb{N}$ is prime and $d\geq 3$. We consider the common generalization
of the Pauli operators to qudit systems as

$\displaystyle X$ $\displaystyle=\sum_{k=0}^{d-1}\ket{k+1}\bra{k},$ (39)
$\displaystyle Z$ $\displaystyle=\sum_{k=0}^{d-1}\eta^{k}\ket{k}\bra{k},$ (40)

where $\eta=\exp(2\pi i/d)$ so that $X^{d}=Z^{d}=\mathds{1}$. In analogy to
the single-qubit Pauli group the single-qudit Pauli group is defined as

$\mathcal{P}^{d}=\\{\eta^{m}\sigma_{a,b}|a,b,m\in\mathbb{Z}_{d}\\},$ (41)

where $\sigma_{a,b}=X^{a}Z^{b}$. As $d$ is prime, all elements in the single-
qudit Pauli group have the same order, namely $d$, and the same set of non-
degenerate eigenvalues. The $n$-qudit Pauli group $\mathcal{P}_{n}^{d}$ is the
group generated by all $n$-fold tensor products of elements of
$\mathcal{P}^{d}$. In analogy to the qubit case, there is a correspondence
between the Pauli group and the vector space $\mathbb{Z}_{d}^{2n}$ with a
symplectic form $\omega$. Let us again define the map
$\sigma:\mathbb{Z}_{d}^{2n}\rightarrow\mathcal{P}_{n}^{d}$ via
$\sigma(a_{1},b_{1},\ldots,a_{n},b_{n})=\sigma_{a_{1},b_{1}}\otimes\ldots\otimes\sigma_{a_{n},b_{n}}$.
Under this map, the group structure of the Pauli group is preserved. More
precisely, from the relation

$\sigma(\bm{f})\sigma(\bm{g})\propto\sigma(\bm{f}+\bm{g})$ (42)

we see that elements of the Pauli group modulo phases can be represented as
vectors of $\mathbb{Z}_{d}^{2n}$, and the multiplication of Pauli operators
corresponds to addition of their corresponding vectors in
$\mathbb{Z}_{d}^{2n}$. The generalized Pauli operators obey the following
commutation relations

$\sigma(\bm{f})\sigma(\bm{g})=\eta^{\omega(\bm{f},\bm{g})}\sigma(\bm{g})\sigma(\bm{f})\
\ \bm{f},\bm{g}\in\mathbb{Z}_{d}^{2n},$ (43)

with the symplectic form

$\displaystyle\omega(\bm{f},\bm{g})=(\bm{a},\bm{b})\begin{pmatrix}0&\mathds{1}\\\
-\mathds{1}&0\end{pmatrix}(\bm{a^{\prime}},\bm{b^{\prime}})^{T}.$ (44)

The Clifford group $\mathcal{C}_{n}(d)$ is defined as the unitary normalizer
of the Pauli group up to phases, i.e., $\mathcal{C}_{n}(d)=\\{U\in
SU(d^{n})|UPU^{\dagger}\in\mathcal{P}_{n}^{d}\ \forall
P\in\mathcal{P}_{n}^{d}\\}/U(1)$. Every $U\in\mathcal{C}_{n}(d)$ defines an
isometry on the symplectic space $\mathbb{Z}_{d}^{2n}$ via Equation (16) and
vice versa.

A stabilizer state is the unique $+1$ eigenstate to a maximal abelian subgroup
of $\mathcal{P}_{n}^{d}$ which does not contain any nontrivial multiples of
the identity. Such a subgroup contains $d^{n}$ elements and is generated by
$n$ independent elements. An abelian subgroup of $\mathcal{P}_{n}^{d}$ which
does not contain any nontrivial multiples of the identity is called a
stabilizer. In complete analogy to the qubit case, a stabilizer associated to
a stabilizer state corresponds to a maximally isotropic subspace of
$\mathbb{Z}_{d}^{2n}$ via the map $\sigma$. Moreover, every qudit stabilizer
state is local Clifford equivalent to a qudit graph state [53]. A qudit graph
state is the unique stabilizer state associated to a multigraph $G$ with
vertices $V$ and edges $E$. In contrast to a simple graph, multigraphs allow
for an arbitrary number of edges between two vertices. Similar to the qubit
case, edges correspond to controlled-$Z$ interactions between qudits, which
are represented by the vertices of the graph. The existence of distinct non-
trivial powers of the gate $CZ=\sum_{k=0}^{d-1}\outerproduct{k}{k}\otimes
Z^{k}$ gives rise to the different numbers of edges between vertices. The
number of edges $m$ between two vertices is called the _multiplicity_ , and
the corresponding interaction is given by $CZ^{m}$, where $0\leq m\leq d-1$.
Given a multigraph the canonical generators of the corresponding stabilizer
are the operators

$g_{i}=X_{i}\bigotimes_{j\in N_{i}}Z_{j}^{m_{ij}},$ (45)

where $m_{ij}$ is the multiplicity of the edges connecting vertex $i$ and $j$.
Finally, the adjacency matrix of a graph state $\ket{G}$ is defined by

$(\Gamma_{G})_{ij}=m_{ij}.$ (46)

In the following we denote by $\text{Stab}_{d}(P(M,n))$ the set of $n$-qudit
stabilizer states for qudits of dimension $d$, which are distributed among $M$
parties according to the partition $P(M,n)$.

The $n$-qudit Pauli group $\mathcal{P}_{n}^{d}$ has an analogous relation to
the symplectic vector space $(\mathbb{Z}_{d}^{2n},\omega)$ as
$\mathcal{P}_{n}$ has to the symplectic vector space
$(\mathbb{Z}_{2}^{2n},\omega)$. It is therefore straightforward to define
commutation matrices via the same construction as in Section 3 for qudit
stabilizer states. Commutation matrices are now tuples of matrices
$(C_{\alpha})_{\alpha\in P(M,n)}$ such that $C_{\alpha}\in\ M_{n\times
n}(\mathbb{Z}_{d})$. The matrices are again alternating due to the fact that
$\omega(\bm{f},\bm{g})=-\omega(\bm{g},\bm{f})$ and satisfy Equation (23),
i.e., they sum up to zero modulo $d$.

Before discussing the other properties of commutation matrices, let us
consider an example. Consider a four qutrit state distributed over $M=4$
parties and let the generator of its stabilizer be $g_{1}=X_{1}Z_{2}Z_{4}$,
$g_{2}=Z_{1}X_{2}$, $g_{3}=X_{3}Z_{4}^{2}$, and $g_{4}=Z_{1}Z_{3}^{2}X_{4}$.
One can then verify that it admits the following set of commutation matrices.

$\begin{split}C_{1}&=\begin{pmatrix}0&2&0&2\\\ 1&0&0&0\\\ 0&0&0&0\\\
1&0&0&0\end{pmatrix}C_{2}=\begin{pmatrix}0&1&0&0\\\ 2&0&0&0\\\ 0&0&0&0\\\
0&0&0&0\end{pmatrix}\\\ C_{3}&=\begin{pmatrix}0&0&0&0\\\ 0&0&0&0\\\ 0&0&0&1\\\
0&0&2&0\end{pmatrix}C_{4}=\begin{pmatrix}0&0&0&1\\\ 0&0&0&0\\\ 0&0&0&2\\\
2&0&1&0\end{pmatrix}.\end{split}$ (47)

These matrices are alternating as $-1=2$ over $\mathbb{Z}_{3}$, and they sum
up to zero modulo $3$. In fact, this state is again a graph state with edges
$\\{\\{1,2\\}_{1},\\{1,4\\}_{1},\\{3,4\\}_{2}\\}$, where the subscript denotes
the multiplicity of its edges. One can again verify that the commutation
matrices can be obtained from the adjacency matrix $\Gamma_{G}$ via

$C_{\alpha}=\sum_{i\in\alpha}\Gamma_{G}(i),$ (48)

where $\Gamma_{G}(i)$ is the matrix that contains the $i$-th column and $(-1)$
times the $i$-th row of $\Gamma_{G}$, and zero everywhere else. E.g., for the
the above example one has

$\Gamma_{G}=\begin{pmatrix}0&1&0&1\\\ 1&0&0&0\\\ 0&0&0&2\\\
1&0&2&0\end{pmatrix},$ (49)

from which the commutation matrices in Equation (47) directly follow.

Let us continue our discussion on properties of commutation matrices. As
stabilizers again correspond to maximally isotropic subspaces of
$\mathbb{Z}_{d}^{2n}$, it is straightforward to verify that the rank condition
in Theorem 6 still holds. Moreover, commutation matrices still have the same
interpretation concerning PLC equivalence of stabilizer states. In fact, a
theorem similar to Theorem 7 in the qubit case still holds in the case of
qudits.

######  Theorem 15.

Let $\ket{\psi},\ket{\phi}\in\text{Stab}_{d}(P(M,n))$. Then $\ket{\psi}$ is
PLC equivalent to $\ket{\phi}$ if and only if they admit the same tuple of
commutation matrices.

The proof closely follows Ref. [28] and can be found in Appendix G.

Figure 5: States in the EGS4 for qutrits. Highlighted in green is the complete
EGS4 for up to five qutrits. The first three states generate all two- and
three-partite qutrit stabilizer states [29]. An exhaustive search through all
four-partite graph states up to 5 qutrits reveals six more states from the
EGS4. Beyond $5$ qutrits we have identified some states that are contained in
the EGS4 for qutrits, however, this list might be incomplete. The EGS4 for
qutrits already has a much richer structure, due to the appearance of graphs
that contain edges of higher multiplicities.

It directly follows that a qudit stabilizer state is decomposable if and only
if its commutation matrices can be block-diagonalized under congruence (cf.
Theorem 8). This is due to the fact that Equation (31) and Inequality (61)
still hold. Thus, we again have that finding states in the EGS is equivalent
to finding indecomposable tuples of commutation matrices. Stabilizer states
decompose uniquely into indecomposable ones if commutation matrices decompose
uniquely into indecomposable blocks. In contrast to qubit systems, the
commutation matrices are now defined over the finite field $\mathbb{Z}_{d}$
with $d\geq 3$, i.e., a field with characteristic not equal to two. Theorem
$2$ of Ref. [34] shows that tuples of alternating matrices over such fields
indeed decompose uniquely into indecomposable blocks. Thus, we have shown the
following theorem.

######  Theorem 16.

All states in $\text{Stab}_{d}(P(M,n))$ decompose uniquely into indecomposable
states in the EGSM, where $d\geq 3$ is a prime.

Due to this theorem, any PLC class is uniquely characterized by a tensor
product of states from the EGS. Therefore, the remaining task is to determine
the EGS.

First, however, some remarks are in order. Let us stress that (qubit and
qudit) stabilizer states distributed among parties (where each party can hold
more than one qubit) can be described by a subset of higher-dimensional qudit
stabilizer states with a single qudit per party and a composite dimension (cf.
Ref. [54]). PLC operations then form a subset of qudit Clifford
transformations. On the other hand, viewing qudit stabilizer states of non-
prime dimension as lower-dimensional weighted graph states [54] also reveals
that for qudit graph states of non-prime dimension the decompositions under
PLU are not necessarily unique. Consider a four ququart state on two parties
that decomposes into a maximally entangled state $\ket{\phi^{+}_{4}}$,
containing 2 ebits of entanglement, and two $\ket{0}$ states. Using some of
the results of Ref. [54] one can see that this decomposition is PLU equivalent
to a decomposition consisting of two entangled pairs of ququarts that each
contain only one ebit of entanglement. Thus, there exist to decompositions
that are PLU equivalent, but the states that occur in these decompositions are
PLU inequivalent. Note that qudit stabilizer states and qudit Clifford
transformations were also investigated in Refs. [36, 37].

Moreover, let us remark that, similar to the qubit case, the results of
Scharlau [47] cannot lead to anything else than the EGS3 for prime dimensions.
In particular, they cannot be used to construct the EGS4 since choosing two
commutation matrices to be indecomposable but not equal to the
$\ket{\phi^{+}_{3}}$ or the $\ket{GHZ_{3}^{3}}$ one cannot find two additional
commutation matrices so that the overall rank constraint is fulfilled.

###  4.1 States in the EGS4 for qutrits

Using the same techniques as in the case of qubits in Section 3.2, i.e.,
Fitting’s Lemma 10, we can compute the EGS4 for up to $5$ qutrits by
performing an exhaustive search through all $4$-partite graph states up to $5$
qutrits. First, one recovers the states $\ket{0}$, $\ket{\phi^{+}_{3}}$, and
$\ket{GHZ_{3}}$ that where already proven in Ref. [29] to generate all three-
partite stabilizer states. This can again be derived from the complete set of
indecomposable pairs of alternating forms in Ref. [47], as these results hold
for any field. Additionally, we identify the $6$ additional states from the
EGS4 up to $5$ qutrits, see Figure 5.

Beyond $5$ qutrits the exhaustive search through all graph states becomes
computationally intractable due to the increasing number of graphs but also
due to the increasing sizes of the endomorphism rings. Nevertheless, one can
gain some additional insight into the EGS4 for more than $5$ qutrits. To that
end, let us first see if the states that we found to be in the EGS4 for qubits
also appear in the case of qutrits. Again employing Lemma 10 (Fitting’s
Lemma), one can show that the spiral graphs containing only edges of
multiplicities $1$ on $5$ to $10$ qubits are also indecomposable and thus in
the EGS4 for qutrits. This raises the question if other spiral graph states
containing edges of other multiplicities are also contained in the EGS4. In
the following we argue that this is not the case, as for many states edges of
higher multiplicities can be removed by local Clifford operations.

To this end, let us recall how the action of the local Clifford group can be
described on the level of graphs. The action of the local Clifford group on
qudit graph states was completely characterized in Ref. [53]. In particular,
it was shown that there exists a local Clifford operation that, when applied
to any vertex $v$, multiplies the multiplicities of all edges connected to $v$
by a constant factor $0\neq b\in\mathbb{Z}_{d}$. Thus, for qutrit graph
states, there exists a local Clifford operation that converts all edges of
multiplicity $2$ to edges of multiplicity $1$ and vice versa. Recall, that a
_tree graph_ is a graph that does not contain any cycle. Then, we have the
following observation.

######  Observation 17.

Any PLC orbit that contains a tree graph, also contains the same tree graph,
where all edges are of multiplicity $1$.

This observation simply follows from the fact that in a tree graph all edges
of higher multiplicities can be moved to a leaf and can then be locally
converted to edges of multiplicities $1$. Notably, this means that any qutrit
spiral graph state, regardless of the multiplicities of its edges, is always
PLC equivalent to the spiral graph states with all multiplicities being equal
to $1$.

Moreover, the graph state containing three leafs is indecomposable and edges
of higher multiplicities play no role by the arguments above. The only state
where edges of higher multiplicities play a role is the one containing cycles.
It is again indecomposable for qutrits and appears in four PLC inequivalent
forms with different numbers of edges with multiplicity $2$.

Finally, as in the case of four qutrits, the closed loop graph containing a
single edge of multiplicity two is indecomposable. From these few states one
can already deduce, that the EGS4 for qutrits already has a much richer
structure, due to the appearance of graphs that contain edges of higher
multiplicities, see Figure 5.

###  4.2 Beyond PLC transformations

Let us finally briefly comment on how (stabilizer) states transform under more
general types of transformations, also constrained by locality.

First, let us consider general PLU transformations (not just PLC). In Ref.
[55] it was shown that already in the case of two parties decompositions of
arbitrary states into indecomposable states is not unique. More precisely, let
$\ket{\psi_{1}}$ ($\ket{\psi_{2}}$) be a state of two qudits of dimension
$d_{1}$ ($d_{2}$). Ref. [55] shows that for any $d_{1},d_{2}\geq 4$ there
exist states of the form $\ket{\psi_{1}}\otimes\ket{\psi_{2}}$ shared among
two parties and a PLU transformation $U$ such that

$U\ket{\psi_{1}}\otimes\ket{\psi_{2}}=\ket{\psi_{1}^{\prime}}\otimes\ket{\psi_{2}^{\prime}}$
(50)

and such that $\ket{\psi_{1}}$ (and $\ket{\psi_{2}}$) is not PLU equivalent to
any $\ket{\psi_{i}^{\prime}}$. If we consider quasilocal unitary operations
instead of PLU, it follows from the results of Ref. [56] that also
decompositions of stabilizer are not unique.

If we allow for measurements in addition to PLC transformations,
transformations between PLC inequivalent decompositions become possible .
Consider for instance two Bell states $\ket{\phi^{+}}^{\otimes 2}$ shared
between parties $\alpha_{1}=\\{1\\}$, $\alpha_{2}=\\{2,3\\}$ and
$\alpha_{3}=\\{4\\}$. Then, applying $CZ_{2,3}$ followed by local
complementation w.r.t. qubit $3$ and a $Z$ basis measurement of qubit $3$
results in the state $\ket{GHZ_{3}}$ shared between all three parties and
$\ket{0}$ at party $\alpha_{2}$ (up to local Pauli corrections). It is clear
that $\ket{\phi^{+}}^{\otimes 2}$ and $\ket{GHZ_{3}}\otimes\ket{0}$ are PLU
inequivalent.

##  5 Conclusion and Outlook

In this work, we studied PLC transformations of stabilizer states. PLC
transformations are a physically motivated extension of local Clifford
operations that naturally arise in the context of quantum networks that can
provide large amounts of bipartite entanglement between well connected nodes.
Moreover, the fact that these operations can be implemented deterministically
makes them particularly interesting to study.

First, we addressed the question of how PLC transformations between graph
states change the corresponding graph. It was shown in Ref. [26] that local
Clifford transformations between graph states correspond to a sequence of
local complementations on the respective graphs. We found that any PLC
transformation between graph states can be realized by local complementations
supplemented by the addition and removal of edges within parties.

Then, we studied the classification of PLC equivalence classes of stabilizer
states. We discussed an approach based on invariant polynomials and showed
that this approach achieves a complete classification. However, since we are
not aware of an efficient way to evaluate those polynomial, the approach seems
unpractical.

Motivated by the results of Ref. [28], we introduced a new mathematical tool,
the commutation matrix formalism, to study PLC equivalence classes of
stabilizer states. More precisely, we related the problem of classifying PLC
equivalence classes to the classification problem of tuples of alternating
forms, which is a well studied problem in linear algebra.

We showed that two stabilizer states are PLC equivalent if they admit the same
set of commutation matrices, and moreover, states can be decomposed into
tensor products of smaller stabilizer states under PLC if their commutation
matrices can be block-diagonalized. This approach allowed us to gain several
insights into the entanglement structure of multipartite stabilzier states. We
showed, that in contrast to the $3$-partite case, $M\geq 4$-partite stabilizer
states contain infinitely many different types of entanglement under PLC
transformations and even under PLU transformations. We derived necessary and
sufficient conditions to decide whether or not a given stabilizer state is
decomposable. To demonstrate the power of our approach we numerically computed
the EGS4 for up to $10$ qubits. We furthermore showed that the decomposition
of states into indecomposable states is unique in case the states do not admit
additional PLC symmetries.

Finally, we generalized the commutation matrix formalism to qudit systems of
prime dimension $d$. As the commutation matrices are now defined over the
field $\mathbb{Z}_{d}$, the results of Ref. [34] imply that qudit stabilizer
states decompose uniquely into tensor products of indecomposable ones. Again
we employed the commutation matrix formalism to compute the EGS4 up to $5$
qutrits.

An interesting topic for future research is to resolve the question whether or
not qubit stabilizer states decompose uniquely into indecomposable ones.
Furthermore, the structure of the EGS4 up to $10$ qubits suggests that maybe a
complete description of the stabilizer states in this set is possible.
Considering PLU transformations, it would be interesting to understand whether
stabilizer states which are indecomposable under PLC can decompose under PLU
into states which are not PLU equivalent to stabilizer states. Note that these
states would have to be locally maximally entangleable (LME) states [56]. In
case such decompositions exist, one can study the question how the EGS for
stabilizer states looks like if it can contain states which are not PLU
equivalent to stabilizer states.

##  6 Acknowledgements

We thank Vladimir V. Sergeĭchuk for helpful correspondence. We acknowledge
financial support from the Austrian Science Fund (FWF): W1259-N27, P32273-N27,
FG5-L, and the SFB BeyondC (Grant No. F7107-N38).

## References

  * [1] H. J. Kimble, ”The quantum internet.”, Nature 453, 1023 (2008).
  * [2] S. Wehner, D. Elkouss, and R. Hanson, ”Quantum internet: A vision for the road ahead.”, Science 362, 9288 (2018).
  * [3] J. I. Cirac, P. Zoller, H. J. Kimble, and H. Mabuchi, ”Quantum State Transfer and Entanglement Distribution among Distant Nodes in a Quantum Network.”, Phys. Rev. Lett. 78, 3221 (1997).
  * [4] S. Muralidharan, L. Li, J. Kim, N. Lütkenhaus, M. D. Lukin, and L. Jiang, ”Efficient long distance quantum communication.”, Sci. Rep. 6, 20463 (2016).
  * [5] S. Perseguers, G. J. Lapeyre Jr, D. Cavalcanti, M. Lewenstein, and A. Acín, ”Distribution of entanglement in large-scale quantum networks.”, Rep. Prog. Phys. 76, 096001 (2013).
  * [6] L.-M. Duan, and C. Monroe, ”Colloquium: Quantum networks with trapped ions.”, Rev. Mod. Phys. 82, 1209 (2010).
  * [7] A. Reiserer, and G. Rempe, ”Cavity-based quantum networks with single atoms and optical photons.”, Rev. Mod. Phys. 87,1379 (2015).
  * [8] J. I. Cirac, A. K. Ekert, S. F. Huelga, and C. Macchiavello, ”Distributed quantum computation over noisy channels.”, Phys. Rev. A 59, 4249 (1999).
  * [9] T. J. Proctor, P. A. Knott, and J. A. Dunningham, ”Multiparameter Estimation in Networked Quantum Sensors.”, Phys. Rev. Lett. 120, 080501 (2018).
  * [10] L.-M. Duan, M. D. Lukin, J. I. Cirac, and P. Zoller, ”Long-distance quantum communication with atomic ensembles and linear optics.”, Nature 414, 413 (2001).
  * [11] A. Tavakoli, A. Pozas-Kerstjens, M. Luo, and M.-O. Renou, ”Bell nonlocality in networks.”, Rep. Prog. Phys. (2021).
  * [12] O. Gühne, and G. Tóth, ”Entanglement detection.”, Phys. Rep. 474, 1 (2009).
  * [13] R. Horodecki, P. Horodecki, M. Horodecki, and K. Horodecki, ”Quantum entanglement.”, Rev. Mod. Phys. 81, 865 (2009).
  * [14] I. Bengtsson, and K. Zyczkowski, ”Geometry of Quantum States.”, (Cambridge University Press, 2006)
  * [15] D. Sauerwein, N. R. Wallach, G. Gour, and B. Kraus, ”Transformations among Pure Multipartite Entangled States via Local Operations are Almost Never Possible.”, Phys. Rev. X 8, 031020 (2018).
  * [16] T. Kraft, S. Designolle, C. Ritz, N. Brunner, O. Gühne, and M. Huber, ”Quantum entanglement in the triangle network.”, Phys. Rev. A 103, L060401 (2021).
  * [17] M. Navascués, E. Wolfe, D. Rosset, and A. Pozas-Kerstjens, ”Genuine Network Multipartite Entanglement.”, Phys. Rev. Lett. 125, 240505 (2020).
  * [18] K. Hansenne, Z.-P. Xu, T. Kraft, and O. Gühne, ”Symmetries in quantum networks lead to no-go theorems for entanglement distribution and to verification techniques.”, Nat. Commun. 13, 496 (2022).
  * [19] M. Hein, W. Dür, J. Eisert, R. Raussendorf, M. Van den Nest, and H.-J. Briegel, ”Entanglement in Graph States and its Applications.”, in _Quantum Computers, Algorithms and Chaos_, edited by G. Casati, D. L. Shepelyansky, P. Zoller, and G. Benenti (IOS Press, Amsterdam, 2006).
  * [20] M. Hein, J. Eisert, and H. J. Briegel, ”Multiparty entanglement in graph states.”, Phys. Rev. A 69, 062311 (2004).
  * [21] D. Gottesman, ”Stabilizer Codes and Quantum Error Correction.”, _PhD thesis_ , California Institute of Technology Pasadena, California (1997).
  * [22] R. Raussendorf and H.J. Briegel, ”A One-Way Quantum Computer.”, Phys. Rev. Lett. 86, 5188 (2001).
  * [23] D. Gottesman, ”The Heisenberg Representation of Quantum Computers.”, in _Proceedings of the XXII International Colloquium on Group Theoretical Methods in Physics_ , edited by S. P. Corneyet al. (International Press, Cambridge, MA 1999).
  * [24] D. Schlingemann and R. F. Werner, ”Quantum error-correcting codes associated with graphs.”, Phys. Rev. A 65, 012308 (2001).
  * [25] D. Gottesman, and I. L. Chuang, ”Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations.”, Nature 402, 390 (1999).
  * [26] M. Van den Nest, J. Dehaene, and B. De Moor, ”Graphical description of the action of local Clifford transformations on graph states.”, Phys. Rev. A 69, 022316 (2004).
  * [27] D. Fattal, T. S. Cubitt, Y. Yamamoto, S. Bravyi, & I. L. Chuang, ”Entanglement in the stabilizer formalism.”, arXiv:quant-ph/0406168 (2004).
  * [28] S. Bravyi, D. Fattal, and D. Gottesman, ”GHZ extraction yield for multipartite stabilizer states.”, J. Math. Phys. 47, 062106 (2006).
  * [29] S. Y. Looi, and R. B. Griffiths, ”Tripartite entanglement in qudit stabilizer states and application in quantum error correction.”, Phys. Rev. A 84, 052306 (2011).
  * [30] K. Wirthmüller, ”Homological invariants of stabilizer states.” Quantum Inf. Comput. 8, 595 (2008).
  * [31] G. Smith, and D. Leung, ”Typical entanglement of stabilizer states.”, Phys. Rev. A 74, 062314 (2006).
  * [32] K. Wirthmüller, ”Homology of Generic Stabilizer States.”, arXiv:0809.3346 (2008).
  * [33] S. Nezami, and M. Walter, ”Multipartite Entanglement in Stabilizer Tensor Networks.”, Phys. Rev. Lett. 125, 241602 (2020).
  * [34] V. V. Sergeĭchuk, ”Classification problems for systems of forms and linear mappings.”, Math. USSR Izv. 31, 481 (1988).
  * [35] A. Dahlberg, J. Helsen, and S. Wehner, ”Counting single-qubit Clifford equivalent graph states is #P-Complete.”, J. Math. Phys. 61, 022202 (2020).
  * [36] F. E. S. Steinhoff, C. Ritz, N. Miklin, and O. Gühne, ”Qudit Hypergraph States.”, Phys. Rev. A 95, 052340 (2017).
  * [37] C. Ritz, ”Characterizing the structure of multiparticle entanglement in high-dimensional systems.”, PhD thesis, University of Siegen 2018.
  * [38] M. Englbrecht, and B. Kraus, ”Symmetries and entanglement of stabilizer states.”, Phys. Rev. A 101, 062302 (2020).
  * [39] D. H. Zhang, H. Fan, and D. L. Zhou, ”Stabilizer dimension of graph states.”, Phys. Rev. A 79, 042318 (2009).
  * [40] A. Bouchet, ”An efficient algorithm to recognize locally equivalent graphs.”, Combinatorica 11, 315 (1991).
  * [41] A. Bouchet, ”Recognizing locally equivalent graphs.” Discrete Math. 114, 75 (1993).
  * [42] S.-K. Liao et al., ”Satellite-Relayed Intercontinental Quantum Network.” Phys. Rev. Lett. 120, 030501 (2018).
  * [43] J. I. Cirac, W. Dür, B. Kraus, and M Lewenstein, ”Entangling operations and their implementation using a small amount of entanglement.” Phys. Rev. Lett. 86, 544 (2001).
  * [44] G. Gour, and N. R. Wallach, ”Classification of multipartite entanglement of all finite dimensionality.”, Phys. Rev. Lett. 111, 060502 (2013).
  * [45] M. Van den Nest, J. Dehaene, and B. De Moor, ”Finite set of invariants to characterize local Clifford equivalence of stabilizer states.”, Phys. Rev. A 72, 014307 (2005).
  * [46] Z. Ji, J. Chen, Z. Wei, and M. Ying, ”The LU-LC conjecture is false.”, Quantum Inf. Comput. 10, 97-108 (2010).
  * [47] R. Scharlau, ”Paare alternierender Formen.”, Math. Z. 147, 13-19 (1976).
  * [48] G. Belitskii, R. Lipyanski, and V. V. Sergeichuk, ”Problems of classifying associative or Lie algebras and triples of symmetric or skew-symmetric matrices are wild.”, Linear Algebra Its Appl. 407, 249-262 (2005).
  * [49] M. Barot, ”Representations of quivers.”, available at https://www.matem.unam.mx/ barot/articles/
notes_ictp.pdf.

  * [50] L. E. Danielsen, Database of Entanglement in Graph States (2011), available at http://www.ii.uib.no/l̃arsed/entanglement/.
  * [51] E. Hostens, J. Dehaene, and B. De Moor, ”Stabilizer states and Clifford operations for systems of arbitrary dimensions and modular arithmetic.”, Phys. Rev. A 71, 042315 (2005).
  * [52] J. M. Farinholt, ”An ideal characterization of the Clifford operators.” J. Phys. A 47, 305303 (2014).
  * [53] M. Bahramgiri, and S. Beigi, ”Graph states under the action of local Clifford group in non-binary case.”, arXiv:quant-ph/0610267 (2006).
  * [54] T. Kraft, C. Ritz, N. Brunner, M. Huber, and O. Gühne, ”Characterizing Genuine Multilevel Entanglement.”, Phys. Rev. Lett. 120, 060502 (2018).
  * [55] A. Neven, D. K. Gunn, M. Hebenstreit, and B. Kraus, ”Local transformations of multiple multipartite states.”, SciPost Phys., 11, 042 (2021).
  * [56] C. Kruszynska, and B. Kraus. ”Local entanglability and multipartite entanglement.” Phys. Rev. A 79, 052304 (2009).
  * [57] M. Aschbacher, Finite group theory, (Cambridge University Press, Cambridge, MA, 2000).
  * [58] S. Lang, Algebra, (Springer, New York, NY, 2002).
  * [59] D. Gross, ”Hudson’s theorem for finite-dimensional quantum systems.” J. Math. Phys. 47, 122107 (2006).
  * [60] F. J. MacWilliams, and N. J. Sloane, The Theory of Error-Correcting Codes, North-Holland Publishing Company (1977).
  * [61] G. Marsaglia, ”Bounds for the Rank of the Sum of Two Matrices.” Mathematical Note, Boeing Scientific Research Labs, Seattle, WA, (1964).
  * [62] C. G. Bartolone, and M. A. Vaccaro. ”The action of the symplectic group associated with a quadratic extension of fields.” J. Algebra 220, 115 (1999).
  * [63] G. Falcone, M. A. Vaccaro, ”Kronecker modules and reductions of a pair of bilinear forms.”, Acta Univ. Palacki. Olomuc., Fac. rer. nat., Mathematica 43, 55 (2004).
  * [64] J. Dieudonné, ”Sur la réduction canonique des couples de matrices.” Bull. Soc. Math. Fr. 74, 130 (1946).
  * [65] Y. A. Drozd, and A. I. Plakosh, ”On nilpotent Chernikov 2-groups with elementary tops.”, Algebra Discrete Math. 22, 201 (2016).

##  Appendix A Generalized local complementation

In this section we provide a proof of Theorem 1. To that end, we first prove
Lemma 2, which shows that the action of any $2$-qubit Clifford operator on a
graph state can be implemented by $CZ$ gates and local complementation (LCE)
on the respective qubits up to local Clifford operations. Let us state the
lemma in its formal version.

######  Lemma 2 (formal version).

Let $\ket{G}$ be a $n\geq 2$ qubit graph state. Then for any
$C\in\mathcal{C}_{2}$ acting on qubits 1 and 2 there exists a local Clifford
operator $L_{1}\in\mathcal{C}_{n}^{L}$ and a LCE transformation with respect
to vertex $1$ and $2$ described by the operator $L_{2}\otimes L_{3}$, where
$L_{2}\in\mathcal{C}_{2}$ acts on qubits 1 and 2, and
$L_{3}\in\mathcal{C}_{n-2}^{L}$ acts on qubits $\\{3,\ldots n\\}$, such that

$C\otimes\mathds{1}\ket{G}=L_{1}(L_{2}\otimes L_{3})\ket{G}.$ (51)

Note that the 2-qubit Clifford group has $|\mathcal{C}_{2}|=11520$ elements
and its subgroup, the local Clifford group, has $|\mathcal{C}_{2}^{L}|=24^{2}$
elements. Thus, $\mathcal{C}_{2}$ partitions into $11520/24^{2}=20$ different
right cosets
$\mathcal{C}_{2}^{L}g=\\{fg|f\in\mathcal{C}_{2}^{L},g\in\mathcal{C}_{2}\\}$ of
$\mathcal{C}_{2}^{L}$, i.e.,
$\mathcal{C}_{2}=\bigcup_{i=1}^{20}\mathcal{C}^{L}_{2}g_{i}$, with
$g_{i}\in\mathcal{C}_{2}^{L}$. With these insights let us show Lemma 2.

###### Proof.

Observe, that Lemma 2 is equivalent to following statement. Clifford operators
corresponding to LCE with respect to vertices $1$ and $2$ can generate (up to
local Clifford operations) an element of every right coset
$\mathcal{C}_{2}^{L}g$, with $g\in\mathcal{C}_{2}$ acting on qubits $1$ and
$2$. We show this in the following by generating an element of each coset via
LCE.

To this end we consider the operators that correspond to LCE. Adding and
removing the edge between vertex $1$ and $2$ corresponds to a controlled phase
gate $CZ_{12}=\outerproduct{0}{0}\otimes\mathds{1}+\outerproduct{1}{1}\otimes
Z$ between qubits $1$ and $2$. Local complementation at qubit $1$ ($2$ qubit)
corresponds to the operator $\exp(-i\pi/4X)\otimes\exp(i\pi/4Z)$
($\exp(i\pi/4Z)\otimes\exp(-i\pi/4X)$) on qubits $1$ and $2$ if qubit $1$ and
$2$ are connected. Otherwise, it corresponds to the operator
$\exp(-i\pi/4X)\otimes\mathds{1}$ ($\mathds{1}\otimes\exp(-i\pi/4X)$).
Moreover, local complementation creates additional local Clifford gates on
other neighbours of qubit $1$ and $2$. Let us write all possible operators on
qubit $1$ and $2$ as an (ordered) tuple

$\left(CZ_{12},e^{-i\frac{\pi}{4}X}\otimes\mathds{1},\mathds{1}\otimes
e^{-i\frac{\pi}{4}X},e^{-i\frac{\pi}{4}X}\otimes
e^{i\frac{\pi}{4}Z},e^{i\frac{\pi}{4}Z}\otimes e^{-i\frac{\pi}{4}X}\right).$
(52)

Figure 6 shows a representative of each right coset of $\mathcal{C}_{2}^{L}$
in $\mathcal{C}_{2}$ and a sequence of the above operators generating it. The
sequence respects that the operators for local complementation depend on
whether qubit $1$ and $2$ are connected. Figure 6 considers the case where
qubit $1$ and $2$ are initially disconnected. Let $\\{C_{j}\\}$ be the
operators listed in the table. Clearly, if qubit $1$ and $2$ are initially
connected, then $\\{C_{j}CZ_{1,2}\\}$ are representatives of all different
cosets. ∎

Next let us show Theorem 1, which we state here again.

######  Theorem 1.

Let $\ket{G}$ and $\ket{G^{\prime}}$ be $n$-qubit graph states distributed
among $P(M,n)$ parties. Then $\ket{G}$ is PLC equivalent to $\ket{G^{\prime}}$
if and only if the graphs $G$ and $G^{\prime}$ are related via a sequence of
local complementations and edge additions/removals within parties (LCE).

###### Proof of Theorem 1.

The if part is trivial. To prove the only if part let $\ket{G}$ and
$\ket{G^{\prime}}$ be $M$-partite graph states. Suppose there exists a PLC
operator $\bigotimes_{\alpha\in P(M,n)}C_{\alpha}$ such that
$\ket{G^{\prime}}=\bigotimes_{\alpha}C_{\alpha}\ket{G}$. Then, for every party
$\beta\in P(M,n)$ we do the following. As $\mathcal{C}_{|\beta|}$ is generated
by single- and two-qubit Clifford operators (see also Section 2.1) we can
write $C_{\beta}=\prod_{j=1}^{k}C_{\beta}^{j}$, where
$C_{\beta}^{j}\in\mathcal{C}_{2}$ for all $j\in[k]$. Lemma 2 allows to replace
the action of $C_{\beta}^{k}$ by the action of a local Clifford operator
$L_{1}$ on the state $L_{2}\otimes L_{3}\ket{G}$. The state $L_{2}\otimes
L_{3}\ket{G}$ is a again a graph state as the operator $L_{2}\otimes L_{3}$
describes a sequence of LCE. The local operator $L_{1}$ can then be commuted
to the end of the circuit by possibly changing the remaining operators
$C_{\beta}^{j}$ to some other $2$-qubit Clifford operators and possibly the
operators $C_{\alpha}$ for $\alpha\neq\beta$ to some other PLC operators. We
now continue like this for the operators $C_{\beta}^{j}$ for $j\in[k-1]$. It
is straightforward to verify that, after applying this reasoning to every
party, we end up with an equation of the form
$\ket{G^{\prime}}=L\ket{G^{\prime\prime}}$, where $\ket{G^{\prime\prime}}$ is
obtained from $\ket{G}$ via LCE. It remains to show that the operator $L$
corresponds to local complementation. In Ref. [26] it is shown that two graph
states are related by a local Clifford operator if and only if their graphs
are related via a sequence of local complementations. We conclude that
$G^{\prime\prime}$ and $G^{\prime}$ are related via a sequence of local
complementations and therefore $G^{\prime}$ and $G$ by a sequence of LCE. ∎

$B$ | generation | $B$ | generation | $B$ | generation | $B$ | generation
---|---|---|---|---|---|---|---
$\begin{pmatrix}1&1&0&0\\\ 0&1&0&0\\\ 0&0&1&0\\\ 0&0&0&1\end{pmatrix}$ | $[1]$ | $\begin{pmatrix}1&1&0&1\\\ 0&1&0&0\\\ 0&1&1&1\\\ 0&0&0&1\end{pmatrix}$ | $[0,3,0,2,0,3,0]$ | $\begin{pmatrix}1&0&1&0\\\ 0&1&0&0\\\ 0&0&1&0\\\ 0&1&0&1\end{pmatrix}$ | $[1,0,3,0]$ | $\begin{pmatrix}1&0&0&0\\\ 0&1&0&1\\\ 1&0&1&1\\\ 0&0&0&1\end{pmatrix}$ | $[0,4,0]$
$\begin{pmatrix}0&0&1&1\\\ 0&0&0&1\\\ 1&0&0&0\\\ 0&1&0&0\end{pmatrix}$ | $[0,4,3,0,2,1,0,4,0]$ | $\begin{pmatrix}0&1&1&0\\\ 0&0&0&1\\\ 1&0&0&1\\\ 0&1&0&0\end{pmatrix}$ | $[0,4,3,4,0]$ | $\begin{pmatrix}1&1&1&1\\\ 0&1&0&0\\\ 0&0&1&1\\\ 0&1&0&1\end{pmatrix}$ | $[2,0,3,0]$ | $\begin{pmatrix}1&0&0&0\\\ 0&1&1&0\\\ 0&0&1&0\\\ 1&0&0&1\end{pmatrix}$ | $[0]$
$\begin{pmatrix}0&1&1&1\\\ 0&1&0&1\\\ 1&1&1&0\\\ 0&1&0&0\end{pmatrix}$ | $[1,2,0,4,3,0]$ | $\begin{pmatrix}0&1&1&0\\\ 0&1&0&1\\\ 1&1&1&1\\\ 0&1&0&0\end{pmatrix}$ | $[1,0,4,3,0]$ | $\begin{pmatrix}1&0&0&0\\\ 0&1&1&1\\\ 0&0&1&1\\\ 1&0&0&1\end{pmatrix}$ | $[2,0]$ | $\begin{pmatrix}1&0&1&0\\\ 0&0&0&1\\\ 1&1&0&1\\\ 0&1&0&1\end{pmatrix}$ | $[1,0,3,4,0]$
$\begin{pmatrix}1&0&1&1\\\ 0&0&1&0\\\ 0&1&1&0\\\ 1&1&1&0\end{pmatrix}$ | $[2,1,0,3,0,2,0]$ | $\begin{pmatrix}1&0&1&0\\\ 0&0&1&1\\\ 0&1&1&1\\\ 1&1&1&1\end{pmatrix}$ | $[0,3,0,2,1,0]$ | $\begin{pmatrix}1&1&1&0\\\ 0&0&0&1\\\ 1&0&0&1\\\ 0&1&0&1\end{pmatrix}$ | $[0,3,4,0]$ | $\begin{pmatrix}1&1&0&0\\\ 0&1&0&1\\\ 1&1&1&1\\\ 0&0&0&1\end{pmatrix}$ | $[1,0,4,0]$
$\begin{pmatrix}1&1&1&1\\\ 0&0&1&0\\\ 0&1&1&0\\\ 1&0&1&0\end{pmatrix}$ | $[2,0,3,0,2,0]$ | $\begin{pmatrix}1&1&0&0\\\ 0&1&1&0\\\ 0&0&1&0\\\ 1&1&0&1\end{pmatrix}$ | $[1,0]$ | $\begin{pmatrix}1&1&0&0\\\ 0&1&1&1\\\ 0&0&1&1\\\ 1&1&0&1\end{pmatrix}$ | $[2,1,0]$ | $\begin{pmatrix}1&1&0&1\\\ 1&1&1&0\\\ 1&0&1&1\\\ 1&1&0&0\end{pmatrix}$ | $[0,4,0,1,0]$
Figure 6: This table contains an element $B$ of each right coset of
$\mathcal{C}_{2}^{L}$ in $\mathcal{C}_{2}$ and a sequence of operators from
the tuple in Eq. (52) generating it. Each sequence is specified by a list of
indices of the respective elements in the tuple (starting from $0$) and
assuming that qubit $1$ and $2$ are initially not connected; the left most
entry is the index of the operator applied first; the order of the generators
is compatible with the fact the operators for local complementation depend on
whether qubit $1$ and $2$ are connected.

##  Appendix B Symplectic vector spaces and their connection to stabilizers

There is a close connection between stabilizer states and symplectic vector
spaces. In this section we recall some important results on symplectic vector
spaces, which have been studied extensively in the literature. For more
details we refer the reader to, e.g., Refs. [57, 59, 58].

Let $V$ be a finite-dimensional vector space over any field $F$. A bilinear
form is a map $\omega:V\times V\rightarrow F$ which is linear in both
arguments. After fixing a basis $\\{\bm{e}_{i}\\}$ for $V$, we can associate
to the bilinear form $\omega$ the matrix $B_{\omega}\in
M_{\text{dim}(V)\times\text{dim}(V)}(F)$ whose entries are given by
$(B_{\omega})_{ij}=\omega(\bm{e}_{i},\bm{e}_{j})$. The bilinear form may then
be written as

$\omega(\bm{f},\bm{g})=\bm{f}^{T}B_{\omega}\bm{g}.$ (53)

A bilinear form is called _alternating_ if $\omega(\bm{f},\bm{f})=0$ for all
$\bm{f}\in V$. Note that any alternating form is also skew-symmetric, i.e.,
$\omega(\bm{x},\bm{y})=-\omega(\bm{y},\bm{x})$, which follows from
$\omega(\bm{x}+\bm{y},\bm{x}+\bm{y})=0$ together with the bilinearity of
$\omega$. Consequently, any matrix representation of an alternating bilinear
form satisfies $(B_{\omega})_{ij}=-(B_{\omega})_{ji}$ and
$(B_{\omega})_{ii}=0$ for all $i,j\in[\text{dim}(V)]$. Any matrix with these
properties is called alternating.

Given an alternating form and a subspace $W\subseteq V$, we define the dual
space as $W^{\perp}=\\{\bm{f}\in V|\omega(\bm{f},\bm{g})=0\ \forall\bm{g}\in
W\\}$. An important type of subspace which appears in this context is a
_hyperbolic plane_. A hyperbolic plane is a $2$-dimensional subspace spanned
by a hyperbolic pair, which is a pair of vectors $\bm{f},\bm{g}\in V$ such
that $\omega(\bm{f},\bm{g})=1$. Given a vector space and an alternating form,
the vector space decomposes into a orthogonal direct sum of hyperbolic planes
and a subspace on which the form is $0$. This is stated in the following
theorem, a proof of which can for instance be found in Ref. [57].

######  Theorem 18.

Let $V$ be a vector space and let $\omega:V\times V\rightarrow F$ be an
alternating form. Then $V=V_{1}\oplus\ldots\oplus V_{m}\oplus V^{\perp}$ where
$V_{1},\ldots,V_{m}$ are hyperbolic planes for some $m\in\mathbb{N}$ and
$\omega(\bm{f},\bm{g})=0$ if $\bm{f}\in V^{\perp}$ or $\bm{g}\in V^{\perp}$.

This Theorem is equivalent to the following statement. For every alternating
form $\omega$ on a vector space $V$ there exists a basis of $V$ w.r.t. which
the matrix representation of $\omega$ is a direct sum of the blocks

$\begin{pmatrix}0\end{pmatrix},\text{ and }\begin{pmatrix}0&1\\\
-1&0\end{pmatrix}.$ (54)

Stated differently, there always exists a basis change in $V$ described by the
invertible matrix $R$ such that $R^{T}B_{\omega}R$ is block-diagonal, with the
blocks as specified above. Note that for $V=\mathbb{Z}_{2}^{n}$ Theorem 18 is
also known as _Dickson’s Theorem_ (cf. Chapter 15 in Ref. [60]). We state it
here for general fields as, when we treat qudit stabilizer states with qudits
of prime dimension $d$, we need the Theorem for the field $\mathbb{Z}_{d}$.

Let us continue with some definitions. A bilinear form is called _non-
degenerate_ if the conditions $\omega(\bm{f},\bm{g})=0$ for all $\bm{g}\in V$
imply that $\bm{f}=0$. An alternating bilinear form which is non-degenerate is
called _symplectic_. A symplectic vector space is a vector space $V$ together
with symplectic bilinear form $\omega$. Symplectic vector spaces have even
dimension as follows for instance from Theorem 18. A subspace $W\subseteq V$
of a symplectic vector space $V$ is called _isotropic_ if $W\subseteq
W^{\perp}$ and _maximally isotropic_ if $W^{\perp}=W$. Moreover, for any
subspace $W\subseteq V$ it holds that
$\text{dim}(W)+\text{dim}(W^{\perp})=\text{dim}(V)$.

An invertible linear map $U:V\rightarrow V$ is referred to as _isometry_ for a
symplectic form $\omega$ if it preserves $\omega$, i.e., if
$\omega(U\bm{f},U\bm{g})=\omega(\bm{f},\bm{g})$ for all $\bm{f},\bm{g}\in V$,
or equivalently, if $U^{T}B_{\omega}U=B_{\omega}$. Such transformations are
also called _symplectic_ transformations. Symplectic vector spaces allow for
the extension of any isometry between subspaces to isometries on the whole
vector space, as stated in the following lemma which can be found in Ref.
[57].

######  Lemma 19 (Witt’s Lemma).

Let $V$ be a symplectic space with symplectic form $\omega:V\times
V\rightarrow\mathcal{F}$. Let $A,B$ be subspaces of $V$ and let
$U:A\rightarrow B$ be an invertible linear map which satisfies
$\omega(U\bm{f},U\bm{g})=\omega(\bm{f},\bm{g})$. Then $U$ can be extended to
an isometry of $V$.

Let us see how the above results connect to the Pauli group and stabilizer
states. As described in Section 2.5, the Pauli group $\mathcal{P}_{n}$ modulo
phases is isomorphic to the vector space $\mathbb{Z}_{2}^{2n}$. The
commutation relations of the Pauli operators define a symplectic form on
$\mathbb{Z}_{2}^{2n}$, i.e., the Pauli group modulo phases is isomorphic to a
symplectic vector space. This correspondence also exists for the qudit Pauli
group and $\mathbb{Z}_{d}^{2n}$ (see Section 4). A stabilizer corresponding to
a stabilizer state is a maximal abelian subgroup of $\mathcal{P}_{n}$ which
does not contain $-\mathds{1}$. Via the above isomorphism it corresponds to a
maximally isotropic subspace of $\mathbb{Z}_{2}^{2n}$.

For instance, consider the Bell state $\ket{\phi^{+}}$, whose stabilizer is
$\mathcal{S}=\\{\mathds{1},X_{1}Z_{2},Z_{1}X_{2},-Y_{1}Y_{2}\\}$. It is
straightforward to verify that any operator in $\mathcal{P}_{2}$ which
commutes with every element of $\mathcal{S}$ is already an element of
$\mathcal{S}$ up to a phase. The stabilizer $\mathcal{S}$ corresponds to the
subspace
$V^{\mathcal{S}}=\\{(0,0,0,0),(1,0,0,1),(0,1,1,0),(1,1,1,1)\\}\subset\mathbb{Z}_{2}^{4}$
via the homomorphism $\sigma:\mathbb{Z}_{2}^{4}\rightarrow\mathcal{P}_{n}$
defined by

$\displaystyle\sigma((1,0,0,0))$ $\displaystyle=X_{1}$ (55)
$\displaystyle\sigma((0,1,0,0))$ $\displaystyle=Z_{1}$ (56)
$\displaystyle\sigma((0,0,1,0))$ $\displaystyle=X_{2}$ (57)
$\displaystyle\sigma((0,0,0,1))$ $\displaystyle=Z_{2}.$ (58)

This subspace is maximally isotropic, i.e., if
$\bm{f}=(a_{1},b_{1},a_{2},b_{2})\in\mathbb{Z}_{2}^{4}$ such that
$\omega(\bm{f},\bm{g})=0$ for all
$\bm{g}=(a_{1}^{\prime},b_{1}^{\prime},a_{2}^{\prime},b_{2}^{\prime})\in
V^{\mathcal{S}}$ with respect to the symplectic form

$\omega(\bm{f},\bm{g})=(a_{1},a_{2},b_{1},b_{2})^{T}\begin{pmatrix}0&\mathds{1}_{2}\\\
\mathds{1}_{2}&0\end{pmatrix}(a_{1}^{\prime},a_{2}^{\prime},b_{1}^{\prime},b_{2}^{\prime}),$
(59)

then $\bm{f}\in V^{\mathcal{S}}$. It is straightforward to see that $\omega$
describes the commutation relations of the respective Pauli operators, for
example $\omega((1,0,0,0),(0,1,0,0))=1$ as $X_{1}Z_{1}=-Z_{1}X_{1}$ but
$\omega((1,0,0,0),(0,0,1,0))=0$ as $X_{1}X_{2}=X_{2}X_{1}$.

Clifford operators map Pauli operators to Pauli operators. As they preserve
the commutation relations of the Pauli operators Clifford operators correspond
to isometries on the symplectic vector space $(\mathbb{Z}_{2}^{2n},\omega)$.
On the contrary, any homomorphism between subgroups of the Pauli group which
preserves commutation relations and is invertible can be extended to an
isometry due to Lemma 19 and can be implemented by a Clifford operator (cf.
Equation (16)).

##  Appendix C Properties of commutation matrices

In this section we are concerned with the rank condition (cf. Equation (31)),
which is necessary for commutation matrices. First, we prove Theorem 6 and
then show that the equality in Equation (31) is an inequality for general
tuples of alternating matrices. We note that the theorem also holds for any
finite field, and the proof follows simply by replacing $\mathbb{Z}_{2}$ with
$\mathbb{Z}_{d}$.

For convenience, let us restate Theorem 6.

######  Theorem 6.

Let $(C_{\alpha})_{\alpha\in P(M,n)}$, $C_{\alpha}\in M_{n\times
n}(\mathbb{Z}_{2})$ be a tuple of alternating matrices such that
$\sum_{\alpha}C_{\alpha}=0$ for some partition $P(M,n)$. Then there exists a
$\ket{\psi}\in\text{Stab}(P(M,n))$ such that $(C_{\alpha})_{\alpha}$ are the
corresponding commutation matrices if and only if

$2\,{\rm rk}([C_{\alpha}]_{\alpha})=\sum_{\alpha}{\rm rk}(C_{\alpha}).$ (60)

Here, $[C_{\alpha}]_{\alpha}$ is the $n\times(nm)$ matrix obtained by
concatenating all matrices $C_{\alpha}$, and the rank is taken over the field
$\mathbb{Z}_{2}$.

###### Proof.

First, we prove the only if part of the statement. Suppose that
$(C_{\alpha})_{\alpha}$, with $C_{\alpha}\in M_{n\times n}(\mathbb{Z}_{2})$,
correspond to an $n$ qubit stabilizer state. We want to prove that Equation
(60) holds. To begin with, let us consider the l.h.s. of Equation (60).
Observe that ${\rm rk}([C_{\alpha}]_{\alpha})={\rm
rk}([QC_{\alpha}Q^{T}]_{\alpha})$ for any invertible $Q\in M_{n\times
n}(\mathbb{Z}_{2})$. Consider a $Q$ such that $[QC_{\alpha}Q^{T}]_{\alpha}$
has the maximum number of zero rows. The number of zero rows is equal to the
number of generators of $\mathcal{S}$ that locally commute with all other
elements in the stabilizer. These generators correspond to qubits that can be
locally extracted, as they are not entangled with any other qubit outside of
their corresponding parties (see discussion above Theorem 8). For convenience,
let us now assume that those states have been extracted, so that ${\rm
rk}([C_{\alpha}]_{\alpha})=N\leq n$ is of full rank, i.e., equal to the number
$N$ of qubits that are entangled with at least one other qubit outside of
their own party. Next, let us consider the r.h.s of Equation (60), and let us
establish the connection between the ranks of the commutation matrices and the
ranks of the corresponding reduced states. Recall, that for stabilizer states
the reduced states are given by Equation (3), i.e., by the sum over all
elements $s\in\mathcal{S}$ with their support fully contained in $\alpha$.
Consider the matrix $C_{\alpha}$. Due to Theorem 18 there exists an invertible
matrix $Q$ such that $QC_{\alpha}Q^{T}$ is a direct sum of blocks of the form
as in Equation (54). We observe that whenever a generator anti-commutes with
another generator on party $\alpha$ they also have to anti-commute on at least
one other party (as the generators have to commute as a whole), and hence,
every nonzero block increases the rank of the reduced state by a factor of
two, and thus, $\text{rk}(\varrho_{\alpha})=2^{\text{rk}(C_{\alpha})/2}$. From
this equation it follows that $\text{rk}(C_{\alpha})/2$ is the number of
qubits in $\alpha$ that are entangled with at least one other qubit in another
party. Thus, $\sum_{\alpha}\text{rk}(C_{\alpha})/2$ is equal to the total
number $N$ of entangled qubits, and thus, Equation (60) holds.

The if part of the statement follows directly form the construction below
Theorem 6 in the main text. ∎

Next, let us show that Equation (31) is an inequality for general sets of
alternating matrices. We show the following theorem over any field $F$ as we
use it later not only for $\mathbb{Z}_{2}$ but any $\mathbb{Z}_{d}$ with $d$ a
prime number.

######  Theorem 20.

Let $\\{A_{\alpha}\\}_{\alpha\in[M]}\subset M_{n\times n}(F)$ with
$M\in\mathbb{N}$ be a finite set of alternating matrices such that
$\sum_{\alpha}A_{\alpha}=0$. Then

$2\,{\rm rk}([A_{\alpha}]_{\alpha\in[M]})\leq\sum_{\alpha\in[M]}{\rm
rk}(A_{\alpha})$ (61)

where $[A_{\alpha}]_{\alpha\in[M]}\in M_{n\times(kn)}(F)$ is the matrix
obtained by concatenating the matrices $\\{A_{\alpha}\\}_{\alpha\in[M]}$.

To prove Theorem 20 we use the following Lemma shown in Ref. [61].

######  Lemma 21.

Let $A,B\in M_{n\times m}(F)$. Then

${\rm rk}([A,B])+{\rm rk}\begin{pmatrix}A\\\ B\end{pmatrix}\leq{\rm
rk}(A)+{\rm rk}(B)+{\rm rk}(A+B).$ (62)

###### Proof of Theorem 20.

Following Ref. [61], we denote in the following for any matrix $A\in
M_{k\times l}(F)$, $k,l\in\mathbb{N}$ by $\overline{A}\in M_{k\times
k}(\mathbb{Z}_{2})$ the orthogonal projector on the columnspace of $A$.

We prove the statement via induction. For $M=3$ the statement is equivalent to
Lemma 21 and holds. Suppose the statement holds for all $M$ from $3$ to $N$.
Let us show that then it also holds for $M=N+1$.

Let $\\{A_{\alpha}\\}_{\alpha\in[N+1]}\subset M_{n\times n}(F)$ be a set of
alternating matrices such that $\sum_{\alpha}A_{\alpha}=0$. We want to show
that Inequality (61) holds. To this end, let us first show another inequality
that will be helpful in the proof. In the following we write $C_{X}$ for the
column space of the matrix $X$. Then, we find that

$\displaystyle{\rm
rk}((\mathds{1}-\overline{[A_{\alpha}]_{\alpha\in[N-1]}})A_{N})+\text{dim}(C_{\sum_{\alpha=1}^{N-1}A_{\alpha}}\cap
C_{A_{N}})$ (63) $\displaystyle\leq$ $\displaystyle{\rm
rk}((\mathds{1}-\overline{[A_{\alpha}]_{\alpha\in[N-1]}})A_{N})+\text{dim}(C_{[A_{\alpha}]_{\alpha\in[N-1]}}\cap
C_{A_{N}})={\rm rk}(A_{N}).$ (64)

The inequality follows from the fact that
$C_{\sum_{\alpha=1}^{N-1}A_{\alpha}}\subseteq
C_{[A_{\alpha}]_{\alpha\in[N-1]}}$. The last equality can be seen as follows.
First observe that the equality holds if and only if it holds for $A_{N}R$,
where $R$ is an invertible matrix. Let $f_{j}=f_{j}^{\perp}\oplus f_{j}^{||}$
for any $j$ be the columns of $A_{N}R$ where
$(\mathds{1}-\overline{[A_{\alpha}]_{\alpha\in[N-1]}})f_{j}^{\perp}=f_{j}^{\perp}$
and $(\mathds{1}-\overline{[A_{\alpha}]_{\alpha\in[N-1]}})f_{j}^{||}=0$. We
choose $R$ such that there exists a $k\leq n$ such that $f_{j}^{\perp}=0$ for
all $j>k$ and $f_{1}^{\perp},\ldots,f_{k}^{\perp}$ are independent. Then,