Complexity of graph-state preparation by Clifford circuits

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