Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Algorithmic approaches to graph states under the action of local Clifford groups

Moshen Bahramgiri

Published Jan 1, 2007• 0 citations
OpenAlex

Abstract

Graph states are quantum states (quantum codes) in qn-dimensional space ... (q being a power of some prime number) which can be described by graphs with edges labeled from the field of order q, Fq. Graph states are determined as a common eigenvector of independent elements of the n-fold Pauli group, on which the local Clifford group has a natural action. This action induces the natural action of the local Clifford group on graph states and hence, its action on graphs. Locally equivalent graphs can be described using this action. For q being a prime number, two graphs are locally equivalent when they are located on the same orbit of this action, in other words, when there is an element of the local Clifford group mapping one graph to the other one. When q is some power of a prime number, the definition of this action is the natural generalization of this action in the case where q is prime. We translate the action of local Clifford groups on graphs to a set of linear and quadratic equations in the field F,. In the case that q is an odd number, given two arbitrary graphs, we present an efficient algorithm (polynomial in n) to verify whether these graphs are locally equivalent or not. Moreover, we present a computational method to calculate the number of inequivalent graph states. We give some estimations on the size of the orbits of this action on graphs, and prove that when either q is equal to 2 or is an odd number, the number of inequivalent quantum codes (i.e., the number of classes of equivalency) is equal to ..., which is essentially as large as the total number of graphs.

Related papers

Graph States Under the Action of Local Clifford Group in Non-Binary Case

Mohsen Bahramgiri, Salman Beigi

Graph states are well-entangled quantum states that are defined based on a graph. Of course, if two graphs are isomorphic their associated states are the same. Also, we know local operations do not change the entanglement of quantum states. Therefore, graph states that are either isomorphic or equivalent under the local Clifford group have the same properties. In this paper, we first establish a bound on the number of graph states which are neither isomorphic nor equivalent under the action of local Clifford group. Also, we study graph states in non-binary case. We translate the action of local Clifford group, as well as measurement of Pauli operators, into transformations on their associated graphs. Finally, we present an efficient algorithm to verify whether two graph states, in non-binary case, are locally equivalent or not.

arXiv:quant-ph/0610267•Oct 31, 2006•74 citations

Polynomial-time local-unitary equivalence of graph states

Yuxuan Zhang

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.

quant-pharXiv:2610.00527•Oct 2, 2026•0 citations

Efficient algorithm to recognize the local Clifford equivalence of graph states

Maarten Van den Nest, Jeroen Dehaene, Bart De Moor

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.

arXiv:quant-ph/0405023•Physical Review A•Sep 17, 2004•86 citations

Local Equivalences of Graph States

Nathan Claudet

Graph states form a large family of quantum states that are in one-to-one correspondence with mathematical graphs. Graph states are used in many applications, such as measurement-based quantum computation, as multipartite entangled resources. It is thus crucial to understand when two such states have the same entanglement, i.e. when they can be transformed into each other using only local operations. In this case, we say that the graph states are LU-equivalent (local unitary). If the local operations are restricted to the so-called Clifford group, we say that the graph states are LC-equivalent (local Clifford). Interestingly, a simple graph rule called local complementation fully captures LC-equivalence, in the sense that two graph states are LC-equivalent if and only if the underlying graphs are related by a sequence of local complementations. While it was once conjectured that two LU-equivalent graph states are always LC-equivalent, counterexamples do exist and local complementation fails to fully capture the entanglement of graph states. We introduce in this thesis a generalization of local complementation that does fully capture LU-equivalence. Using this characterization, we prove the existence of an infinite strict hierarchy of local equivalences between LC- and LU-equivalence. This also leads to the design of a quasi-polynomial algorithm for deciding whether two graph states are LU-equivalent, and to a proof that two LU-equivalent graph states are LC-equivalent if they are defined on at most 19 qubits. Furthermore, we study graph states that are universal in the sense that any smaller graph state, defined on any small enough set of qubits, can be induced using only local operations. We provide bounds and an optimal, probabilistic construction.

quant-pharXiv:2511.22271•Nov 28, 2025•4 citations

Graph states and the variety of principal minors

Vincenzo Galgano, Frédéric Holweck

Abstract In Quantum Information theory, graph states are quantum states defined by graphs. In this work we exhibit a correspondence between orbits of graph states and orbits in the variety of binary symmetric principal minors, under the action of SL $$(2,{\mathbb {F}}_2)^{\times n}\rtimes {\mathfrak {S}}_n$$ ( 2 , F 2 ) × n ⋊ S n . First we study the orbits of maximal abelian subgroups of the n-fold Pauli group under the action of $${\mathcal {C}}_n^{\textrm{loc}}\rtimes {\mathfrak {S}}_n$$ C n loc ⋊ S n , where $${\mathcal {C}}_n^{\textrm{loc}}$$ C n loc is the n-fold local Clifford group, and we show that this action corresponds to the natural action of SL $$(2,{\mathbb {F}}_2)^{\times n}\rtimes {\mathfrak {S}}_n$$ ( 2 , F 2 ) × n ⋊ S n on the variety $${\mathcal {Z}}_n\subset {\mathbb {P}}({\mathbb {F}}_2^{2^n})$$ Z n ⊂ P ( F 2 2 n ) of principal minors of binary symmetric $$n\times n$$ n × n matrices: the crucial step is in translating the action of SL $$(2,{\mathbb {F}}_2)^{\times n}$$ ( 2 , F 2 ) × n into an action of the local symplectic group Sp $$_{2n}^{\textrm{loc}}({\mathbb {F}}_2)$$ 2 n loc ( F 2 ) . We conclude by showing how the former action restricts onto stabilizer groups, stabilizer states and graph states.

arXiv:2107.02479•Annali di Matematica Pura ed Applicata (1923 -)•Jul 28, 2023•1 citation

Algorithm to Verify Local Equivalence of Stabilizer States

Adam Burchardt, Jarn de Jong, Lina Vandré

We present an algorithm for verifying the local unitary (LU) equivalence of graph and stabilizer states. Our approach reduces the problem to solving a system of linear equations in modular arithmetic. Furthermore, we demonstrate that any LU transformation between two graph states takes a specific form, naturally generalizing the class of local Clifford (LC) transformations. Lastly, using existing libraries, we verify that for up to $n=11$, the number of LU and LC orbits of stabilizer states is identical.

arXiv:2410.03961•Oct 4, 2024•11 citations
Graph states are quantum states (quantum codes) in qn-dimensional space ... (q being a power of some prime number) which can be described by graphs with edges labeled from the field of order q, Fq. Graph states are determined as a common eigenvector of independent elements of the n-fold Pauli group, on which the local Clifford group has a natural action. This action induces the natural action of the local Clifford group on graph states and hence, its action on graphs. Locally equivalent graphs can be described using this action. For q being a prime number, two graphs are locally equivalent when they are located on the same orbit of this action, in other words, when there is an element of the local Clifford group mapping one graph to the other one. When q is some power of a prime number, the definition of this action is the natural generalization of this action in the case where q is prime. We translate the action of local Clifford groups on graphs to a set of linear and quadratic equations in the field F,. In the case that q is an odd number, given two arbitrary graphs, we present an efficient algorithm (polynomial in n) to verify whether these graphs are locally equivalent or not. Moreover, we present a computational method to calculate the number of inequivalent graph states. We give some estimations on the size of the orbits of this action on graphs, and prove that when either q is equal to 2 or is an odd number, the number of inequivalent quantum codes (i.e., the number of classes of equivalency) is equal to ..., which is essentially as large as the total number of graphs.
Graph states are well-entangled quantum states that are defined based on a graph. Of course, if two graphs are isomorphic their associated states are the same. Also, we know local operations do not change the entanglement of quantum states. Therefore, graph states that are either isomorphic or equivalent under the local Clifford group have the same properties. In this paper, we first establish a bound on the number of graph states which are neither isomorphic nor equivalent under the action of local Clifford group. Also, we study graph states in non-binary case. We translate the action of local Clifford group, as well as measurement of Pauli operators, into transformations on their associated graphs. Finally, we present an efficient algorithm to verify whether two graph states, in non-binary case, are locally equivalent or not.
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 nnn labelled vertices in O~(n6.38)\widetilde O(n^{6.38})O(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 O~(n5)\widetilde O(n^5)O(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.
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.
Graph states form a large family of quantum states that are in one-to-one correspondence with mathematical graphs. Graph states are used in many applications, such as measurement-based quantum computation, as multipartite entangled resources. It is thus crucial to understand when two such states have the same entanglement, i.e. when they can be transformed into each other using only local operations. In this case, we say that the graph states are LU-equivalent (local unitary). If the local operations are restricted to the so-called Clifford group, we say that the graph states are LC-equivalent (local Clifford). Interestingly, a simple graph rule called local complementation fully captures LC-equivalence, in the sense that two graph states are LC-equivalent if and only if the underlying graphs are related by a sequence of local complementations. While it was once conjectured that two LU-equivalent graph states are always LC-equivalent, counterexamples do exist and local complementation fails to fully capture the entanglement of graph states. We introduce in this thesis a generalization of local complementation that does fully capture LU-equivalence. Using this characterization, we prove the existence of an infinite strict hierarchy of local equivalences between LC- and LU-equivalence. This also leads to the design of a quasi-polynomial algorithm for deciding whether two graph states are LU-equivalent, and to a proof that two LU-equivalent graph states are LC-equivalent if they are defined on at most 19 qubits. Furthermore, we study graph states that are universal in the sense that any smaller graph state, defined on any small enough set of qubits, can be induced using only local operations. We provide bounds and an optimal, probabilistic construction.
Abstract In Quantum Information theory, graph states are quantum states defined by graphs. In this work we exhibit a correspondence between orbits of graph states and orbits in the variety of binary symmetric principal minors, under the action of SL (2,F2)×n⋊Sn(2,{\mathbb {F}}_2)^{\times n}\rtimes {\mathfrak {S}}_n(2,F2​)×n⋊Sn​ ( 2 , F 2 ) × n ⋊ S n . First we study the orbits of maximal abelian subgroups of the n-fold Pauli group under the action of Cnloc⋊Sn{\mathcal {C}}_n^{\textrm{loc}}\rtimes {\mathfrak {S}}_nCnloc​⋊Sn​ C n loc ⋊ S n , where Cnloc{\mathcal {C}}_n^{\textrm{loc}}Cnloc​ C n loc is the n-fold local Clifford group, and we show that this action corresponds to the natural action of SL (2,F2)×n⋊Sn(2,{\mathbb {F}}_2)^{\times n}\rtimes {\mathfrak {S}}_n(2,F2​)×n⋊Sn​ ( 2 , F 2 ) × n ⋊ S n on the variety Zn⊂P(F22n){\mathcal {Z}}_n\subset {\mathbb {P}}({\mathbb {F}}_2^{2^n})Zn​⊂P(F22n​) Z n ⊂ P ( F 2 2 n ) of principal minors of binary symmetric n×nn\times nn×n n × n matrices: the crucial step is in translating the action of SL (2,F2)×n(2,{\mathbb {F}}_2)^{\times n}(2,F2​)×n ( 2 , F 2 ) × n into an action of the local symplectic group Sp 2nloc(F2)_{2n}^{\textrm{loc}}({\mathbb {F}}_2)2nloc​(F2​) 2 n loc ( F 2 ) . We conclude by showing how the former action restricts onto stabilizer groups, stabilizer states and graph states.
We present an algorithm for verifying the local unitary (LU) equivalence of graph and stabilizer states. Our approach reduces the problem to solving a system of linear equations in modular arithmetic. Furthermore, we demonstrate that any LU transformation between two graph states takes a specific form, naturally generalizing the class of local Clifford (LC) transformations. Lastly, using existing libraries, we verify that for up to n=11n=11n=11, the number of LU and LC orbits of stabilizer states is identical.