Local Equivalence of Stabilizer States: A Graphical Characterisation

Stabilizer states, and in particular graph states, form a versatile family of entangled quantum states, which allow for easy and compact representations. They are used as entangled resource states in various quantum information applications, like measurement-based computation [29, 30, 5], error corrections [35, 34, 10, 33], quantum communication network routing [19, 26, 4, 7], and quantum secret sharing [25, 17], to cite a few. In all these applications, stabilizer states are used as multi-partite entangled resources, it is thus crucial to understand when two such states have the same entanglement. According to standard quantum information theory, two quantum states have the same entanglement if they can be transformed into each other using only local operations, where “local” refers to operations that can be applied to at most one qubit at a time. Indeed, intuitively, such local operations can only decrease the strength of the entanglement of a quantum state, thus if a state can be transformed into another and back to the original one using only local operations, the two states do have the same entanglement. Concretely, the most general case is the so-called SLOCC-equivalence (stochastic local operations and classical communications) that encompass the use of local unitaries and measurements. In the particular case of stabilizer states, it is enough to consider LU-equivalence (local unitaries), as two stabilizer states are SLOCC-equivalent iff there exists $U=U_1\otimes \mathrm{\dots }\otimes U_n$ that transforms one state into the other, where each $U_i$ is a 1-qubit unitary transformation [21]. Therefore, in this paper, we refer to LU-equivalence when stating that two stabilizer states possess the same entanglement.

Stabilizer states can be graphically represented through the graph state formalism, which consists in representing quantum states using graphs where each vertex corresponds to a qubit. Graph states form actually a sub-family of stabilizer states but any stabilizer state can be transformed into a graph state using local Clifford unitaries in a straightforward way [21], as a consequence it is sufficient to consider graph states when dealing with entanglement equivalence of stabilizer states. Notice that understanding the entanglement structure of graph states and how it can be characterised in a graphical way is the most fascinating fundamental question of the graph state formalism [21, 13, 14, 18, 23, 36, 37, 11].

An interesting combinatorial property of entanglement has been proved in [21]: LU-equivalent graph states have the same cut-rank function¹¹1The cut-rank function over a graph $G=(V,E)$ is the function that maps a set $A\subseteq V$ to the rank (in ${𝔽}_2$) of the cut-matrix ${\mathrm{\Gamma }}_A=({({\mathrm{\Gamma }}_A)}_{ab}:a\in A\text{, }b\in V\setminus A)$ where ${\mathrm{\Gamma }}_{ab}=1$ if and only if $(a,b)\in E$.. However, there exist pairs of graph states that have the same cut-rank function but which are not LU-equivalent: a counterexample involves two isomorphic Petersen graphs [16, 21].

A fundamental property of the graph state formalism is that a local complementation – a graph transformation that consists in complementing the neighbourhood of a given vertex – preserves entanglement: if a graph can be transformed into another by means of local complementations then the two corresponding graph states are LU-equivalent. More precisely the corresponding graph states are LC-equivalent (local Clifford). Van den Nest [13] proved that two graph states are LC-equivalent if and only if the corresponding graphs are related by a sequence of local complementations. LC-equivalence and LU-equivalence of graph states were conjectured to coincide [24], as they coincide for several families of graph states [14, 38]. However, a counterexample of order 27 has been discovered using computer assisted methods [23]. Since then, the existence of a graphical characterisation of LU-equivalence has remained an open question. Furthermore, families of graph states for which LC-equivalence and LU-equivalence coincide have been a subject of interest [33, 37].

Let us first give some notations and basic definitions. A graph³³3We only consider simple (no selfloop) undirected graphs. $G$ is a pair $(V,E)$, where $V$ is a finite set of vertices, and $E$ is a set of unordered pairs of distinct vertices called edges. We assume the set of vertices to be totally ordered and use the notation $V=\{u_1,\mathrm{\dots },u_n\}$ s.t. $u_i\prec u_j$ iff . The number $n=|V|$ of vertices is called the order of the graph and $|G|:=|E|$ its size. We use the notation $u{\sim }_{G}v$ when the vertices $u$ and $v$ are connected in $G$, i.e. $(u,v)\in E$. Given a vertex $u$, $N_G(u)=\{v\in V|(u,v)\in E\}$ is the neighbourhood of $u$. The odd and the common neighbourhoods are two natural generalisations of the notion of neighbourhoods to sets of vertices: for any $D\subseteq V$, $Od{d}_G(D)={\mathrm{\Delta }}_{u\in D}{N}_G(u)=\{v\in V||N_G(v)\cap D|=1\text{ mod }2\}$ is the odd neighbourhood of $D$, where $\mathrm{\Delta }$ denotes the symmetric difference on vertices. Informally, $Od{d}_G(D)$ is the set of vertices that are the neighbours of an odd number of vertices in $D$. The common neighbourhood of $D$ is denoted ${\mathrm{\Lambda }}_G^D={\bigcap }_{u\in D}{N}_G(u)=\{v\in V|\forall u\in D,v\in N_G(u)\}$. A local complementation with respect to a given vertex $u$ consists in complementing the subgraph induced by the neighbourhood of $u$, leading to the graph $G\star u=G\mathrm{\Delta }{K}_{N_G(u)}$ where $\mathrm{\Delta }$ denotes the symmetric difference on edges and $K_A$ is the complete graph on the vertices of $A$. Local complementation is an involution, i.e. $G\star u\star u=G$. A pivoting with respect to two connected vertices $u$ and $v$ is the operation that maps $G$ to $G\wedge uv:=G\star u\star v\star u$. Notice that pivoting is symmetric ($G\wedge uv=G\wedge vu$) and is an involution ($G\wedge uv\wedge uv=G$). With a slight abuse of notation we identify multisets of vertices with their multiplicity function $V\to \mathbb{N}$. ⁴⁴4Hence we also identify sets of vertices with their indicator functions $V\to \{0,1\}$. A (multi)set $S$ of vertices is independent if there is no two vertices of $S$ that are connected.

Graph states form a standard family of quantum states that can be represented using graphs (Ref. [20] is an excellent introduction to graph states). Given a graph $G$ of order $n$, the corresponding graph state $|G⟩$ is the $n$-qubit state:

where $G[x]$ denotes the subgraph of $G$ induced by $\{u_i|x_i=1\}\subseteq V$.

The $i^{\text{th}}$ qubit of $|G⟩$ can be associated with the vertex $u_i$ of $G$, so, with a slight abuse of notation, we refer to $V$ as the set of qubits of $|G⟩$. Given a 1-qubit operation $R$, like $X:|a⟩\mapsto |1-a⟩$ or $Z:|a⟩\mapsto {(-1)}^a|a⟩$, and a subset $D\subseteq V$ of qubits, $R_D:={⨂}_{u\in D}{R}_u$ is the local operation which consists in applying $R$ on each qubit of $D$.

The graph state $|G⟩$ is the unique quantum state (up to a global phase) that, for every vertex $u\in V$, is a fixed point of the Pauli operator $X_u{Z}_{N_G(u)}$. More generally, $|G⟩$ is an eigenvector of any Pauli operator $X_D{Z}_{Odd(D)}$ with $D\subseteq V$:

The proof of Proposition 1 can be found in the full version of this paper [9]. The fact that a graph state can be defined as the common eigenvector of Pauli operators witnesses that graph states form a subfamily of stabilizer states⁵⁵5A $n$-qubit state is a stabilizer state if it is the fixpoint of $n$ independent commuting Pauli operators (or equivalently $2^n$ distinct commuting Pauli operators).. Conversely, any stabilizer state can be turned into a graph state by means of local Clifford unitaries⁶⁶6Local Clifford unitaries are tensor products of single-qubit Clifford gates, which map the Pauli group to itself under conjugation. Formally, a single-qubit gate $U$ is Clifford if for any $P\in 𝒫:=\{\pm 1,\pm i\}\times \{I,X,Y,Z\}$, $UP{U}^{†}\in 𝒫$. in a straightforward way (see for instance [13]). Thus we will focus in the rest of this paper on graph states.

The action of measuring, in the standard basis, a qubit of a graph state leads, roughly speaking, to the graph state where the corresponding vertex has been removed. A diagonal measurement can also be used to remove a vertex when this vertex is isolated:

We are interested in the action of 1-qubit unitaries on graph states, in particular Hadamard $H:|a⟩\mapsto \frac{|0⟩+{(-1)}^a|1⟩}{\sqrt{2}}$, and Z- and X-rotations respectively defined as follows:

In particular, local complementations can be implemented by $\pi /2$ X- and Z-rotations:

Similarly, pivoting can be implemented by means of Hadamard transformations (up to Pauli transformations):

Beyond $\frac{\pi }{2}$ rotations, notice that any local unitary can be implemented using Hadamard and Z-rotations with arbitrary angles. We consider for any $r\in \mathbb{N}$ the set LC_r of local unitaries generated by $H$ and $Z(\frac{\pi }{2^r})$. In particular LC₁ is the set of local Clifford operators, moreover, for any $r$, LC${}_r{}^{}\subseteq L{C}_{r+1}$. Notice that there exist local unitaries, e.g. $Z(\frac{\pi }{3})$, that are not contained in LC_r for any $r$. We say that two states are LU-equivalent, denoted $|\psi ⟩{=}_{LU}|{\psi }^{\prime }⟩$ when there exists a local unitary transformation $U$ such that $|\psi ⟩=U|{\psi }^{\prime }⟩$. Similarly two states are LC_r-equivalent, denoted $|\psi ⟩{=}_{L{C}_r}|{\psi }^{\prime }⟩$ when there exists a local unitary $U\in L{C}_r$ s.t. $|\psi ⟩=U|{\psi }^{\prime }⟩$.

It is well-known that two graph states $|G⟩$ and $|G^{\prime }⟩$ are LC₁-equivalent if and only if there exists a sequence of local complementations that transforms $G$ into $G^{\prime }$ [13]. We slightly refine this result showing that there exists a reasonnably small sequence of local complementation transforming $G$ into $G^{\prime }$, that corresponds to a particular Clifford operator:

The proof of Proposition 6 can be found in the full version of this paper [9]

Whereas it has been originally conjectured that if two graphs states are LU-equivalent then there exists a sequence of local complementations transforming one in another [24], a couple of counter examples of pairs of LC₂- but not LC₁-equivalent graph states have been pointed out [23, 36]. To further understand the action of local unitaries on graph states, we thus introduce in the next section a generalisation of local complementation to graphically capture the equivalence of graph states that are LU- but not LC₁-equivalent.

Two $r$-locally equivalent graphs are also $(r+1)$-locally equivalent. This can be seen graphically as a direct consequence of Proposition 10, or using graph states through Theorem 32, as two LC_r-equivalent states are obviously LC_r+1-equivalent. The known counter examples to the LU-LC conjecture introduced in [23, 36] are actually LC₂-equivalent graph states that are not LC₁-equivalent, thus the corresponding graphs are $2$-locally equivalent but not $1$-locally equivalent. There was however no known examples of graph states that are LC₃-equivalent but not LC₂-equivalent, and more generally no known examples of graph states that are LC_r-equivalent but not LC_r-1-equivalent for $r>2$. We introduce such examples in this section, by showing that for any $r$ there exist pairs of graphs that are $(r+1)$-locally equivalent but not $r$-locally equivalent leading to an infinite hierarchy of generalised local equivalences. Our proof is constructive: for any $r$ we exhibit pairs of graphs that are $(r+1)$-locally equivalent but not $r$-locally equivalent.

We introduce a family of bipartite graphs $C_{t,k}$ parametrized by two integers $t$ and $k$. This family is a variant of the (bipartite) Kneser graphs and uniform subset graphs. The graph $C_{t,k}$ is bipartite: the first independent set of vertices corresponds to the integers from $1$ to $t$, and the second independent set is composed of all the subsets of $[1,t]$ of size $k$. There is an edge between an integer $u\in [1,t]$ and a subset $A\subseteq [1,t]$ of size $k$ if and only if $u\in A$:

We introduce a second family of graphs $C_{t,k}^{\prime }$, defined similarly to $C_{t,k}$, the independent set $[1,t]$ being replaced by a clique:

Examples of such graphs with parameters $t=4$ and $k=2$ are given in Figure 3. For any odd $k⩾3$, $t⩾k+2$, $C_{t,k}$ and $C_{t,k}^{\prime }$ are in standard form for any ordering such that, for any $u\in \left(\genfrac{}{}{0pt}{}{[1,t]}{k}\right)$ and for any $v\in [1,t]$, $u\prec v$. More precisely the vertices in $\left(\genfrac{}{}{0pt}{}{[1,t]}{k}\right)$ are of type X and the vertices in $[1,t]$ are of type Z. The proof can be found in the full version of this paper [9].

The following proposition gives a sufficient condition on $t$ and $k$ for the $r$-local equivalence of $C_{t,k}$ and $C_{t,k}^{\prime }$.