Complexity of graph-state preparation by Clifford circuits

In this work, we study the complexity of graph-state preparation. We consider general quantum algorithms consisting of Clifford operations acting on at most two qubits for graph-state preparations. We define the CZ-complexity of a graph state $\mathrm{\mid }G⟩$ as the minimum number of two-qubit Clifford operations (excluding single-qubit Clifford operations) for generating $\mathrm{\mid }G⟩$ from a trivial state $\mathrm{\mid }0{⟩}^{\otimes n}$. We first prove that a graph state $\mathrm{\mid }G⟩$ is generated by at most $t$ two-qubit Clifford operations if and only if $\mathrm{\mid }G⟩$ is generated by at most $t$ controlled-Z (CZ) operations. We next prove that a graph state $\mathrm{\mid }G⟩$ is generated from another graph state $\mathrm{\mid }H⟩$ by $t$ CZ operations if and only if the graph $G$ is generated from $H$ by some combinatorial graph transformation with cost $t$. As the main results, we show a connection between the CZ-complexity of graph state $\mathrm{\mid }G⟩$ and the rank-width of the graph $G$. Indeed, we prove that for any graph $G$ with $n$ vertices and rank-width $r$, 1. The CZ-complexity of $\mathrm{\mid }G⟩$ is $O(rn)$. 2. If $G$ is connected, the CZ-complexity of $\mathrm{\mid }G⟩$ is at least $n+r-2$. We also demonstrate the existence of graph states whose CZ-complexities are close to the upper and lower bounds. Finally, we present quantum algorithms for preparing graph states for three specific graph classes related to intervals: interval graphs, interval containment graphs, and circle graphs. We prove that the CZ-complexity is $O(n)$ for interval graphs, and $O(n\log n)$ for both interval containment graphs and circle graphs.