Abstract 1 Introduction 2 Preliminaries 3 Algorithms for LCr- and LU-equivalences 4 LU- and LC-equivalence coincide for graph states up to 19 qubits 5 Conclusion References Appendix A Computer-assisted study of 2-local complementation

Deciding Local Unitary Equivalence of Graph States in Quasi-Polynomial Time

Nathan Claudet ORCID Inria Mocqua, LORIA, CNRS, Université de Lorraine, F-54000 Nancy, France Simon Perdrix ORCID Inria Mocqua, LORIA, CNRS, Université de Lorraine, F-54000 Nancy, France
Abstract

We describe an algorithm with quasi-polynomial runtime nlog2(n)+O(1) for deciding local unitary (LU) equivalence of graph states. The algorithm builds on a recent graphical characterisation of LU-equivalence via generalised local complementation. By first transforming the corresponding graphs into a standard form using usual local complementations, LU-equivalence reduces to the existence of a single generalised local complementation that maps one graph to the other. We crucially demonstrate that this reduces to solving a system of quasi-polynomially many linear equations, avoiding an exponential blow-up. As a byproduct, we generalise Bouchet’s algorithm for deciding local Clifford (LC) equivalence of graph states by allowing the addition of arbitrary linear constraints. We also improve existing bounds on the size of graph states that are LU- but not LC-equivalent. While the smallest known examples involve 27 qubits, and it is established that no such examples exist for up to 8 qubits, we refine this bound by proving that LU- and LC-equivalence coincide for graph states involving up to 19 qubits.

Keywords and phrases:
Quantum computing, Graph theory, Entanglement, Local complementation
Category:
Track A: Algorithms, Complexity and Games
Copyright and License:
[Uncaptioned image] © Nathan Claudet and Simon Perdrix; licensed under Creative Commons License CC-BY 4.0
2012 ACM Subject Classification:
Theory of computation Quantum information theory
; Mathematics of computing Graph algorithms
Related Version:
Full Version: https://arxiv.org/abs/2502.06566 [12]
Acknowledgements:
The authors want to thank Adam Burchardt for fruitful discussions.
Funding:
This work is supported by the the Plan France 2030 through the PEPR integrated project EPiQ ANR-22-PETQ-0007 and the HQI platform ANR-22-PNCQ-0002; and by the European projects Quantum Flagship NEASQC, European High-Performance Computing HPCQS and MSCA Staff Exchanges Qcomical HORIZON-MSCA-2023-SE-01. The project is also supported by the Maison du Quantique MaQuEst.
Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele Puppis

1 Introduction

Graph states form a ubiquitous family of quantum states. They are used as entangled resource states in various quantum information applications, such as measurement-based computation [28, 29, 5], error correction [32, 31, 14, 30], quantum communication network routing [19, 26, 4, 8], and quantum secret sharing [25, 18], to cite a few. In all these applications, graph states are used as multipartite entangled resources, it is thus crucial to understand when two such states have the same entanglement, i.e. when they can be transformed into each other using only local operations. SLOCC-equivalence (stochastic local operations and classical communications) is the most general case that encompasses the use of local unitaries and measurements. In the particular case of graph states, it is enough to consider LU-equivalence (local unitaries), as two graph states are SLOCC-equivalent if and only if there exists U=U1Un that transforms one state into the other, where each Ui is a single-qubit unitary transformation [21]. One can also consider LC-equivalence (local Clifford) which is known to be distinct from LU-equivalence, the smallest known examples of graph states that are LU-equivalent but not LC-equivalent have 27 qubits [23, 35].

As their name suggests, graph states can be uniquely represented by simple undirected graphs. Remarkably, LC-equivalence of graph states is captured by applications of a simple transformation on the corresponding graphs: local complementation [16]. Local complementation consists in complementing the neighbourhood of a given vertex. Local complementation was introduced by Kotzig in the 1960s [24], and has been studied independently of its applications in quantum computing. In particular, Bouchet has introduced an efficient algorithm for deciding whether two graphs are related by a sequence of local complementations [1]. This has led to an efficient algorithm for deciding the local Clifford equivalence of graph states within O(n4) operations, where n is the number of qubits [15].

Recently a graphical characterisation of LU-equivalence has been introduced by means of generalised local complementation [13]. The characterisation relies in particular on some peculiar graph structures called minimal local sets that are known to be invariant under local unitary transformations [22]. In [11], it was shown that any vertex is covered by a minimal local set and that a family of minimal local sets covering every vertex of the graph, called an MLS cover, can be computed efficiently. Roughly speaking each minimal local set imposes a constraint on the local unitary transformations mapping a graph state to another, so that the existence of such a local unitary is reduced to solving a linear system over integers modulo a power of 2. The solutions can then be graphically interpreted as generalised local complementations.

Shortly after, an algorithm for deciding LU-equivalence was independently introduced [6] based on a similar idea of reducing the problem of LU-equivalence to a linear system, benefiting in particular from the fact that an MLS cover can be computed efficiently. The overall complexity of this algorithm for deciding LU-equivalence depends on two parameters, roughly speaking the size of the linear system and the number of connected components of an intersection graph related to the MLS cover. Both parameters can potentially make the runtime of the algorithm exponential.

We introduce a new algorithm for LU-equivalence of graph states that relies on generalised local complementation and allows us to mitigate both sources of exponential complexity. First, we reduce the LU-equivalence problem to the existence of a single generalised local complementation. To achieve this efficient reduction, we extend Bouchet’s algorithm. Then, we demonstrate that the level of the remaining generalised local complementation can be upper bounded by at most the logarithm of the order n of the graphs, leading to a linear system of size at most nlog2(n)+O(1). This results in an overall algorithm whose time-complexity is quasi-polynomial in n. Notice that the generalisation of Bouchet’s algorithm provides an efficient algorithm for deciding whether two graphs are related by local complementations under additional constraints, for instance that the local complementations are applied to a particular subset of vertices.

Thanks to the graphical characterisation of LU-equivalence by means of generalised local complementation, we also address the question of the smallest graphs that are LU- but not LC-equivalent. The study of graph classes where LU-equivalence coincides with LC-equivalence has garnered significant attention [21, 20, 17, 37, 23, 7, 36, 13, 6]. Notably, the smallest known examples of graphs that are LU- but not LC-equivalent have 27 vertices while it is established that no such counterexamples exist for fewer than 8 vertices [7]. We significantly improve this result by showing that any counterexample has at least 20 vertices.

2 Preliminaries

Notations. Given an undirected simple graph G=(V,E), we use the notation uGv when the vertices u and v are connected in G, i.e. (u,v)E. NG(u)={vV|uGv} is the neighbourhood of u, OddG(D)={vV||NG(v)D|=1mod2} is the odd-neighbourhood of the set DV of vertices, and ΛGD={vV|uD,uGv} is the common neighbourhood of DV. We assume V totally ordered by a relation . 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 Gu=GΔKNG(u) where Δ denotes the symmetric difference on edges and KA is the complete graph on the vertices of A. With a slight abuse of notation we identify multisets of vertices with their multiplicity function V (hence we also identify sets of vertices with their indicator functions V{0,1}). We consider sums of multisets: for any vertex u, (S1+S2)(u)=S1(u)+S2(u). The support supp(S) of a multiset S of vertices denotes the set of vertices uV such that S(u)>0. S is said independent if no two vertices of supp(S) are connected. For any multiset S and set D, SΛGD is the number of vertices of S, counted with their multiplicity, that are neighbours to all vertices of D; in other words, SΛGD is the number of common neighbours of D in S (.. is the scalar product: AB=uVA(u).B(u), so SΛGD=uΛGDS(u)).

To any simple undirected graph G=(V,E), is associated a quantum state |G, called graph state, defined as

|G=12nx{0,1}n(1)|G[x]||x

where n is the order of G and |G[x]| denotes the number of edges in the subgraph of G induced by x.111With a slight abuse of notation, x{0,1}n denotes the subset of vertices {uV|xι(u)=1}, where ι:V[0,n1] s.t. uvι(u)<ι(v). ι is unique as V is totally ordered by .

We are interested in the action of local unitaries on graph states. A local unitary is a tensor product of 1-qubit unitaries like Hadamard H:|a|0+(1)a|12, and Z- and X-rotations that are respectively defined as follows:

Z(α):=eiα2(cos(α2)Iisin(α2)Z);X(α):=HZ(α)H=eiα2(cos(α2)Iisin(α2)X)

where X:|a|1a and Z:|a(1)a|a. Any 1-qubit unitary can be decomposed into H and Z(α) rotations, whereas 1-qubit Clifford operators are those generated by H and Z(π2). Local complementation (denoted by the operator ) can be implemented by local Clifford operators:

|Gu=Xu(π2)vNG(u)Zv(π2)|G

Conversely, if two graph states are related by local Clifford unitaries, the corresponding graphs are related by local complementations [16]. Thus, we use the term of LC-equivalence to describe both local Clifford equivalent graph states, and graphs related by local complementations (conveniently, LC stands for both local Clifford and local complementation). Similarly, we say that two graphs are LU-equivalent (resp. LCr-equivalent) when there is a local unitary (resp. a local unitary generated by H and Z(π2r)) transforming the corresponding graph states into each other.

Graph states form a subfamily of the well-known stabilizer states, indeed |G is the fix point of XuvNG(u)Zv for any uV. When analysing the entanglement properties of stabilizer states, it is natural to focus on graph states as every stabilizer state is known to be local Clifford equivalent to a graph state [16]. Moreover, there are efficient procedures to associate with any stabilizer state an LC-equivalent graph state [15], thus the problem of deciding the LU-equivalence of stabilizer states naturally reduces to the LU-equivalence of graph states.

We describe in the next section a recent graphical characterisation of LU- and LCr-equivalences of graph states based on the so-called generalised local complementation [13].

2.1 Generalised local complementation

We review the definition of generalised local complementation and a few of its basic properties. The reader is referred to [13] for a more detailed introduction. A generalised local complementation is a graph transformation parametrised by an independent (multi)set of vertices S and a positive number r called level. Like the usual local complementation, the transformation consists in toggling some of the edges of the graph depending on the number of neighbours the endpoint vertices have in common in S. Roughly speaking an r-local complementation toggles an edge if the number of common vertices in S is an odd multiple of 2r1 (an example of 2-local complementation is given in Figure 1). To be a valid r-local complementation, the (multi)set S on which the transformation is applied should be r-incident, i.e. the number of common neighbours in S of any set of at most r vertices should be an appropriate power of two:

Definition 1 (r-Incidence).

Given a graph G, a multiset S of vertices is r-incident, if for any k[0,r), and any KVsupp(S) of size k+2, their number SΛGK of common neighbours in S is a multiple of 2rkδ(k), where δ is the Kronecker delta222δ(x){0,1} and δ(x)=1x=0. .

Definition 2 (r-Local Complementation).

Given a graph G and an r-incident independent multiset S, let GrS be the graph defined as

uGrSv(uGvSΛGu,v=2r1mod2r)

Below we recall some basic properties of generalised local complementation.

Proposition 3.

[13]

  • Generalised local complementations are self inverse: if GrS is valid, then (GrS)rS=G.

  • The multiplicity in S can be upperbounded by 2r: if GrS is valid, then GrS=GrS, where, for any vertex u, S(u)=S(u)mod2r.

  • If GrS1 and GrS2 are valid and S1+S2 is independent in G, then Gr(S1+S2)=(GrS1)rS2.

  • If GrS is valid then Gr+1(S+S) is valid and induces the same transformation: Gr+1(S+S)=Gr+1Sr+1S=GrS.

  • If GrS is valid then Gr1S is valid (when r>1) and Gr1S=G.

2.2 1- and 2-local complementation

To illustrate how r-local complementation behaves, we consider the simple cases r=1 and r=2. First, any multiset S is 1-incident, and a 1-local complementation is nothing but a sequence of usual local complementations. 2-local complementations cannot always be decomposed into usual local complementations, it is however sufficient to consider 2-local complementations over sets, rather than multisets (see Figure 1):

Figure 1: Illustration of a 2-local complementation over the multiset S={a,a,b,c}. S is 2-incident: indeed SΛG{d,e,f}=2, which is a multiple of 2210=2. Similarly, SΛG{d,e}=SΛG{d,f}=2 and SΛG{e,f}=4. Edges de and df are toggled as SΛG{d,e}=SΛG{d,f}=2mod4, but not edge ef as SΛG{e,f}=0mod4. Following Proposition 4, the 2-local complementation over S can be decomposed into a 2-local complementation over the set {b,c} and a 1-local complementation over the set {a}.
Proposition 4.

Any 2-local complementation can be decomposed into 1- and 2-local complementations over sets.

Proof.

Given a 2-local complementation over a multiset S, we assume without loss of generality that multiplicities are defined modulo 22=4. Let S1 be the set of vertices that have multiplicity 2 or 3 in S. Notice that G2S=G2S1S11S1 as S1 is an independent set, S1 is 1-incident and generalised local complementations are self inverse. So G2S=G2S2(S1+S1)1S1=G2(S+S1+S1)1S1, where the multiplicity in S+S1+S1 is either 0 or 1 modulo 4. Thus the 2-local complementation over the multiset S can be decomposed into 2- and 1-local complementations over sets supp(S+S1+S1) and S1 respectively.

The 2-incidence condition can be rephrased as follows when S is a set: for any subset K of VS of size 2 or 3, there is an even number of common neighbours in S: |SΛGK|=0mod2. In other words, the cut matrix describing the edges between S and VS is tri-orthogonal [3, 33, 27].

2.3 LU-equivalence and generalised local complementation

While local complementation can be implemented on graph states by means of local Clifford unitaries, r-local complementations can be implemented on graph states with local unitaries generated by H and Z(π2r):

|GrS=uVX(S(u)π2r)vVZ(π2ruNG(v)S(u))|G

Conversely, if two graph states are related by local unitaries generated by H and Z(π2r), the corresponding graphs are related by r-local complementations [13]. In other words two graphs are LCr-equivalent if and only if there is a series of r-local complementations transforming one into another. Two LCr-equivalent graphs are also LCr+1-equivalent, however the converse does not hold, resulting in an infinite strict hierarchy of local equivalences [13]. Most importantly, generalised local complementations capture the LU-equivalence of graphs:

Theorem 5.

[13] If G1 and G2 are LU-equivalent, then G1 and G2 are LC⌊n/2⌋-1 equivalent, where n is the order of the graphs, i.e. there exists a sequence of (n/21)-local complementations transforming G1 into G2.

Finally, a peculiar property is that for any pair of LU-equivalent graphs, a single generalised complementation, together with usual local complementations, is sufficient to transform one graph into the other:

Proposition 6.

[13] If G1 and G2 are LCr-equivalent, then G1 and G2 are related by a sequence of generalised local complementations, such that a single one is of level r, all the others are usual local complementations (i.e. level 1).

3 Algorithms for LCr- and LU-equivalences

In this section, we address the problem of deciding whether two given graphs are LU-equivalent. Additionally, we consider a variant of this problem which consists in deciding whether two graphs are LCr-equivalent for a fixed r. Since LU-equivalent graphs are necessarily LCr-equivalent for some r, the difference lies in whether the level r is fixed or not.

Thanks to Proposition 6, if G1 is LCr-equivalent to G2, there exists a single r-local complementation, together with usual local complementations, that transforms G1 into G2. We introduce an algorithm that builds such a sequence of generalised local complementations, in essentially four stages:

  1. (i)

    Both G1 and G2 are turned in standard forms G1 and G2 by means of (usual) local complementations. These transformations are driven by a so-called minimal local set cover which can be efficiently computed.

  2. (ii)

    We then focus on the single r-local complementation: all the possible actions of a single r-local complementation on G1 are described as a vector space, for which we compute a basis .

  3. (iii)

    It remains to find, if it exists, the r-local complementation to apply on G1 that leads to G2 up to some additional usual local complementations. With an appropriate construction depending on G1, G2 and , we reduce this problem to deciding whether two graphs are LC-equivalent under some additional requirements on the sequence of local complementations to apply. These requirements can be expressed as linear constraints.

  4. (iv)

    Finally, to find such a sequence of local complementations, we apply a variant of Bouchet’s algorithm, generalised to accommodate the additional linear constraints.

Stages (i), (iii) and (iv) can be performed in polynomial time in the order n of the graphs. Stage (ii) has essentially a O(nr) time complexity, thus deciding LCr-equivalence for a fixed r can be done in polynomial time. Regarding LU-equivalence, Theorem 5 implies rn2. We improve this upperbound and show that r is at most logarithmic in n, leading to a quasi-polynomial time algorithm for LU-equivalence.

The rest of this section is dedicated to the description of the algorithm, its correctness and complexity, beginning with the generalisation of Bouchet’s algorithm to decide, in polynomial time, LC-equivalence with additional constraints.

3.1 Bouchet algorithm, revisited

LC-equivalence can be efficiently decided thanks to the famous Bouchet’s algorithm [1]. Bouchet proved that LC-equivalence of two given graphs, defined on the same vertex set V, reduces to the existence of subsets of vertices satisfying the following two equations:

Proposition 7.

[1] Two graphs G, G are LC-equivalent if and only if there exist A,B,C,DV such that

  • (i)

    u,vV,
    |BNG(u)NG(v)|+|ANG(u){v}|+|D{u}NG(v)|+|C{u}{v}|=0mod2

  • (ii)

    (AD)Δ(BC)=V

While the original proof involves isotropic systems [2], we provide an alternative, self-contained proof in the full version of this paper [12], that we believe to be more accessible than the original one.

Notice that Equation (i) is actually a linear equation: the set 𝒮V4 of solutions to (i) is a vector space, indeed given two solutions S=(A,B,C,D) and S=(A,B,C,D) of (i), so is S+S=(AΔA,BΔB,CΔC,DΔD). The linearity of equation (i) can be emphasised using the following encoding:

A set AV can be represented by n binary variables a1,,an𝔽2 s.t. av=1vA, moreover, with a slight abuse of notations, we identify any set AV with the corresponding diagonal 𝔽2 matrix of dimension n×n in which diagonal elements are the (av)vV. Following [15, 20], equation (i) is equivalent to

ΓBΓ+ΓA+DΓ+C=0 (1)

and equation (ii) to

AD+BC=I (2)

where Γ and Γ are the adjacency matrices of G and G respectively.

In this section, we consider an extension of Bouchet’s algorithm where an additional set of linear constraints on A,B,C and D is added as input of the problem. Such additional linear equations can reflect constraints on the applied local complementations, e.g. deciding whether two graphs are LC-equivalent under the additional constraint that all local complementations are applied on a fixed set V0 of vertices (see Example 11).

While solving linear equations is easy, equation (ii) is not linear, and the tour de force of Bouchet’s algorithm is to point out the fundamental properties of the solutions to both equations (i) and (ii) that allow to decide efficiently the LC-equivalence of graphs. In particular, Bouchet showed that a set of solutions 𝒞𝒮 that satisfies both (i) and (ii), is either small or it contains an affine subspace of 𝒮 of small co-dimension. In the latter case, the entire set 𝒮 is actually an affine space except for some particular cases that can be avoided by assuming that the graphs contain vertices of even degree. We extend this result as follows:

Lemma 8.

Given G, G two connected graphs with at least one vertex of even degree, and a set L of linear constraints on V4, then either the set 𝒮L of solutions to both L and (i) is of dimension at most 4, or the set 𝒞L𝒮L that additionally satisfies (ii) is either empty or an affine subspace of 𝒮L of codimension at most 2.

Proof.

It is enough to consider the case dim(𝒮L)>4 and 𝒞L. The set 𝒮 of solutions to (i) contains 𝒮L, so dim(𝒮)>4. According to [1], 𝒞, the solutions to (i) and (ii), is an affine subspace of 𝒮 of codimension at most 2. For any a𝒞L, 𝒞=a+𝒩 where 𝒩 is a subvector space of 𝒮. Notice that 𝒞L=𝒞𝒮L=a+𝒩𝒮L. We have dim(𝒞L)=dim(𝒩𝒮L)=dim(𝒩)+dim(𝒮L)dim(𝒩+𝒮L)dim(𝒩)+dim(𝒮L)dim(𝒮)dim(𝒮L)2 as 𝒩 is of codimension at most 2 in 𝒮.

 Remark 9.

Lemma 8 holds actually for any graph that is not in the so-called “Class α” of graphs with only odd-degree vertices together with a few additional properties333(a) any pair of non adjacent vertices should have an even number of common neighbours ; (b) for any cycle C, the number of triangles having a edge in C is equal to the size of C modulo 2.. When the graphs are in “Class α”, and in the absence of additional constraints, Bouchet proved that there is at most 2 solutions in 𝒞 which do not belong to the affine subspace of small codimension, and these two solutions can be easily computed (see [1], section 7). We leave as an open question the description of the set of solutions for graphs in “Class α”, in particular when the two particular solutions pointed out by Bouchet do not satisfy L, the set of additional constraints.

From an algorithmic point of view, Lemma 8 leads to a straightforward generalisation of Bouchet’s algorithm to efficiently decide LC-equivalence of graphs, under a set of additional linear constraints:

Proposition 10.

Given G, G two connected graphs of order n with an even-degree vertex, and a set L of linear constraints on V4, one can compute a solution to both (i), (ii) and L when it exists, or claim there is no solution, in runtime O((n2+)n2).

Proof.

A Gaussian elimination can be used to compute a basis ={S0,,Sk} of 𝒮L, with k<n, in O((n2+)n2) operations as there are n2 equations in (i). If the dimension of 𝒮L is at most 4 (so |𝒮L|16), we check in O(n) operations, for each element of 𝒮L whether equation (ii) is satisfied. Otherwise, when dim(𝒮L)>4, if 𝒞L is non empty, at least one element of 𝒞L is the sum Si+Sj of two elements of (see Lemma 4.4 in [1]). For each of the O(n2) candidates we check whether condition (ii) is satisfied. If no solution is found, it implies that 𝒞L=.

As the algorithm described in the full version of this paper [12] translates a solution to (i) and (ii), into a sequence of local complementations relating two graphs, some constraints on the sequence of local complementations may be encoded as additional linear constraints. We give a fairly simple example below. A more intricate example is presented in Lemma 21 (in Section 3.3).

Example 11.

Let G, G be two connected graphs of order n with an even-degree vertex, and V0 a set of vertices. One can decide in runtime O(n4) whether there exists a sequence of (possibly repeating) vertices a1,,amV0 such that G=Ga1am. Roughly speaking, the idea is to consider the linear constraint bu=0 (i.e. uB¯) for any uV0, to reflect the constraints that local complementations should not be applied outside of V0.

An interpretation of the possible additional constraints of the extended Bouchet algorithm in terms of local Clifford operators over graph states is given in the full version of this paper [12].

3.2 Minimal local sets and standard form

We consider in this section the first stage of the LU-equivalence algorithm, which consists in putting the two input graphs into a particular shape called standard form by means of local complementations. We adapt a transformation introduced in [13], which is based on the so-called minimal local sets, and turn it into an efficient procedure.

Definition 12.

A local set L is a non-empty subset of V of the form L=DOddG(D) for some DV called a generator. A minimal local set is a local set that is minimal by inclusion.

A key property of local sets is that they are invariant under LU-equivalence: Two LU-equivalent graphs G1, G2 have the same local sets, but not necessarily with the same generators. Moreover, the way the generators of a minimal local set differ in G1 and G2, provides some information on the sequence of generalised local complementations that transforms G1 into G2. It is thus important to cover all vertices of a graph with at least one minimal local set. Fortunately, any graph admits a minimal local set cover (MLS cover for short), and an MLS cover can be computed efficiently, within O(n6.38) operations444The algorithm presented in [11] computes a MLS cover in O(n4) evaluations of the so-called cut-rank function, which itself can be computed in O(nω) field operations where ω<2.38. where n is the order of the graph [11]. The information that an MLS cover provides on each vertex, is reflected by a type X, Y, Z or , defined as follows:

Definition 13.

Given a graph G, a vertex u is of type P {X, Y, Z, } with respect to a MLS cover , where P is

  • X if for any generator D of a minimal local set of containing u, uDOdd(D),

  • Y if for any generator D of a minimal local set of containing u, uDOdd(D),

  • Z if for any generator D of a minimal local of set containing u, uOdd(D)D,

  • otherwise.

When a local complementation is applied on a vertex u, its type remains unchanged if it is X or , while types Y and Z are swapped. For the neighbours of u, types Z and remain unchanged, whereas X and Y are exchanged. This leads to a notion of standard form:

Definition 14.

A graph G is in standard form with respect to a MLS cover if

  • There are no vertices of type Y with respect to ,

  • For every vertex u of type X with respect to , any neighbour v of u is of type Z with respect to and satisfies uv, in particular the vertices of type X with respect to form an independent set,

  • For every vertex u of type X with respect to , {u}NG(u).

 Remark 15.

This notion of standard form is a generalisation of the one introduced in [13], where the MLS cover considered consists of every minimal local set of the graph: max:={LV|L is a minimal local set}. Since there can be exponentially many minimal local sets, using max does not lead to an efficient procedure, for instance when computing the type of each vertex.

Given a pair of LU-equivalent graphs, one can efficiently compute a (common) MLS cover and put both graphs in standard form by means of local complementations:

Lemma 16.

There exists an efficient algorithm that takes as inputs two graphs G1 and G2 of order n, and either claim that they are not LU-equivalent, or compute an MLS cover and two graphs G1 and G2 LC-equivalent to G1 and G2 respectively, such that G1 and G2 are both in standard form with respect to , in runtime O(n6.38).

The algorithm is fairly similar to the one presented in the proof of Proposition 24 in [13] (the main difference being that we may now add minimal local sets to the MLS cover) and can be found in the full version of this paper [12]. Notice the most computationally expensive step of the algorithm is the computation of the MLS cover, hence the runtime O(n6.38). Standard forms with respect to a common MLS cover implies some strong similarities in the structure of graphs:

Lemma 17.

If two graphs G1 and G2 are LU-equivalent and in standard form with respect to an MLS cover , then every vertex has the same type in G1 and G2, and every vertex u of type X satisfies NG1(u)=NG2(u).

Lemma 17 was proved in [13] for the maximal MLS cover max, but the mathematical arguments hold for any arbitrary MLS cover. A key argument is that two LU-equivalent graphs have the same vertices of type with respect to any arbitrary MLS cover.

After performing the algorithm described in Lemma 16, one can check in quadratic time555In the order of the graphs, assuming the information of the types of the vertices with respect to the MLS cover is conserved. whether each vertex has the same type in G1 and G2, and whether every vertex of type X has the same neighbourhood in both graphs. If either condition is not met, the graphs are not LU-equivalent.

Finally, thanks to standard form, deciding LCr-equivalence of graphs reduces to determining whether they are related by a single r-local complementation along with some usual local complementations:

Lemma 18.

If G1 and G2 are LCr-equivalent and are both in standard form with respect to an MLS cover , then G1 and G2 are related by a sequence of local complementations on the vertices of type along with a single r-local complementation over the vertices of type X.

Lemma 18 was proved in [13] for the maximal MLS cover max, but the mathematical arguments hold for any arbitrary MLS cover.

3.3 An algorithm to recognise LCr-equivalent graph states

We are now ready to describe the algorithm that recognises two LCr-equivalent graphs. We consider a level r1, and two graphs G1 and G2 of order n, defined on the same vertex set V. Following Lemma 16, assume, without loss of generality, that G1 and G2 are both in standard form with respect to the same MLS cover. Then, it is valid (see Lemma 17) to define VX,VZV, the sets of vertices respectively of type X and Z with respect to the MLS cover. Also, each vertex in VX has the same neighbourhood in both G1 and G2. According to Lemma 18, if G1 and G2 are LCr-equivalent then there is a single r-local complementation over vertices of VX together with a series of local complementations on vertices of type that transform G1 into G2. We first focus on the single r-local complementation (that commutes with the local complementations on vertices of type , as there is no edge between a vertex of type X and a vertex of type ) and thus consider all the possible graphs that can be reached from G1 by mean of a single r-local complementation over vertices of VX. Notice that such a r-local complementation only toggles edges which both endpoints are in VZ. Given a multiset S, the edges toggled in G1rS can be represented by a vector ω(S)𝔽2{u,vVZ|uv} such that for any u,vVZ, ωu,v(S)=uG1vuG1rSv. The actions of all the possible r-local complementations on G1 can thus be described as the set Ω={ω(S)|S is an r-incident multiset of vertices of type X}.

Lemma 19.

Ω is a vector space and a basis of Ω can be computed in runtime O(rnr+2.38).

Proof.

A multiset S of vertices of type X can be represented as a vector in (/2r)VX which entries are S(u)mod2r, as the multiplicity can be considered modulo 2r in the context of a r-local complementation. Let Σ be the subset of (/2r)VX which corresponds to all r-incident independent multisets of vertices in VX. Σ is a vector space since the property of r-incidence is preserved under the addition of two vectors. Σ is actually the space of solutions to a set of O(nr+1) equations666There are precisely (|VZ|r+1)+(|VZ|r)++(|VZ|3)+(|VZ|2) equations. given by the conditions of r-incidence. With some multiplications by powers of 2, all these equations are expressible as equations modulo 2r. For every set KVZ of size between 2 and r+1, the corresponding equation is

uΛG1K2|K|2+δ(|K|2)S(u)=0mod2r

Notice that if r=1, the space of solutions is the entire space (/2r)VX, as there are no incidence constraints on usual local complementations. Summing up, to compute a basis of Σ, we solve a system of O(nr+1) equations modulo 2r with O(n) variables. One can obtain a generating set {S1,S2,,St} of Σ of size tn in O(rnr+2.38) basic operations using an algorithm based on the Howell transform [34].

Let f be the function that associates with each element SΣ, its action f(S)Ω on the edges: for any u,vVZ, f(S)u,v=uG1vuG1rSv. Notice that f is linear, as for any S,SΣ:

f(S+S) =uG1vuG1r(S+S)v=uG1vu(G1rS)rSv
=uG1vuG1rSv(SΛG1rSu,v=2r1mod2r)
=uG1vuG1rSv(SΛG1u,v=2r1mod2r)
=uG1rSvuG1rSv
=uG1vuG1rSvuG1vuG1rSv=f(S)+f(S)

This directly implies that Ω is a vector space: if ω,ωΩ, by definition there exists S,SΣ such that f(S)=ω and f(S)=ω, moreover ω+ω=f(S)+f(S)=f(S+S)Ω. Also, let us prove that Ω is generated by {f(S1),f(S2),,f(St)}. Take a vector ω~Ω, by definition there exists S~Σ such that ω~=f(S~). S~ can be expressed as a linear combination of vectors from the generating set, i.e. S~=i[1,t]aiSi where ai/2r. Then, for any u,vVZ, (ω~)u,v=f(i[1,t]aiSi)u,v=i[1,t]aif(Si)u,v by linearity of f, where ai𝔽2 such that ai=aimod2 when ai and ai are viewed as integers. In other words, w~=i[1,t]aif(Si), implying that {f(S1),f(S2),,f(St)} is a generating set of Ω. Using Gaussian elimination, one can easily obtain a basis of Ω from {f(S1),f(S2),,f(St)}.

Thanks to the exhaustive description of all possible r-local complementations on G1, we are now ready to reduce LCr-equivalence to LC-equivalence with some additional constraint. We denote by G1# (resp. G2#) the graph obtained from G1 (resp. G2) by the following procedure. First, remove the vertices of VX. Then, for each vector ω, for each u,vVZ such that ωu,v=1, add a vertex connected only to u and v and call it pu,vω, and let 𝒫ω={pu,vω|ωu,v=1}. In the following, we refer to the vertices added by this procedure as “new vertices”.

Lemma 20.

G1 and G2 are LCr-equivalent if and only if there exists a sequence of (possibly repeating) vertices a1,,am such that G2#=G1#a1am satisfying the following additional constraints:

  • the sequence contains no vertex of VZ;

  • for each ω, either the sequence contains every vertex of 𝒫ω exactly once, or it contains none.

The proof of Lemma 20 makes use of Lemma 18 and is given in the full version of this paper [12].

There exists an efficient algorithm that decides whether two graphs are LC-equivalent with such additional constraints using our generalisation of Bouchet’s algorithm.

Lemma 21.

Deciding whether there exists a sequence of (possibly repeating) vertices a1,,am such that G2#=G1#a1am, satisfying the additional constraints described in Lemma 20, can be done in runtime O(n4).

Proof.

If the vector space Ω is of dimension zero (i.e. Ω only contains the null vector), then there is no additional constraint, thus one can apply the usual Bouchet algorithm that decides LC-equivalence of graphs.

If Ω is not of dimension zero, then G1# and G2# both have at least one even-degree vertex (since every “new vertex” is of degree 2). Using the notations of Section 3.1, let us define the following linear constraints on V4: uVZ, ω, v,v𝒫ω,

  • uB¯;

  • vC¯;

  • vB if and only if vB.

According to Proposition 10, a solution to the system of equations composed of (i), (ii) (see Proposition 7) and the additional linear constraints can be computed in runtime O(n4) when it exists. Following the algorithm in the full version of this paper [12], such a solution yields a sequence of local complementations satisfying the additional constraints described in Lemma 20. Conversely, such a sequence of local complementations can be converted into a valid solution to the system of equations.

Summing up, we have an algorithm that decides, for a fixed level r, the LCr-equivalence of graphs in polynomial runtime.

Theorem 22.

There exists an algorithm that decides if two graphs are LCr-equivalent with runtime O(rnr+2.38+n6,38), where n is the order of the graphs.

The algorithm reads as follows:

  1. 1.

    Put G1 and G2 in standard form with respect to the same MLS cover if possible, otherwise output NO.

  2. 2.

    Check whether each vertex has the same type in G1 and G2, and whether every vertex of type X has the same neighbourhood in both graphs, otherwise output NO.

  3. 3.

    Compute a basis of the vector space Ω.

  4. 4.

    Compute the graphs G1# and G2#.

  5. 5.

    Decide whether G1# and G2# are LC-equivalent with the additional constraints described in Lemma 20. Output YES if this is the case, NO otherwise.

Notice that the algorithm is exponential in r, in particular it does not provide an efficient algorithm to decide LU-equivalence of graph states. To address this issue, we provide in the next subsection some upper bounds on the level of a generalised local complementation.

3.4 Bounds for generalised local complementation

In this section, we prove an upper bound on the level of a valid generalised local complementation: roughly speaking we show that if GrS is valid then r is at most logarithmic in the order of the graph G. This bound is however not true in general as it has been shown in [13] that whenever GrS is valid, we have GrS=Gr+1(S+S). To avoid these pathological cases, we thus focus on genuine r-incident independent multisets:

Definition 23.

Given a graph G, a r-incident independent multiset S is genuine if there exists a set KVsupp(S) such that |K|>1 and NG(u)=KS(u) is odd777With a slight abuse of notation, NG(u)=KS(u) is the sum over all uV s.t. NG(u)=K..

Proposition 24.

If GrS is valid and there is no S such that Gr1S=GrS then S is a genuine r-incident independent multiset.

Proof.

By contradiction assume S is an r-incident independent multiset which is not genuine. Let S be the multiset obtained from S by choosing, for every set KVsupp(S) s.t. {usupp(S)|NG(u)=K} is not empty, a single vertex usupp(S) s.t. NG(u)=K, and setting S(u)=NG(u)=KS(u) and for any other vertex vsupp(S) s.t. NG(v)=K, S(v)=0. It is direct to show that S is r-incident and that GrS=GrS. Then, let S/2 be the multiset obtained from S by dividing by 2 the multiplicity of each vertex in supp(S). It is direct to show that S is (r1)-incident and that GrS=Gr1S/2.

Genuine r-incidence can only occur for multisets whose support is of size at least exponential in r.

Lemma 25.

If r>1 and S is a genuine r-incident independent multiset of a graph G, then |supp(S)|2r+2r3.

Proof.

Let m>1 be the smallest integer such that there exists a set K0Vsupp(S) of size m such that SΛGK0 is odd. Note that by hypothesis there exists such an integer. Indeed, let Kmax be the biggest subset (by inclusion) of Vsupp(S) such that NG(u)=KmaxS(u) is odd: then SΛGKmax is odd. Thus, by definition of the r-incidence, mr+2.

Let G=G[supp(S)K0] the graph obtained from G by removing the vertices that are neither in the support of S, nor in K0. By definition, S is also r-incident in G. Also, SΛGK0 is odd, and for every set KK0 s.t. |K|>1, SΛGK is even.

Let us prove that for any KK0 s.t. |K|>1, NG(u)=KS(u) is odd, by induction over the size of K. First notice that NG(u)=K0S(u)=SΛGK0 is odd. Then, let K1K0 s.t. |K1|>1.

SΛGK1=K1KK0NG(u)=KS(u)=NG(u)=K1S(u)+K1KK0NG(u)=KS(u)
=NG(u)=K1S(u)+|{KK0|K1K}|mod2 by hypothesis of induction
=NG(u)=K1S(u)+1mod2

Thus, NG(u)=K1S(u) is odd. As a consequence, for any KK0 s.t. |K|>1, there exists at least one vertex usupp(S) s.t. NG(u)=K. Then, |supp(S)||{KK0||K|>1}|=2mm12r+2(r+2)1=2r+2r3.

Likewise, r-local complementations that cannot be implemented by (r1)-local complementations can only occur or multisets with sufficiently many vertices outside their support.

Lemma 26.

If GrS is valid and there is no S such that Gr1S=GrS, then |Vsupp(S)|r+3.

The proof of Lemma 26 involves similar techniques as the proof of Lemma 25 and is given in the full version of this paper [12]. Lemmas 25 and 26 together give a simple bound involving only the order of the graph.

Proposition 27.

If GrS is valid and there is no S such that Gr1S=GrS, then n2r+2, where n is the order of G.

Put differently, any r-local complementation on a graph of order at most 2r+21 can be implemented by (r1)-local complementations:

Corollary 28.

If two graphs of order at most 2r+21 are LCr-equivalent, then they are LCr-1-equivalent.

In other words, two LCr-equivalent but not LCr-1-equivalent graphs are of order at least 2r+2. This implies the following strengthening of Theorem 5.

Corollary 29.

If two graphs of order at most 2r+31 are LU-equivalent, they are LCr-equivalent.

Proof.

Suppose that G1 and G2 of order n2r+31 are LU-equivalent. According to Theorem 5, G1 and G2 are LC⌊n/2⌋-1-equivalent. If n/21r then G1 and G2 are trivially LCr-equivalent. Otherwise, according to Corollary 28, G1 and G2 are LCr-equivalent by direct induction.

Corollary 29 provides a logarithmic bound on the level of generalised local complementations to consider for LU-equivalence: if two graphs of order n>7 are LU-equivalent then they are LClog2(n+18)-equivalent. This bound leads to a quasi-polynomial time algorithm for LU-equivalence, as described in the next section. Notice that in Section 4, we elaborate on the consequences of Corollary 29 on the minimal order of graphs that are LU- but not LC-equivalent.

3.5 An algorithm to recognise LU-equivalent graph states

According to Theorem 22, we have an algorithm that recognises two LCr-equivalent graphs of order n in runtime O(rnr+2.38+n6,38). According to Corollary 29, G1 and G2 are LU-equivalent if and only if they are LCr-equivalent, where r=log2(n)+O(1). Thus, our algorithm that decides LCr-equivalence translates directly to an algorithm that decides LU-equivalence.

Theorem 30.

There exists an algorithm that decides if two graphs are LU-equivalent with runtime nlog2(n)+O(1), where n is the order of the graphs.

In comparison, Burchardt et al. algorithm for LU-equivalence [6] has two sources of exponential time complexity. The logarithmic upper bound on the level of generalised local complementation we introduce may mitigate one of these sources (making one parameter of the complexity quasi-polynomial), but does not affect a priori the second one, which is roughly speaking the number of connected components of an intersection graph related to the MLS cover.

4 LU- and LC-equivalence coincide for graph states up to 19 qubits

It is known that there exists a pair of 27-vertex graphs that are not LC-equivalent, but LU-equivalent, more precisely they are LC2-equivalent [23, 35]. It is still an open question whether this is a minimal example (in number of vertices). In other words, does a pair of graphs that are LU-equivalent but not LC-equivalent on 26 vertices or less exist? In theory, one could check every pair of graphs of order up to 26, but the rapid combinatorial explosion in the number of graphs as the number of vertices increases, makes it unfeasible in practice.

The best bound known so far888In [6] it is proved that the number of LU- and LC-orbits of unlabelled graphs of order up to 11 is the same. is that for graphs of order up to 8, LU=LC i.e. LU- and LC-equivalence coincide [7]. The results of Section 3.4 (see Corollary 29) already imply a substantial improvement on this bound: LU=LC for graphs of order up to 15. Furthermore, for graphs of order up to 31, LU=LC2, i.e. if two graphs of order up to 31 are LU-equivalent, they are LC2-equivalent. Thus, asking whether LU=LC holds for graphs of order up to 26 is equivalent to asking whether LC2=LC holds for graphs of order up to 26. One direction is to study when a 2-local complementation on an multiset S can be implemented using only usual local complementations over vertices in the support of S. If this were to be the case for every graph of order up to 26, it would show that the 27-vertex counterexample is minimal in number of vertices. In the following we study the structure of 2-local complementation to prove that LU=LC holds for graph of order up to 19.

According to Lemma 26, if there are at most 4 vertices outside the support of some 2-incident independent multiset S, then a 2-local complementation on S can be implemented by usual local complementations. In the peculiar case of 2-local complementation, we are able to use computer-assisted generation (see Appendix A) to extend the result. The code is available at [10].

Lemma 31.

Let S be a 2-incident independent multiset of a graph G. If |Vsupp(S)|5, or if |Vsupp(S)|=6 and |supp(S)|20, then a 2-local complementation on S can be implemented by local complementations over a subset of supp(S).

Likewise, according to Lemma 25 and Proposition 24, if the support of some 2-incident independent multiset S is of size at most 10, then a 2-local complementation on S can be implemented by usual local complementations. To extend this result to 2-incident independent multisets whose supports is of size at most 12, we first study the case of twin-less sets (two distinct non-connected vertices u and v are twins if NG(u)=NG(v)).

Lemma 32.

Let S be a 2-incident independent set of a graph G such that S does not contain any twins and |S|12. Then, G2S=G.

The proof of Lemma 32 is an induction over the number of vertices connected to S and is given in the full version of this paper [12].

According to Proposition 4, any 2-local complementation can be decomposed into 1- and 2-local complementations over sets. Furthermore, one can check that if an 2-incident independent set S contains two twins u and v, then a 2-local complementation over S has the same effect as a 2-local complementation over S{u,v} followed by a local complementation over u. Thus, the action of a 2-local complementation can be described by a 2-local complementation over a twin-less set followed by usual local complementations. Then, Lemma 32 can be applied on the twin-less set to yield the following result:

Lemma 33.

Let S be a 2-incident independent multiset of a graph G such that |supp(S)|12. Then, a 2-local complementation over S can be implemented by local complementations over a subset of supp(S).

According to Lemma 31 and Lemma 33, if a 2-incident independent multiset S satisfies |supp(S)|12 or |Vsupp(S)|5, or alternatively if |supp(S)|20 and |Vsupp(S)|=6, then a 2-local complementation over S can be implemented by usual local complementations. Thus, for graphs of order up to 19, any 2-local complementation can be implemented by usual local complementations, implying LU=LC. In other words, a 2-local complementation that cannot be implemented by usual local complementation is possible only on a graph of order at least 20. We summarise our findings in the following proposition:

Proposition 34.

LU- and LC-equivalence coincide for graph states up to 19 qubits.

5 Conclusion

In this paper, we have introduced a quasi-polynomial runtime algorithm to recognise the LU-equivalence of graph states – and more generally stabilizer states – based on a recent generalisation of local complementation that captures the LU-equivalence of graph states. A key component of our approach is a new, nontrivial logarithmic bound on the level of the generalised local complementation.

We have also extended the well-known Bouchet algorithm to recognise the LC-equivalence of graph states, by allowing the addition of arbitrary linear constraints. This extension enables finer control over local complementations (or local Clifford operators) in the LC-equivalence problem, and we believe it will have broader applications.

We have also made significant progress in understanding the structure of quantum entanglement by demonstrating that LC-equivalence and LU-equivalence coincide for graph states with up to 19 qubits, extending the previously known bound of 8 qubits. The smallest known example of a pair of graph states that are LU- but not LC-equivalent consists of 27 qubits. A natural next step is to determine whether LU- and LC-equivalence continue to coincide for graph states up to 26 qubits or, alternatively, to find a counterexample in the range of 20 to 26 qubits. As shown in this work, leveraging generalised local complementation should facilitate this exploration.

References

  • [1] André Bouchet. An efficient algorithm to recognize locally equivalent graphs. Combinatorica, 11(4):315–329, December 1991. doi:10.1007/BF01275668.
  • [2] André Bouchet. Isotropic systems. European Journal of Combinatorics, 8(3):231–244, 1987. doi:10.1016/S0195-6698(87)80027-6.
  • [3] Sergey Bravyi and Jeongwan Haah. Magic-state distillation with low overhead. Physical Review A—Atomic, Molecular, and Optical Physics, 86(5):052329, 2012. doi:10.1103/PhysRevA.86.052329.
  • [4] Sergey Bravyi, Yash Sharma, Mario Szegedy, and Ronald de Wolf. Generating k epr-pairs from an n-party resource state. Quantum, 8:1348, 2024. doi:10.22331/q-2024-05-14-1348.
  • [5] Hans J. Briegel, David E. Browne, Wolfgang Dür, Robert Raussendorf, and Maarten Van den Nest. Measurement-based quantum computation. Nature Physics, 5(1):19–26, 2009. doi:10.1038/nphys1157.
  • [6] Adam Burchardt, Jarn de Jong, and Lina Vandré. Algorithm to verify local equivalence of stabilizer states, 2024. arXiv:2410.03961.
  • [7] Adán Cabello, Antonio J. López-Tarrida, Pilar Moreno, and José R. Portillo. Entanglement in eight-qubit graph states. Physics Letters A, 373(26):2219–2225, 2009. doi:10.1016/j.physleta.2009.04.055.
  • [8] Maxime Cautrès, Nathan Claudet, Mehdi Mhalla, Simon Perdrix, Valentin Savin, and Stéphan Thomassé. Vertex-minor universal graphs for generating entangled quantum subsystems. In Proceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024), 2024. doi:10.4230/LIPIcs.ICALP.2024.36.
  • [9] Nathan Claudet. LU-equals-LC-up-to-19qubits. Software, swhId: swh:1:dir:9a2dae69bfe44d00e0a28d0b426596c4a56dc9c5 (visited on 2025-05-09). URL: https://github.com/nathanclaudet/LU-equals-LC-up-to-19qubits, doi:10.4230/artifacts.23042.
  • [10] Nathan Claudet. LU=LC up to 19 qubits, 2024. URL: https://github.com/nathanclaudet/LU-equals-LC-up-to-19qubits.
  • [11] Nathan Claudet and Simon Perdrix. Covering a graph with minimal local sets. In Proceedings of the 24th workshop on Graph Theory (WG 2024), 2024. doi:10.1007/978-3-031-75409-8_10.
  • [12] Nathan Claudet and Simon Perdrix. Deciding local unitary equivalence of graph states in quasi-polynomial time. (long version with proofs), 2025. doi:10.48550/arXiv.2502.06566.
  • [13] Nathan Claudet and Simon Perdrix. Local equivalence of stabilizer states: a graphical characterisation. In Proceedings of the 42nd Symposium on Theoretical Aspects of Computer Science (STACS 2025), 2025. doi:10.4230/LIPIcs.STACS.2025.27.
  • [14] Andrew Cross, Graeme Smith, John A. Smolin, and Bei Zeng. Codeword stabilized quantum codes. In 2008 IEEE International Symposium on Information Theory, pages 364–368. IEEE, 2008. doi:10.1109/TIT.2008.2008136.
  • [15] Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor. Efficient algorithm to recognize the local Clifford equivalence of graph states. Phys. Rev. A, 70:034302, September 2004. doi:10.1103/PhysRevA.70.034302.
  • [16] Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor. Graphical description of the action of local Clifford transformations on graph states. Physical Review A, 69(2), February 2004. doi:10.1103/physreva.69.022316.
  • [17] Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor. Local unitary versus local Clifford equivalence of stabilizer states. Physical Review A, 71(6), June 2005. doi:10.1103/physreva.71.062323.
  • [18] Sylvain Gravier, Jérôme Javelle, Mehdi Mhalla, and Simon Perdrix. Quantum secret sharing with graph states. In Proceedings of the 8th Mathematical and Engineering Methods in Computer Science International Doctoral Workshop (MEMICS 2012), 2013. doi:10.1007/978-3-642-36046-6_3.
  • [19] Frederik Hahn, Anna Pappa, and Jens Eisert. Quantum network routing and local complementation. npj Quantum Information, 5(1):1–7, 2019. doi:10.1038/s41534-019-0191-6.
  • [20] Mayan Hein, Wolfgang Dür, Jens Eisert, Robert Raussendorf, Maarten Van den Nest, and Hans J. Briegel. Entanglement in graph states and its applications. Quantum computers, algorithms and chaos, 162, March 2006. doi:10.3254/978-1-61499-018-5-115.
  • [21] Mayan Hein, Jens Eisert, and Hans J. Briegel. Multiparty entanglement in graph states. Physical Review A, 69(6), June 2004. doi:10.1103/physreva.69.062311.
  • [22] Peter Høyer, Mehdi Mhalla, and Simon Perdrix. Resources required for preparing graph states. In 17th International Symposium on Algorithms and Computation (ISAAC 2006), volume 4288 of Lecture Notes in Computer Science, pages 638–649, December 2006. doi:10.1007/11940128_64.
  • [23] Zhengfeng Ji, Jianxin Chen, Zhaohui Wei, and Mingsheng Ying. The LU-LC conjecture is false, 2007. arXiv:0709.1266.
  • [24] Anton Kotzig. Eulerian lines in finite 4-valent graphs and their transformations. Colloqium on Graph Theory Tihany 1966, pages 219–230, 1968.
  • [25] Damian Markham and Barry C. Sanders. Graph states for quantum secret sharing. Physical Review A, 78(4):042309, 2008. doi:10.1103/PhysRevA.78.042309.
  • [26] Clément Meignant, Damian Markham, and Frédéric Grosshans. Distributing graph states over arbitrary quantum networks. Physical Review A, 100:052333, November 2019. doi:10.1103/PhysRevA.100.052333.
  • [27] Sepehr Nezami and Jeongwan Haah. Classification of small triorthogonal codes. Phys. Rev. A, 106:012437, July 2022. doi:10.1103/PhysRevA.106.012437.
  • [28] Robert Raussendorf and Hans J. Briegel. A one-way quantum computer. Physical review letters, 86(22):5188, 2001. doi:10.1103/PhysRevLett.86.5188.
  • [29] Robert Raussendorf, Daniel E. Browne, and Hans J. Briegel. Measurement-based quantum computation on cluster states. Physical review A, 68(2):022312, 2003. doi:10.1103/PhysRevA.68.022312.
  • [30] Pradeep Sarvepalli and Robert Raussendorf. Local equivalence of surface code states. In Proceedings of the 5th Conference on the Theory of Quantum Computation, Communication, and Cryptography (TQC 2010), 2011. doi:10.1007/978-3-642-18073-6_5.
  • [31] Dirk Schlingemann. Stabilizer codes can be realized as graph codes, 2001. arXiv:quant-ph/0111080.
  • [32] Dirk Schlingemann and Reinhard F. Werner. Quantum error-correcting codes associated with graphs. Physical Review A, 65(1):012308, 2001. doi:10.1103/PhysRevA.65.012308.
  • [33] Minjia Shi, Haodong Lu, Jon-Lark Kim, and Patrick Solé. Triorthogonal codes and self-dual codes. Quantum Information Processing, 23(7):280, July 2024. doi:10.1007/s11128-024-04485-9.
  • [34] Arne Storjohann. Algorithms for matrix canonical forms. PhD thesis, ETH Zurich, 2000. URL: https://cs.uwaterloo.ca/˜astorjoh/diss2up.pdf.
  • [35] Nikoloz Tsimakuridze and Otfried Gühne. Graph states and local unitary transformations beyond local Clifford operations. Journal of Physics A: Mathematical and Theoretical, 50(19):195302, April 2017. doi:10.1088/1751-8121/aa67cd.
  • [36] Ilan Tzitrin. Local equivalence of complete bipartite and repeater graph states. Physical Review A, 98(3):032305, 2018. doi:10.1103/PhysRevA.98.032305.
  • [37] Bei Zeng, Hyeyoun Chung, Andrew W. Cross, and Isaac L. Chuang. Local unitary versus local Clifford equivalence of stabilizer and graph states. Physical Review A, 75(3), March 2007. doi:10.1103/physreva.75.032325.

Appendix A Computer-assisted study of 2-local complementation

We use the following lemma to drastically decrease the size of the space to explore when studying 2-local complementation.

Lemma 35.

Let S be a 2-incident independent multiset of a graph G=(V,E) and suppose that there exists no set Asupp(S) such that G2S=G1A. Then there exists a graph G=(V,E) bipartite with respect to a bipartition S,VS of the vertices such that:

  • S is 2-incident;

  • S contains no twins;

  • S contains no vertex of degree 0 or 1;

  • |S||supp(S)|;

  • |VS||Vsupp(S)|;

  • there exists no set AS such that G2S=G1A.

Proof.

The proof is constructive, in the sense that we construct G and S from G and S. According to Proposition 4, there exists set S1,S2supp(S) such that S2 is 2-incident and G2S=G2S21S1. Also, the existence of a set AS2 such that G2S2=G1A implies G2S=G1(AΔS1). Let G=G and S=S2, then apply the following operations:

  1. 1.

    Remove the edges between vertices of VS;

  2. 2.

    Remove each vertex of S of degree 0 or 1;

  3. 3.

    If there exists a pair of twins u,v in S, remove u and v. Repeat until S contains no twins.

Notice that each operation preserves the 2-incidence of S and that G2S=G1A for no set AS.

Given an integer k, let 𝒢k be the class of graphs that are bipartite with respect to a bipartition S,VS of the vertices such that:

  • S is 2-incident;

  • S contains no twins;

  • S contains no vertex of degree 0 or 1;

  • |VS|=k.

It is easy to generate each graph of 𝒢k, although the number of elements in 𝒢k grows double exponentially fast with k. S can be defined as a list of words in {0,1}k of weight at least 2. More precisely each vertex of S is uniquely associated with a set of VS of size at least 2, its neighbourhood. Furthermore, the 2-incidence of S implies that S is uniquely determined by the set of its vertices of degree at least 4. Indeed, starting from a set containing only vertices of degree at least 4, the conditions of the form “SΛGK=0mod2rkδ(k)” translate into a procedure to find which vertices of degree 3 then 2 need to be added to the set so that S is 2-incident. This proves that there is a bijection between 𝒢k and lists of words in {0,1}k of weight at least 4. Thus, the size of 𝒢k is exactly given by the formula

|𝒢k|=2(k4)+(k5)++(kk)

For k=1,2,3,4,5 and 6, the size of 𝒢k is respectively 1,1,1,2,26=64, and 2224×106 which is suitable for computation. But, even for k as low as seven, the size of 𝒢7 is 2642×1019.

For every k from 1 to 6, we generate each graph G of 𝒢k, along with the set S defined above. Notice that a local complementation over a vertex u of S toggles the connectivity of some pairs of vertices of VS, here the pairs where each end is a neighbour of u. In other words, to each vertex u of S we associate a vector in 𝔽2(k2) corresponding to the action of the local complementation of u on the graph. The set of the vectors corresponding to each vertex of S spans a 𝔽2-vector space describing the action of local complementation over vertices of S on the graph. Using Gaussian elimination, we are able to compute a basis of . Furthermore, we compute the vector x in 𝔽2(k2) corresponding to the action of a 2-local complementation over S on the graph. Checking if the action of a 2-local complementation over S can be implemented by local complementations on vertices of S amounts to checking if x belongs to the vector space , which can be done efficiently using Gaussian elimination.

For k[1,3], the set S corresponding to the only graph G𝒢k is empty, hence a 2-local complementation over S leaves G invariant, i.e. G2S=G. For k=4, S is either empty of contains 11 vertices; in both case it is easy to check that G2S=G. For k=5, the computation shows that for each graph G𝒢5, G2S=G. Now, fix k=6. For each graph G𝒢6 such that the corresponding set S contains at most 16 vertices, G2S=G. For each graph G𝒢6 such that the corresponding set S contains at most 20 vertices, a 2-local complementation over the corresponding set S can be implemented by local complementations over vertices of S, i.e. there exists a set AS such that G2S=G1A. The property does not hold if S is of size 21, for instance we recover the well-known 27-vertex counterexample to the LU=LC conjecture described in [35].

According to Lemma 35, this is enough to prove Lemma 31:

See 31