  In this work, we study a complexity of graph-state preparation. We consider
general quantum algorithms consisting of the Clifford operations on at most two
qubits for graph-state preparations. We define the CZ-complexity of graph state
$|G\rangle$ as the minimum number of two-qubit Clifford operations (excluding
single-qubit Clifford operations) for generating $|G\rangle$ from a trivial
state $|0\rangle^{\otimes n}$. We first prove that a graph state $|G\rangle$ is
generated by at most $t$ two-qubit Clifford operations if and only if
$|G\rangle$ is generated by at most $t$ controlled-Z (CZ) operations. We next
prove that a graph state $|G\rangle$ is generated from another graph state
$|H\rangle$ 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
$|G\rangle$ 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 $|G\rangle$ is $O(rn\log n)$.
  2. If $G$ is connected, the CZ-complexity of $|G\rangle$ is at least $n + r -
2$.
  We also show the existence of graph states whose CZ-complexities are close to
the upper and lower bounds. Finally, we present quantum algorithms preparing
$|G\rangle$ with $O(n)$ CZ-complexity when $G$ is included in special classes
of graphs, namely, cographs, interval graphs, permutation graphs and circle
graphs.
