Algorithm solves graph state equivalence in polynomial time
Polynomial-time local-unitary equivalence of graph states
Computational Complexity
Summary
Two quantum states are considered equivalent if one can be changed into the other by adjusting each qubit independently. The authors found a way to quickly check if two special quantum states called graph states are equivalent, doing this much faster than before. They created an algorithm that not only decides if the states match but also shows how to change one into the other with simple operations. This helps understand complex quantum codes and the kinds of changes needed to go between related states.
What this means in practice
- •For quantum computing engineers: Identify when two graph-based quantum states are equivalent efficiently to optimize quantum circuit design and error correction.
- •For quantum cryptography teams: Verify transformations between quantum codes encoding a single logical qubit to ensure secure quantum information protocols.
Authors
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.