Complexity of graph-state preparation by Clifford circuits

Quantum 10, 2165 (2026).

https://doi.org/10.22331/q-2026-07-18-2165

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 $|Grangle$ as the minimum number of two-qubit Clifford operations required to generate $|Grangle$ from $|0rangle^{otimes (n+s)}$ for some $sge 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, $|Grangle$ can be generated from another graph state $|Hrangle$ 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(rn)$, 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(nlog n)$, respectively.