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:2402.05874 · Quantum

Complexity of graph-state preparation by Clifford circuits

Soh Kumabe, Ryuhei Mori, Yusei Yoshimura

Published Jul 18, 2026• 15 citations
arXivHTMLPDF

Abstract

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.

DOI
10.22331/q-2026-07-18-2165

Related papers

Optimal preparation of graph states

Adán Cabello, Lars Eirik Danielsen, Antonio J. López-Tarrida +1 more

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.

arXiv:1011.5464•Physical Review A•Apr 12, 2011•50 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

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

Transforming graph states using single-qubit operations

Axel Dahlberg, Stephanie Wehner

Stabilizer states form an important class of states in quantum information, and are of central importance in quantum error correction. Here, we provide an algorithm for deciding whether one stabilizer (target) state can be obtained from another stabilizer (source) state by single-qubit Clifford operations (LC), single-qubit Pauli measurements (LPM) and classical communication (CC) between sites holding the individual qubits. What is more, we provide a recipe to obtain the sequence of LC+LPM+CC operations which prepare the desired target state from the source state, and show how these operations can be applied in parallel to reach the target state in constant time. Our algorithm has applications in quantum networks, quantum computing, and can also serve as a design tool—for example, to find transformations between quantum error correcting codes. We provide a software implementation of our algorithm that makes this tool easier to apply. A key insight leading to our algorithm is to show that the problem is equivalent to one in graph theory, which is to decide whether some graph G ′ is a vertex-minor of another graph G . The vertex-minor problem is, in general, -Complete, but can be solved efficiently on graphs which are not too complex. A measure of the complexity of a graph is the rank-width which equals the Schmidt-rank width of a subclass of stabilizer states called graph states, and thus intuitively is a measure of entanglement. Here, we show that the vertex-minor problem can be solved in time O (| G | 3 ), where | G | is the size of the graph G , whenever the rank-width of G and the size of G ′ are bounded. Our algorithm is based on techniques by Courcelle for solving fixed parameter tractable problems, where here the relevant fixed parameter is the rank width. The second half of this paper serves as an accessible but far from exhausting introduction to these concepts, that could be useful for many other problems in quantum information. This article is part of a discussion meeting issue ‘Foundations of quantum mechanics and their impact on contemporary society’.

arXiv:1805.05305•Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences•May 28, 2018•65 citations

A combinatorial framework for clustering graph states: Algorithms and hardness for rank-integrity

Romain Bourneuf, Nathan Claudet, Sang Yoon Kim +3 more

We introduce a new notion of distance between two graph states $|G\rangle$ and $|G'\rangle$ on the same set of qubits. This distance is the minimum number of ancilla qubits in a graph state $|\widehat{G}\rangle$ from which both $|G\rangle$ and $|G'\rangle$ can be ``easily prepared''. (When preparing graph states, we are only allowed to use one-qubit Clifford gates, one-qubit Pauli measurements, and classical communication.) We give a graphical description of this distance through the lens of vertex-minors. We then show how this distance yields quantum network analogs of many graph edit-distance problems. Using this framework, we develop classical algorithms for identifying the ``highly entangled clusters'' of a graph state $|G\rangle$. The ancilla integrity problem asks, given a graph $G$ and integer $k$, for the minimum -- over all graph states $|G'\rangle$ with distance at most $k$ from $|G\rangle$ -- of the maximum component size of $G'$. Up to a factor of $2$ in the number of ancilla qubits, this problem is equivalent to rank integrity, where the distance between $G$ and $G'$ is instead the minimum rank of the sum of their adjacency matrices over $\text{GF}(2)$. We prove that rank integrity is XP parameterized by $k$. We also prove the complementary hardness result that rank integrity is W[1]-hard in $k$. Finally, we give an explicit $\mathcal{O}(n^6)$-time algorithm for ancilla integrity when $G$ has $n$ vertices and $k=1$.

cs.DSCross-listedarXiv:2607.09469•Jul 13, 2026•2 citations

Improvements of the classical simulation of quantum circuits: Using graph states with local Cliffords

Matthijs S. C. Rijlaarsdam

With this thesis project, we improve the classical simulation of quantum computers using stabilizers in the GSLC formalism. We do this in two ways: we present new algorithms that speed up their simulation and extend their applicability by defining new operations and subroutines for existing general circuit simulation using GSLC. To be precise: we present multiple new algorithms that speed up the simulation of the CZ gates, the most computationally expensive quantum operation in GSLC formalism. We define two new operations on GSLC that are useful when simulating stabilizer circuits: calculating fidelity (a measure of 'closeness' between two quantum states), and tracing out qubits (throwing away the information about the state contained in these qubits) from a GSLC. Finally, we present a new GSLC-based subroutine for a state of the art general quantum circuit simulation algorithm by Bravyi et al. that allows for the usage of the faster CZ algorithms. We show that the GSLC formalism can give a speedup in practical simulation tasks by evaluating the complexity of simulating an algorithm with possible applications on near-term quantum hardware: the quantum approximate optimization algorithm.

•Jan 1, 2020•0 citations
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.
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.
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.
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.
Stabilizer states form an important class of states in quantum information, and are of central importance in quantum error correction. Here, we provide an algorithm for deciding whether one stabilizer (target) state can be obtained from another stabilizer (source) state by single-qubit Clifford operations (LC), single-qubit Pauli measurements (LPM) and classical communication (CC) between sites holding the individual qubits. What is more, we provide a recipe to obtain the sequence of LC+LPM+CC operations which prepare the desired target state from the source state, and show how these operations can be applied in parallel to reach the target state in constant time. Our algorithm has applications in quantum networks, quantum computing, and can also serve as a design tool—for example, to find transformations between quantum error correcting codes. We provide a software implementation of our algorithm that makes this tool easier to apply. A key insight leading to our algorithm is to show that the problem is equivalent to one in graph theory, which is to decide whether some graph G ′ is a vertex-minor of another graph G . The vertex-minor problem is, in general, -Complete, but can be solved efficiently on graphs which are not too complex. A measure of the complexity of a graph is the rank-width which equals the Schmidt-rank width of a subclass of stabilizer states called graph states, and thus intuitively is a measure of entanglement. Here, we show that the vertex-minor problem can be solved in time O (| G | 3 ), where | G | is the size of the graph G , whenever the rank-width of G and the size of G ′ are bounded. Our algorithm is based on techniques by Courcelle for solving fixed parameter tractable problems, where here the relevant fixed parameter is the rank width. The second half of this paper serves as an accessible but far from exhausting introduction to these concepts, that could be useful for many other problems in quantum information. This article is part of a discussion meeting issue ‘Foundations of quantum mechanics and their impact on contemporary society’.
We introduce a new notion of distance between two graph states ∣G⟩|G\rangle∣G⟩ and ∣G′⟩|G'\rangle∣G′⟩ on the same set of qubits. This distance is the minimum number of ancilla qubits in a graph state ∣G^⟩|\widehat{G}\rangle∣G⟩ from which both ∣G⟩|G\rangle∣G⟩ and ∣G′⟩|G'\rangle∣G′⟩ can be ``easily prepared''. (When preparing graph states, we are only allowed to use one-qubit Clifford gates, one-qubit Pauli measurements, and classical communication.) We give a graphical description of this distance through the lens of vertex-minors. We then show how this distance yields quantum network analogs of many graph edit-distance problems. Using this framework, we develop classical algorithms for identifying the ``highly entangled clusters'' of a graph state ∣G⟩|G\rangle∣G⟩. The ancilla integrity problem asks, given a graph GGG and integer kkk, for the minimum -- over all graph states ∣G′⟩|G'\rangle∣G′⟩ with distance at most kkk from ∣G⟩|G\rangle∣G⟩ -- of the maximum component size of G′G'G′. Up to a factor of 222 in the number of ancilla qubits, this problem is equivalent to rank integrity, where the distance between GGG and G′G'G′ is instead the minimum rank of the sum of their adjacency matrices over GF(2)\text{GF}(2)GF(2). We prove that rank integrity is XP parameterized by kkk. We also prove the complementary hardness result that rank integrity is W[1]-hard in kkk. Finally, we give an explicit O(n6)\mathcal{O}(n^6)O(n6)-time algorithm for ancilla integrity when GGG has nnn vertices and k=1k=1k=1.
With this thesis project, we improve the classical simulation of quantum computers using stabilizers in the GSLC formalism. We do this in two ways: we present new algorithms that speed up their simulation and extend their applicability by defining new operations and subroutines for existing general circuit simulation using GSLC. To be precise: we present multiple new algorithms that speed up the simulation of the CZ gates, the most computationally expensive quantum operation in GSLC formalism. We define two new operations on GSLC that are useful when simulating stabilizer circuits: calculating fidelity (a measure of 'closeness' between two quantum states), and tracing out qubits (throwing away the information about the state contained in these qubits) from a GSLC. Finally, we present a new GSLC-based subroutine for a state of the art general quantum circuit simulation algorithm by Bravyi et al. that allows for the usage of the faster CZ algorithms. We show that the GSLC formalism can give a speedup in practical simulation tasks by evaluating the complexity of simulating an algorithm with possible applications on near-term quantum hardware: the quantum approximate optimization algorithm.