Deciding Local Unitary Equivalence of Graph States in Quasi-Polynomial Time
Abstract
We describe an algorithm with quasi-polynomial runtime 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 complementationCategory:
Track A: Algorithms, Complexity and GamesCopyright and License:
![[Uncaptioned image]](x1.png)
2012 ACM Subject Classification:
Theory of computation Quantum information theory ; Mathematics of computing Graph algorithmsSupplementary Material:
Software (Script): https://github.com/nathanclaudet/LU-equals-LC-up-to-19qubits [9]archived at

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 PuppisSeries and Publisher:

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 that transforms one state into the other, where each 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 operations, where 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 of the graphs, leading to a linear system of size at most . This results in an overall algorithm whose time-complexity is quasi-polynomial in . 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 , we use the notation when the vertices and are connected in , i.e. . is the neighbourhood of , is the odd-neighbourhood of the set of vertices, and is the common neighbourhood of . We assume totally ordered by a relation . A local complementation with respect to a given vertex consists in complementing the subgraph induced by the neighbourhood of , leading to the graph where denotes the symmetric difference on edges and is the complete graph on the vertices of . With a slight abuse of notation we identify multisets of vertices with their multiplicity function (hence we also identify sets of vertices with their indicator functions ). We consider sums of multisets: for any vertex , . The support of a multiset of vertices denotes the set of vertices such that . is said independent if no two vertices of are connected. For any multiset and set , is the number of vertices of , counted with their multiplicity, that are neighbours to all vertices of ; in other words, is the number of common neighbours of in ( is the scalar product: , so ).
To any simple undirected graph , is associated a quantum state , called graph state, defined as
where is the order of and denotes the number of edges in the subgraph of induced by .111With a slight abuse of notation, denotes the subset of vertices , where s.t. . is unique as 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 , and Z- and X-rotations that are respectively defined as follows:
where and . Any 1-qubit unitary can be decomposed into and rotations, whereas 1-qubit Clifford operators are those generated by and . Local complementation (denoted by the operator ) can be implemented by local Clifford operators:
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 and ) transforming the corresponding graph states into each other.
Graph states form a subfamily of the well-known stabilizer states, indeed is the fix point of for any . 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 and a positive number 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 . Roughly speaking an -local complementation toggles an edge if the number of common vertices in is an odd multiple of (an example of -local complementation is given in Figure 1). To be a valid -local complementation, the (multi)set on which the transformation is applied should be -incident, i.e. the number of common neighbours in of any set of at most vertices should be an appropriate power of two:
Definition 1 (-Incidence).
Given a graph , a multiset of vertices is -incident, if for any , and any of size , their number of common neighbours in is a multiple of , where is the Kronecker delta222 and . .
Definition 2 (-Local Complementation).
Given a graph and an -incident independent multiset , let be the graph defined as
Below we recall some basic properties of generalised local complementation.
Proposition 3.
[13]
-
Generalised local complementations are self inverse: if is valid, then .
-
The multiplicity in can be upperbounded by : if is valid, then , where, for any vertex , .
-
If and are valid and is independent in , then .
-
If is valid then is valid and induces the same transformation: .
-
If is valid then is valid (when ) and .
2.2 1- and 2-local complementation
To illustrate how -local complementation behaves, we consider the simple cases and . First, any multiset is -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 -local complementations over sets, rather than multisets (see Figure 1):
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 , we assume without loss of generality that multiplicities are defined modulo . Let be the set of vertices that have multiplicity or in . Notice that as is an independent set, is 1-incident and generalised local complementations are self inverse. So , where the multiplicity in is either or modulo . Thus the -local complementation over the multiset can be decomposed into 2- and 1-local complementations over sets and respectively.
2.3 LU-equivalence and generalised local complementation
While local complementation can be implemented on graph states by means of local Clifford unitaries, -local complementations can be implemented on graph states with local unitaries generated by and :
Conversely, if two graph states are related by local unitaries generated by and , the corresponding graphs are related by -local complementations [13]. In other words two graphs are LCr-equivalent if and only if there is a series of -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 and are LU-equivalent, then and are LC⌊n/2⌋-1 equivalent, where is the order of the graphs, i.e. there exists a sequence of -local complementations transforming into .
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 and are LCr-equivalent, then and are related by a sequence of generalised local complementations, such that a single one is of level , all the others are usual local complementations (i.e. level ).
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 . Since LU-equivalent graphs are necessarily LCr-equivalent for some , the difference lies in whether the level is fixed or not.
Thanks to Proposition 6, if is LCr-equivalent to , there exists a single -local complementation, together with usual local complementations, that transforms into . We introduce an algorithm that builds such a sequence of generalised local complementations, in essentially four stages:
-
(i)
Both and are turned in standard forms and by means of (usual) local complementations. These transformations are driven by a so-called minimal local set cover which can be efficiently computed.
-
(ii)
We then focus on the single -local complementation: all the possible actions of a single -local complementation on are described as a vector space, for which we compute a basis .
-
(iii)
It remains to find, if it exists, the -local complementation to apply on that leads to up to some additional usual local complementations. With an appropriate construction depending on , 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.
-
(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 , and can be performed in polynomial time in the order of the graphs. Stage has essentially a time complexity, thus deciding LCr-equivalence for a fixed can be done in polynomial time. Regarding LU-equivalence, Theorem 5 implies . We improve this upperbound and show that is at most logarithmic in , 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 , reduces to the existence of subsets of vertices satisfying the following two equations:
Proposition 7.
[1] Two graphs , are LC-equivalent if and only if there exist such that
-
(i)
,
-
(ii)
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 is actually a linear equation: the set of solutions to is a vector space, indeed given two solutions and of , so is . The linearity of equation can be emphasised using the following encoding:
A set can be represented by binary variables s.t. , moreover, with a slight abuse of notations, we identify any set with the corresponding diagonal matrix of dimension in which diagonal elements are the . Following [15, 20], equation is equivalent to
(1) |
and equation to
(2) |
where and are the adjacency matrices of and respectively.
In this section, we consider an extension of Bouchet’s algorithm where an additional set of linear constraints on and 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 of vertices (see Example 11).
While solving linear equations is easy, equation 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 and that allow to decide efficiently the LC-equivalence of graphs. In particular, Bouchet showed that a set of solutions that satisfies both and , 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 , two connected graphs with at least one vertex of even degree, and a set of linear constraints on , then either the set of solutions to both and is of dimension at most , or the set that additionally satisfies is either empty or an affine subspace of of codimension at most .
Proof.
It is enough to consider the case and . The set of solutions to contains , so . According to [1], , the solutions to and , is an affine subspace of of codimension at most . For any , where is a subvector space of . Notice that . We have as is of codimension at most 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 , the number of triangles having a edge in is equal to the size of modulo .. When the graphs are in “Class ”, and in the absence of additional constraints, Bouchet proved that there is at most 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 , 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 , two connected graphs of order with an even-degree vertex, and a set of linear constraints on , one can compute a solution to both , and when it exists, or claim there is no solution, in runtime .
Proof.
A Gaussian elimination can be used to compute a basis of , with , in operations as there are equations in . If the dimension of is at most (so ), we check in operations, for each element of whether equation is satisfied. Otherwise, when , if is non empty, at least one element of is the sum of two elements of (see Lemma 4.4 in [1]). For each of the candidates we check whether condition is satisfied. If no solution is found, it implies that .
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 , be two connected graphs of order with an even-degree vertex, and a set of vertices. One can decide in runtime whether there exists a sequence of (possibly repeating) vertices such that . Roughly speaking, the idea is to consider the linear constraint (i.e. ) for any , to reflect the constraints that local complementations should not be applied outside of .
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 is a non-empty subset of of the form for some 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 , have the same local sets, but not necessarily with the same generators. Moreover, the way the generators of a minimal local set differ in and , provides some information on the sequence of generalised local complementations that transforms into . 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 operations444The algorithm presented in [11] computes a MLS cover in evaluations of the so-called cut-rank function, which itself can be computed in field operations where . where 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 , a vertex is of type P {X, Y, Z, } with respect to a MLS cover , where P is
-
X if for any generator of a minimal local set of containing , ,
-
Y if for any generator of a minimal local set of containing , ,
-
Z if for any generator of a minimal local of set containing , ,
-
otherwise.
When a local complementation is applied on a vertex , its type remains unchanged if it is X or , while types Y and Z are swapped. For the neighbours of , types Z and remain unchanged, whereas X and Y are exchanged. This leads to a notion of standard form:
Definition 14.
A graph is in standard form with respect to a MLS cover if
-
There are no vertices of type Y with respect to ,
-
For every vertex of type X with respect to , any neighbour of is of type Z with respect to and satisfies , in particular the vertices of type X with respect to form an independent set,
-
For every vertex of type X with respect to , .
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: . Since there can be exponentially many minimal local sets, using 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 and of order , and either claim that they are not LU-equivalent, or compute an MLS cover and two graphs and LC-equivalent to and respectively, such that and are both in standard form with respect to , in runtime .
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 . Standard forms with respect to a common MLS cover implies some strong similarities in the structure of graphs:
Lemma 17.
If two graphs and are LU-equivalent and in standard form with respect to an MLS cover , then every vertex has the same type in and , and every vertex of type satisfies .
Lemma 17 was proved in [13] for the maximal MLS cover , 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 and , 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 -local complementation along with some usual local complementations:
Lemma 18.
If and are LCr-equivalent and are both in standard form with respect to an MLS cover , then and are related by a sequence of local complementations on the vertices of type along with a single -local complementation over the vertices of type X.
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 , and two graphs and of order , defined on the same vertex set . Following Lemma 16, assume, without loss of generality, that and are both in standard form with respect to the same MLS cover. Then, it is valid (see Lemma 17) to define , the sets of vertices respectively of type X and Z with respect to the MLS cover. Also, each vertex in has the same neighbourhood in both and . According to Lemma 18, if and are LCr-equivalent then there is a single -local complementation over vertices of together with a series of local complementations on vertices of type that transform into . We first focus on the single -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 by mean of a single -local complementation over vertices of . Notice that such a -local complementation only toggles edges which both endpoints are in . Given a multiset , the edges toggled in can be represented by a vector such that for any , . The actions of all the possible -local complementations on can thus be described as the set .
Lemma 19.
is a vector space and a basis of can be computed in runtime .
Proof.
A multiset of vertices of type X can be represented as a vector in which entries are , as the multiplicity can be considered modulo in the context of a -local complementation. Let be the subset of which corresponds to all -incident independent multisets of vertices in . is a vector space since the property of -incidence is preserved under the addition of two vectors. is actually the space of solutions to a set of equations666There are precisely equations. given by the conditions of -incidence. With some multiplications by powers of 2, all these equations are expressible as equations modulo . For every set of size between and , the corresponding equation is
Notice that if , the space of solutions is the entire space , as there are no incidence constraints on usual local complementations. Summing up, to compute a basis of , we solve a system of equations modulo with variables. One can obtain a generating set of of size in basic operations using an algorithm based on the Howell transform [34].
Let be the function that associates with each element , its action on the edges: for any , . Notice that is linear, as for any :
This directly implies that is a vector space: if , by definition there exists such that and , moreover . Also, let us prove that is generated by . Take a vector , by definition there exists such that . can be expressed as a linear combination of vectors from the generating set, i.e. where . Then, for any , by linearity of , where such that when and are viewed as integers. In other words, , implying that is a generating set of . Using Gaussian elimination, one can easily obtain a basis of from .
Thanks to the exhaustive description of all possible -local complementations on , we are now ready to reduce LCr-equivalence to LC-equivalence with some additional constraint. We denote by (resp. ) the graph obtained from (resp. ) by the following procedure. First, remove the vertices of . Then, for each vector , for each such that , add a vertex connected only to and and call it , and let . In the following, we refer to the vertices added by this procedure as “new vertices”.
Lemma 20.
and are LCr-equivalent if and only if there exists a sequence of (possibly repeating) vertices such that satisfying the following additional constraints:
-
the sequence contains no vertex of ;
-
for each , either the sequence contains every vertex of exactly once, or it contains none.
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 such that , satisfying the additional constraints described in Lemma 20, can be done in runtime .
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 and 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 : , , ,
-
;
-
;
-
if and only if .
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 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 , the LCr-equivalence of graphs in polynomial runtime.
Theorem 22.
There exists an algorithm that decides if two graphs are LCr-equivalent with runtime , where is the order of the graphs.
The algorithm reads as follows:
-
1.
Put and in standard form with respect to the same MLS cover if possible, otherwise output NO.
-
2.
Check whether each vertex has the same type in and , and whether every vertex of type X has the same neighbourhood in both graphs, otherwise output NO.
-
3.
Compute a basis of the vector space .
-
4.
Compute the graphs and .
-
5.
Decide whether and 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 , 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 is valid then is at most logarithmic in the order of the graph . This bound is however not true in general as it has been shown in [13] that whenever is valid, we have . To avoid these pathological cases, we thus focus on genuine -incident independent multisets:
Definition 23.
Given a graph , a -incident independent multiset is genuine if there exists a set such that and is odd777With a slight abuse of notation, is the sum over all s.t. ..
Proposition 24.
If is valid and there is no such that then is a genuine -incident independent multiset.
Proof.
By contradiction assume is an -incident independent multiset which is not genuine. Let be the multiset obtained from by choosing, for every set s.t. is not empty, a single vertex s.t. , and setting and for any other vertex s.t. , . It is direct to show that is -incident and that . Then, let be the multiset obtained from by dividing by 2 the multiplicity of each vertex in . It is direct to show that is -incident and that .
Genuine -incidence can only occur for multisets whose support is of size at least exponential in .
Lemma 25.
If and is a genuine -incident independent multiset of a graph , then .
Proof.
Let be the smallest integer such that there exists a set of size such that is odd. Note that by hypothesis there exists such an integer. Indeed, let be the biggest subset (by inclusion) of such that is odd: then is odd. Thus, by definition of the -incidence, .
Let the graph obtained from by removing the vertices that are neither in the support of , nor in . By definition, is also -incident in . Also, is odd, and for every set s.t. , is even.
Let us prove that for any s.t. , is odd, by induction over the size of . First notice that is odd. Then, let s.t. .
Thus, is odd. As a consequence, for any s.t. , there exists at least one vertex s.t. . Then, .
Likewise, -local complementations that cannot be implemented by -local complementations can only occur or multisets with sufficiently many vertices outside their support.
Lemma 26.
If is valid and there is no such that , then .
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 is valid and there is no such that , then , where is the order of .
Put differently, any -local complementation on a graph of order at most can be implemented by -local complementations:
Corollary 28.
If two graphs of order at most 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 . This implies the following strengthening of Theorem 5.
Corollary 29.
If two graphs of order at most are LU-equivalent, they are LCr-equivalent.
Proof.
Suppose that and of order are LU-equivalent. According to Theorem 5, and are LC⌊n/2⌋-1-equivalent. If then and are trivially LCr-equivalent. Otherwise, according to Corollary 28, and 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 are LU-equivalent then they are LC-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 in runtime . According to Corollary 29, and are LU-equivalent if and only if they are LCr-equivalent, where . 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 , where 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 can be implemented using only usual local complementations over vertices in the support of . 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 , then a 2-local complementation on 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 be a -incident independent multiset of a graph . If , or if and , then a 2-local complementation on can be implemented by local complementations over a subset of .
Likewise, according to Lemma 25 and Proposition 24, if the support of some 2-incident independent multiset is of size at most 10, then a 2-local complementation on 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 and are twins if ).
Lemma 32.
Let be a 2-incident independent set of a graph such that does not contain any twins and . Then, .
The proof of Lemma 32 is an induction over the number of vertices connected to 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 contains two twins and , then a 2-local complementation over has the same effect as a 2-local complementation over followed by a local complementation over . 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 be a 2-incident independent multiset of a graph such that . Then, a 2-local complementation over can be implemented by local complementations over a subset of .
According to Lemma 31 and Lemma 33, if a 2-incident independent multiset satisfies or , or alternatively if and , then a 2-local complementation over 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 epr-pairs from an -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 be a 2-incident independent multiset of a graph and suppose that there exists no set such that . Then there exists a graph bipartite with respect to a bipartition of the vertices such that:
-
is 2-incident;
-
contains no twins;
-
contains no vertex of degree 0 or 1;
-
;
-
;
-
there exists no set such that .
Proof.
The proof is constructive, in the sense that we construct and from and . According to Proposition 4, there exists set such that is 2-incident and . Also, the existence of a set such that implies . Let and , then apply the following operations:
-
1.
Remove the edges between vertices of ;
-
2.
Remove each vertex of of degree 0 or 1;
-
3.
If there exists a pair of twins in , remove and . Repeat until contains no twins.
Notice that each operation preserves the 2-incidence of and that for no set .
Given an integer , let be the class of graphs that are bipartite with respect to a bipartition of the vertices such that:
-
is 2-incident;
-
contains no twins;
-
contains no vertex of degree 0 or 1;
-
.
It is easy to generate each graph of , although the number of elements in grows double exponentially fast with . can be defined as a list of words in of weight at least 2. More precisely each vertex of is uniquely associated with a set of of size at least 2, its neighbourhood. Furthermore, the 2-incidence of implies that 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 “” translate into a procedure to find which vertices of degree 3 then 2 need to be added to the set so that is 2-incident. This proves that there is a bijection between and lists of words in of weight at least 4. Thus, the size of is exactly given by the formula
For and , the size of is respectively , and which is suitable for computation. But, even for as low as seven, the size of is .
For every from 1 to 6, we generate each graph of , along with the set defined above. Notice that a local complementation over a vertex of toggles the connectivity of some pairs of vertices of , here the pairs where each end is a neighbour of . In other words, to each vertex of we associate a vector in corresponding to the action of the local complementation of on the graph. The set of the vectors corresponding to each vertex of spans a -vector space describing the action of local complementation over vertices of on the graph. Using Gaussian elimination, we are able to compute a basis of . Furthermore, we compute the vector in corresponding to the action of a 2-local complementation over on the graph. Checking if the action of a 2-local complementation over can be implemented by local complementations on vertices of amounts to checking if belongs to the vector space , which can be done efficiently using Gaussian elimination.
For , the set corresponding to the only graph is empty, hence a 2-local complementation over leaves invariant, i.e. . For , is either empty of contains 11 vertices; in both case it is easy to check that . For , the computation shows that for each graph , . Now, fix . For each graph such that the corresponding set contains at most 16 vertices, . For each graph such that the corresponding set contains at most 20 vertices, a 2-local complementation over the corresponding set can be implemented by local complementations over vertices of , i.e. there exists a set such that . The property does not hold if is of size 21, for instance we recover the well-known 27-vertex counterexample to the LU=LC conjecture described in [35].
See 31