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 $\ket{G}$ as the minimum number of two-qubit Clifford operations (excluding single-qubit Clifford operations) for generating $\ket{G}$ from a trivial state $\ket{0}^{\otimes n}$.

We first prove that a graph state $\ket{G}$ is generated by at most $t$ two-qubit Clifford operations if and only if
$\ket{G}$ is generated by at most $t$ controlled-Z (CZ) operations.
We next prove that a graph state $\ket{G}$ is generated from another graph state $\ket{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 $\ket{G}$ and the rank-width of the graph $G$.
Indeed, we prove that for any graph $G$ with $n$ vertices and rank-width $r$,

* The CZ-complexity of $\ket{G}$ is $O(rn\log n)$.

* If $G$ is connected, the CZ-complexity of $\ket{G}$ 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 $\ket{G}$ with $O(n)$ CZ-complexity when $G$ is included in special classes of graphs, namely, cographs, interval graphs, permutation graphs and circle graphs.

§ INTRODUCTION

The set of stabilizer states is a large class of quantum states used in quantum information processing.
The set of graph states is a subclass of stabilizer states represented by an undirected graph.
Any stabilizer state can be transformed to a graph state by local-Clifford operations [30].
Hence, it is important to develop efficient quantum algorithms preparing graph states since
any stabilizer state can be transformed from some graph state by local-Clifford operations.
Properties of graph states have been studied so far [12, 29, 19, 30, 15, 11, 14, 1].

In general, any stabilizer state can be generated from $\ket{0}^{\otimes n}$ by an $n$-qubit Clifford operation.
Any $n$-qubit Clifford operation is generated by single-qubit Clifford operations and two-qubit Clifford operations.
For example, commonly used generator of the Clifford group is the $S$, $H$ and $CZ$ gates.
In this work, we study a complexity of graph-state preparation.
While there are several implementations of quantum computing, e.g., superconductor, trapped-ion, etc.,
we are interested in complexity measures that capture universal difficulties of the graph-state preparation.
The implementations of two-qubit operations are generally challenging so that
we define the complexity of graph states as follows.

Let $\mathcal{A}$ be a quantum algorithm
that consists of the following operations.

* Measurements of qubits by the computational basis.

* Single-qubit Clifford operations.

* Two-qubit Clifford operations.

Here, we assume that measured qubits disappear in quantum algorithms.
After the measurements of some qubits, the algorithm can choose the subsequent operations depending on the measurement outcome.
The CZ-complexity of $\mathcal{A}$ is defined as the maximum number (with respect to the measurement outcome) of two-qubit Clifford operations in $\mathcal{A}$.
The CZ-complexity $\NCZ(\ket{G})$ of graph state $\ket{G}$ is defined as the minimum CZ-complexity of $\mathcal{A}$
that generates the $n$-qubit graph state $\ket{G}$ from $\ket{0}^{\otimes (n+s)}$ with probability 1 for some $s\ge 0$.

There is a simple quantum algorithm generating an $n$-qubit graph state $\ket{G}$.
First, prepare $\ket{+}^{\otimes n}$, which corresponds to the graph state for the empty graph of $n$ vertices.
Here, each qubit corresponds to each vertex of $G$.
Then, for each edge of $G$, apply the controlled-Z (CZ) operation for the corresponding pair of qubits.
This quantum algorithm generates $\ket{G}$ with $m$ two-qubit Clifford operations where $m$ is the number of edges in $G$.

Van den Nest, Dehaene, and De Moor proved that two graph states $\ket{G}$ and $\ket{H}$ are transformed
to each other by local Clifford operations if and only if $G$ and $H$ are transformed to each other
by some combinatorial graph transformations, called local complementations [30].
The local complementation for a vertex $v$ is an operation that complement edges for all pairs of the neighborhoods of $v$.
The local complementation reduces the number of edges of graphs in some cases.
For example, the complete graph $K_n$ can be transformed to the star graph $S_{n-1}$ by the local complementation.
This means that $\ket{K_n}$ is generated from $\ket{S_{n-1}}$ by local Clifford operations.
Since $S_{n-1}$ has $n-1$ edges, $\ket{S_{n-1}}$ can be generated with $n-1$ two-qubit Clifford operations.
Hence, the CZ-complexity of $\ket{K_n}$ is at most $n-1$
(Indeed, this is a lower bound for any connected graph as well).
This example shows that local Clifford operations are useful for reducing the number of two-qubit Clifford operations.
As another important example, Figure <ref> shows that the cycle graph $C_4$ of size four can be transformed to the path graph $P_4$ of size four by the local complementations.
Note that we do not allow to use local non-Clifford operations in Definition <ref>
although they are generally stronger than local Clifford operations [21].

[circle,minimum size=15,draw,very thick] (a) at (0:4) ;
[circle,minimum size=15,draw,very thick] (b) at (90: 4) ;
[circle,minimum size=15,draw,very thick,fill=red] (c) at (180: 4) ;
[circle,minimum size=15,draw,very thick] (d) at (270: 4) ;
[-,very thick] (a) – (b);
[-,very thick] (b) – (c);
[-,very thick] (c) – (d);
[-,very thick] (d) – (a);

[circle,minimum size=15,draw,very thick] (a) at (0:4) ;
[circle,minimum size=15,draw,very thick,fill=red] (b) at (90: 4) ;
[circle,minimum size=15,draw,very thick] (c) at (180: 4) ;
[circle,minimum size=15,draw,very thick] (d) at (270: 4) ;
[-,very thick] (a) – (b);
[-,very thick] (b) – (c);
[-,very thick] (c) – (d);
[-,very thick] (d) – (a);
[-,very thick] (b) – (d);

[circle,minimum size=15,draw,very thick] (a) at (0:4) ;
[circle,minimum size=15,draw,very thick] (b) at (90: 4) ;
[circle,minimum size=15,draw,very thick,fill=red] (c) at (180: 4) ;
[circle,minimum size=15,draw,very thick] (d) at (270: 4) ;
[-,very thick] (a) – (b);
[-,very thick] (b) – (c);
[-,very thick] (b) – (d);
[-,very thick] (a) – (c);

[circle,minimum size=15,draw,very thick] (a) at (0:4) ;
[circle,minimum size=15,draw,very thick] (b) at (90: 4) ;
[circle,minimum size=15,draw,very thick] (c) at (180: 4) ;
[circle,minimum size=15,draw,very thick] (d) at (270: 4) ;
[-,very thick] (b) – (c);
[-,very thick] (b) – (d);
[-,very thick] (a) – (c);

$C_4$ and $P_4$ are local-complement equivalent. When the local complementations are applied for the filled vertices, graphs are transformed from $C_4$ to $P_4$.

[circle,draw,very thick] (a) at (90:0.4) ;
[circle,draw,very thick] (b) at (-150:0.4) ;
[circle,draw,very thick] (c) at (-30:0.4) ;
[circle,draw,very thick] (e) at (90:1) ;
[circle,draw,very thick] (f) at (-150:1) ;
[circle,draw,very thick] (g) at (-30:1) ;
[very thick] (a) – (b);
[very thick] (b) – (c);
[very thick] (c) – (a);
[very thick] (a) – (e);
[very thick] (b) – (f);
[very thick] (c) – (g);

[circle,draw,very thick] (a) at (0:0.7) ;
[circle,draw,very thick] (b) at (90:0.7) ;
[circle,draw,very thick] (c) at (180:0.7) ;
[circle,draw,very thick] (d) at (-90:0.7) ;
[circle,draw,very thick] (e) at (0:1.6) ;
[circle,draw,very thick] (f) at (180:1.6) ;
[very thick] (a) – (b);
[very thick] (b) – (c);
[very thick] (c) – (d);
[very thick] (d) – (a);
[very thick] (a) – (e);
[very thick] (c) – (f);

Graphs that have minimum number of edges among all graphs obtained by local complementations, and include cycles of size three or four.

From the above observations, we can consider a general strategy for designing low CZ-complexity quantum algorithms.
For a generation of $\ket{G}$, find a graph $H$ that has minimum number of edges among all graphs
that can be transformed to $G$ by local complementations.
Then, $\ket{H}$ can be generated with $m$ two-qubit operations where $m$ is the number of edges of $H$.
Finally, $\ket{G}$ can be generated from $\ket{H}$ by a local Clifford operation.
The CZ-complexities of algorithms based on this strategy were calculated for all graph states up to 12 qubit in [11].
In quantum algorithms of this type, the CZ operations are applied for $\ket{+}^{\otimes n}$ first, and then
a local-Clifford operation is applied.

In fact, the above simple strategy is not necessarily optimal.
Indeed, two graphs in Figure <ref> have six edges, which are minimum under the local-complementations [1].
However, these graphs can be generated with five operations since cycles of size three and four can be generated with two and three operations, respectively.[Interestingly, there exist graphs that have minimum number of edges among all graphs obtained by local complementations, and do not contain cycles of size three nor four, but can be generated more efficiently, e.g., No.131 in [1].]
The class of quantum algorithms in Definition <ref> is more general than quantum algorithms from the above strategy since any two-qubit Clifford operations rather than the CZ operations are allowed, and single-qubit Clifford operations and two-qubit Clifford operations can be applied in arbitrary order.
We first prove that we can assume without loss of generality that all two-qubit Clifford operations in graph-state preparation algorithms are the operations, so that the terminology of the CZ-complexity in Definition <ref> is justified.

For any graph $G$, there exists a quantum algorithm $\mathcal{A}$ generating $\ket{G}$
of the type in Definition <ref> with the CZ-complexity $\NCZ(\ket{G})$
where all two-qubit Clifford operations in $\mathcal{A}$ are the operations.

For a graph state $\ket{G}$, the operation corresponds to the edge complementation on $G$.
However, in quantum algorithms in Definition <ref>, the operations can be performed to a stabilizer state which may not be a graph state.
We prove a combinatorial characterization of graph state transformation with positive CZ-complexity.

For any graphs $G$ and $H$, $\ket{G}$ is generated from $\ket{H}$ with the CZ-complexity $t$
if and only if $G$ is transformed from $H$ with some combinatorial transformation of graphs with cost $t$, which is defined in Definition <ref>.

This combinatorial characterization can be regarded as a generalization of the combinatorial characterizations for $t=0$ [30, 14].
Theorem <ref> is obtained on the basis of the graphical description of the CZ operation on stabilizer states [15].

By using the above results, we find a connection between the CZ-complexity of graph state $\ket{G}$ and
the rank-width of $G$.
The rank-width is a complexity measure of graphs introduced by Oum and Seymour [24, 28].
We prove an upper bound and a lower bound of the CZ-complexity using the rank-width.

For any graph $G$ with $n$ vertices and rank-width $r$, $\NCZ(\ket{G})=O(rn\log n)$.

This upper bound is almost optimal due to the following lemma obtained by the information-theoretic counting arguments.

There exists a positive constant $c$ such that
for any positive integer $n$ and $r\le \lceil n/3\rceil$,
there exists a graph $G$ with $n$ vertices and rank-width at most $r$ such that $\NCZ(\ket{G})\ge crn/\log n$.

The lower bound using the rank-width is stated as follows.

For any connected graph $G$ with $n\ge 2$ vertices and rank-width at least $r$, $\NCZ(\ket{G})\ge n+r-2$.

For instance, the cycle graph $C_n$ with $n$ vertices and $n$ edges has rank-width 2 when $n\ge 5$.
Theorem <ref> implies that $\NCZ(\ket{C_n})=n$ for $n\ge 5$.
This is in contrasts to the fact $\NCZ(\ket{C_n})=n-1$ for $n=3,4$.
From the analysis of the rank-width of random sparse graphs [23], the following lemma is obtained.

There exists a constant $c\ge 1$ such that
for any $r'$ there exists $n'$ and $r\ge r'$
such that for any $n\ge n'$,
there exists a connected graph $G$ with $n$ vertices and rank-width $r$ satisfying $\NCZ(\ket{G})\le n - 1 + c (r-1)$.

This lemma shows that the lower bound $\NCZ(\ket{G})-(n-1)\ge r-1$ for a connected graph $G$ obtained by Theorem <ref> is optimal up to a constant factor.

It is natural to ask whether the rank-width is an appropriate choice of the complexity measure of graphs for bounding the CZ-complexity of graph states.
Similar upper bound to Theorem <ref> may be obtained from other complexity measures satisfying some properties required for the proof of Theorem <ref>.
On the other hand, for the proof of Theorem <ref>, the invariance under the local complementations is required for the complexity measure.
This requirement is strong so that
it seems not easy to obtain lower bounds of the CZ-complexity from other complexity measures of graphs
although the upper and lower bounds in Theorems <ref> and <ref> are not tight.

Finally, we present efficient quantum algorithms for special classes of graphs.

For any cograph $G$ with $n$ vertices, $\NCZ(\ket{G})\le (5/4)n-1$.
For any interval graph $G$ with $n$ vertices, $\NCZ(\ket{G})\le 2n-2$.
For any permutation graph $G$ with $n\ge 2$ vertices, $\NCZ(\ket{G})\le 5n-6$.
For any circle graph $G$ with $n$ vertices, $\NCZ(\ket{G})\le 10n-7$.

Note that the rank-widths of interval graph, permutation graph and circle graph are unbounded while the rank-width of cograph is one.

§.§ Related work

The graph state was introduced in [12],
and has been studied well so far [29, 19, 30, 15].

Before the introduction of graph states, Bouchet introduced, and has studied the isotropic systems, which is technically very similar to the stabilizer states [4, 5, 6, 7, 8, 9, 10].
Important notions in graph states, e.g., the local complementation, the pivoting, the vertex-minor, etc., has been studied in the above literature.
As an important result, Bouchet presented an $O(n^4)$-time algorithm to decide whether two graphs can be transformed to each other by the local complementations [8].
The notion of the local complementation was introduced by Kotzig in the context of Eulerian cycle of 4-regular graphs [22].
Fon-Der-Flaass also showed some properties of the local complementations [16].

Oum and Seymour introduced the rank-width [24, 28].
The rank-width is based on the cut-rank function, which was introduced, and called the connectivity function by Bouchet [3, 9].
Although the rank-width was originally introduced for approximating the clique-with,
it has own interesting features, and has been studied so far [26, 25, 28, 23].

Høyer, Mhalla, and Perdrix proved that any graph state can be prepared by a constant-depth Clifford circuit [20].

§.§ Organization

The rest of the paper is organized as follows.
In Section <ref>, notation and terminology on the stabilizer states and the Clifford group are introduced.
In Section <ref>, we introduce the graph states and the combinatorial characterizations of local Clifford operations and measurements on graph states, proved in previous work.
In Section <ref>, we prove Theorem <ref>, which implies that it is sufficient to use the operation in place of general two-qubit Clifford operations in graph state preparation algorithms.
In Section <ref>, we introduce the combinatorial characterization of two-qubit Clifford operations,
and prove Theorem <ref>.
In Section <ref>, the rank-width and its known properties are introduced.
The proofs of Lemmas <ref> and <ref> are given as well.
In Section <ref>, we prove Theorem <ref>.
In Section <ref>, we prove Theorem <ref>.
In Section <ref>, we prove Theorem <ref>.

§ STABILIZER STATES AND CLIFFORD GROUP

§.§ Stabilizer states

The Pauli matrices are defined as

\begin{align*}
I_2 &:= \begin{bmatrix}
\end{bmatrix},&
X &:= \begin{bmatrix}
\end{bmatrix},&
Y &:= \begin{bmatrix}
\end{bmatrix},&
Z &:= \begin{bmatrix}
\end{bmatrix}.
\end{align*}

The Pauli group $\mathcal{G}_n$ is defined as

\begin{align*}
\mathcal{G}_n &:= \bigl\{\alpha h_1\otimes h_2\otimes\dotsm\otimes h_n\mid \alpha \in\{\pm1,\pm i\},\quad
h_j\in \{I_2,X,Y,Z\}\ \forall j\in\{1,2,\dotsc,n\}\bigr\}.
\end{align*}

Let $S$ be a subset of $\mathcal{G}_n$ of size $n$ satisfying

* $\forall s\in S,\quad s^2 = I_2^{\otimes n}$.

* $\forall s, t\in S,\quad st=ts$.

* For $T\subseteq S,\quad \prod_{s\in T}s = \pm I_2^{\otimes n}$ only when $T=\varnothing$.

Then, there exists an one-dimensional subspace
$\bigl\{\ket{\psi}\in\mathbb{C}^{2^n}\mid s\ket{\psi}=\ket{\psi}\ \forall s\in S\bigr\}$.
Here, the quantum state in the subspace is called a stabilizer state
that is stabilized by the stabilizer $\langle S\rangle$.
Furthermore, $S$ is called the stabilizer generator.

From the condition $s^2=I_2^{\otimes n}$ for stabilizer generators, a stabilizer $\langle S\rangle$ must be a subset of

\begin{align*}
\mathcal{G}_n^\pm &:= \bigl\{\alpha h_1\otimes h_2\otimes\dotsm\otimes h_n\mid \alpha \in\{\pm1\},\quad
h_j\in \{I_2,X,Y,Z\}\ \forall j\in\{1,2,\dotsc,n\}\bigr\}.
\end{align*}

If $S=\{s_1,\dotsc, s_n\}\subseteq \mathcal{G}_n^\pm$ is a stabilizer generator,
then for any $v\in\{0,1\}^n$, $\{(-1)^{v_1}s_1,\dotsc, (-1)^{v_n}s_n\}\subseteq \mathcal{G}_n^\pm$ is also a stabilizer generator for some stabilizer state.
Stabilizers without the sign information are represented by $n\times 2n$ binary matrices.

There is an isomorphism between
$\mathcal{G}_n/\langle i I_2^{\otimes n}\rangle$ and $(\mathbb{Z}/2\mathbb{Z})^{2n}$.
For $n=1$, there is an isomorphism defined as

\begin{align*}
\sigma_{00}:=I_2 &\longleftrightarrow \begin{bmatrix}0&0\end{bmatrix},&
\sigma_{10}:=X &\longleftrightarrow \begin{bmatrix}1&0\end{bmatrix},&
\sigma_{11}:=Y &\longleftrightarrow \begin{bmatrix}1&1\end{bmatrix},&
\sigma_{01}:=Z &\longleftrightarrow \begin{bmatrix}0&1\end{bmatrix}.
\end{align*}

For general $n$, there is an isomorphism defined as

\begin{align*}
\sigma_{x_1z_1}\otimes \sigma_{x_2z_2}\otimes\dotsm \otimes\sigma_{x_nz_n} &\longleftrightarrow
\begin{bmatrix}
\cdots&
\cdots&
\end{bmatrix}.
\end{align*}

For $a\in(\mathbb{Z}/2\mathbb{Z})^{2n}$, the corresponding operator in $\mathcal{G}_n/\langle i I_2^{\otimes n}\rangle$ is denoted by $\sigma_a:=\sigma_{a_1a_{n+1}}\otimes\dotsm\otimes \sigma_{a_{n}a_{2n}}$.

For row vectors $a, b \in (\mathbb{Z}/2\mathbb{Z})^{2n}$, $\sigma_a$ and $\sigma_b$ commute if and only if

\begin{align*}
\begin{bmatrix}
\end{bmatrix}
\end{align*}

where $O_n$ and $I_n$ are the $n\times n$ zero matrix and identity matrix on the field $\mathbb{F}_2$.
For a set $A=\{a_1,\dotsc,a_n\}\subseteq (\mathbb{Z}/2\mathbb{Z})^{2n}$ of size $n$,
a set of Pauli operators $\{\sigma_a\mid a\in A\}$ is a stabilizer generator if and only if

\begin{align*}
\begin{bmatrix}
\end{bmatrix}
\qquad
\text{and} \qquad \text{rows of $G$ are linearly independent}
\end{align*}

where $G\in\mathbb{F}_2^{n\times 2n}$ denotes a matrix whose $j$-th row is $a_j$ [30].
Here, $G$ is called a generating matrix of the stabilizer state.

In this work, we do not distinguish stabilizer states that have the same generating matrix since they are equivalent up to a Pauli operator.

For any two stabilizer states $\ket{\psi}$ and $\ket{\varphi}$ with the same generating matrices,
there exists a Pauli operator $g\in\mathcal{G}_n$ such that $\ket{\psi}$ is equal to $g\ket{\varphi}$ up to a constant factor.

The proof of Fact <ref> is shown in Appendix <ref>.

§.§ Clifford group

Let $U(n)$ be a set of unitary matrices of size $n$. Then, the Clifford group is defined as

\begin{align*}
\mathcal{C}_n &:= \left\{ U\in U(2^n)\mid U\mathcal{G}_n U^\dagger = \mathcal{G}_n\right\}.
\end{align*}

It is known that $\mathcal{C}_n$ is generated by the following three quantum gates

\begin{align*}
\frac1{\sqrt{2}}
\begin{bmatrix}
\end{bmatrix}
\begin{bmatrix}
\end{bmatrix}
\CZ&:=
\begin{bmatrix}
\end{bmatrix}.
\end{align*}

A set of local Clifford operators is a subset of $\mathcal{C}_n$ defined as

\begin{align*}
\mathcal{C}_1^{\otimes n} &:= \left\{ C_1\otimes\dotsm\otimes C_n\mid C_i \in \mathcal{C}_1,\,\forall i\in\{1,\dotsc,n\} \right\}.
\end{align*}

A Clifford operator $C\in\mathcal{C}_n$ transforms a stabilizer state to another stabilizer state.
A stabilizer $s\in\mathcal{G}_n$ is transformed to $CsC^\dagger$ by the application of Clifford operator $C\in\mathcal{C}_n$ to the stabilizer state.
Indeed, $X$ and $Z$ are transformed as follows.

\begin{align}
HXH^\dagger &= Z,&
HZH^\dagger &= X,\nonumber\\
SXS^\dagger &= Y,&
SZS^\dagger &= Z\nonumber\\
\CZ (X\otimes I_2) \CZ^\dagger &= X\otimes Z,&
\CZ (I_2\otimes X) \CZ^\dagger &= Z\otimes X,\nonumber\\
\CZ (Z\otimes I_2) \CZ^\dagger &= Z\otimes I_2,&
\CZ (I_2\otimes Z) \CZ^\dagger &= I_2\otimes Z.
\label{eq:clifford}
\end{align}

Let $\sigma_{f_C(a)} := C\sigma_aC^\dagger$.
The following equality holds on $\mathcal{G}_n/\langle i I_2^{\otimes n}\rangle$

\begin{align*}
\sigma_{f_C(a+b)} = C \sigma_{a+b} C^\dagger = C \sigma_a \sigma_b C^\dagger = C \sigma_a C^\dagger C\sigma_b C^\dagger=\sigma_{f_C(a)}\sigma_{f_C(b)}=\sigma_{f_C(a)+f_C(b)}.
\end{align*}

Hence, the function $f_C\colon(\mathbb{Z}/2\mathbb{Z})^{2n}\to(\mathbb{Z}/2\mathbb{Z})^{2n}$ is linear so that there exists a unique $2n\times 2n$ $\mathbb{F}_2$-matrix $L_C$ satisfying $a L_C = f_C(a)$.
From (<ref>), we obtain the following $\mathbb{F}_2$-matrix representations,

\begin{align*}
L_H &= \begin{bmatrix}0&1\\1&0\end{bmatrix},&
L_S &= \begin{bmatrix}1&1\\0&1\end{bmatrix},&
L_\CZ &=
\begin{bmatrix}
\end{bmatrix}.
\end{align*}

Note that all of the six invertible $2\times 2$ $\mathbb{F}_2$-matrices are generated by $L_H$ and $L_S$ as follows.

\begin{align}
L_I = L_H^2 = L_S^2 &= \begin{bmatrix}
\end{bmatrix},&
L_H &= \begin{bmatrix}
\end{bmatrix},&
L_SL_H &= \begin{bmatrix}
\end{bmatrix},&
L_S &= \begin{bmatrix}
\end{bmatrix},\nonumber\\
L_HL_SL_H = L_SL_HL_S &= \begin{bmatrix}
\end{bmatrix},&
L_HL_S &= \begin{bmatrix}
\end{bmatrix}.
\label{eq:1clifford}
\end{align}

Obviously, $L_{DC} = L_C L_D$ for any Clifford operations $C, D \in \mathcal{C}_n$.

In this work, we do not distinguish Clifford operators that have the same $\mathbb{F}_2$-matrix representation since they are equivalent up to a Pauli operator.

Let $C, D\in\mathcal{C}_n$ be Clifford operators.
Then, $L_C=L_D$ if and only if there exists a Pauli operator $g\in\mathcal{G}_n$ such that $C$ is equal to $gD$ up to a constant factor.

The proof of Fact <ref> is shown in Appendix <ref>.

§ GRAPH STATE AND COMBINATORIAL CHARACTERIZATIONS OF LOCAL CLIFFORD OPERATIONS AND MEASUREMENTS

For a finite set $V$, let $\binom{V}{2}$ denote a family of subsets of $V$ of size exactly two.
For a finite set $V$, and $E\subseteq\binom{V}{2}$, a pair $(V,E)$ is called a graph.
For a graph $G=(V, E)$, $V(G):=V$ and $E(G):=E$ are called vertex set and edge set, respectively.
The size of graph $G$ is defined as $|V(G)|$.
For a graph $G$ and $v\in V(G)$,
neighbors of $v$ on $G$ is defined as $N_G(v):=\{w\in V\mid \{v,w\}\in E\}$.

For a graph $G=(V=\{1,2,\dotsc,n\},E)$, a graph state $\ket{G}$ is a stabilizer state defined by stabilizer generators

\begin{align*}
X_v\otimes \bigotimes_{w\in N_G(v)} Z_w,\qquad v\in V.
\end{align*}

Here, for any $2\times 2$ matrix $U$, $U_v := g_1\otimes\dotsm\otimes g_n$ where $g_v = U$ and $g_w = I_2$ for $w\in V\setminus\{v\}$.

The generating matrix of $\ket{G}$ is
I\mid A
\end{bmatrix}$
where $A\in\mathbb{F}_2^{n\times n}$ is the adjacency matrix of $G$, i.e., $A_{v,w}=1$ if and only if $\{v,w\}\in E(G)$.

In Definition <ref>, the local Clifford operations are free to use.
Hence, the two stabilizer states that are equivalent up to the local Clifford operations can be identified.

Stabilizer states $\ket{\psi}$ and $\ket{\varphi}$ are local-Clifford (LC) equivalent if
there exists a local Clifford operator $C\in\mathcal{C}_1^{\otimes n}$ such that $C\ket{\psi} = \ket{\varphi}$.

The following lemma implies that it is sufficient to prepare graph states for preparing general stabilizer states.

For any stabilizer state $\ket{\psi}$, there exists a graph $G$ such that $\ket{\psi}$ and $\ket{G}$ are LC-equivalent.

For the combinatorial characterization of LC-equivalence of two graph states, the local complementation is defined as follows.

The local complementation is an operation on a graph.
For a graph $G=(V,E)$, and a vertex $v\in V$,
the local complementation $\tau_v(G)=(V,E')$ is defined as

\begin{align*}
E' &= \left\{\{u,w\}\in\binom{V}{2} \mid ((u\notin N_G(v) \lor w\notin N_G(v)) \land \{u,w\}\in E)
\lor(u\in N_G(v) \land w\in N_G(v) \land \{u,w\}\notin E)\right\}.
\end{align*}

Two graphs $G$ and $H$ are said to be local-complement equivalent if $G$ and $H$ can be transformed to each other by a sequence of local complementations.

For any graphs $G$ and $H$, $\ket{G}$ and $\ket{H}$ are local-Clifford equivalent if and only if
$G$ and $H$ are local-complement equivalent.

Lemma <ref> gives a combinatorial characterization of local Clifford operations on graph states.
Next, we consider a combinatorial characterization of measurements.
In quantum algorithms in Definition <ref>, general stabilizer states, which are not necessarily graph states, are measured by the computational basis.
Since any stabilizer state is LC-equivalent to some graph state,
it is sufficient to consider Pauli measurements for graph states.

For any graph $G$, let $\ket{G^+}$ and $\ket{G^-}$ be two possible stabilizer states obtained by a Pauli measurement, e.g., either of eigenbasis of $X$, $Y$ or $Z$, of a qubit in $\ket{G}$.
Then, $\ket{G^+}$ and $\ket{G^-}$ are LC-equivalent to some common graph state $\ket{H}$.
Here, $H$ is obtained from $G$ by some local complementations and deletion of the vertex that corresponds to the measured qubit.

Lemma <ref> implies that a Pauli measurement and an adaptive local Clifford operation for a graph state $\ket{G}$ give some graph state $\ket{H}$ deterministically.
Furthermore, the graph $H$ is obtained by local complementation and a vertex deletion for $G$.
This observation implies the following lemma.

A graph $H$ is a vertex minor of graph $G$ $\defiff$ $H$ is obtained from $G$ by local complementations and vertex deletions.

For any graphs $G$ and $H$, $\ket{H}$ is obtained from $\ket{G}$ with probability 1 by a local Clifford operation followed by measurement of qubits by the computational basis and an adaptive local Clifford operation if and only if
$H$ is a vertex-minor of $G$.

Dahlberg, Helsen, and Wehner showed that it is NP-hard to decide whether $G$ is a vertex-minor of $H$ for given graphs $G$ and $H$ [13].

§ SUFFICIENCY OF THE OPERATORS: PROOF OF THEOREM <REF>

In this section, we prove Theorem <ref>.
We first prove that any two-qubit Clifford gate can be replaced by single-qubit gates, at most one gate and at most one SWAP gate.

Any two-qubit Clifford operator is represented by a quantum circuit consisting of arbitrary number of single-qubit Clifford gates, at most one CZ gate and at most one SWAP gate.

From Fact <ref>, for given two-qubit Clifford operator $\mathcal{C}$, it is sufficient to show the existence of the quantum circuit $\mathcal{D}$ satisfying $L_\mathcal{C}=L_\mathcal{D}$.
Since the $S$, $H$ and gates generate the Clifford group, any two-qubit Clifford operator is represented by a Clifford circuit consisting of these gates.
When the Clifford circuit includes more than one gates, we can reduce the number of gates by the following procedure.
There are six possible single-qubit Clifford gates (up to succeeding Pauli gates) in (<ref>).
Since $S$ commutes with , we can assume without loss of generality that single-qubit gates between two specific gates are all Hadamard gates.
For the possible two cases, the number of gates can be reduced by using the SWAP gate as follows.

\begin{align*}
\Qcircuit @C=1em @R=.7em {
& \ctrl{1} & \gate{H} & \ctrl{1} & \qw \\
& \control\qw & \qw & \control\qw & \qw \\
\quad&\raisebox{-1em}{=}\quad
\Qcircuit @C=1em @R=.7em {
& \gate{H} & \targ & \control\qw & \qw \\
& \qw & \ctrl{-1} & \ctrl{-1} & \qw \\
\quad\raisebox{-1em}{=}\quad
\Qcircuit @C=1em @R=.7em {
& \gate{H} & \gate{iY} & \qw \\
& \qw & \ctrl{-1} & \qw \\
\quad\raisebox{-1em}{=}\quad
\Qcircuit @C=1em @R=.7em {
& \gate{H} & \gate{Y} & \qw&\qw \\
& \qw & \ctrl{-1} & \gate{S}&\qw  \\
\quad&\raisebox{-1em}{=}\quad
\Qcircuit @C=1em @R=.7em {
&\gate{H}& \gate{S^\dagger} & \gate{H} & \ctrl{1}    & \gate{H} &\gate{S}& \qw \\
& \qw&\qw      & \qw      & \control\qw & \gate{S} &\qw& \qw \\
\Qcircuit @C=1em @R=.7em {
& \ctrl{1} & \gate{H} & \ctrl{1} & \qw \\
& \control\qw & \gate{H} & \control\qw & \qw \\
\quad&\raisebox{-1em}{=}\quad
\Qcircuit @C=1em @R=.7em {
& \qswap & \gate{H} & \ctrl{1} & \gate{H} & \qw \\
& \qswap\qwx & \gate{H} & \control\qw&\gate{H} & \qw \\
\end{align*}

The second relation is obtained from the following Clifford circuit for the SWAP gate.

\begin{equation*}
\Qcircuit @C=1em @R=2em {
\quad\raisebox{-1.0em}{=}\quad
\Qcircuit @C=1em @R=2em {
\quad\raisebox{-1.7em}{=}\quad
\Qcircuit @C=1em @R=2em {
\quad\raisebox{-1.7em}{=}\quad
\Qcircuit @C=1em @R=2em {
\end{equation*}

The SWAP gate commutes with arbitrary quantum gate $U$ by changing the qubits for which $U$ is applied.
Hence, we can put the SWAP gate at the beginning of the quantum circuit.
By repeating this procedure, the number of the gates is reduced to at most one.

Then, by replacing all two-qubit Clifford gates in quantum circuits with Clifford circuits with at most one CZ gate and SWAP gate, we obtain the following theorem.

Let $\mathcal{C}$ be a Clifford circuit that consists of arbitrary number of single-qubit Clifford gates and $t$ two-qubit Clifford gates.
Then, there exists a Clifford circuit $\mathcal{D}$ that consists of arbitrary number of single-qubit Clifford gates and at most $t$ CZ gates and a permutation of qubits $\mathcal{P}$ such that $\mathcal{D}\mathcal{P} = \mathcal{C}$.

From Lemma <ref>, all two-qubit Clifford gates in $\mathcal{C}$ can be replaced by Clifford circuits consisting of arbitrary number of single-qubit Clifford gates, at most one gates and at most one SWAP gates.
The SWAP gate commutes with arbitrary quantum gate $U$ by changing qubits for which $U$ is applied.
Then, we can move the SWAP gates to the beginning of the quantum circuit and obtain Theorem <ref>.

Now, we are ready to prove Theorem <ref>.

From Lemma <ref>, irrespective of a measurement outcome, an adaptive local Clifford operation gives some graph state deterministically.
Hence, it is sufficient to show that there is a quantum algorithm with $\NCZ(\ket{G})$ operations and no other two-qubit Clifford operations producing $\ket{G}$ when all measurement outcomes are zero.
There exist a Clifford circuit $\mathcal{C}$
including some single-qubit Clifford gates and $\NCZ(\ket{G})$ two-qubit Clifford gates such that

\begin{align*}
\bra{0}^{\otimes s}\mathcal{C}\ket{0}^{\otimes(n+s)} &\propto \ket{G}
\end{align*}

From Theorem <ref>,
there exists a Clifford circuit $\mathcal{D}$ including some single-qubit Clifford gates and at most $\NCZ(\ket{G})$ gates such that

\begin{align*}
\bra{0}^{\otimes s}\mathcal{D}\ket{0}^{\otimes(n+s)} &\propto \ket{G}
\end{align*}

This proves Theorem <ref>.

\begin{align*}
\Qcircuit @C=1em @R=2em {
\end{align*}

Zero gate.

\begin{align*}
\Qcircuit @C=1em @R=2em {
\end{align*}

One gate.

\begin{align*}
\Qcircuit @C=1em @R=2em {
\end{align*}

Two gates.

\begin{align*}
\Qcircuit @C=1em @R=2em {
\end{align*}

Three gates.

Classification of two-qubit Clifford operators (up to succeeding Pauli gates): The gates A and B are chosen from the six single-qubit Clifford operators in (<ref>). The gates C and D are chosen from $I$, $H$, $HS$.

In terms of the number of gates when the SWAP gate is not allowed, two-qubit Clifford operators are classified as in Figure <ref>.
The number of two-qubit Clifford operators of types (a), (b), (c) and (d) are $36=6^2$, $324=3^2\times 6^2$, $324$ and $36$, respectively.
Note that the numbers of required $\mathrm{CNOT}$ gates (equivalently the gates) for Clifford operators up to six qubits are calculated by computer search in [2].

§ COMBINATORIAL CHARACTERIZATION OF TWO-QUBIT CLIFFORD OPERATIONS: PROOF OF THEOREM <REF>

In this section, we consider a combinatorial characterization of two-qubit Clifford operations.
For the combinatorial interpretation of the operation, we define the cost-one operation as follows.

For a graph $G=(V,E)$, the cost-one operation is a one of the following operations:

* For $\{v,w\}\in \binom{V}{2}$, complement an edge $\{v,w\}$.

* For $\{v,w\}\in \binom{V}{2}$, complement all edges between $v$ and $N_G(w)\setminus\{v\}$.

* For $\{v,w\}\in \binom{V}{2}\setminus E$, complement all edges in $\bigl\{\{x,y\}\in \binom{V}{2}\mid x\in N_G(v),\, y\in N_G(w),\, \{x,y\}\nsubseteq N_G(v)\cap N_G(w)\bigr\}$.

The second operation is called the edge complementation between $v$ and $N_G(w)$.
The third operation is called the edge complementation between $N_G(v)$ and $N_G(w)$.

It is easy to see that the above operations correspond to some two-qubit Clifford operations.
The first operation corresponds to the operation.
Let $\zeta^{(1)}_{v,w}$ be a mapping on graphs corresponding to the edge complementation for $\{v,w\}\in \binom{V}{2}$.
The second operation is equivalent to

\begin{align*}
\zeta^{(1)}_{v,w}\circ\tau_w\circ\zeta^{(1)}_{v,w}\circ\tau_w &=
\tau_w\circ\zeta^{(1)}_{v,w}\circ\tau_w\circ\zeta^{(1)}_{v,w}.
\end{align*}

The third operation for $\{v,w\}\in \binom{V}{2}\setminus E$ is equivalent to

\begin{align*}
\zeta^{(1)}_{v,w}\circ\tau_v\circ\tau_w\circ\tau_v\circ\zeta^{(1)}_{v,w}
\zeta^{(1)}_{v,w}\circ\tau_w\circ\tau_v\circ\tau_w\circ\zeta^{(1)}_{v,w}
\end{align*}

and swapping the labels of the vertices $v$ and $w$.
Note that $\tau_v\circ\tau_w\circ\tau_v = \tau_w\circ\tau_v\circ\tau_w$ for $\{v,w\}\in E$ is called the pivot operation, which is the edge complementation between $N_G(v)$ and $N_G(w)$ and the swapping of the labels of $v$ and $w$ [10, 26].
Indeed, the three operations in Definition <ref> explains all two-qubit Clifford operations.

We use a detailed version of Lemma <ref> for the proof of Theorem <ref>.

For any stabilizer state $\ket{\psi}$,
there exist a graph $G=(V,E)$ and $A, B\subseteq V$ such that
$A\cap B = \varnothing$,
$G$ has no edge between vertices in $B$, and
$\ket{G}$ is equal to
$\bigotimes_{v\in A} S_v \bigotimes_{w\in B} H_w \ket{\psi}$
up to a Pauli operator.

The following lemma was essentially proved in [15].

For any graph $G$, the following equalities hold up to a Pauli operator:

\begin{align*}
H_b\CZ_{a,b}H_b \ket{G} &= \ket{\zeta_{a,b}^{(2)}(G)}\qquad \forall \{a,b\}\in\binom{V}{2}\\
(H_a\otimes H_b)\CZ_{a,b}(H_a\otimes H_b) \ket{G} &= \ket{\zeta_{a,b}^{(3)}(G)}\qquad \forall \{a,b\}\in\binom{V}{2}\setminus E(G)
\end{align*}

where $\zeta_{a,b}^{(2)}$ denotes the edge complementation between $a$ and $N_G(b)$, and $\zeta_{a,b}^{(3)}$ denotes the edge complementation between $N_G(a)$ and $N_G(b)$.

From Lemmas <ref> and <ref>, we obtain the combinatorial characterization of quantum algorithm with CZ-complexity one.

For any graphs $G$ and $H$, graph states $\ket{G}$ and $\ket{H}$ are transformed to each other by arbitrary number of local Clifford operations and one operation if and only if $G$ and $H$ can be transformed to each other by arbitrary number of local complementations and single cost-one operation.

From Lemmas <ref> and <ref>, the direction $\Leftarrow$ is obvious.
We will prove the other direction.
Let $\ket{\psi}$ be a stabilizer state just before the operation is performed in the transformation from $\ket{G}$ to $\ket{H}$.
From Lemma <ref>, there exist a graph $G'$ and $A, B\subseteq V$ such that
$A\cap B=\varnothing$, $G'$ has no edge between vertices in $B$ and $\bigotimes_{v\in A} S_v \bigotimes_{w\in B} H_w \ket{\psi}$ is equal to $\ket{G'}$ up to a Pauli operator.
Then, some CZ operation is applied to a pair $\{a,b\}\in\binom{V}{2}$ of qubits of $\ket{\psi}$.
Assume $a$ and $b$ are both not in $B$.
Then, up to a Pauli operator,

\begin{align*}
\left(\bigotimes_{v\in A} S_v\bigotimes_{w\in B}H_w\right) \CZ_{a,b} \ket{\psi}
\CZ_{a,b} \left(\bigotimes_{v\in A} S_v\bigotimes_{w\in B}H_w\right)  \ket{\psi}
\CZ_{a,b} \ket{G'}
\ket{\zeta^{(1)}_{a,b}(G')}
\end{align*}

since the gate and $S$ gate commute.
Assume $a$ is not in $B$ and $b$ is in $B$.
Then, up to a Pauli operator,

\begin{align*}
\left(\bigotimes_{v\in A} S_v\bigotimes_{w\in B}H_w\right) \CZ_{a,b} \ket{\psi}
\left(\bigotimes_{v\in A} S_v\bigotimes_{w\in B}H_w\right) \CZ_{a,b} \left(\bigotimes_{v\in A} S^\dagger_v\bigotimes_{w\in B}H_w\right)\ket{G'}\\
H_b \CZ_{a,b} H_b \ket{G'}
\ket{\zeta^{(2)}_{a,b}(G')}.
\end{align*}

Finally, assume $a$ and $b$ are both in $B$.
Then, up to a Pauli operator,

\begin{align*}
\left(\bigotimes_{v\in A} S_v\bigotimes_{w\in B}H_w\right) \CZ_{a,b} \ket{\psi}
\left(\bigotimes_{v\in A} S_v\bigotimes_{w\in B}H_w\right) \CZ_{a,b} \left(\bigotimes_{v\in A} S^\dagger_v\bigotimes_{w\in B}H_w\right)\ket{G'}\\
(H_a \otimes H_b) \CZ_{a,b} (H_a \otimes H_b) \ket{G'}
\ket{\zeta^{(3)}_{a,b}(G')}.
\end{align*}

Since $\ket{G}$ and $\ket{G'}$ are LC-equivalent, $G$ and $G'$ are local-complement equivalent.
Then, the transformations of graph $G\rightarrow G'\rightarrow \zeta_{a,b}^{(i)}(G') \rightarrow H$
for some $i\in\{1,2,3\}$ are realized by arbitrary number of local complementations and single cost-one operation.

From Lemmas <ref>, <ref> and Theorem <ref>, the CZ-complexity of graph state is now stated in a combinatorial way.

Let $\mathcal{A}$ be an algorithm acting on a graph that consists of the following operations.

* Deletion of a vertex.

* Local complementation.

* Cost-one operation.

The edge-complementation-complexity of $\mathcal{A}$ is defined as the number of cost-one operations in $\mathcal{A}$.
The edge-complementation-complexity (EC-complexity) $\NCO(G)$ of a graph $G$ is defined as the minimum edge-complementation-complexity of $\mathcal{A}$
that generates $G$ with $n$ vertices from the empty graph with $n+s$ vertices for some $s\ge 0$.

For any graph $G$, $\NCZ(\ket{G})= \NCO(G)$.

In the rest of this paper, we mainly consider $\NCO(G)$ rather than $\NCZ(\ket{G})$ since it is combinatorial and easier to analyze.

§ RANK-WIDTH

The rank-width is a complexity measure of a graph [24, 28].
The rank-width is defined using a cut-rank.

For a graph $G=(V,E)$ and $S\subseteq V$, the bipartite adjacency matrix $A_{S, V\setminus S}\in\mathbb{F}_2^{|S|\times|V\setminus S|}$ is a matrix whose rows and columns are indexed by $s\in S$ and $t\in V\setminus S$, receptively. An $(s,t)$-entry of $A_{S,V\setminus S}$ is 1 if and only if $\{s,t\}\in E$.
The cut-rank of $S$ for $G$ is defined as $\cutrank_G(S):=\mathrm{rank}_{\mathbb{F}_2}(A_{S,V\setminus S})$.

the cut-rank is symmetric, i.e., $\cutrank_G(V\setminus S) = \cutrank_G(S)$ for any $S\subseteq V$.
The cut-rank plays an important role in this work since it is invariant under the local complementations.

For any $G=(V,E)$, $S\subseteq V$ and $v\in V$, $\cutrank_G(S) = \cutrank_{\tau_v(G)}(S)$.

Let $A_{S,V\setminus S}\in\mathbb{F}_2^{|S|\times|V\setminus S|}$ be the bipartite adjacency matrix of $G$.
Without loss of generality, we can assume $v\in S$.
Then, the bipartite adjacency matrix for $\tau_v(G)$ is obtained from $A_{S,V\setminus S}$ by adding $v$-th row to all rows that corresponds to a neighborhood of $v$.
This transform does not change the rank of the bipartite adjacency matrix.

The rank-width is defined as follows.

Let $G=(V,E)$ be a graph.
A subcubic tree is a tree whose maximum degree is at most three.
A rank-decomposition of $G$ is a pair $(T, L)$ of a subcubic tree $T$ with at least two vertices and a bijection $L$ from $V$ to a set of all leaves of $T$.
For a rank-decomposition $(T=(W, F), L)$ and an edge $e\in F$, $T-e$ defines a partition of leaves of $T$, equivalently a partition of $V$ defined by $L$.
A width of $e\in F$ is $\cutrank_G(S)$ where $S, V\setminus S$ is the partition of $V$ defined by $e$.
A width of the rank-decomposition $T$ is the maximum of the width of all edges in $T$.
A rank-width $\rw(G)$ of $G$ is the minimum width of all rank-decompositions of $G$.
When $G$ has at most one vertices, $G$ has no rank-decomposition. In this case, the rank-width of $G$ is defined as zero.

For a graph $G=(V,E)$, let $G[W]$ denote the induced subgraph in $G$ by $W\subseteq V$.
In other words, $G[W] := (W, E \cap \binom{W}{2})$.
The cut-rank and rank-width are monotone with respect to induced subgraphs, i.e.,

* For any $S\subseteq W\subseteq V$, $\cutrank_{G[W]}(S) \le \cutrank_G(S)$.

* For any $W\subseteq V$, $\rw(G[W])\le\rw(G)$.

The rank-width can be computed in time $\mathrm{poly}(n) 2^n$ [27].
There also exists fixed parameter-tractable algorithm computing the rank-width [25].

Here, we provide the proof of Lemma <ref> using the information theoretic counting argument.

Any bipartite graph with $r$ vertices at one side and $n-r$ vertices at the other side has rank-width at most $r$.
Hence, the number of graphs with $n$ vertices and rank-width at most $r$ is at least $2^{r(n-r)}$.
All graph states have different generating matrices.
Since quantum algorithm in Definition <ref> have to generate $\ket{G}$ with probability 1, the quantum algorithm generates $\ket{G}$ when the all measurement outcomes for the $s$ working qubits are zero.
In this case, we can consider a corresponding Clifford circuit with the projectors $\ket{0}\bra{0}$ for the $s$ working qubits.
The output of the Clifford circuit with the projectors must be proportional to $\ket{G}$.
In the following, we count the number of Clifford circuits with the projectors.
There are $324$ two-qubit Clifford operators acting on the generating matrices from Figure <ref> (b).
Non-working qubits that do not appear in any two-qubit operation must be $\ket{+}$.
Then, the number of Clifford circuits including at most $t$ two-qubit Clifford gates is at most

\begin{align*}
\left(1+324\binom{n+s}{2}\right)^t.
\end{align*}

We can assume without loss of generality that all working qubits “connect” to some non-working qubit by two-qubit Clifford operations.
This observation implies $s\le t\le \binom{n}{2}$.
If $t$ two-qubit Clifford gates are sufficient for all graph states with $n$ vertices and rank-width $r$,

\begin{align*}
\left(1+324\binom{n+n^2}{2}\right)^{t} &\ge 2^{r(n-r)} \ge 2^{r\lfloor\frac23 n\rfloor}
\end{align*}

since $r\le \lceil n/3\rceil$.
Then, we obtain

\begin{align*}
t \ge \frac{r}{\log\left(1+324\binom{n+n^2}{2}\right)}\left\lfloor\frac23n\right\rfloor.
\end{align*}

Here, we also provide the proof of Lemma <ref> using the rank-width of random sparse graph analyzed in [23].

Let $G(n, p)$ denote the Erdős–Rényi random graph.
The rank-width of $G(n, c/n)$ with constant $c>1$ was analyzed in [23].

For any constant $c>1$, there exists constants $d>0$ and $e>0$ such that $G(n,c/n)$ contains a connected subgraph $H$ satisfying $|V(H)|\ge dn$ and $\rw(H)\ge en$ asymptotically almost surely.

Here, $G(n, c/n)$ contains at most $(c/2)n-1$ edges with probability asymptotically $1/2$.
Hence, for $c > 1$,

\begin{align}
\NCO(H)\le (c/2)n - 1 &= dn - 1 + (c/2-d) n
\le |V(H)| - 1 + [(c/2-d)/e] \rw(H).
\label{eq:H}
\end{align}

holds with probability asymptotically at least $1/2$.

Then, fix $c>1$ arbitrarily.
For any $r'$, let $n'$ be a minimum integer such that there exists a connected graph $H$ satisfying (<ref>), $|V(H)|=n'$ and $\rw(H)\ge r'$.
Note that such graph $H$ always exists since asymptotically at least half of $H$ in Lemma <ref> satisfy (<ref>) and have linear rank-width.
Adding a new vertex of degree one to $H$ gives a new graph $H'$ such that $|V(H')|=|V(H)|+1$, $\NCO(H')\le\NCO(H)+1$ and $\rw(H')=\rw(H)$.
Hence, (<ref>) still holds for $H'$.
This argument implies that for any $r'$, there exists $n'$ and $r\ge r'$ such that for any $n\ge n'$ there exists a graph $H$ with $n$ vertices and rank-width $r$ satisfying $\NCO(H)\le n - 1 + [(c/2-d)/e] r$.

It is interesting to minimize the constant $(c/2-d)/e$, and ask whether it attains the constant 1, which appears in the lower bound in Theorem <ref>.

§ LOWER BOUND: PROOF OF THEOREM <REF>

In this section, we prove Theorem <ref>.
The following lemma states that the cut-rank is unchanged by a cost-one operation that does not cross the cut, and is changed by at most one by a cost-one operation that cross the cut.

For a graph $G=(V,E)$ and a pair $\{v,w\}\in \binom{V}{2}$ of vertices,
let $G'$ be a graph obtained by a cost-one operation for $\{v,w\}$ from $G$.

* For any $W\subseteq V$, $\cutrank_G(W)=\cutrank_{G'}(W)$ when $(v\in W\land w\in W)\lor(v\notin W\land w\notin W)$.

* For any $W\subseteq V$, $|\cutrank_G(W)-\cutrank_{G'}(W)|\le 1$ when $(v\in W\land w\notin W)\lor(v\notin W\land w\in W)$.

First, let us consider the case $v\in W\land w\in W$.
Since the bipartite adjacency matrix $A_{W,V\setminus W}$ does not change by the edge complementation between $v$ and $w$, its rank does not change.
For the edge complementation between $v$ and $N_G(w)$, the new bipartite adjacency matrix is obtained by adding the $w$-th row to the $v$-th row for $A_{W,V\setminus W}$.
Hence, the rank does not change.
For the edge complementation between $N_G(v)$ and $N_G(w)$ for vertices $v$ and $w$ not connected on $G$, the new bipartite adjacency matrix is obtained by adding the $v$-th row to rows in $N_G(w)\cap W$ and adding the $w$-th row to rows in $N_G(v)\cap W$.
Hence, the rank does not change.
Similarly, for the case $v\notin W\land w\notin W$, the rank of the bipartite adjacency matrix does not change.

Next, let us consider the case $v\in W\land w\notin W$.
For the edge complementation between $v$ and $w$, the new bipartite adjacency matrix is obtained by flipping the $(v,w)$-entry.
Hence, the rank changes by at most one.
For the edge complementation between $v$ and $N_G(w)$, the new bipartite adjacency matrix is obtained by flipping $(v,u)$-entry for $u\in N_G(w)\setminus W$.
Hence, the rank changes by at most one.
For the edge complementation between $N_G(v)$ and $N_G(w)$ for vertices $v$ and $w$ not connected on $G$, the new bipartite adjacency matrix is obtained by adding the $v$-th row to rows in $N_G(w)\cap W$ and adding a row vector $1_{N_G(w)\setminus W}$ to rows in $N_G(v)\cap W$ where $1_{N_G(w)\setminus W}$ is a row vector whose $u\in V\setminus W$-th element is 1 if and only if $u\in N_G(w)\setminus W$.
Hence, the rank changes by at most one.
Similarly, for the case $v\notin W\land w\in W$, the rank of the bipartite adjacency matrix changes by at most one.

For any connected graph $G$ with $n\ge 2$ vertices and rank-width at least $r$, $\NCO(G)\ge n+r-2$.

Let $G=(V,E)$ be a connected graph with at least two vertices.
Then, $\rw(G)\ge 1$ so that we assume $r\ge 1$ in the following.
From the connectivity of $G$, $\NCO(G)\ge n-1$.
Hence, Theorem holds for $r=1$.

In the following, we assume $r\ge 2$ and show that
if $\NCO(G)\le n+r-3$, then, $\rw(G)\le r-1$.
Let $S$ be the set of vertices of size $s$ that are deleted in an algorithm in Definition <ref>.
Without loss of generality, we can assume that the vertices are deleted at the end of the algorithm.
Let $G'=(V\cup S, E')$ be a graph just before the vertex deletion.
Then, $G'[V] = G$.
From Fact <ref>, it is sufficient to show $\rw(G')\le r-1$.
In the following, we will show $\rw(G')\le r-1$.
Let $k:=\NCO(G)$.
Let $e_1,e_2,\dotsc,e_k$ be a sequence of pairs of vertices of $G'$ for which the cost-one operations are applied in this order.
Furthermore, let

\begin{align*}
F:=\Bigl\{ e_i=\{v,w\} &\mid
\text{$v$ and $w$ belong to different connected components}\\
&\qquad \text{in a graph $(V\cup S, \{e_1,\dotsc,e_{i-1}\})$}
\Bigr\}.
\end{align*}

Let $T:=(V\cup S, F)$.
From the definition of $F$, $T$ is a forest.
From the connectivity of $G$, all vertices in $V$ must belong to a common connected component of $T$.
Since all other vertices that do not belong to the connected component including $V$ does not affect the generation of the graph $G$, we can assume that there does not exist such vertices without loss of generality.
In the following, we assume that $|F|=n+s-1$, and $T$ is a tree.

[inner sep = 0, minimum size = 20pt, very thick, scale=1.5]
[circle,radius=100pt,draw] (c) at (4,0) $v$;
(c) – node[above=0.0em,at end] $e_{v_1}$ (5.5,2);
(c) – node[above=0.0em,at end] $e_{v_2}$ (5.5,1);
(c) – node[above=0.0em,at end] $e_{v_3}$ (5.5,0);
at (6.5,0) $\bm{\longmapsto}$;
[circle,draw] (c) at (7.7,0) $l_v$;
[circle,draw] (d) at (9.2,0) $b_{v,3}$;
[circle,draw] (e) at (9.2,1) $b_{v,2}$;
[circle,draw] (f) at (9.2,2) $b_{v,1}$;
(c) – (d) – (e) – (f);
(f) – (10.7,2);
(e) – (10.7,1);
(d) – (10.7,0);

Construction of rank-decomposition on the basis of the tree $T$.
Left: A vertex $v$ in $T$.
Right: A leaf of the rank-decomposition corresponding to $v$.

On the basis of $T$, we provide the rank-decomposition of $G'$ of width at most $r-1$ as follows.
For each $v\in V\cup S$, let $e_{v_1},\dotsc,e_{v_{d_v}} \in F$ be edges of $T$ incident to $v$ where $v_1< v_2< \dotsb< v_{d_v}$.
A gadget $H_v$ corresponds to the vertex $v$ is defined as

\begin{align*}
V(H_v) &:= \{l_v\}\cup\{b_{v,i}\mid i=1,\dotsc,d_v\}\\
E(H_v) &:= \{\{l_v,b_{v,d_v}\}\}\cup \{\{b_{v,i},b_{v,i+1}\}\mid i= 1,\dotsc,d_v-1\}
\end{align*}

Figure <ref> shows the correspondence between $v$ and $H_v$.
We now define the rank-decomposition $H$ of $G'$ as

\begin{align*}
V(H) &:= \bigcup_{v\in V\cup S} V(H_v)\\
E(H) &:= \bigcup_{v\in V\cup S} E(H_v) \cup \bigcup_{\{v,w\}\in F} \bigl\{\{b_{v,i},b_{w,j}\}\mid v_i=w_j, i\in\{1,\dotsc,d_v\}, j\in\{1,\dotsc,d_w\}\bigr\}.
\end{align*}

Then, it is obvious that $H$ is a subcubic tree and the set of leaves of $H$ is $\{l_v\mid v\in V\cup S\}$.
Hence, $(H, L\colon v \mapsto l_v)$ is a rank-decomposition of $G'$.

We will show that the width of the rank-decomposition $(H, L)$ is at most $r-1$.
For each edge $e\in E(H)$ defines a partition $P_e:=\{V_e, (V\cup S)\setminus V_e\}$ of vertices of $G'$.
In the following, we will show $\cutrank_{G'}(V_e)\le r-1$ for all $e\in E(H)$.

If $e=\{l_v, b_{v,d_v}\}$ for some $v\in V\cup S$, then $P_e=\{\{v\}, (V\cup S)\setminus\{v\}\}$. This implies $\cutrank_{G'}(V_e)=1$.

If $e=\{b_{v,i},b_{w,j}\}$ for some $v\ne w$, edges in $F\setminus\{v,w\}$ do not cross the cut $V_e$.
The number of cost-one operations cross the cut $V_e$ is at most $k-|F|+1=k-n-s+2\le (n+r-3)-n-s+2 = r-s-1\le r-1$.
From Lemmas <ref> and <ref>, $\cutrank_{G'}(V_e)\le r-1$.

Finally, assume $e=\{b_{v,i},b_{v,i+1}\}$, for some $v\in V\cup S$.
Without loss of generality, we can assume $v\in V_e$.
Before the cost-one operation corresponding to $e_{v_{i+1}}$ is applied,
$v$ is the unique vertex in $V_e$ that may connect to $(V\cup S)\setminus V_e$.
This means that the cut-rank of $V_e$ is at most one at this time.
After $e_{v_{i+1}}$, the number of cost-one operations that cross the cut $V_e$
is at most $k-|F|\le r-2$.
From Lemmas <ref> and <ref>, $\cutrank_{G'}(V_e)\le r-1$.

From these observations, $\cutrank_{G'}(V_e)\le r-1$ for all $e\in E(H)$, which implies that the width of the rank-decomposition $H$ is at most $r-1$.

§ UPPER BOUND: PROOF OF THEOREM <REF>

In this section, we give an algorithm that generate $G$ with EC-complexity $O(rn\log n)$ and prove Theorem <ref>.
Our algorithm is based on the divide-and-conquer method on a rank-decomposition of $G$. The following lemma shows the existence of a balanced partition in arbitrary rank-decomposition.

Let $T$ be a subcubic tree with at least two vertices and $L$ leaves. Then, there exists an edge $e \in E(T)$ such that both of the two trees obtained by removing $e$ from $T$ contain at least $\lceil L/3\rceil$ leaves of $T$.

It is clear that the lemma holds when $T$ has two vertices. Assume that $T$ has at least three vertices. We will show that the edge $e \in E(T)$ selected in Algorithm <ref> satisfies the conditions of the lemma.

Consider the two trees obtained by removing the edge $\{r,s\}$ selected by this algorithm.  The tree containing the vertex $r$ has at least $L/3$ leaves of $T$ according to the stopping condition of the algorithm.
Consider the tree containing the vertex $s$.
First, if $r=r^*$, the tree with root $r$ is the entire tree $T$, and since $r$ has at most three children, the tree with root $s$ contains at least $L/3$ leaves of $T$.
If $r \ne r^*$, the tree with root $r$ considered one step before the algorithm stopped contains at least $2L/3$ leaves of $T$ according to the stopping condition.
Since $r$ has at most two children, the tree with root $s$ contains at least $L/3$ leaves of $T$.

Algorithm to find an edge that satisfies the condition in Lemma <ref>.
A subcubic tree $T$ with at least three vertices.
An edge $e$ in $T$ that satisfies the condition in Lemma <ref>.
$L\leftarrow $ number of edges in $T$
aux$T, r$
$(T', s)\leftarrow$ the rooted tree obtained by removing $r$ from $T$ that has the largest number of leaves and its root from neighbors of $r$ on $T$
number of leaves in $T'<2L/3$

$r^*\leftarrow $ arbitrary non-leaf vertex of $T$

Graph preparation algorithm from rank-decomposition.
$G\colon$ A graph to generate,  $(T,L)\colon$ A rank-decomposition of $G$ of width at most $r$.
A graph $G$ generated by the operations in Definition <ref>.
GenGraph$G=(V,E), (T,L)$
Prepare a vertex $u_v$

Delete all degree $2$ vertices in $T$ by shrinking edges
Let $e$ be an edge in $T$ such that there are at least $\lceil|V|/3\rceil$ leaves in both side
Decompose $(T, L)$ at $e$ into two rank-decompositions $(T_1,L_1),(T_2,L_2)$ for graphs $G[W]$ and $G[V\setminus W]$, respectively
$G_1\leftarrow \Call{GenGraph}{G[W], (T_1,L_1)}$
$G_2\leftarrow \Call{GenGraph}{G[V\setminus W], (T_2,L_2)}$
Compute the binary adjacency matrix $A_{W,V\setminus W} \in \mathbb{F}_2^{|W|\times |V\setminus W|}$ corresponding to the cut $\{W,V\setminus W\}$ in $G$ and represent it as the sum of $r$ rank-one matrices $s_1t_1^T,\dots, s_rt_r^T$
$i=1,\dotsc, r$
$S\leftarrow \{ u_v \in V(G_1)\mid s_{i v} = 1\}$
$T\leftarrow \{ u_v \in V(G_2)\mid t_{i v} = 1\}$
Prepare a vertex $w$
$u_v\in S$
Edge complementation between $u_v$ and  $w$ (cost-one operation)

$u_v\in T$
Edge complementation between $u_v$ and $N(w)$ (cost-one operation)

Delete $w$

$\{u_v\mid v\in V\}$

On the basis of this lemma, Algorithm <ref> generates a graph by the divide-and-conquer manner.

For any graph $G$ with $n$ vertices and its rank-decomposition $(T,L)$ of width at most $r$, Algorithm <ref> generates $G$ with EC-complexity $O(rn\log n)$.

The correctness of the algorithm is clear.
In the following, we evaluate the EC-complexity of the algorithm.
Let $C(n,r)$ denote the maximum EC-complexity of Algorithm <ref> for a graph $G$ with $n$ vertices and its rank-decomposition $(T,L)$ of width at most $r$.
From Fact <ref>, the widths of rank-decompositions $(T_1,L_1)$ for $G[W]$ and $(T_2,L_2)$ for $G[V\setminus W]$ are at most $r$ as well.
Then, we have

\begin{align*}
C(1,r) &= 0\\
C(n,r) &\le rn + C(k,r) + C(n-k,r)\text{ for some } k\in\bigl\{\lceil n/3\rceil,\lceil n/3\rceil+1,\dotsc,\lfloor 2n/3\rfloor\bigr\},\qquad n\ge 2.
\end{align*}

Therefore, we have $C(n,r)=O(rn\log n)$.

Note that Algorithm <ref> gives a quantum algorithm that only uses the $H$, and adaptive-$Z$ operators, and does not use the $S$ operator.

§ SPECIAL GRAPHS

§.§ Cographs

Cograph preparation.
$G\colon$ A cograph to generate.
A graph generated by the operations in Definition <ref>.
Prepare vertices $u_v, z_G$
Edge complementation between $u_v$ and $z_G$ (cost-one operation)

$G$ is connected
$(S,z)\leftarrow \Call{RecCograph}{\overline{G}}$
Local complementation on $z$

Let $C$ be an arbitrary connected component of $G$
$(S_1,z_1)\leftarrow \Call{RecCograph}{G[C]}$
$(S_2,z_2)\leftarrow \Call{RecCograph}{G[V\setminus C]}$
Edge complementation between $z_1$ and $N(z_2)$ (cost-one operation)
Delete $z_2$
$(S_1\cup S_2,z_1)$

$(S,z)\leftarrow \Call{RecCograph}{G}$

Cograph is a class of graphs recursively defined by the following rules:

* A single-vertex graph is a cograph.

* For a cograph $G$, its complement $\overline{G}:=\bigl(V(G), \binom{V(G)}{2}\setminus E(G)\bigr)$ is a cograph.

* For two cographs $G$ and $H$, their disjoint union $G\cup H:=\bigl(V(G)\cup V(H), E(G)\cup E(H)\bigr)$ is a cograph.

It is not difficult to see that the rank-width of cographs with at least one edge is one.
Theorem <ref> implies $\NCO(G)=O(n\log n)$.
Here, we prove better upper bounds.
We first prove a simple bound $2n-1$.

For any cograph $G$ with $n$ vertices, $\NCO(G)\le 2n-1$.

For a cograph $G$, the enhanced graph $\Lambda(G)$ of $G$ is defined as

\begin{align*}
\Lambda(G)&:=(V(G)\cup\{v_G\}, E(G)\cup \{\{v,v_G\}\mid v\in V(G)\}).
\end{align*}

Here, $v_G$ is called the auxiliary vertex for $G$.
We will show that $\NCO(\Lambda(G))\le 2n-1$ for any cograph $G$ with $n$ vertices, which implies $\NCO(G)\le 2n-1$.

Now, we show $\NCO(\Lambda(G))\le 2n-1$ by the induction on the number of vertices.
When $n=1$, obviously $\NCO(\Lambda(G)) = 1 = 2n-1$.

When $n\ge 2$, there exist cographs $G_1$ and $G_2$ such that $G = G_1\cup G_2$ or $G = \overline{G_1\cup G_2}$.
Let $n_1:=|V(G_1)|$ and $n_2:=|V(G_2)|$.
From the induction hypothesis, $\NCO(\Lambda(G_1))\le 2n_1-1$ and $\NCO(\Lambda(G_2))\le 2n_2-1$.
When we have $\Lambda(G_1)\cup \Lambda(G_2)$, we can generate $\Lambda(G_1\cup G_2)$ by merging the auxiliary vertices $v_{G_1}$ and $v_{G_2}$.
This can be done by the edge complementation between $v_{G_1}$ and $N_{\Lambda(G_1)\cup\Lambda(G_2)}(v_{G_2})$ and the deletion of $v_{G_2}$.
Hence, the EC-complexity of the merging is one.
That implies $\NCO(\Lambda(G_1\cup G_2)) \le \NCO(\Lambda(G_1)) + \NCO(\Lambda(G_2)) + 1 \le 2n_1 - 1 + 2n_2 - 1 + 1 = 2(n_1+n_2) - 1=2n-1$.
We can generate $\Lambda(\overline{G})$ from $\Lambda(G)$ by the local complementation on $v_G$.
This implies $\NCO(\Lambda(\overline{G})) = \NCO(\Lambda(G))$.

Obviously, for any cograph $G$ and $W\subseteq V(G)$, an induced subgraph $G[W]$ is a cograph.
Hence, any connected component of $G$ is a cograph.
This observation gives Algorithm <ref>, which generates a cograph $G$ with the EC-complexity $2n-1$.

On the basis of the proof of Lemma <ref>, we can improve the upper bound.

For any cograph $G$ with $n$ vertices, $\NCO(G)\le (5/4)n-1$.

For the improvement, we do not add the auxiliary vertex for cographs of size at most three.
In the improved algorithm, cographs of size at most three are generated directly without the auxiliary vertex.
For any graph $G$ with at most three vertices, it is obvious that $\NCO(G)=n-s$ where $s$ is the number of connected components in $G$.
For integers $n_1$ and $n_2$ at most three satisfying $n_1+n_2> 3$, $n_1$-vertex graph $G_1$ with $s_1$ connected components and $n_2$-vertex graph $G_2$ with $s_2$ connected components, the EC-complexity for generating $\Lambda(G_1\cup G_2)$ from $G_1\cup G_2$ is $s_1+s_2$.
The merging of this type is called the bad merging.
The EC-complexity of generating $\Lambda(G_1\cup G_2)$ from $\Lambda(G_1)\cup G_2$ where $G_2$ is connected and has vertices at most three is one.
Here, we can assume that $G_2$ is connected without loss of generality since if not, the connected components of $G_2$ can be merged to $\Lambda(G_1)$ separately.
Then, the EC-complexity of the algorithm for generating an $n$-vertex cograph $G$ is equal to

\begin{align*}
n-1 + \text{the number of bad mergings}.
\end{align*}

The size of a graph generated by the bad merging is at least four.
Hence, the number of bad mergings is at most $n/4$.
This implies the upper bound $(5/4)n-1$.

Obviously, algorithms in this section can be straightforwardly generalized to tree-cographs, which is a class of graphs generated by the complementations and the disjoint unions from trees.

§.§ Interval graphs

Interval graph preparation.
A permutation $p$ on $\{1,1,2,2,\dotsc,n,n\}$.
An interval graph defined by $p$ generated by the operations in Definition <ref>.
Prepare a vertex $z$
Prepare vertices $\{u_i\}_{1,\dotsc,n}$
$t=1,\dotsc, 2n-2$
$t$-th element of $p$ is the first appearance in $p$

Local complementation on $z$
Edge complementation between $u_{p_1^{-1}(t)}$ and $z$ (cost-one operation)
Local complementation on $z$

Edge complementation between $u_{p_2^{-1}(t)}$ and $z$ (cost-one operation)

Delete $z$
$\{u_1,\dotsc, u_n\}$

$G=(V,E)$ is an interval graph if there exists an interval $S_v=[l_v,r_v]$ on $\mathbb{R}$ for each $v\in V$ such that

\begin{align*}
E &= \left\{\{v, w\}\in\binom{V}{2}\,\middle|\, S_v\cap S_w \ne \varnothing\right\}.
\end{align*}

For a simple representation of a interval graph, we can use a permutation $p$ of multiset $\{1,1,2,2,3,3,\dotsc,n,n\}$.
Then, we can define the interval graph defined by $p$ as $V=\{1,2,\dotsc,n\}$ and

\begin{align*}
E &= \left\{\{a, b\}\in\binom{V}{2}\,\middle|\, \text{$a$ and $b$ appear in $p$ in the order $abba$, $baab$, $abab$ or $baba$}\right\}.
\end{align*}

It is known that the class of interval graphs with the restriction $r_v-l_v=1$ for all $v\in V$ has unbounded rank-width [18].

For the permutation $p$ and $a\in V$, let $p_1(a)$ and $p_2(a)$ denote the positions of the first and second appearance of $a$ in $p$.
For example, $V = \{1,2,3\}$, and $p$ that determines an order $3,2,2,1,3,1$,

\begin{align*}
p_1(1) &= 4,&
p_2(1) &= 6,&
p_1(2) &= 2,&
p_2(2) &= 3,&
p_1(3) &= 1,&
p_2(3) &= 5.
\end{align*}

For any interval graph $G$ with $n$ vertices, Algorithm <ref> generates $G$ with the EC-complexity $2n-2$.

The EC-complexity of Algorithm <ref> is obviously $2n-2$.
The correctness of Algorithm <ref> is obvious if $t$ runs from $1$ to $2n$.
We can omit the case $t=2n$ since $(2n)$-th element of $p$ is the second appearance in $p$.
We can also omit the case $t=2n-1$ since if $(2n-1)$-th element of $p$ is the second appearance in $p$,
we can simply ignore this, and if $(2n-1)$-th element of $p$ is the first appearance, then the $(2n-1)$-th and $(2n)$-th elements are equal and represent an isolated vertex in $G$.

§.§ Permutation graphs

Permutation graph preparation.
A permutation $p$ on $\{1,2,\dotsc,n\}$.
A permutation graph defined by $p$ generated by the operations in Definition <ref>.
Prepare vertices $\{u_i\}_{i=1,\dotsc,n}$
Prepare vertices $\{z_i\}_{i=2,\dotsc,n}$
$t=2,\dotsc, n$
Edge complementation between $z_t$ and $u_{p^{-1}(t-1)}$ (cost-one operation)
$t < n$
Edge complementation between $z_{t+1}$ and $N(z_t)$ (cost-one operation)

Prepare a vertices $y$
$t=1,\dotsc, n$
$t > 1$
Edge complementation between $y$ and $u_{t-1}$ (cost-one operation)
Edge complementation between $u_t$ and $N(y)$ (cost-one operation)

$p(t) > 1$
Edge complementation between $u_t$ and $N(z_{p(t)})$ (cost-one operation)

Delete $y$
Delete $\{z_i\}_{i=2,\dotsc,n}$
$\{u_1,\dotsc, u_n\}$

$G=(V=\{1,2,\dotsc,n\},E)$ is a permutation graph if there exists a permutation $p$ on $V$ satisfying

\begin{align*}
E &= \left\{\{v, w\}\in\binom{V}{2}\,\middle|\, v < w,\ p(v) > p(w) \right\}.
\end{align*}

It is known that the class of permutation graphs has unbounded rank-width [18].

For any permutation graph $G$ with $n\ge 2$ vertices, Algorithm <ref> generates $G$ with the EC-complexity $5n-6$.

Let $G$ be a permutation graph defined by a permutation $p$.

\begin{align*}
N_G(v) &= \{w\in V\mid w < v\} \bigtriangleup \{w\in V\mid p(w)<p(v)\}
\end{align*}

where $\bigtriangleup$ denotes the symmetric difference, i.e., $A\bigtriangleup B:= (A\cup B)\setminus(A\cap B)$.
After the first “For loop” in Algorithm <ref>, the neighborhood of $z_t$ is $\{u_k\mid p(k) < t\}$.
In the second “For loop”, the neighborhood of $y$ is $\{u_k\mid k < t\}$ after Line 11.
Then, the neighborhood of $u_t$ should be the symmetric difference of $N(y)$ and $N(z_{p(t)})$.
The neighborhood of $u_t$ is generated by Lines 12 and 14.

Note that Algorithm <ref> gives a quantum algorithm that only uses the $H$, and adaptive-$Z$ operators, and does not use the $S$ operator.

§.§ Circle graphs

Circle graph preparation.
A permutation $p$ on $\{1,1,2,2,\dotsc,n,n\}$.
A circle graph defined by $p$ generated by the operations in Definition <ref>.
Prepare vertices $\{u_i\}_{i=1,\dotsc,n}$
Prepare vertices $\{z_i\}_{i=2,\dotsc,2n}$
Prepare vertices $\{x_i\}_{i=2,\dotsc,2n}$
$t=2,\dotsc, 2n$
$(t-1)$-th element of $p$ is the first appearance in $p$
Edge complementation between $z_t$ and $u_{p_1^{-1}(t-1)}$ (cost-one operation)

Edge complementation between $x_t$ and $u_{p_2^{-1}(t-1)}$ (cost-one operation)

$t < 2n$
Edge complementation between $z_{t+1}$ and $N(z_t)$ (cost-one operation)
Edge complementation between $x_{t+1}$ and $N(x_t)$ (cost-one operation)

$t=1,\dotsc, n$
Edge complementation between $u_t$ and $N(z_{p_1(t)})$ (cost-one operation)
Edge complementation between $u_t$ and $N(x_{p_1(t)})$ (cost-one operation)

Edge complementation between $u_t$ and $N(z_{p_2(t)})$ (cost-one operation)
Edge complementation between $u_t$ and $N(x_{p_2(t)})$ (cost-one operation)

Delete $\{z_i\}_{i=2,\dotsc,2n}$
Delete $\{x_i\}_{i=2,\dotsc,2n}$
$\{u_1,\dotsc, u_n\}$

$G=(V,E)$ is a circle graph if there exists a chord diagram such that
each vertex $v\in V$ corresponds to a chord and $\{v,w\}\in E$ if and only if the chords corresponding to $v$ and $w$ are intersecting.

For a simple representation of a circle graph, we can use a permutation $p$ of multiset $\{1,1,2,2,3,3,\dotsc,n,n\}$.
Then, we can define the circle graph defined by $p$ as $V=\{1,2,\dotsc,n\}$ and

\begin{align*}
E &= \left\{\{a, b\}\in\binom{V}{2}\,\middle|\, \text{$a$ and $b$ appear in $p$ in the order $abab$ or $baba$}\right\}.
\end{align*}

The class of circle graphs includes all permutation graphs, and hence has unbounded rank-width.
The class of circle graphs is closed under vertex-minor.

For any circle graph $G$ with $n$ vertices, Algorithm <ref> generates $G$ with the EC-complexity $10n-7$.

Let $G$ be a circle graph defined by a permutation $p$.

\begin{align*}
N_G(a) &=
\{b\mid p_1(b) < p_1(a)\} \bigtriangleup
(\{b\mid p_1(b) < p_2(a)\}\setminus\{a\}) \bigtriangleup
\{b\mid p_2(b) < p_1(a)\} \bigtriangleup
\{b\mid p_2(b) < p_2(a)\}.
\end{align*}

After the first “For loop”, the neighborhood of $z_t$ and $x_t$ are $\{u_k\mid p_1(k) < t\}$ and $\{u_k\mid p_2(k) < t \}$, respectively.
Then, the neighborhood of $u_t$ should be the symmetric difference of $N(z_{p_1(t)})$, $N(z_{p_2(t)})\setminus\{u_t\}$, $N(x_{p_1(t)})$ and $N(x_{p_2(t)})$.
The neighborhood of $u_t$ is generated by Lines 15, 16, 17 and 18.

Note that Algorithm <ref> gives a quantum algorithm that only uses the $H$, and adaptive-$Z$ operators, and does not use the $S$ operator.

§ ACKNOWLEDGMENT

The work of RM was supported by JST FOREST Program Grant Number JPMJFR216V and JSPS KAKENHI Grant Numbers JP20H04138, JP20H05966 and JP22H00522.

[1]
Jeremy C. Adcock, Sam Morley-Short, Axel Dahlberg, and Joshua W. Silverstone.
Mapping graph state orbits under local complementation.
Quantum, 4:305, Aug. 2020.

[2]
Sergey Bravyi, Joseph A. Latone, and Dmitri Maslov.
6-qubit optimal Clifford circuits.
npj Quantum Information, 8(1):79, 2022.

[3]
André Bouchet.
Digraph decompositions and eulerian systems.
SIAM Journal on Algebraic Discrete Methods, 8(3):323–337,

[4]
André Bouchet.
Isotropic systems.
European Journal of Combinatorics, 8(3):231–244, 1987.

[5]
André Bouchet.
Graphic presentations of isotropic systems.
Journal of Combinatorial Theory, Series B, 45(1):58–76, 1988.

[6]
André Bouchet.
Connectivity of isotropic systems.
Annals of the New York Academy of Sciences, 555(1):81–93,

[7]
André Bouchet.
$\kappa$-transformations, local complementations and switching.
In Geňa Hahn, Gert Sabidussi, and Robert E. Woodrow, editors,
Cycles and Rays, pages 41–50. Springer Netherlands, Dordrecht, 1990.

[8]
André Bouchet.
An efficient algorithm to recognize locally equivalent graphs.
Combinatorica, 11:315–329, 1991.

[9]
André Bouchet.
Recognizing locally equivalent graphs.
Discrete Mathematics, 114(1):75–86, 1993.

[10]
André Bouchet.
Circle graph obstructions.
Journal of Combinatorial Theory, Series B, 60(1):107–144,

[11]
Adán Cabello, Lars Eirik Danielsen, Antonio J. López-Tarrida, and José R.
Optimal preparation of graph states.
Phys. Rev. A, 83:042314, Apr. 2011.

[12]
Wolfgang Dür, Hans Aschauer, and Hans J. Briegel.
Multiparticle entanglement purification for graph states.
Phys. Rev. Lett., 91:107903, Sep. 2003.

[13]
Axel Dahlberg, Jonas Helsen, and Stephanie Wehner.
How to transform graph states using single-qubit operations:
Computational complexity and algorithms.
Quantum Science and Technology, 5(4):045016, Sep. 2020.

[14]
Axel Dahlberg and Stephanie Wehner.
Transforming graph states using single-qubit operations.
Philosophical Transactions of the Royal Society A: Mathematical,
Physical and Engineering Sciences, 376(2123):20170325, 2018.

[15]
Matthew B. Elliott, Bryan Eastin, and Carlton M. Caves.
Graphical description of the action of Clifford operators on
stabilizer states.
Phys. Rev. A, 77:042307, Apr. 2008.

[16]
Dmitriĭ G. Fon-Der-Flaass.
Local complementations of simple and directed graphs.
In Alekseǐ D. Korshunov, editor, Discrete Analysis and
Operations Research, pages 15–34. Springer Netherlands, Dordrecht, 1996.

[17]
Daniel Gottesman.
Stabilizer Codes and Quantum Error Correction.
PhD thesis, California Institute of Technology, 1997.

[18]
Martin C. Golumbic and Udi Rotics.
On the clique-width of some perfect graph classes.
International Journal of Foundations of Computer Science,
11(03):423–443, 2000.

[19]
Marc Hein, Jens Eisert, and Hans J. Briegel.
Multiparty entanglement in graph states.
Phys. Rev. A, 69:062311, Jun. 2004.

[20]
Peter Høyer, Mehdi Mhalla, and Simon Perdrix.
Resources required for preparing graph states.
In Algorithms and Computation: 17th International Symposium,
ISAAC 2006, Kolkata, India, December 18-20, 2006. Proceedings 17, pages
638–649. Springer, 2006.

[21]
Zhengfeng Ji, Jianxin Chen, Zhaohui Wei, and Mingsheng Ying.
The LU-LC conjecture is false.
Quantum Info. Comput., 10(1):97–108, Jan. 2010.

[22]
Anton Kotzig.
Eulerian lines in finite $4$-valent graphs and their
In Theory of Graphs (Proc. Colloq., Tihany, 1966),
pages 219–230. Academic Press, New York-London, 1968.

[23]
Choongbum Lee, Joonkyung Lee, and Sang-il Oum.
Rank-width of random graphs.
Journal of Graph Theory, 70(3):339–347, 2012.

[24]
Sang-il Oum and Paul Seymour.
Approximating clique-width and branch-width.
Journal of Combinatorial Theory, Series B, 96(4):514–528,

[25]
Sang-il Oum and Paul Seymour.
Testing branch-width.
Journal of Combinatorial Theory, Series B, 97(3):385–393,

[26]
Sang-il Oum.
Rank-width and vertex-minors.
Journal of Combinatorial Theory, Series B, 95(1):79–100, 2005.

[27]
Sang-il Oum.
Computing rank-width exactly.
Information Processing Letters, 109(13):745–748, 2009.

[28]
Sang-il Oum.
Rank-width: Algorithmic and structural results.
Discrete Applied Mathematics, 231:15–24, 2017.

[29]
Robert Raussendorf, Daniel E. Browne, and Hans J. Briegel.
Measurement-based quantum computation on cluster states.
Phys. Rev. A, 68:022312, Aug. 2003.

[30]
Maarten Van den Nest, Jeroen Dehaene, and Bart De Moor.
Graphical description of the action of local Clifford
transformations on graph states.
Phys. Rev. A, 69:022316, Feb. 2004.

§ PROOFS OF FACTS <REF> AND <REF>

§.§ Proof of Fact <ref>

Let $G$ be the common generating matrix for $\ket{\psi}$ and $\ket{\varphi}$.
Let $v\in\mathbb{F}_2^n$ be a vector where $v_i=1$ if and only if the sign of the $i$-th stabilizer for $\ket{\psi}$ and $\ket{\varphi}$ differs.
There exists a row vector $a\in\mathbb{F}_2^{2n}$ satisfying

\begin{align*}
\begin{bmatrix}
\end{bmatrix}
\end{align*}

\begin{bmatrix}
\end{bmatrix}\in\mathbb{F}_2^{n\times 2n}$ has linearly independent rows.
Then, $S_i \sigma_a\ket{\varphi} = (-1)^{v_i} \sigma_a\ket{\varphi}$ where $S_i$ is the $i$-th stabilizer of $\ket{\varphi}$.
Hence, $\sigma_a \ket{\varphi}$ has the same stabilizer as $\ket{\psi}$.

§.§ Proof of Fact <ref>

First, we prove that $L_C = I_{\mathbb{F}_2^{2n}}$ implies $C$ is in $\mathcal{G}_n$ up to a constant factor.
Assume $L_C = I_{\mathbb{F}_2^{2n}}$.
Then, for any $h\in\mathcal{G}_n$, there exists $\alpha_h\in\{\pm1\}$ such that $ChC^\dagger = \alpha_h h$.
For any $h_1,h_2\in\mathcal{G}_n$, $\alpha_{h_1h_2} h_1 h_2 = Ch_1h_2C^\dagger = C h_1 C^\dagger C h_2 C^\dagger= \alpha_{h_1}\alpha_{h_2} h_1 h_2$.
Hence, $\alpha_{h_1h_2} = \alpha_{h_1}\alpha_{h_2}$ for any $h_1,h_2\in\mathcal{G}_n$.
This implies that there exists $g\in\mathcal{G}_n$ such that $gh = \alpha_h hg$ for any $h\in\mathcal{G}_n$
as in the proof of Fact <ref>.
Then, $(Cg)h (Cg)^\dagger = \alpha_h ChC^\dagger = \alpha^2_h  h = h$.
Hence, $Cg$ commutes with any matrix in $\mathcal{G}_n$, and hence commutes with any matrix in $U(2^n)$.
This means that $Cg$ is equal to the identity matrix up to a constant factor.
Hence, $C$ is in $\mathcal{G}_n$ up to a constant factor.

Next, assume $L_C=L_D$. Then, $L_{C D^{-1}} = L_{D^{-1}} L_C = L_D^{-1} L_C = I_{\mathbb{F}_2^{2n}}$.
This means that there exists $g\in\mathcal{G}_n$ such that $C D^{-1}$ is equal to $g$ up to a constant factor.