arXiv:2610.00527
Polynomial-time local-unitary equivalence of graph states
Yuxuan Zhang
Abstract
Local-unitary (LU) equivalence asks whether two quantum states differ only by independent changes of basis on their qubits. For graph states, whether this relation can be decided in polynomial time has remained open for over a decade. We give a deterministic algorithm that decides LU equivalence for graphs on $n$ labelled vertices in $\widetilde O(n^{6.38})$ bit operations and constructs exact single-qubit unitaries whenever the states are equivalent. Building on Claudet and Perdrix's quasipolynomial algorithm, we replace the enumeration of vertex subsets by a compact system of constraints generated from pairs and triples. The remaining graph transformation is found by solving linear equations over the binary field. These new steps cost $\widetilde O(n^5)$ bit operations; the inherited graph preprocessing sets the overall bound. We also count the local-Clifford (LC) classes of graph states within any LU class: their number is a power of two, computable within the same bound. For any given graph state, this decides whether single-qubit Clifford gates reach every graph state in its LU class, and supplies a counterexample when they do not. The method also decides LU equivalence of stabilizer codes encoding one logical qubit.
AI Summary
The paper addresses whether local-unitary (LU) equivalence of qubit graph states can be decided in polynomial time, with qubit correspondence fixed and no permutations allowed. It gives a deterministic algorithm using $\widetilde O(n^{6.38})$ bit operations that also constructs exact single-qubit unitaries, represented using $O(n\log(n+1))$ bits. This extends to pure stabilizer states, their SLOCC-equivalence problem, and LU equivalence of stabilizer codes encoding one logical qubit. The algorithm retains the Claudet–Perdrix common-standard-form reduction and its logarithmic bound on the required dyadic rotation level. It replaces quasipolynomial enumeration of vertex-subset incidence constraints with a modular row-module closure generated by pair and triple constraints. The resulting kernel determines a binary space of admissible edge changes, with multiplicity witnesses. Choosing an edge change and the remaining restricted local complementations becomes an affine system over $\mathbb F_2$; a determinant identity enforces Clifford invertibility across connected components. These new stages cost $\widetilde O(n^5)$; inherited preprocessing determines the overall exponent. The paper also proves that the number of LC classes within any labelled graph-state LU class is a power of two, computes it within the same bound, and constructs an LU-but-not-LC partner when one exists. The method does not optimize preparation cost, circuit length, or non-Clifford gate count. The code-space reduction does not extend directly to multiple logical qubits, and approximate equivalence of imperfect experimental states is not addressed. Finite computational checks support the implementation; larger-resource benchmarking remains future work.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.