Graph states are one of the workhorse resources of quantum information: they underlie measurement-based quantum computation, many quantum error-correcting codes and several quantum-repeater designs. A basic question about them sounds almost too simple to be hard: given two graph states on the same labelled qubits, can one be turned into the other by independent single-qubit unitaries? A new single-author preprint by Yuxuan Zhang (EPFL and Princeton) gives a deterministic polynomial-time algorithm that answers it, and constructs the unitaries when the answer is yes. The author describes the polynomial-time question as having been open for over a decade.
This article was drafted with Claude and fact-checked against the cited primary sources.
Why this paper is worth reading
For the restricted case of local Clifford (LC) operations, the problem has long been solved: two graph states are LC-equivalent exactly when their graphs are related by local complementations, and Bouchet’s algorithm decides this in polynomial time. For years it was conjectured (the “LU–LC conjecture”) that local-unitary (LU) equivalence always coincides with LC equivalence, which would have made the Clifford test enough. Ji, Chen, Wei and Ying disproved this with a 27-qubit counterexample, and Claudet later proved that 27 qubits are necessary. Since then the complexity of recognising full LU equivalence was unclear. Claudet and Perdrix recently gave a quasipolynomial algorithm, running in time nlog2 n + O(1). The new paper closes the gap to polynomial time.
What the paper does
The main theorem (Theorem 1.1) states that a deterministic classical algorithm decides LU equivalence of two graph states on n labelled vertices in Õ(n6.38) bit operations, and, if they are equivalent, returns single-qubit unitaries realising the map with an exact symbolic description of O(n log n) bits. Vertex labels are fixed; permutations of qubits are not allowed.
Several further results come out of the same machinery:
Counting Clifford classes. Inside the LU class of any graph state, the number of distinct LC classes is a power of two, 2κ, and κ is computable within the same time bound. When κ > 0 the algorithm outputs an explicit graph that is LU- but not LC-equivalent to the input, with the connecting unitary (Theorem 5.1).
Least non-Clifford level. It computes the smallest level r of a dyadic gate hierarchy needed for an equivalence (Corollary 4.5).
Stabilizer states and codes. It decides SLOCC equivalence of pure stabilizer states given by Pauli generators, and LU equivalence of stabilizer codes encoding one logical qubit (Corollaries 4.6 and 4.7).
Counting graphs is hard. Combined with prior hardness results, counting the labelled graphs in an LU class is #P-complete (Corollary 5.3).
The key idea
The paper builds directly on the Claudet–Perdrix reduction, and is explicit about what is inherited. Claudet and Perdrix showed that for graphs with at most 2r+3−1 vertices, LU equivalence coincides with equivalence under a gate set LCr generated by Hadamards and phase gates diag(1, eiπ/2r). Level one is ordinary Clifford; level two adds the T gate. So r only needs to grow logarithmically with n. After putting both graphs in a common “standard form”, the vertices split into three types (X, Z and a mixed type), and the only non-Clifford freedom left is a single “generalised local complementation” on the X vertices, which can toggle edges only among the Z vertices.
Which generalised complementations are allowed is governed by divisibility conditions modulo 2r on common-neighbour counts, one condition for every subset of up to r+1 vertices. Listing all those subsets is what made the previous algorithm quasipolynomial. Zhang’s observation is that the higher-order conditions are generated from the pair and triple conditions by a simple linear map: multiplying a constraint row coordinatewise by twice the neighbourhood vector of one more vertex produces the next-order row. Because these maps are linear, one can apply them to a small generating set, reduce with modular elimination after each round, and never store more than |X| generators. The paper proves that O(r) rounds suffice.
How the algorithm works
The full procedure (Algorithm 2) has these steps:
Check that the labelled connected components agree, then work component by component.
Compute common standard forms with the inherited Claudet–Perdrix procedure, and reject if vertex types or X-neighbourhoods differ.
Run the new incidence compression to describe all valid multiplicities as the kernel of a small matrix over ℤ/2rℤ, and extract a binary basis of all admissible edge changes, keeping a multiplicity vector that realises each one.
Solve one affine linear system over the binary field that simultaneously chooses an edge change and the remaining local Clifford operations. A determinant identity (Lemma 4.1) shows that, for a connected target, every solution of the linear Clifford equations automatically satisfies the per-vertex invertibility conditions once one vertex is fixed, which is what removes the apparent nonlinearity.
Assemble the witness: each qubit gets a unitary of the form Clifford · Z(kπ/q) · Clifford.
The new algebraic steps cost Õ(n5) bit operations. The overall Õ(n6.38) bound is set by the inherited standard-form preprocessing, which uses fast binary matrix rank; with classical cubic rank computation, the paper states the bound becomes Õ(n7).
What was checked
The results are established by proof. In addition, Appendix B reports finite computational checks of the algebraic stages: for example, the incidence compressor was compared with the original constraints on 1,536 binary incidence systems, and 91 end-to-end constructions on four to eight qubits produced local unitaries matching the target state with Euclidean error below 10−10. On the published 27-vertex LU-but-not-LC pair of Tsimakuridze and Gühne, the constructive algorithm rejects level one, accepts level two, and recovers multiplicities realising the extra clique.
Why it matters
As the paper notes, when arbitrary single-qubit measurement bases are available, local basis changes in a resource state can be absorbed into the measurements in measurement-based computation. That makes LU equivalence the natural notion of “the same resource”. An efficient, constructive test lets one compare resources produced by different compilation routes, detect duplicates in a catalogue, or check whether an easier-to-prepare graph state is LU-equivalent to a desired one. The LC-class count also makes the failure of LU = LC checkable on individual inputs, rather than only through special counterexamples.
Technical perspective (interpretation)
My reading is that the contribution is a clean piece of algebra applied at exactly the right bottleneck. The deep structural work, including the standard form, the reduction to one generalised complementation and the logarithmic level bound, is due to Claudet and Perdrix, and the paper says so plainly. What changes is that an exponentially large family of congruences turns out to be a module generated by a polynomial-size seed under a few linear maps. Combined with the determinant identity, the remaining problem becomes linear algebra over 𝔽2. The power-of-two count of LC classes inside an LU class is, in my view, the most conceptually interesting by-product: it says the LU/LC gap has a vector-space structure for every graph state.
Limitations and open questions
Preprint status. This is a v1 arXiv preprint and has not been peer reviewed. The proofs are long and should be checked by the community.
AI-assisted research. The acknowledgements state that the work is part of the author’s experimental series on agentic scientific research: the author set directions and supervised, while OpenAI models developed candidate arguments and derivations, searched the literature, wrote and ran computational checks, and drafted the manuscript. Readers may want to weigh independent verification accordingly.
No end-to-end implementation yet. The paper states that the full minimal-local-set cover and standardisation procedures are not implemented or benchmarked, and that the checks do not give end-to-end timings. No code link is provided on the arXiv page.
Polynomial, but high degree. The Õ(n6.38) exponent comes from the inherited preprocessing; improving that step would lower the bound.
Exact, not approximate. The algorithm addresses ideal states. A noise-tolerant version would need an approximation criterion and a description of imperfect inputs.
Other objectives remain open. The least dyadic level does not minimise the number of non-Clifford gates or circuit length, and extending the code result to codes with several logical qubits faces a separate obstruction identified by the author.
Paper information
Title: Polynomial-time local-unitary equivalence of graph states
Author: Yuxuan Zhang (Institute of Physics, EPFL, Lausanne; Department of Physics, Princeton University)
arXiv: 2610.00527v1 [quant-ph], submitted 30 September 2026
Code/data: none linked
Primary sources
Paper (abstract page): arxiv.org/abs/2610.00527
Full text (HTML): arxiv.org/html/2610.00527v1
Claudet and Perdrix’s quasipolynomial algorithm, as cited in the paper: arXiv:2502.06566