THEOREM. Labelled graph-state local-unitary equivalence is decidable deterministically in polynomial bit complexity. Input is two finite simple graphs on the same labelled n-vertex set, and the question is whether their graph states are related, up to global phase, by a tensor product of single-qubit unitaries. No connectivity, circle-graph, degree or other promise is required. The algorithm uses exact finite modular/binary linear algebra and the established Claudet–Perdrix graph reductions; it does not numerically optimize continuous unitaries.

The new ingredient is polynomial compression of the high-order incidence module. Its proof and the kernel/image interface are included below. Other graph-theoretic reductions are explicitly attributed to Claudet–Perdrix, arXiv:2502.06566, Sections3.1–3.5 and AppendicesC,D. This is a correctness claim using those published theorems, not an assertion that the entire LU theory has been proved anew or that independent literature priority is established.

PART I. Exact incidence compression (round20 proof).
Exact polynomial compression of generalized-local-complementation incidence constraints. Let G be a finite simple graph on a labelled vertex set V, let X⊆V be an independent set, put Y=V\X and m=|X|, and let r>=1 be an integer. All complexity bounds below are polynomial in |V| and r, rather than in log r. Write R=Z/(2^r), and, for v∈Y, define a_v∈{0,1}^X by a_v(x)=1 iff {v,x}∈E(G). For K⊆Y put a_K(x)=∏_{v∈K}a_v(x). Define δ(0)=1 and δ(j)=0 for j>0. The R-row module generated by 2^(|K|-2+δ(|K|-2))a_K, for 2<=|K|<=r+1, admits a generating matrix B with at most m rows that can be constructed deterministically in polynomial time in |V| and r. Consequently the exponentially indexed incidence requirements s·a_K divisible by 2^(r-|K|+2-δ(|K|-2)) are equivalent to Bs=0 modulo 2^r.

Moreover, given another graph H on the same labelled vertices, one can decide in polynomial time in |V| and r whether H results from G by a single r-local complementation on an r-incident multiset supported in X, and construct its multiplicities in binary when it exists. Here r-incidence means that, for every 0<=k<r and every (k+2)-element K⊆V\supp(S), the common-neighbor multiplicity is divisible by 2^(r-k-δ(k)); the complementation toggles a pair outside supp(S) exactly when its common-neighbor multiplicity is congruent to 2^(r-1) modulo 2^r. The output uses multiplicities in {0,...,2^r-1}, not an expanded listing of the multiset.

Put q=2^r. First suppose m>0. Products and spans in the next two paragraphs are taken over R. For each v∈Y define the linear operator T_v(z)=2a_v⊙z, where ⊙ is coordinatewise multiplication. Let M be the module in the claim, and let N be the smallest module containing every row 2a_K for |K|=2 or 3 and invariant under every T_v. When r=1 these seed rows are zero, so including triples even though the stated indexing stops at pairs is harmless.

We prove M=N. The seeds belong to M: pairs always occur, triples occur for r>=2, and all seeds vanish for r=1. Write w(k)=k-2+δ(k-2), so w(2)=w(3)=1 and w(k)=k-2 for k>=3. Apply T_v to a generating row 2^w(k)a_K. If v∈K, idempotence of the binary coordinates gives twice that row. If v∉K and k=2, the image is twice the triple row; if triples are outside the indexing, the image is zero modulo q. If v∉K and k>=3, the image is exactly the prescribed row for K∪{v}, provided k+1<=r+1. At the last permitted size, its coefficient is 2^r and it vanishes. Thus M is invariant and N⊆M. Conversely, every row of size k>=4 is obtained by starting with the weight-2 row of any three-element subset of K and applying the operators for the remaining k-3 distinct vertices. The resulting coefficient is 2·2^(k-3)=2^(k-2), exactly the required weight. Pairs and triples are already seeds. Therefore M⊆N, proving equality. In particular, repetitions of vertices in arbitrary closure operations introduce no additional constraints.

Here is a polynomial construction, including a termination and bit-size bound. Work with full-rank integer lattices in Z^m. Let L_0 be generated by qZ^m and the integer seed rows. For i>=0 define
L_(i+1)=L_i + sum_{v∈Y} T_v(L_i),
using the same integer diagonal operators. Compute a row Hermite normal form basis after each step, and stop when the lattice is unchanged. It suffices to apply each operator to a lattice basis. Every lattice contains qZ^m and lies in Z^m. Therefore every strict enlargement increases the cardinality of L_i/qZ^m by a factor of at least two. Since |Z^m/qZ^m|=2^(rm), there are at most rm strict enlargements. Equality at one step is the required simultaneous invariance and hence implies stabilization.

The initial generating matrix has O(m+|Y|^3) rows. Each subsequent matrix has at most m(1+|Y|) rows. A Hermite basis can be chosen with diagonal entries at most q and off-diagonal entries reduced below the associated pivots: the determinant argument giving a diagonal bound can also be seen directly by reducing q times each coordinate vector against the triangular basis. Thus every retained entry has O(r+1) bits. Applying a T_v multiplies selected coordinates by two, so the next input still has O(r+1)-bit entries. Deterministic integer Hermite normal form algorithms have polynomial bit complexity in matrix dimensions and entry bit lengths. Together with the bound on strict enlargements, this gives a polynomial-time construction. Reduction of the final basis modulo q gives B, with m rows. Its row span is exactly N=M. Consequently annihilating B is equivalent to annihilating every original row. For any integer c and exponent 0<=w<=r, 2^w c=0 modulo 2^r is equivalent to divisibility of c by 2^(r-w). This proves the asserted equivalence to the incidence requirements.

We next verify that these requirements exactly describe incidence of multisets supported in X, including those with smaller actual support. Represent a multiset by its nonnegative multiplicity vector s on X. If K⊆V\supp(S) contains a vertex x∈X, then no vertex of X is adjacent to x, because X is independent. Hence its common-neighbor multiplicity in S is zero. All such requirements hold automatically. The other relevant sets are precisely K⊆Y, and their common-neighbor multiplicities are a_K·s. Thus Bs=0 is equivalent to the definition of r-incidence, with no assumption that every vertex of X has positive multiplicity. Reducing multiplicities modulo q preserves all required divisibilities.

For the constructive decision statement, first reject unless G and H agree on every pair meeting X. This is necessary: pairs meeting the actual support are unchanged by definition, and a pair meeting X but not the support has zero common-neighbor multiplicity in S, so cannot be toggled. For distinct u,v∈Y let d_uv∈{0,1} indicate whether G and H disagree on that edge. In addition to Bs=0, impose the linear congruences
(a_u⊙a_v)·s = 2^(r-1)d_uv modulo 2^r.
There are only O(|V|^2+m) equations. Incidence for pairs says their common-neighbor counts are divisible by 2^(r-1). Modulo q, the only two possible residues are consequently 0 and 2^(r-1), with the latter exactly the toggling condition. Thus these congruences are necessary and sufficient for the desired single complementation.

For completeness, the resulting linear system over R can be solved with polynomial bit complexity, without enumerating multiplicities. In the remaining coefficient submatrix, select a nonzero entry with minimum 2-adic valuation e, swap it into the pivot position, and multiply its row by an odd unit so that the pivot becomes 2^e. Every remaining entry is divisible by 2^e. Row and column subtraction therefore eliminate the pivot column and row using integer quotients, computed modulo q. These operations are invertible over R. Repeat on the remaining submatrix, tracking the right-hand side and the column transformations modulo q. For each diagonal pivot 2^e, solvability is exactly divisibility of the corresponding right-hand side by 2^e; zero rows require zero right-hand sides. Choose solutions for the diagonal equations and transform back. There are polynomially many operations on O(r)-bit ring elements. Representatives between 0 and q-1 provide the promised multiplicities and satisfy every required condition. Finally, if m=0, the incidence module is the zero module on zero coordinates, the only multiset is empty, and the answer to the constructive decision problem is simply whether H=G. This also satisfies all stated bounds.

PART II. Modular kernel and complete binary image (round21 interface proof).
Polynomial construction of the complete toggle image and witnessing multiplicities. Let G be any finite simple graph on the labelled vertex set [n], let X be a prescribed independent set, let Y=[n]\X, let m=|X|, and let r>=1. Set q=2^r, h=2^(r-1), and R=Z/qZ. For K⊆Y define a_K∈{0,1}^X by a_K(x)=1 exactly when x is adjacent to every vertex of K. Put w(2)=1 and w(k)=k-2 for k>=3. Define Sigma={s∈R^X: 2^w(|K|) a_K·s=0 in R for every K⊆Y with 2<=|K|<=r+1}. For each unordered pair p⊆Y define f(s)_p=(a_p·s/h) mod 2, using any integer lift of s. Then f is well-defined on Sigma, and Omega=f(Sigma) is a binary linear subspace of F_2^{binom(|Y|,2)}. Using the supplied polynomial incidence-compression theorem, there is a deterministic algorithm, polynomial in n and r in bit complexity, which constructs a basis b_1,...,b_d of Omega and preimages s_1,...,s_d∈Sigma with f(s_i)=b_i, where d<=m and every multiplicity is represented by an r-bit integer. It also gives a polynomial-size binary linear description of Omega and constructs a witnessing multiplicity vector for every member. The graphs obtainable from G by a single r-local complementation with an r-incident multiset supported in X are exactly the graphs agreeing with G on pairs meeting X and whose difference from G on pairs in Y belongs to Omega. Here r-incidence means that for every K⊆[n]\supp(S) of size k with 2<=k<=r+1, its common-neighbor multiplicity in S is divisible by 2^(r-w(k)); the complementation toggles a pair outside supp(S) exactly when its common-neighbor multiplicity is h modulo q. The result includes r=1, X empty, isolated vertices, and disconnected graphs. It is not an algorithm for unrestricted LU equivalence, because X is prescribed and the subsequent reduction stages are not established here.

Write N=binom(|Y|,2). We use precisely the accepted incidence-compression theorem supplied with the problem: the R-row module generated by all 2^w(|K|)a_K, with 2<=|K|<=r+1, has a matrix B with at most m rows, constructible in deterministic polynomial bit complexity in n and r. Its annihilator is exactly Sigma, so Sigma=ker_R B. The theorem applies because X is independent; it does not require connectivity or nonempty neighborhoods.

1. Well-definedness and carries. The pair constraints in Sigma are 2a_p·s=0 modulo q. Thus, for every integer lift of s, a_p·s is divisible by h. This also holds for r=1, where h=1 and the pair constraints are vacuous. Replacing a lift s by s+qz changes a_p·s/h by 2a_p·z, an even integer. Therefore f(s) is independent of the lift. For s,t∈Sigma, if representatives of s+t are reduced modulo q coordinatewise, the reduction subtracts qz for some integer vector z. Consequently f(s+t)=f(s)+f(t) in F_2^N. Likewise f(cs)=(c mod 2)f(s) for every c∈R: the same calculation removes every modular carry. Reduction R→F_2 is well-defined because q is even. Thus f is an R-module homomorphism when F_2^N is regarded as an R-module by this reduction. Its image Omega is a binary linear space.

2. Constructing generators of the modular kernel. This step must use the R-kernel, not the ordinary binary kernel of B. Let B have b<=m rows. Perform invertible row and column operations over R to obtain U B V=D, a rectangular diagonal matrix whose nonzero entries are powers 2^e_i with 0<=e_i<r. Here U and V are invertible over R, and we track V.

For completeness, this diagonalization has a direct polynomial algorithm. In the remaining submatrix select a nonzero entry of minimum 2-adic valuation e and move it to the pivot position. Multiply its row by an odd unit so that the pivot becomes exactly 2^e modulo q. Every entry in the submatrix is divisible by 2^e. Row subtraction, using integer quotients of representatives divisible by 2^e, clears the pivot column. Column subtraction then clears its row. These operations are invertible; clearing the row does not reintroduce entries below the pivot, since its column has already been cleared. Repeat on the remaining submatrix. Odd inverses are obtained by the integer Euclidean algorithm. Every stored entry can be reduced modulo q after each operation, so all entries have O(r) bits. There are polynomially many operations on matrices of dimensions at most m, including the tracked transformations.

Let t be the number of nonzero diagonal entries. A vector z belongs to ker D exactly when z_i is a multiple of 2^(r-e_i) for i<=t; coordinates i>t are unrestricted. Thus ker D is generated by 2^(r-e_i)e_i for the pivot coordinates and by e_i for the free coordinates, where e_i here denotes the corresponding coordinate vector. A pivot with exponent zero contributes the zero generator and may be omitted. Multiplying these generators by V gives generators g_1,...,g_ell of Sigma, with ell<=m. Indeed B(Vz)=0 if and only if Dz=0 because U is invertible. This proves both completeness and the polynomial bit complexity of the kernel construction. It does not assume that Sigma is a free R-module.

3. Constructing the image and retaining witnesses. For each g_j choose its representatives in {0,...,q-1}. For every pair p⊆Y compute c_p=(a_p·g_j) mod q in {0,...,q-1}. By step 1, c_p is either 0 or h. Therefore f(g_j)_p is obtained exactly by the integer division c_p/h. No approximation or division by a nonunit in R occurs.

Every s∈Sigma has an expression s=sum_j c_j g_j with c_j∈R. The homomorphism calculation gives f(s)=sum_j(c_j mod 2)f(g_j). Conversely, every binary sum of the f(g_j) is the image of the corresponding sum of the g_j. Hence Omega is exactly the F_2-span of these at most m image vectors.

Perform binary Gaussian elimination on the image vectors, carrying along their preimages. Whenever one image row is added to another over F_2, add its preimage to the other preimage over R. Step 1 guarantees that the witness invariant is preserved. Row swaps simply swap the witnesses. Discard dependent zero image rows. The surviving rows b_1,...,b_d form a basis of Omega, have preimages s_1,...,s_d in Sigma, and satisfy d<=m. For a proposed difference vector delta, binary elimination either rejects delta∉Omega or constructs coefficients epsilon_i∈{0,1} with delta=sum_i epsilon_i b_i. Then s=sum_i epsilon_i s_i modulo q is a witnessing multiplicity vector. Alternatively, a basis of the binary orthogonal complement Omega^perp gives a homogeneous binary equation matrix whose kernel is Omega.

There are N image coordinates and at most m modular generators. Computing all images requires O(Nm^2) elementary arithmetic operations; binary elimination with preimage tracking requires polynomially many further operations on binary entries and O(r)-bit residues. The modular diagonalization uses polynomially many O(r)-bit ring operations. Together with the supplied polynomial construction of B, these bounds prove deterministic polynomial bit complexity in n and r. In particular, this is polynomial in n whenever r=O(log n). The dimension N is O(n^2), so even the explicit orthogonal-complement description has polynomial size.

4. Identification with graph operations. Let s be represented by nonnegative integers below q, and let S be the multiset with those multiplicities on X. If a set K outside supp(S) contains any vertex of X, then no vertex in X is adjacent to every vertex of K, because X is independent. Its common-neighbor multiplicity in S is therefore zero. All incidence requirements for such K hold automatically. For K⊆Y that multiplicity is exactly a_K·s. The equivalence between 2^w(|K|)a_K·s=0 modulo q and divisibility by 2^(r-w(|K|)) shows that S is r-incident if and only if s∈Sigma.

Pairs meeting supp(S) are unchanged by the definition of the operation. A pair meeting X but not supp(S) has zero common-neighbor multiplicity in S and is also unchanged. For p⊆Y, incidence restricts its common-neighbor count modulo q to 0 or h; the pair is toggled exactly in the latter case. This is precisely the bit f(s)_p. Reduction of multiplicities modulo q preserves every relevant divisibility and toggle condition. It follows in both directions that the obtainable graphs are exactly those described in the claim.

If X is empty, Sigma has only its zero vector, Omega={0}, the basis and preimage lists are empty, and the only obtainable graph is G. The arguments above already cover r=1, empty pair sets, isolated vertices and disconnected graphs without modification. Vertex coordinates and pair coordinates retain their original labels throughout.

PART III. Complete integration into the published graph reduction.

We use the following precise established results of Claudet–Perdrix2502.06566 (CP). Lemma3.12 provides a polynomial-time procedure which either correctly rejects LU-equivalence or puts both graphs in standard form with respect to a common minimal-local-set (MLS) cover by ordinary local complementations. Its bound is O(n^6.38). Lemma3.13 allows rejection if vertex types or the neighborhoods of type-X vertices differ. In standard form X=V_X is independent, its neighbors are in V_Z, and there are no X-to-bottom-type edges. Lemma3.14 reduces level-r equivalence to one r-local complementation supported on this X and ordinary local complementations on bottom-type vertices. Lemmas3.17 and3.18 give an exact polynomial reduction from this test, supplied with a basis of the binary toggle space Omega, to constrained ordinary LC-equivalence. Corollary3.29 states that graphs of order n<=2^(r+3)-1 which are LU-equivalent are level-r equivalent; the reverse implication follows because generalized local complementations are local unitaries (CP Section2.3, its displayed local-unitary identity and level characterization). All of these are theorems used as dependencies.

1. Components and labels. A graph state factors across a vertex bipartition S:S^c if and only if the graph has no edge across that cut. One direct proof uses its computational-basis amplitudes: after cancelling phases from within each side, the coefficient matrix is (-1)^(x_S^T Gamma_(S,S^c) x_(S^c)) times a common scalar. If a crossing matrix entry is1, the2 by2 submatrix at the two corresponding single-bit assignments is [[1,1],[1,-1]], with nonzero determinant, so the coefficient matrix has rank at least2. With no crossing edge it is a product matrix. Product unitaries preserve this factorization property for each fixed labelled cut. Thus LU-equivalent graphs have identical partitions into connected components. Compute and compare these partitions; reject if different. Solve separately on each common component and accept if and only if every component accepts. Tensor products of the component witnesses suffice in the accepting direction. Empty graphs and one-vertex components are immediate. No permutation of labels is allowed. It remains to describe the procedure on a connected component with v>=2 vertices.

2. Choose r=max(1,ceil(log2(v+1))). This integer has O(log v) value and meets v<=2^(r+3)-1. CP Corollary3.29 therefore makes LU-equivalence exactly level-r equivalence. This loose choice avoids small-order special formulas. Run CP Lemma3.12 and the type/neighborhood checks from Lemma3.13. If they reject, answer NO. Otherwise retain the common cover, types and standard forms G1,G2. Ordinary LC preserves connectivity: when complementing at a vertex, any deleted edge between two of its neighbors is replaced by a two-edge path through that vertex. Hence these standard forms remain connected.

3. Compute the exact binary toggle space. Apply Part I to the prescribed independent support X=V_X of G1, using Y=V\X. It returns a polynomially sized exact incidence matrix B over Z/(2^r), without enumerating high-order subsets. Part II returns a binary basis omega_1,...,omega_d for all edge toggles obtainable by one valid r-local complementation on X, with d<=|X| and optional witnessing multiplicities. There are no possible toggles outside pairs in V_Z: any other outside vertex has no neighbor in X. Restricting the image coordinates to pairs in V_Z therefore loses no information. This is precisely the space Omega required by CP Lemma3.15; all incidence divisibility exponents coincide with its displayed equations. Part I replaces the enumeration step in that lemma, while Part II implements its complete image construction, including nonfree modular kernels and carries. No target graph or multiplicity is enumerated.

4. Explicit size and applicability of the downstream reduction. Follow CP Lemma3.17. Delete X from each standard form. For every basis vector omega_i and each pair {u,w} in V_Z toggled by that vector, add to BOTH resulting graphs a fresh labelled degree-two vertex joined only to u and w. The same fresh labels are used in both graphs. Group these new vertices as P_i according to their basis vector. The augmented graphs have at most v+|X| binom(v,2)=O(v^3) vertices. The constrained LC question forbids complementation at V_Z and requires, for each P_i, that either all of its vertices are complemented once or none are. CP Lemma3.17 establishes equivalence of this question to the original level-r question after standardization. CP Lemma3.18 solves it in polynomial time using linear constraints on the local-Clifford equation variables: B_u=0 on V_Z, C_p=0 on every new vertex, and B_p=B_p0 for a chosen representative p0 of each nonempty P_i. There are polynomially many such equations; equality to a representative avoids even an unnecessary pairwise list. These variable names are CP's binary local-Clifford coordinates, unrelated to our modular incidence matrix.

The even-degree and connectedness hypotheses in CP Proposition3.5 must not be silently discarded. If d>0 there is a degree-two new vertex. Moreover the augmented graph remains connected, as follows. For each x in X, the multiplicity vector 2^(r-1)e_x is r-incident: every required weighted row has coefficient divisible by2, so its scalar product is divisible by2^r. Its toggle vector is exactly the clique on the neighbors of x. Since the omega_i span Omega, for any two distinct neighbors u,w of x, at least one omega_i toggles that pair. Thus some added degree-two vertex supplies a path u--p--w. Any path in the original connected standard form between vertices outside X can be modified by replacing every passage through X with such a path. If x has at most one neighbor it never needs to be an internal vertex of a simple path with endpoints outside X. All new vertices attach to the resulting connected remainder. The outside set is nonempty because X is independent and the original component has at least two vertices. This proves connectedness of both augmented graphs. Hence the nonzero-image branch of CP Lemma3.18 really meets the connected/even-degree hypotheses. If d=0, instead run the ordinary polynomial LC decision algorithm directly on the original standard forms G1,G2, before deleting X. This branch needs no constrained-LC theorem: if they are level-r equivalent, Lemma3.14 writes the transformation as bottom-type ordinary complementations and one operation on X; the latter changes no edge because Omega={0}, so the graphs are ordinarily LC-equivalent. Conversely ordinary LC-equivalence implies level-r equivalence. This proves the exact zero-image branch, including X empty, without assuming that ordinary LC on the deleted graphs would lift or applying Proposition3.5 to an all-odd graph.

5. Correctness. Every rejection in component comparison, MLS standardization or type checks is sound by step1 and CP Lemmas3.12–3.13. On surviving instances, Part I and Part II compute exactly the space used in CP's reduction. For nonzero Omega, Lemma3.17 therefore says that constrained LC acceptance is equivalent to level-r equivalence; Lemma3.18 decides exactly that predicate. The zero-image branch has the separate equivalence proved in step4. The chosen r and Corollary3.29 make it equivalent to LU-equivalence. This proves both completeness and soundness. All graph transformations keep the original labels; auxiliary labels are matched consistently. Disconnected cases were reduced with an exact factorization criterion, so no connectedness promise remains.

6. Bit complexity. The MLS stage, type tests and all binary graph operations are polynomial by the cited CP procedures. Part I uses at most r|X| strict lattice enlargements, each with polynomial-size integer Hermite computations on O(r)-bit retained entries. Part II diagonalizes a matrix of dimension at most |X| over Z/(2^r), produces at most |X| kernel generators, evaluates O(v^2) image coordinates and performs binary elimination with O(r)-bit witness residues. These operations are polynomial in v and r. Here r=O(log v), and even the numeric modulus2^r is at most2(v+1); in particular there is no hidden exponential dependence on the precision of the modulus. The augmented graphs have O(v^3) vertices and a polynomial number of constraints, so the constrained LC algorithm is polynomial on their actual size. One may use its conservative generic bound O((N^2+ell)N^2) for N augmented vertices and ell binary constraints in the nonzero-image branch; an optimized exponent is not claimed. Summing a fixed polynomial bound over at most n disjoint components is still polynomial in n. Thus the complete decision algorithm has deterministic polynomial bit complexity.

SOURCE COMPARISON. CP Section3 explicitly identifies its incidence/image stage(ii) as the only stage with n^r dependence, while stages(i),(iii),(iv) are polynomial. Lemma3.15 and thesis2511.22271 Chapter6 enumerate O(n^(r+1)) rows. Their own image and constrained-LC reductions are credited, not new results. The new replacement is the exact weighted diagonal closure from Part I; Part II and the integration ensure this replacement actually fits every interface. The circle-graph result2603.08847 is a restricted LU=LC theorem, not this unrestricted algorithm. No exhaustive priority claim is made.