Polynomial-time local-unitary equivalence of graph states
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 Õ(n6.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 Õ(n5) 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.
Related
- Characterizing local unitary equivalence of multipartite states by local unitary Bargmann invariants
- Quantum states with the same entanglement and local unitary equivalence
- Local unitary equivalence of orthogonal arrays and related linear codes
- Local Clifford equivalence to CSS codes: Polynomial-time classification and conversion
- Five-Dimensional Compatibility and Stratified Local-Unitary Structure of Pure Three-Qubit States
BibTeX
@misc{zhang2026polynomialtime,
title = {{Polynomial-time local-unitary equivalence of graph states}},
author = {Yuxuan Zhang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.00527},
eprint = {2610.00527},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.00527},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Polynomial-time local-unitary equivalence of graph states
AU - Yuxuan Zhang
PY - 2026
DA - 2026/10/04
PB - arXiv
DO - 10.48550/arxiv.2610.00527
UR - https://arxiv.org/abs/2610.00527
AB - 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 Õ(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 Õ(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.
ER -