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

arXiv:1011.5464 · Physical Review A

Optimal preparation of graph states

Adán Cabello, Lars Eirik Danielsen, Antonio J. López-Tarrida, José R. Portillo

Published Apr 12, 2011• 41 citations
arXivHTMLPDF

Abstract

We show how to prepare any graph state of up to 12 qubits with (a) the minimum number of controlled-$Z$ gates and (b) the minimum preparation depth. We assume only one-qubit and controlled-$Z$ gates. The method exploits the fact that any graph state belongs to an equivalence class under local Clifford operations. We extend up to 12 qubits the classification of graph states according to their entanglement properties, and identify each class using only a reduced set of invariants. For any state, we provide a circuit with both properties (a) and (b), if it does exist, or, if it does not, one circuit with property (a) and one with property (b), including the explicit one-qubit gates needed.

DOI
10.1103/physreva.83.042314

Related papers

Complexity of graph-state preparation by Clifford circuits

Soh Kumabe, Ryuhei Mori, Yusei Yoshimura

In this work, we study the complexity of graph-state preparation in a general model of quantum algorithms that allows measurements in the computational basis, single-qubit Clifford operations, and two-qubit Clifford operations. We define the CZ-complexity of a graph state | G ⟩ as the minimum number of two-qubit Clifford operations required to generate | G ⟩ from | 0 ⟩ ⊗ ( n + s ) for some s ≥ 0 . Equivalently, every optimal algorithm can be taken to use only controlled-Z (CZ) gates as its two-qubit Clifford operations. We then give a combinatorial characterization of graph-state transformations. Specifically, | G ⟩ can be generated from another graph state | H ⟩ by an algorithm of CZ-complexity at most t if and only if G can be obtained from H by vertex deletions, local complementations and at most t elementary edge-complementations. Here, an elementary edge-complementation toggles either a single edge, all edges between one vertex and the neighborhood of another, or all edges between the neighborhoods of two non-adjacent vertices. Using this characterization, we relate CZ-complexity to rank-width. For any graph G with n vertices and rank-width r , the CZ-complexity is O ( r n ) , and if G is connected then it is at least n + r − 2 . We also show that these bounds are close to optimal. Finally, for interval graphs and circle graphs, whose rank-width is unbounded, we present preparation algorithms with CZ-complexity O ( n ) and O ( n log ⁡ n ) , respectively.

arXiv:2402.05874•Quantum•Jul 18, 2026•1 citation

Compact set of invariants characterizing graph states of up to eight qubits

Adán Cabello, Antonio J. López-Tarrida, Pilar Moreno +1 more

The set of entanglement measures proposed by Hein, Eisert, and Briegel for $n$-qubit graph states [Phys. Rev. A 69, 062311 (2004)] fails to distinguish between inequivalent classes under local Clifford operations if $n\ensuremath{\ge}7$. On the other hand, the set of invariants proposed by van den Nest, Dehaene, and De Moor (VDD) [Phys. Rev. A 72, 014307 (2005)] distinguishes between inequivalent classes, but contains too many invariants (more than $2\ifmmode\times\else\texttimes\fi{}{10}^{36}$ for $n=7$) to be practical. Here we solve the problem of deciding which entanglement class a graph state of $n\ensuremath{\le}8$ qubits belongs to by calculating some of the state's intrinsic properties. We show that four invariants related to those proposed by VDD are enough for distinguishing between all inequivalent classes with $n\ensuremath{\le}8$ qubits.

arXiv:0904.3551•Physical Review A•Jul 1, 2009•13 citations

Distinguishing graph states by the properties of their marginals

Lina Vandré, Jarn de Jong, Frederik Hahn +3 more

Graph states are a class of multipartite entangled quantum states that are ubiquitous in quantum information. We study equivalence relations between graph states under local unitaries (LU) to obtain distinguishing methods both in local and in networked settings. Based on the marginal structure of graph states, we introduce a family of easy-to-compute LU invariants. We show that these invariants uniquely identify the entanglement classes of every graph state up to eight qubits and discuss their reliability for larger numbers of qubits. To handle larger graphs, we generalize tools to test for local Clifford (LC) equivalence of graph states that work by condensing large graphs into smaller graphs. In turn, we show that statements on the equivalence of these smaller graphs (which are easier to compute) can be used to infer statements on the equivalence of the original, larger graphs. We analyze LU equivalence in two key settings, with and without allowing for the permutation of qubits. We identify entanglement classes, whose marginal structure does not allow us to distinguish them. As a result, we increase the bound on the number of qubits where the LU-LC conjecture holds from 8 to 10 qubits in the setting where qubit permutations are allowed.

arXiv:2406.09956•Physical Review A•May 28, 2025•5 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

Fast stabilizer state preparation via AI-optimized graph decimation

Michael Doherty, Matteo Puviani, Jasmine Brewer +4 more

We propose a general method for preparing stabilizer states with reduced two-qubit gate count and depth compared to the state of the art. The method starts from a graph state representation of the stabilizer state and iteratively reduces the number of edges in the graph using two-qubit Clifford gates to produce a unitary preparation circuit. We explore various heuristic search and AI-based approaches to optimally choose Clifford gates at each step, the most sophisticated of which is a combination of reinforcement learning and Monte Carlo tree search that we call QuSynth. We apply our method to synthesize code states of various quantum error correcting codes including the 23-qubit Golay code and the 144-qubit gross code, the latter of which is significantly beyond the qubit number that is accessible to prior optimal circuit synthesis methods. We demonstrate that our techniques are capable of reducing the required two-qubit gates by up to a factor of 2.5 compared to previous approaches while retaining low circuit depth.

quant-pharXiv:2603.17743•Mar 19, 2026•1 citation

Distinguishing graph states by the properties of their marginals

Lina Vandré, Jarn de Jong, Frederik Hahn +3 more

Graph states are a class of multipartite entangled quantum states that are ubiquitous in quantum information. We study equivalence relations between graph states under local unitaries (LU) to obtain distinguishing methods both in local and in networked settings. Based on the marginal structure of graph states, we introduce a family of easy-to-compute LU invariants. We show that these invariants uniquely identify the entanglement classes of every graph state up to eight qubits and discuss their reliability for larger numbers of qubits. To handle larger graphs, we generalize tools to test for local Clifford (LC) equivalence of graph states that work by condensing large graphs into smaller graphs. In turn, we show that statements on the equivalence of these smaller graphs (which are easier to compute) can be used to infer statements on the equivalence of the original, larger graphs. We analyze LU equivalence in two key settings, with and without allowing for the permutation of qubits. We identify entanglement classes, whose marginal structure does not allow us to distinguish them. As a result, we increase the bound on the number of qubits where the LU-LC conjecture holds from 8 to 10 qubits in the setting where qubit permutations are allowed.

•May 28, 2025•0 citations
We show how to prepare any graph state of up to 12 qubits with (a) the minimum number of controlled-ZZZ gates and (b) the minimum preparation depth. We assume only one-qubit and controlled-ZZZ gates. The method exploits the fact that any graph state belongs to an equivalence class under local Clifford operations. We extend up to 12 qubits the classification of graph states according to their entanglement properties, and identify each class using only a reduced set of invariants. For any state, we provide a circuit with both properties (a) and (b), if it does exist, or, if it does not, one circuit with property (a) and one with property (b), including the explicit one-qubit gates needed.
In this work, we study the complexity of graph-state preparation in a general model of quantum algorithms that allows measurements in the computational basis, single-qubit Clifford operations, and two-qubit Clifford operations. We define the CZ-complexity of a graph state | G ⟩ as the minimum number of two-qubit Clifford operations required to generate | G ⟩ from | 0 ⟩ ⊗ ( n + s ) for some s ≥ 0 . Equivalently, every optimal algorithm can be taken to use only controlled-Z (CZ) gates as its two-qubit Clifford operations. We then give a combinatorial characterization of graph-state transformations. Specifically, | G ⟩ can be generated from another graph state | H ⟩ by an algorithm of CZ-complexity at most t if and only if G can be obtained from H by vertex deletions, local complementations and at most t elementary edge-complementations. Here, an elementary edge-complementation toggles either a single edge, all edges between one vertex and the neighborhood of another, or all edges between the neighborhoods of two non-adjacent vertices. Using this characterization, we relate CZ-complexity to rank-width. For any graph G with n vertices and rank-width r , the CZ-complexity is O ( r n ) , and if G is connected then it is at least n + r − 2 . We also show that these bounds are close to optimal. Finally, for interval graphs and circle graphs, whose rank-width is unbounded, we present preparation algorithms with CZ-complexity O ( n ) and O ( n log ⁡ n ) , respectively.
The set of entanglement measures proposed by Hein, Eisert, and Briegel for nnn-qubit graph states [Phys. Rev. A 69, 062311 (2004)] fails to distinguish between inequivalent classes under local Clifford operations if $n\ensuremath{\ge}7$. On the other hand, the set of invariants proposed by van den Nest, Dehaene, and De Moor (VDD) [Phys. Rev. A 72, 014307 (2005)] distinguishes between inequivalent classes, but contains too many invariants (more than $2\ifmmode\times\else\texttimes\fi{}{10}^{36}$ for n=7n=7n=7) to be practical. Here we solve the problem of deciding which entanglement class a graph state of $n\ensuremath{\le}8$ qubits belongs to by calculating some of the state's intrinsic properties. We show that four invariants related to those proposed by VDD are enough for distinguishing between all inequivalent classes with $n\ensuremath{\le}8$ qubits.
Graph states are a class of multipartite entangled quantum states that are ubiquitous in quantum information. We study equivalence relations between graph states under local unitaries (LU) to obtain distinguishing methods both in local and in networked settings. Based on the marginal structure of graph states, we introduce a family of easy-to-compute LU invariants. We show that these invariants uniquely identify the entanglement classes of every graph state up to eight qubits and discuss their reliability for larger numbers of qubits. To handle larger graphs, we generalize tools to test for local Clifford (LC) equivalence of graph states that work by condensing large graphs into smaller graphs. In turn, we show that statements on the equivalence of these smaller graphs (which are easier to compute) can be used to infer statements on the equivalence of the original, larger graphs. We analyze LU equivalence in two key settings, with and without allowing for the permutation of qubits. We identify entanglement classes, whose marginal structure does not allow us to distinguish them. As a result, we increase the bound on the number of qubits where the LU-LC conjecture holds from 8 to 10 qubits in the setting where qubit permutations are allowed.
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.
We propose a general method for preparing stabilizer states with reduced two-qubit gate count and depth compared to the state of the art. The method starts from a graph state representation of the stabilizer state and iteratively reduces the number of edges in the graph using two-qubit Clifford gates to produce a unitary preparation circuit. We explore various heuristic search and AI-based approaches to optimally choose Clifford gates at each step, the most sophisticated of which is a combination of reinforcement learning and Monte Carlo tree search that we call QuSynth. We apply our method to synthesize code states of various quantum error correcting codes including the 23-qubit Golay code and the 144-qubit gross code, the latter of which is significantly beyond the qubit number that is accessible to prior optimal circuit synthesis methods. We demonstrate that our techniques are capable of reducing the required two-qubit gates by up to a factor of 2.5 compared to previous approaches while retaining low circuit depth.
Graph states are a class of multipartite entangled quantum states that are ubiquitous in quantum information. We study equivalence relations between graph states under local unitaries (LU) to obtain distinguishing methods both in local and in networked settings. Based on the marginal structure of graph states, we introduce a family of easy-to-compute LU invariants. We show that these invariants uniquely identify the entanglement classes of every graph state up to eight qubits and discuss their reliability for larger numbers of qubits. To handle larger graphs, we generalize tools to test for local Clifford (LC) equivalence of graph states that work by condensing large graphs into smaller graphs. In turn, we show that statements on the equivalence of these smaller graphs (which are easier to compute) can be used to infer statements on the equivalence of the original, larger graphs. We analyze LU equivalence in two key settings, with and without allowing for the permutation of qubits. We identify entanglement classes, whose marginal structure does not allow us to distinguish them. As a result, we increase the bound on the number of qubits where the LU-LC conjecture holds from 8 to 10 qubits in the setting where qubit permutations are allowed.