Efficient algorithm to recognize the local Clifford equivalence of graph states

In Van den Nest et al. 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.