Efficient algorithm to recognize the local Clifford equivalence of graph states

In Van den Nest [Phys. Rev. A 69, 022316 (2004)] we presented a description of the action of local Clifford operations on graph states in terms of a graph transformation rule, known in graph theory as local complementation. It was shown that two graph states are equivalent under the local Clifford group if and only if there exists a sequence of local complementations which relates their associated graphs. In this Brief Report we report the existence of a polynomial time algorithm, published in A. Bouchet [Combinatorica 11, 315 (1991)], which decides whether two given graphs are related by a sequence of local complementations. Hence an efficient algorithm to detect local Clifford equivalence of graph states is obtained.