# A graph-state based synthesis framework for Clifford isometries

Timothée Goubault de Brugière  Inria Mocqua, LORIA, CNRS, Université de
Lorraine, F-54000 Nancy, France  Simon Martiel  Atos Quantum Lab, Les Clayes-
sous-Bois, France  Christophe Vuillot  Inria Mocqua, LORIA, CNRS, Université
de Lorraine, F-54000 Nancy, France

###### Abstract

We tackle the problem of Clifford isometry compilation, i.e, how to synthesize
a Clifford isometry into an executable quantum circuit. We propose a simple
framework for synthesis that only exploits the elementary properties of the
Clifford group and one equation of the symplectic group. We highlight the
versatility of our framework by showing that several normal forms of the
literature are natural corollaries. We report an improvement of the two-qubit
depth necessary for the execution of a Clifford circuit on an LNN
architecture. We also apply our framework to the synthesis of graph states and
the codiagonalization of Pauli rotations and we improve the 2-qubit count and
2-qubit depth of circuits taken from quantum chemistry experiments.

##  1 Introduction

Clifford operators represent one of the most useful and one of the most
studied subclass of quantum operators. Clifford operators are involved in
numerous applications such as quantum error correction [1], randomized
benchmarking protocols [2, 3], quantum state distillation [4, 5], the study of
entanglement [6]. It is known that Clifford operators can be generated by the
Hadamard gates, the Phase gates and the CNOT gate [7]. Moreover the simulation
of such circuits, the so-called Clifford circuits, can be done efficiently on
a classical computer [8] and there is a one-to-one mapping between the
Clifford operators and the $2n\times 2n$ binary matrices from the symplectic
group $Sp(2n,\mathbb{F}_{2})$.

Our work lies in the domain of quantum compilation for the quantum circuit
model, where one wants to generate quantum circuits for a given hardware to
execute a given quantum algorithm. Given the variety of quantum hardwares,
each having its own set of universal gates, its own costly resources, and
given the different approaches for quantum computation, namely a fault-
tolerant approach [9, 10] or a NISQ approach [11], today’s compilers have to
be able to generate and optimize quantum circuits for several metrics (number
of non Clifford gates, number of entangling gates, depth), several set of
gates (Clifford+T, MS+SU(2), etc.) and several architectures (Rigetti [12],
IBM [13, 14], Google [15], etc.). While universal for quantum computation, the
Clifford group plays a significant role in quantum compilation for several
types of hardware [16, 17, 18] in both a NISQ of a fault-tolerant setting and
notably for the hardwares using the Clifford+T gate set, one of the most
studied gate set for compilation problems. In this setting, the available
multi-qubit gates, generally the 2-qubit CNOT gate or the CZ gate, belong to
the Clifford group and looking at a quantum circuit as a succession of
Clifford operators separated by layers of T-gates is one way to express the
problem of optimizing 2-qubit cost as a Clifford circuit optimization problem.
Given that the abstract and compact representation of Clifford operators makes
it easier to design efficient synthesis algorithms the Clifford operator
synthesis problem emerges naturally as an essential brick for quantum circuit
optimization, and notably to reduce the 2-qubit cost.

The structure of the Clifford group has been deeply studied in the literature.
Notably, many normal forms for Clifford circuits have been proposed [7, 19,
20, 21, 22]. Those normal forms express any Clifford operator as a series of
stages containing one particular gate. For instance, the first normal form
proposed by Aaronson and Gottesman is -H-CX-P-CX-P-CX-H-P-CX-P where -H-
stands for a stage of Hadamard gates, -P- a stage of phase gates, and -CX- a
stage of CNOT gates [7]. An important part of the work in Clifford circuits
synthesis during the last decade was to propose shorter normal forms,
resulting in shorter or shallower circuits with respect to the 2-qubit gates.
Normal forms for the preparation of stabilizer states (states that can be
prepared with a Clifford circuit) have also been proposed [7, 23, 24]. Those
normal forms, while being universal, impose a strict structure on the produced
circuits and may fail to find more efficient implementations for a given
operator. Notably the most recent normal forms expose the role of a particular
class of quantum operators, the so-called phase polynomials, in the
implementation of a Clifford operator [19, 21]. Phase polynomials are now
extensively studied in the literature and the best synthesis algorithms show
that a stage by stage implementation of phase polynomials is irrelevant [25,
26]. We can expect that a more efficient approach for Clifford synthesis that
does not rely on a stage by stage implementation can also be found.

Optimal synthesis of Clifford operators through brute-force search has been
recently proposed [27], but for the moment the method is limited to small
Clifford circuits, up to 6 qubits. Other works in the literature also focus on
directly optimizing Clifford circuits through template matchings or peephole
optimizations [28, 29]. These methods cannot handle the synthesis from an
abstract representation nor leverage the global structure of these operators
with potential efficiency and performance loss.

Overall, it lacks an efficient approach to synthesize Clifford operators other
than by using normal forms or the unpractical tableau formalism. Furthermore,
there are many cases in the literature where only a partial implementation of
a Clifford operator is necessary: obviously the synthesis of stabilizer states
is one example, but more generally the synthesis of Clifford isometries where
some of the input qubits are in the state $\ket{0}$ is of particular interest
in some error-correction protocols such as magic state distillation [30, 31].
Again, to our knowledge, no work in the literature proposes to generalize the
concept of normal forms and synthesis frameworks to Clifford isometries.

The main result of our paper is a generalized synthesis framework for Clifford
isometries. Our framework is strongly inspired by the results obtained via the
ZX-calculus for the optimization of quantum circuits [20] although the
derivation of our framework is done without any use of the ZX-calculus.
Indeed, our proof uses only the properties of the Clifford group and the
symplectic matrices used to represent Clifford operators. Our framework shares
also some similarities with the normal form proposed in [21]. Where our
framework stands out is first of all in its simplicity: it only requires to
reduce a symmetric boolean matrix into a suitable defined identity matrix with
the use of a few elementary operations, each corresponding to one elementary
Clifford gate. Notably it naturally includes the Hadamard gate in the
available operations, which is the gate that is missing when considering a
Clifford operator with stages of phase polynomials. We also highlight its
versatility by showing that many normal forms proposed in the literature can
be trivially recovered. Similarly to [21], we also characterize more precisely
the operators involved in the synthesis of one operator when the gate set is
restricted to $\\{CNOT,CZ,S\\}$. We show that any Clifford operator on $n$
qubits can be executed in two-qubit depth $7n$ on a Linear Nearest Neighbour
(LNN) architecture, improving the previous best result of $9n$ [20, 21].
Finally we apply our framework to the synthesis of graph states and the
codiagonalization of groups of commuting Pauli rotations, we apply our
algorithms to a set of benchmarks from quantum chemistry and report
improvements over the state of the art in both the number of 2-qubit gates and
the 2-qubit depth.

##  2 Background

###  2.1 Quantum isometries

An isometry is a generalization of quantum states and quantum operators. They
map Hilbert spaces of possibly two different dimensions and they preserve the
inner products, similarly to unitary matrices.

######  Definition 1.

Let $0\leq k\leq n$ be two integers. A $k$ to $n$ isometry can be represented
by a $2^{n}\times 2^{k}$ complex matrix $V$ such that

$V^{{\dagger}}V=I_{2^{k}\times 2^{k}}.$

In other words, isometries can be seen as the action of a quantum operator on
a quantum memory where some of the qubits are in the state $\ket{0}$ — those
qubits can be regarded as ancillary qubits. Generally the compilation of
isometries result in shorter circuits than systematically synthesizing the
full quantum operator because the ancillary qubits in a fixed input state
offer some degrees of freedom in the synthesis. Clearly, a state preparation
is usually less costly than a full operator compilation.

In this paper we focus on the synthesis of a particular subclass of
isometries: Clifford isometries, i.e, isometries that can be generated by a
Clifford operator.

###  2.2 Pauli matrices and the Clifford group

The Pauli matrices are defined by

$I=\begin{bmatrix}1&0\\\ 0&1\end{bmatrix},X=\begin{bmatrix}0&1\\\
1&0\end{bmatrix},Z=\begin{bmatrix}1&0\\\
0&-1\end{bmatrix},Y=\begin{bmatrix}0&-i\\\ i&0\end{bmatrix}$

and they obey the following equations:

$X^{2}=Y^{2}=Z^{2}=I=\begin{bmatrix}1&0\\\ 0&1\end{bmatrix},$ $XY=iZ,$
$ZX=iY,$ $YZ=iX.$

Therefore, the Pauli matrices generate a group where any member can be written
as

$i^{k}\\{I,X,Y,Z\\}\text{ for some $k\in\\{0,1,2,3\\}$. }$

This generalizes to several qubits: a Pauli operator on $n$ qubits is any
operator of the form

$P=i^{k}\bigotimes_{j=1}^{n}G_{j},\text{ where
}G_{j}\in\\{I,X,Z,Y\\},k\in\\{0,1,2,3\\}.$

We write $\mathcal{P}_{n}$ for the set of Pauli operators on $n$ qubits. For
conciseness any Pauli operator, up to the global phase, can be written as a
Pauli word, for instance $IZXI=I\otimes Z\otimes X\otimes I$. We also write
$G_{j},G\in\\{X,Z,Y\\}$, the Pauli operator that applies solely the operator
$G$ on qubit $j$.

With the 2-bit encoding

$I\rightarrow 00,X\rightarrow 01,Z\rightarrow 10,Y\rightarrow 11$

we can always represent a Pauli operator with a boolean vector $p$ of size
$2n$ where $(p[j],p[j+n])$ encodes the Pauli matrix applied on qubit $j$ plus
an extra two bits to encode the value of $k$. We write $P$ interchangeably for
the Pauli operator or the associated boolean vector.

Example:

$YZXI=\begin{bmatrix}1\\\ 1\\\ 0\\\ 0\\\ \---\\\ 1\\\ 0\\\ 1\\\
0\end{bmatrix}.$

Given such a boolean vector $P$, we write $P^{Z}$ for the first $n$ values of
$P$ (encoding the $Z$ components) and $P^{X}$ for the last $n$ values
(encoding the $X$ components). The product of two Pauli operators
$(P,k)=(P_{1},k_{1})\times(P_{2},k_{2})$ is given by

$P=P_{1}\oplus P_{2}$
$k=k_{1}+k_{2}+\|P_{2}^{X}*P_{1}^{Z}\|-\|P_{1}^{X}*P_{2}^{Z}\|\mod 4$

i.e, the boolean vector of the product of two Pauli operators is given by the
bitwise XOR of the associated boolean vectors. Here $\|\cdot\|$ stands for the
Hamming norm and $*$ stands for the element-wise product.

######  Definition 2.

The Clifford group on $n$ qubits is defined by

$\mathcal{C}_{n}=\\{U\in\mathcal{U}(2^{n})\;|\;UPU^{{\dagger}}\in\mathcal{P}_{n}\;\;\forall
P\in\mathcal{P}_{n}\\}.$

For the rest of the paper, we will solely focus on the conjugation of Pauli
operators of the form

$\bigotimes_{j=1}^{n}G_{j},\text{ where }G_{j}\in\\{I,X,Z,Y\\}$

i.e, without a global phase.

######  Property 1.

The conjugations of any n-qubit Pauli word can be efficiently stored in a
boolean vector of size $2n+1$.

###### Proof.

The eigenvalues of the Pauli matrices without a global phase are $\\{-1,1\\}$
and are unchanged after the conjugation by a Clifford. Therefore, the
conjugations obtained can only be of the form

$(-1)^{k}\bigotimes_{j=1}^{n}G_{j},\text{ where
}G_{j}\in\\{I,X,Z,Y\\},k\in\\{0,1\\}$

and we only have to store the value of $k$ on one bit.

∎

###  2.3 Tableau representation of Clifford isometries

It is well-known that Clifford operators can be efficiently represented by a
polynomial sized tableau with boolean entries and the tableau can also be
efficiently updated when multiplied by another Clifford operator. This relies
on the fact that only the conjugations of the Pauli operators
$Z_{i},X_{i},i=1\ldots n$ are sufficient to fully characterize an n-qubit
Clifford operator111By product we get the conjugation of any Pauli word, and
the set of the $4^{n}$ Pauli words is a basis for the full set of complex
matrices.. The tableau is of size $(2n+1)\times 2n$, one column for each
conjugation, and the first $2n$ rows define a boolean matrix that belongs to
the symplectic group $Sp(2n,\mathbb{F}_{2})$. A matrix $M$ in the symplectic
group satisfies the following relation:

$M\Omega M^{T}=\Omega$

where $\Omega=\begin{bmatrix}0&I_{n}\\\ I_{n}&0\end{bmatrix}$. The symplectic
product between two Pauli vectors is $0$ if they commute and $1$ otherwise. So
matrices in the symplectic group are simply one case of commutation relations
between a set of Pauli vectors. Given that the identity tableau is symplectic
and that $CP_{1}C^{{\dagger}}$ and $CP_{2}C^{{\dagger}}$ have the same
commutation relation as $P_{1}$ and $P_{2}$, the tableau of any Clifford
operator $C$ necessarily has the same commutation relations as the identity
tableau and the tableau belongs to the symplectic group.

We write the tableau

$M=\begin{bmatrix}Z\to Z&X\to Z\\\ Z\to X&X\to X\end{bmatrix}$

where the block $Z/X\to Z/X$ explicitly shows which part corresponds to the
$Z/X$ components of the images of the $Z_{i}/X_{i}$ operators.

This efficient representation can be generalized to Clifford isometries and we
give a constructive proof that a $k$ to $n$ Clifford isometry can be
represented by a subset of $n+k$ columns of the tableau of a Clifford
operator. We also show that this representation is not unique and we give a
construction of the equivalence class.

######  Theorem 1.

Any $k$ to $n$ Clifford isometry $V$ can be represented by $n+k$ columns of a
Clifford tableau $M$. We write

$M_{V}=\begin{bmatrix}Z_{1}\to Z&Z_{2}\to Z&X\to Z\\\ Z_{1}\to X&Z_{2}\to
X&X\to X\end{bmatrix}$

where

  * •

$\begin{bmatrix}Z_{1}\to Z\\\ Z_{1}\to
X\end{bmatrix}\in\mathbb{F}_{2}^{(2n+1)\times k}$ encodes the conjugations of
$Z_{i},i=1\ldots k$,

  * •

$\begin{bmatrix}Z_{2}\to Z\\\ Z_{2}\to
X\end{bmatrix}\in\mathbb{F}_{2}^{(2n+1)\times(n-k)}$ encodes the conjugations
of $Z_{i},i=k+1\ldots n$

  * •

$\begin{bmatrix}X\to Z\\\ X\to X\end{bmatrix}\in\mathbb{F}_{2}^{(2n+1)\times
k}$ encodes the conjugations of $X_{i},i=1\ldots k$.

Moreover, any of the $n-k$ columns of $\begin{bmatrix}Z_{2}\to Z\\\ Z_{2}\to
X\end{bmatrix}$ can be added to any other column other than itself such that
the specification of the isometry is unchanged.

###### Proof.

Let $V$ be a $k$ to $n$ Clifford isometry. There exists a Clifford operator
$C$ such that $V$ is characterized by the set

$\\{V\ket{b}=C\ket{b}\ket{0}^{\otimes n-k}\,|\,b\in\mathbb{F}_{2}^{k}.\\}.$

Let $\ket{\psi}=C\ket{0}^{\otimes n}$, we have

$\displaystyle\forall b\in\mathbb{F}_{2}^{k},C\ket{b}\ket{0}^{\otimes n-k}$
$\displaystyle=C\bigotimes_{i=1}^{k}X_{i}^{b_{i}}\ket{0}^{\otimes n}$
$\displaystyle=C\bigotimes_{i=1}^{k}X_{i}^{b_{i}}C^{{\dagger}}C\ket{0}^{\otimes
n}$
$\displaystyle=\left(C\bigotimes_{i=1}^{k}X_{i}^{b_{i}}C^{{\dagger}}\right)\ket{\psi}.$

Therefore, $V$ is completely characterized by the values of

$C\bigotimes_{i=1}^{k}X_{i}^{b_{i}}C^{{\dagger}}\ket{\psi},\forall
b\in\mathbb{F}_{2}^{k}.$

By product we only need the knowledge of $\ket{\psi}$ and
$CX_{i}C^{{\dagger}},i=1\ldots k$. Equivalently we only need the states
$VX_{i}\ket{0}^{\otimes k},i=1\ldots k$.

It is well-known that a Clifford state is completely determined by the
knowledge of $n$ Pauli operators that stabilize the state [7]. Given that

$Z_{i}\ket{0}^{\otimes n}=\ket{0}^{\otimes n},\;i=1\ldots n,$

we have

$CZ_{i}C^{{\dagger}}\ket{\psi}=\ket{\psi},\;i=1\ldots n$

that represent such a set of stabilizers for $\ket{\psi}$.

Overall, we need the values of

$CZ_{i}C^{{\dagger}},\;i=1\ldots n$

and

$CX_{i}C^{{\dagger}},\;i=1\ldots k$

to completely determine $V$. The tableau representation of $C$ gives the
conjugations of $Z_{i},X_{i},i=1\ldots n$ by $C$ so finally we only need the
first $n+k$ columns of the tableau of $C$.

We write

$M_{V}=\begin{bmatrix}Z_{1}\to Z&Z_{2}\to Z&X\to Z\\\ Z_{1}\to X&Z_{2}\to
X&X\to X\end{bmatrix}$

where

  * •

$\begin{bmatrix}Z_{1}\to Z\\\ Z_{1}\to
X\end{bmatrix}\in\mathbb{F}_{2}^{(2n+1)\times k}$ encodes the conjugations of
$Z_{i},i=1\ldots k$,

  * •

$\begin{bmatrix}Z_{2}\to Z\\\ Z_{2}\to
X\end{bmatrix}\in\mathbb{F}_{2}^{(2n+1)\times(n-k)}$ encodes the conjugations
of $Z_{i},i=k+1\ldots n$

  * •

$\begin{bmatrix}X\to Z\\\ X\to X\end{bmatrix}\in\mathbb{F}_{2}^{(2n+1)\times
k}$ encodes the conjugations of $X_{i},i=1\ldots k$.

We now show that adding any column of $\begin{bmatrix}Z_{2}\to Z\\\ Z_{2}\to
X\end{bmatrix}$ to any column of $\begin{bmatrix}X\to Z\\\ X\to
X\end{bmatrix}$ does not modify the isometry specified.

This result relies on the following identities

$\displaystyle\forall i\in{[\\![}1,k{]\\!]},\forall
a\in\mathbb{F}_{2}^{n-k},\;VX_{i}\ket{0}^{\otimes k}$
$\displaystyle=CX_{i}\ket{0}^{\otimes n}$
$\displaystyle=CX_{i}\bigotimes_{i=k+1}^{n}Z_{i}^{a_{i-k}}\ket{0}^{\otimes n}$
$\displaystyle=C\left(X_{i}\bigotimes_{j=k+1}^{n}Z_{j}^{a_{j-k}}\right)C^{{\dagger}}\ket{\psi}$
$\displaystyle=\underbrace{\left(CX_{i}C^{{\dagger}}\right)}_{\text{one column
of }\begin{bmatrix}X\to Z\\\ X\to
X\end{bmatrix}}\times\bigotimes_{i=k+1}^{n}\underbrace{\left(CZ_{i}^{a_{i-k}}C^{{\dagger}}\right)}_{\text{one
column of }\begin{bmatrix}Z_{2}\to Z\\\ Z_{2}\to X\end{bmatrix}}\ket{\psi},$

Normally, to reconstruct the states $VX_{i}\ket{0}^{\otimes k}$ from our
tableau, we need the images of the $Z_{i}$’s to reconstruct $\ket{\psi}$ and
the images of the $X_{i}$. What the identity above shows is that if we know
any image of a Pauli word of the form
$X_{i}\bigotimes_{j=k+1}^{n}Z_{j}^{a_{j-k}},a\in\mathbb{F}_{2}^{n-k}$ then we
can still reconstruct the desired state. This is equivalent to adding any
column of $\begin{bmatrix}Z_{2}\to Z\\\ Z_{2}\to X\end{bmatrix}$ to any column
of $\begin{bmatrix}X\to Z\\\ X\to X\end{bmatrix}$. Similarly, adding any
column of $\begin{bmatrix}Z_{2}\to Z\\\ Z_{2}\to X\end{bmatrix}$ to
$\begin{bmatrix}Z_{1}\to Z\\\ Z_{1}\to X\end{bmatrix}$ and
$\begin{bmatrix}Z_{2}\to Z\\\ Z_{2}\to X\end{bmatrix}$ (other than itself)
only gives a new basis for the stabilizers of $\ket{\psi}$ but it does not
change the specification of $\ket{\psi}$.

∎

###  2.4 The synthesis problem

We propose one formalization of the synthesis of Clifford isometries. We work
in the gate set $\\{H,S,CZ,CNOT\\}$ which is known to be universal for
Clifford computation. We suppose we are given the tableau representation
$M_{V}$ of a $k$ to $n$ isometry. We only have access to a black box
representation of the isometry in a circuit, see Figure 1.

Figure 1: Illustration of the synthesis framework: gates and their inverses
are applied on the left and right of the isometry. One gate is merged with the
isometry while the other one is stacked into a left/right circuit. Once
$M_{V}=I$, then $C_{l}::C_{r}$ implements the desired isometry.

####  2.4.1 Action of the elementary gates.

Given a black box circuit implementing the isometry $V$, adding a gate $G_{1}$
from the right gives the operator $G_{1}V$ to characterize and we therefore
need to compute the values of

$G_{1}VZ_{i}(G_{1}V)^{{\dagger}}=G_{1}\left(VZ_{i}V^{{\dagger}}\right)G_{1}^{{\dagger}},i=1..n$

and

$G_{1}VX_{i}(G_{1}V)^{{\dagger}}=G_{1}\left(VX_{i}V^{{\dagger}}\right)G_{1}^{{\dagger}},i=1..k.$

The values of $VZ_{i}V^{{\dagger}}$ and $VX_{i}V^{{\dagger}}$ are given by
$M_{V}$ and by the rules of conjugation we know how to directly update
$M_{V}$. For simplicity we write

$M_{V}=\begin{bmatrix}T\\\ r\end{bmatrix}$

where $r$ stands for the sign vector and $T$ is the $(2n\times(n+k))$ matrix
that specifies the conjugations without the sign. We also note $\land$ for the
bitwise AND operation.

  * •

Hadamard on qubit $m$: swap rows $m$ and $n+m$, set

$r=r\oplus\left(T[m,:]\land T[n+m,:]\right),$

  * •

S on qubits $m$: add row $n+m$ to row $m$, set

$r=r\oplus\left(T[m,:]\land T[n+m,:]\right),$

  * •

CZ on qubits $p,m$: add row $n+p$ to row $m$ and row $n+m$ to row $p$, set

$r=r\oplus\big{[}T[n+m,:]\land T[n+p,:]\land\left(T[p,:]\oplus
T[m,:]\right)\big{]},$

  * •

CNOT with control $p$ and target $m$: add row $n+p$ to row $n+m$ and row $m$
to row $p$, set

$r=r\oplus\big{[}T[n+p,:]\land T[m,:]\land\left(1\oplus T[n+m,:]\oplus
T[p,:]\right)\big{]}.$

When a gate $G_{2}$ is added from the left the simulation, we need the values
of

$VG_{2}Z_{i}G_{2}^{{\dagger}}V^{{\dagger}}$

and

$VG_{2}X_{i}G_{2}^{{\dagger}}V^{{\dagger}}.$

Writing
$G_{2}Z_{i}G_{2}^{{\dagger}}=\bigoplus_{i}a_{i}Z_{i}\oplus\bigoplus_{i}b_{i}X_{i},a_{i}\in\\{0,1\\},b_{i}\\{0,1\\}$
we have

$VG_{2}Z_{i}G_{2}^{{\dagger}}V^{{\dagger}}=\bigoplus_{i}a_{i}\left(VZ_{i}V^{{\dagger}}\right)\oplus\bigoplus_{i}b_{i}\left(VX_{i}V^{{\dagger}}\right).$

Therefore the values of $VG_{2}Z_{i}G_{2}^{{\dagger}}V^{{\dagger}}$ are linear
combinations of the columns of $M_{V}$. The same applies for the values of
$VG_{2}X_{i}G_{2}^{{\dagger}}V^{{\dagger}}$.

This gives:

  * •

Hadamard on qubit $m$: swap columns $m$ and $n+m$,

  * •

S on qubits $m$: add column $m$ to column $n+m$,

  * •

CZ on qubits $p,m$: add column $p$ to column $n+m$ and column $m$ to column
$n+p$,

  * •

CNOT with control $p$ and target $m$: add column $p$ to column $m$ and column
$n+m$ to column $n+p$,

Similar updates for the sign vector can be derived.

For the rest of the paper we will now refer as the input qubits the $k$ qubits
on which a gate can be applied on the left. Similarly we refer as the output
qubits the $n$ qubits on which a gate can be applied on the right.

####  2.4.2 The synthesis workflow.

The synthesis process consists in adding a Clifford gate and its inverse side
by side on the left or right of the black box isometry, as shown in Fig. 1.
This will not change the overall functionality of the circuit but one can
merge one Clifford gate to the black box and update $M_{V}$. At the same time
the inverse gate is stacked to a list of left or right operations. When
$M_{V}$ is equal to the identity tableau, we have a valid sequence of
operations implementing the Clifford isometry by stacking the left operations
and the reverse of the right operations.

Note that we can only focus on reducing $T$ to the identity because the sign
vector can be treated separately at the end of the computation. Indeed, if
$T=I$, applying twice an $S$ gate on qubit $m$ on the right will simply do the
operation

$r[m]=r[m]\oplus 1.$

In other words, keeping track of the value of $r$ is sufficient because it can
be ultimately zeroed with a layer of $Z$ gates.

Designing synthesis algorithms directly from the tableau representation is
clumsy. For the synthesis of Clifford states and Clifford operators the
derivation of normal forms is common instead of proposing a direct synthesis
algorithm [7, 19, 20, 21, 22, 23, 24].

We try to overcome both the difficulty of manipulating the Clifford tableaus
and the necessity to use normal forms by proposing a simple framework for the
synthesis of Clifford isometries. One advantage of our framework will be its
versatility: it can be used to design either direct synthesis algorithms or to
prove normal forms.

##  3 A graph-state formalism for Clifford isometries synthesis

We prove that any $k$ to $n$ Clifford isometry can be put in a graph-state
form up to local Hadamard gates. Then we derive a synthesis framework by
showing the behavior of the different elementary Clifford gates.

###  3.1 Graph-state structure of the tableau representation

First, we prove a normal form for symplectic matrices that exposes an
underlying graph-state structure of Clifford operators.

######  Theorem 2.

Let $M=\begin{bmatrix}A&C\\\ B&D\end{bmatrix}=\begin{bmatrix}Z\to Z&X\to Z\\\
Z\to X&X\to X\end{bmatrix}\in Sp(2n,\mathbb{F}_{2})$. If $B$ is invertible,
then there exist two boolean symmetric matrices $S,S^{\prime}$ such that

$M=\left[\begin{array}[]{c|c}S^{\prime}B&(B^{T})^{-1}\oplus S^{\prime}BS\\\
\hline\cr B&BS\end{array}\right].$ (1)

###### Proof.

If $B$ is invertible, then we can define $S=B^{-1}D$ and $S^{\prime}=AB^{-1}$
and $K=C\oplus(B^{T})^{-1}$ such that

$A=S^{\prime}B,$ $D=BS,$ $C=(B^{T})^{-1}\oplus K.$

Matrices in the symplectic group verify three different equations. One of them
will prove that $K=S^{\prime}BS$ and the two others will show that $S$ and
$S^{\prime}$ are symmetric.

  1. 1.

$B^{T}A\oplus A^{T}B=0$ gives

$B^{T}S^{\prime}B\oplus B^{T}S^{\prime T}B=B^{T}(S^{\prime}\oplus S^{\prime
T})B=0$

which is possible if and only if $S^{\prime}=S^{\prime T}$.

  2. 2.

$B^{T}C\oplus A^{T}D=I$ gives

$B^{T}((B^{T})^{-1}\oplus K)\oplus B^{T}S^{\prime T}BS=I\oplus B^{T}(K\oplus
S^{\prime}BS)=I.$

So we have $B^{T}(K\oplus S^{\prime}BS)=0$ which is possible if and only if
$K=S^{\prime}BS$.

  3. 3.

$D^{T}C\oplus C^{T}D=0$ gives

$\displaystyle S^{T}B^{T}(B^{-T}\oplus S^{\prime}BS)\oplus((B^{-T}\oplus
S^{\prime}BS))^{T}BS$ $\displaystyle=S^{T}B^{T}B^{-T}\oplus
S^{T}B^{T}S^{\prime}BS\oplus B^{-1}BS\oplus S^{T}B^{T}S^{\prime T}BS$
$\displaystyle=S^{T}\oplus S=0$

which is possible if and only if $S=S^{T}$.

∎

This trivially extends to Clifford isometries:

######  Corollary 1.

Let $M_{V}=\begin{bmatrix}A&C\\\
B&D\end{bmatrix}\in\mathbb{F}_{2}^{2n\times(n+k)}$ be the tableau
representation of a Clifford isometry. If $B$ is invertible, then there exist
two boolean symmetric matrices $G_{k}\in F_{2}^{k\times k},G_{n}\in
F_{2}^{n\times n}$ such that

$M_{V}=\left[\begin{array}[]{c|c}G_{n}B&(B^{T})^{-1}\begin{pmatrix}I_{k}\\\
0\end{pmatrix}\oplus G_{n}B\begin{pmatrix}G_{k}\\\ 0\end{pmatrix}\\\ \hline\cr
B&B\begin{pmatrix}G_{k}\\\ 0\end{pmatrix}\end{array}\right].$ (2)

###### Proof.

From Eq. 1, by taking the first $n+k$ columns we have an operator of the form

$M_{V}=\left[\begin{array}[]{c|c}G_{n}B&(B^{T})^{-1}\begin{pmatrix}I_{k}\\\
0\end{pmatrix}\oplus G_{n}B\begin{pmatrix}G_{k}\\\ F\end{pmatrix}\\\ \hline\cr
B&B\begin{pmatrix}G_{k}\\\ F\end{pmatrix}\end{array}\right]$

where $F\in F_{2}^{(n-k)\times k}$ is an arbitrary rectangular boolean matrix,
$G_{n}$ is $S^{\prime}$ in Eq. 1 and $G_{k}$ is the top block $k\times k$ of
$S$.

We rewrite $M_{V}$ as

$M_{V}=\left[\begin{array}[]{c|c|c}G_{n}B\begin{pmatrix}I_{k}\\\
0_{(n-k)\times k}\end{pmatrix}&G_{n}B\begin{pmatrix}0_{k\times(n-k)}\\\
I_{n-k}\end{pmatrix}&(B^{T})^{-1}\begin{pmatrix}I_{k}\\\ 0\end{pmatrix}\oplus
G_{n}B\begin{pmatrix}G_{k}\\\ F\end{pmatrix}\\\ \hline\cr
B\begin{pmatrix}I_{k}\\\ 0_{(n-k)\times
k}\end{pmatrix}&B\begin{pmatrix}0_{k\times(n-k)}\\\
I_{n-k}\end{pmatrix}&B\begin{pmatrix}G_{k}\\\
F\end{pmatrix}\end{array}\right]$

and we recall from Theorem 1 that adding any column $k+1\ldots n$ to any
column $n+1\ldots n+k$ of $M_{V}$ is free and does not change the
functionality of the Clifford isometry. So with suitable column operations we
can zero $F$. Hence the result.

∎

######  Theorem 3.

Any Clifford isometry, up to Hadamard gates on the output qubits, has a normal
form given by Eq. 2.

###### Proof.

It is sufficient to prove that for any tableau representation of a Clifford
isometry the action of Hadamard gates on the output qubits, i.e, specific row
swaps on the tableau, is enough to make $B$ invertible. This is a well-known
result already proved in [7] for instance.

∎

At first sight, it seems that a Clifford isometry is determined by the values
of $G_{n},G_{k},B$ and $F$. In fact, the knowledge of $G_{n},G_{k}$ and a
submatrix of $B$ is sufficient:

######  Theorem 4.

Given a Clifford isometry of the form given by Eq. 2, if $G_{k},G_{n}$ are
equal to the null matrix and if $B=\begin{bmatrix}I_{k}&0_{k\times(n-k)}\\\
B^{\prime}&B^{\prime\prime}\end{bmatrix}$ for some boolean matrices
$B^{\prime},B^{\prime\prime}$, then the Clifford isometry acts as the
$H^{\otimes n}$ operator on the quantum memory.

###### Proof.

Replacing in Eq. 2 gives

$M_{V}=\left[\begin{array}[]{c|c}0&(B^{T})^{-1}\begin{pmatrix}I_{k}\\\
0\end{pmatrix}\\\ \hline\cr B&0\end{array}\right].$

Given that $B=\begin{bmatrix}I_{k}&0_{k\times(n-k)}\\\
B^{\prime}&B^{\prime\prime}\end{bmatrix}$, we also have
$B^{-1}=\begin{bmatrix}I_{k}&0_{k\times(n-k)}\\\
B^{\prime\prime\prime}&B^{\prime\prime\prime\prime}\end{bmatrix}$ for some
boolean matrices $B^{\prime\prime\prime},B^{\prime\prime\prime\prime}$.
Therefore, it is easy to check that

$(B^{T})^{-1}\begin{bmatrix}I_{k}\\\ 0\end{bmatrix}=\begin{bmatrix}I_{k}\\\
0\end{bmatrix}$

Overall, we have a new block structure for $M_{V}$,

$M_{V}=\left[\begin{array}[]{c|c|c}0&0&\begin{pmatrix}I_{k}\\\
0\end{pmatrix}\\\ \hline\cr I_{k}&0_{k\times(n-k)}&0\\\
B^{\prime}&B^{\prime\prime}&0\end{array}\right].$

$B$ is invertible, therefore $B^{\prime\prime}$ is also invertible. We recall
that we can add any column of $B^{\prime\prime}$ on any other column of
$M_{V}$, it does not change the functionality of the Clifford isometry. So
with suitable column operations we can reduce $B^{\prime\prime}$ to the
identity operator and zero $B^{\prime}$. We end with the operator

$M_{V}=\left[\begin{array}[]{c|c}0_{k\times n}&I_{k}\\\ 0_{(n-k)\times
n}&0_{(n-k)\times k}\\\ \hline\cr I_{n}&0_{n\times k}\end{array}\right].$

which correspond to the $k$ to $n$ isometry $H^{\otimes
k}\otimes\ket{+}^{n-k}$.

∎

This means that the last $n-k$ rows of $B$ or $B^{-1}$ do not influence the
specification of the isometry and it is useless to keep track of their values.
Instead, we set

$G=\begin{bmatrix}G_{k}&B_{k}\\\ B_{k}^{T}&G_{n}\end{bmatrix}$

where $B_{k}=B^{-1}[1:k,:]\in F_{2}^{k\times n}$. This is the graph-state form
of the Clifford isometry because $G$ can be seen as an adjacency matrix and as
we will see the $CZ$ gates directly add or remove an edge from $G$, similarly
to the graph-state formalism.

The goal is to reduce $G$ to

$\left[\begin{array}[]{c|cc}0_{k}&I_{k}&0_{k\times(n-k)}\\\ \hline\cr
I_{k}&\lx@intercol\hfil\hbox{\multirowsetup$0_{n\times
n}$}\hfil\lx@intercol\\\ 0_{n-k\times k}\end{array}\right].$

Indeed, when $G_{n}=0,G_{k}=0$ and $B_{k}=\begin{bmatrix}I_{k}\\\
0_{(n-k)\times k}\end{bmatrix}$ we have seen from the proof above that $M_{V}$
acts as the $H^{\otimes n}$ operator. Adding $n$ Hadamard gates from the right
in the framework illustrated in Fig. 1 reduces $M_{V}$ to the identity
isometry and this finishes the synthesis.

###  3.2 Available operations

We now list the action of the authorized operations on $G$. We write $e_{i}$
the $i$-th canonical vector, $e_{ij}$ the matrix with all zero except on entry
$(i,j)$ and $E_{ij}=I\oplus e_{ij}$. For clarity we also note
$\tilde{e}_{ij}=e_{ij}\oplus e_{ji}$ if $i\neq j$ and $\tilde{e}_{ii}=e_{ii}$.
The proofs are given in the Appendix.

  * •

$S$ on the output qubit $i$ ($1\leq i\leq n$):

$G=G\oplus\tilde{e}_{i+k,i+k}$

  * •

$S$ on the input qubit $i$ ($1\leq i\leq k$):

$G=G\oplus\tilde{e}_{i,i}$

  * •

$CZ$ on the output qubits $i,j$ ($1\leq i<j\leq n$):

$G=G\oplus\tilde{e}_{i+k,j+k}$

  * •

$CZ$ on the input qubits $i,j$ ($1\leq i<j\leq n$):

$G=G\oplus\tilde{e}_{ij}$

  * •

$CNOT$ on the output qubits with control $i$, target $j$ ($1\leq i<j\leq n$):

$G=E_{i+k,j+k}GE_{j+k,i+k}.$

  * •

$CNOT$ on the input qubits with control $i$, target $j$ ($1\leq i<j\leq k$):

$G=E_{ij}GE_{ji}.$

Contrary to the other gates that preserve the structure of Eq. 2, the Hadamard
gate and the $R_{x}(\pi/2)$ gate do not guarantee it because the matrix $B$
can become non invertible. We need to separate two cases.

  * •

if $G_{n}[i,i]=0$, then we can apply an $R_{x}(\pi/2)$ on the output qubit
$i$:

$G\leftarrow G\oplus G[:,k+i]G[:,k+i]^{T}.$

  * •

if $G_{n}[i,i]=1$, then we apply an Hadamard gate on the output qubit $i$, or
equivalently we apply $SR_{x}(\pi/2)S$, and the action on $G$ is

$G\leftarrow G\oplus g_{i}g_{i}^{T}$

where $g_{i}=G[:,k+i]\oplus e_{i}$.

  * •

if $G_{k}[i,i]=0$, then we can apply an $R_{x}(\pi/2)$ on the input qubit $i$,
we get

$G\leftarrow G\oplus G[:,i]G[:,i]^{T}.$

  * •

if $G_{k}[i,i]=1$, then we apply an Hadamard gate on the input qubit $i$, or
equivalently we apply $SR_{x}(\pi/2)S$, and the action on $G$ is

$G\leftarrow G\oplus g_{i}g_{i}^{T}$

where where $g_{i}=G[:,i]\oplus e_{i}$.

###  3.3 Summary: the synthesis framework

We have shown that any $k$ to $n$ Clifford isometry, up to Hadamard gates, is
completely determined by a symmetric boolean matrix $G\in
F_{2}^{(n+k)\times(n+k)}$. $G$ has the following block structure

$G=\begin{bmatrix}G_{k}&B_{k}\\\ B_{k}^{T}&G_{n}\end{bmatrix}$

where $G_{k}\in F_{2}^{k\times k},G_{n}\in F_{2}^{n\times n}$ are symmetric
and $B_{k}\in F_{2}^{k\times n}$ is full rank. Synthesizing the isometry is
equivalent to reducing $G$ to the identity operator

$\left[\begin{array}[]{c|cc}0_{k}&I_{k}&0_{k\times n-k}\\\ \hline\cr
I_{k}&\lx@intercol\hfil\hbox{\multirowsetup$0_{n\times
n}$}\hfil\lx@intercol\\\ 0_{n-k\times k}\end{array}\right]$

The available operations are summarized in Table 1. We also give the available
operations as actions on the submatrices $G_{n},G_{k}$ and $B$ in Table 2.

Clifford gate | Action on $G$ | Matrix interpretation | Graph interpretation | Range of validity
---|---|---|---|---
$S_{i}$ | $G[i,i]=G[i,i]\oplus 1$ | Flips diagonal entry | Complements loop of node $i$ | $1\leq i\leq n+k$
$CZ_{i,j}$ | $G[i,j]=G[i,j]\oplus 1$ | Flips two symmetric | Complements edge $(i,j)$ | $1\leq i,j\leq k$
$G[j,i]=G[j,i]\oplus 1$ | entries | or $k+1\leq i,j\leq n+k$
$CNOT_{i,j}$ | $G[i,:]=G[i,:]\oplus G[j,:]$ | Elementary row | Complements the neighborhood | $1\leq i,j\leq k$
$G[:,i]=G[:,i]\oplus G[:,j]$ | and column operation | of node $j$ for node $i$ | or $k+1\leq i,j\leq n+k$
$H_{i}$ | $G=G\oplus gg^{T}$ | Rank-one update | Local complementation on node $i$ | $1\leq i\leq n+k$
(if $G[i,i]=1$) | $g=G[:,i]\oplus e_{i}$ |  | (with loops except on node $i$) |
$(R_{x})_{i}$ | $G=G\oplus gg^{T}$ | Rank-one update | Local complementation on node $i$ | $1\leq i\leq n+k$
(if $G[i,i]=0$) | $g=G[:,i]$ |  | (with loops) |

Table 1: Available operations for the synthesis of a $k$ to $n$ Clifford isometry $G$. Clifford gate | Side | Qubits | Acts on |  | Action
---|---|---|---|---|---
$S$ | Input | $i$ | $G_{k}$ |  | $G_{k}[i,i]=G_{k}[i,i]\oplus 1$
$S$ | Output | $i$ | $G_{n}$ |  | $G_{n}[i,i]=G_{n}[i,i]\oplus 1$
$CZ$ | Input | $i,j$ | $G_{k}$ |  | $G_{k}[i,j]=G_{k}[i,j]\oplus 1$
| $G_{k}[j,i]=G_{k}[j,i]\oplus 1$
$CZ$ | Output | $i,j$ | $G_{n}$ |  | $G_{n}[i,j]=G_{n}[i,j]\oplus 1$
| $G_{n}[j,i]=G_{n}[j,i]\oplus 1$
$CNOT$ | Input | $i,j$ | $G_{k},B$ |  | $G_{k}[i,:]=G_{k}[j,:]\oplus G_{k}[i,:]$
| $G_{k}[:,i]=G_{k}[:,j]\oplus G_{k}[:,i]$
| $B[i,:]=B[j,:]\oplus B[i,:]$
$CNOT$ | Output | $i,j$ | $G_{n},B$ |  | $G_{n}[i,:]=G_{n}[j,:]\oplus G_{n}[i,:]$
| $G_{n}[:,i]=G_{n}[:,j]\oplus G_{n}[:,i]$
| $B[:,i]=B[:,j]\oplus B[:,i]$
$H/R_{x}$ | Input | $i$ | $G_{k},G_{n},B$ |  | $G_{k}=G_{k}\oplus gg^{T}$
| $G_{n}=G_{n}\oplus B[i,:]^{T}B[i,:]$
| $B=B\oplus gB[i,:]$
| ($g=G_{k}[:,i]$ if $G_{k}[i,i]=0$,
|  $g=G_{k}[:,i]\oplus e_{i}$ otherwise)
$H/R_{x}$ | Output | $i$ | $G_{k},G_{n},B$ |  | $G_{n}=G_{n}\oplus gg^{T}$
| $G_{k}=G_{k}\oplus B[:,i]^{T}B[:,i]$
| $B=B\oplus B[:,i]g^{T}$
| ($g=G_{n}[:,i]$ if $G_{n}[i,i]=0$,
|  $g=G_{n}[:,i]\oplus e_{i}$ otherwise)
Table 2: An alternative way to present the available operations for the
synthesis of a $k$ to $n$ Clifford isometry $G=[G_{k}\;B;B^{T}\;G_{n}]$.

Overall, everything acts as if we have a graph state on $n+k$ qubits on which
only a subset of operations are available: two-qubit gates are only possible
among one set of $k$ qubits or the complementary set of $n$ qubits. Contrary
to the graph state synthesis where one wants to remove every edge of the
graph, we look for an "identity" layout of the edges where $k$ qubits of the
first set are solely connected to one qubit of the other set. This form is a
generalization of the form derived in [20] but we did not use the ZX-calculus
in our proof and we provide a more in-depth characterization of the synthesis
framework implied by this graph-state form.

We remind that our framework is not universal in the sense that we are not
authorized to apply any Clifford gate, therefore we cannot generate any
Clifford circuit. Solving optimally an instance of our framework does not
guarantee that we have an optimal implementation of the Clifford isometry.

We now review the possibilities offered by this new framework and propose some
algorithms to perform the synthesis of Clifford isometries.

##  4 Synthesis algorithms

###  4.1 Normal forms

One advantage of this framework is that normal forms can be derived quite
easily with short proofs. We now propose some of them. As a corollary we
recover previous normal forms for Clifford operators that can be found in the
literature.

We use the following terminology: -S- corresponds to a layer of S gates, -C-
corresponds to a layer of CNOT gates, -CZ- corresponds to a layer of CZ gates
and -H- corresponds to a layer of H gates. Given that the gates on the input
side are only applied to the first $k$ qubits, and that the gates in the
output side can be applied to the whole $n$ qubits, we will note the layers
with a subscript to emphasize when it concerns only $k$ or $n$ qubits.

Note that our normal forms always end with a layer of Hadamard gates: this
layer transforms any isometry into its graph-state form. For each qubit, there
may or may not be an Hadamard gate applied. We also always have a full layer
of $n$ Hadamard gates "in the middle" of our normal forms that ends the
synthesis of our graph-state framework. This layer draws a boundary between
the operations on the input qubits and the operations on the output qubits.
For clarity we omit the subscript for this layer.

Note also that the layers applied on the output side have to be read in
reverse order to understand their action in our graph-state framework.

####  4.1.1 Sk-CZk-H-Cn-CZn-Sn-Hn.

The layers of -S- and -CZ- gates on the input side zero $G_{k}$. The layers
-S- and -CZ- on the output side zero $G_{n}$. Finally the -C- layer reduces
$B$ to the identity. Note that we are free to place these three last layers
(CNOT, S and CZ) as we like: this will not change the -C- layer but we have to
adjust the -S- and -CZ- layers depending on the value of $G_{n}$ that can be
changed by the action of the CNOT layer. In fact, as long as a suitable phase
polynomial is implemented we have a valid implementation of the Clifford
isometry.

With a full Clifford operator, i.e when $k=n$, we recover the normal form
-H-S-CZ-C-H-CZ-S-H- given in [20]. Note that, in this particular case, the -C-
layer can be placed before or after the -H- layer: the only difference is that
we will act on the $B$ or $B^{T}$ part of $G$. We also have one -H- layer
less.

######  Corollary 2.

Given a $k$ to $n$ Clifford isometry $V$ under graph-state form
$\begin{bmatrix}G_{k}&B_{k}\\\ B_{k}^{T}&G_{n}\end{bmatrix}$, then, up to
Pauli operators,

$V=\frac{1}{\sqrt{2}^{n}}\sum_{x\in\\{0,1\\}^{k}}\sum_{y\in\\{0,1\\}^{n}}e^{i\frac{\pi}{2}\left(x^{T}G_{k}x\oplus
y^{T}G_{n}y\right)+i\pi x^{T}B_{k}y}\ket{y}\bra{x}$ (3)

###### Proof.

We start from the identity isometry and we check that the normal form gives
the expected formula.

$\displaystyle\sum_{x\in\\{0,1\\}^{k}}\ket{x}\ket{0}^{\otimes n-k}\bra{x}$
$\displaystyle\xrightarrow[]{CZ+S}$
$\displaystyle\sum_{x\in\\{0,1\\}^{k}}e^{i\frac{\pi}{2}x^{T}G_{k}x}\ket{x}\ket{0}^{\otimes
n-k}\bra{x}$ $\displaystyle\xrightarrow[]{H^{\otimes n}}$
$\displaystyle\frac{1}{\sqrt{2}^{n}}\sum_{x\in\\{0,1\\}^{k}}\sum_{y\in\\{0,1\\}^{n}}e^{i\frac{\pi}{2}x^{T}G_{k}x+i\pi\sum_{j=1}^{k}x_{j}y_{j}}\ket{y}\bra{x}$
$\displaystyle\xrightarrow[]{CNOT}$
$\displaystyle\frac{1}{\sqrt{2}^{n}}\sum_{x\in\\{0,1\\}^{k}}\sum_{y\in\\{0,1\\}^{n}}e^{i\frac{\pi}{2}x^{T}G_{k}x+i\pi
x^{T}E_{k}y}\ket{By}\bra{x}$ $\displaystyle\xrightarrow[]{CZ+S}$
$\displaystyle\frac{1}{\sqrt{2}^{n}}\sum_{x\in\\{0,1\\}^{k}}\sum_{y\in\\{0,1\\}^{n}}e^{i\frac{\pi}{2}\left(x^{T}G_{k}x+y^{T}B^{T}G_{n}By\right)+i\pi
x^{T}E_{k}y}\ket{By}\bra{x}$ $\displaystyle\xrightarrow[]{y\leftarrow By}$
$\displaystyle\frac{1}{\sqrt{2}^{n}}\sum_{x\in\\{0,1\\}^{k}}\sum_{y\in\\{0,1\\}^{n}}e^{i\frac{\pi}{2}\left(x^{T}G_{k}x+y^{T}G_{n}y\right)+i\pi
x^{T}E_{k}B^{-1}y}\ket{y}\bra{x}$
$\displaystyle\xrightarrow[]{B_{k}=B^{-1}[1:k,:]}$
$\displaystyle\frac{1}{\sqrt{2}^{n}}\sum_{x\in\\{0,1\\}^{k}}\sum_{y\in\\{0,1\\}^{n}}e^{i\frac{\pi}{2}\left(x^{T}G_{k}x+y^{T}G_{n}y\right)+i\pi
x^{T}B_{k}y}\ket{y}\bra{x}$

∎

####  4.1.2 Sk-Ck-Sk-H-Cn-Sn-Cn-Sn-Hn.

We can remove any use of -CZ- layers with the use of CNOT gates. Any symmetric
boolean matrix $M$ can be written $M=LDL^{T}\oplus D^{\prime}$ where $L$ is
lower triangular and $D,D^{\prime}$ are diagonal [7]. This applies to $G_{k}$
and $G_{n}$. Write $G_{k}=LDL^{T}\oplus D^{\prime}$. The first layer of -S-
gates on the input side adds $D^{\prime}$ to $G_{k}$ such that $G_{k}\oplus
D^{\prime}=LDL^{T}$. Then the -C- layer only need to implement a triangular
operator $L$ to reduce $G_{k}\oplus D^{\prime}$ to $D$ which is zeroed with a
second layer of -S- gates. We have a similar argument to treat the zeroing of
$G_{n}$. The last layer -C- on the output side ultimately reduces $B$ to the
identity.

For the full Clifford operator case, we recover a normal form similar to -C-S-
C-S-H-C-S-C-S- given in [19]. In this case each -C- stage implements a
triangular operator. This is also true in our own normal form as two -C-
blocks are already triangular and the -C- block that reduces $B$ to the
identity can be written as a product of two triangular matrices.

####  4.1.3 Other normal forms for Clifford operators.

We show how other normal forms in the literature for Clifford operators can
also be derived from our framework.

##### -C-CZ-S-H-S-CZ-C- [19]

This normal form consists in an application of a stage of CNOT gates, then a
stage of CZ gates and finally a stage of S stages on both the input and the
output side (remember that the operations done on the output side are
reversed). Our normal form also has an additional -H- layer at an ultimate
layer.

It is straightforward to define suitable operators for each stage:

  * •

the -C- stage on the input side can implement any operator $C_{1}$ and the -C-
stage on the output side can implement any operator $C_{2}$, as long as
$C_{1}BC_{2}=I$,

  * •

the -CZ- and -S- stages on the input side are defined such that it implements
the graph state $C_{1}G_{k}C_{1}^{T}$,

  * •

the -CZ- and -S- stages on the output side are defined such that it implements
the graph state $C_{2}^{T}G_{n}C_{2}$.

Naturally, as explained in [19], the order of the -C-, -CZ- and -S- stages are
free. In fact, as long as a suitable phase polynomial is implemented, then we
have a valid implementation of the Clifford operator.

##### -C-CZ-S-H-CZ-S-H- [22]

Similar to the normal form -C-CZ-S-H-S-CZ-C-, this normal form highlights the
fact that only one -C- stage is sufficient on one of the two sides. Again,
here is a viable construction in our framework:

  * •

reduce $B$ to the identity with the -C- stage,

  * •

reduce the new $G_{k}$ and $G_{n}$ to zero with the -CZ- and -S- stages on
both input and output sides.

###  4.2 Synthesis in {CNOT, S, CZ}

Overall, the structure of the normal forms given in Section 4.1 are very
similar: two phase polynomials are implemented from either side of the
Hadamard layer, the differences being in the way those phase polynomials are
implemented. If we restrict the synthesis of $G$ in the gate set {CNOT, S,
CZ}, we necessarily implement phase polynomials and we show that only a
partial specification of the phase polynomials is sufficient.

######  Theorem 5.

Let $V$ be a $k$ to $n$ Clifford isometry $V$ under graph-state form specified
by its graph matrix $G=\begin{bmatrix}G_{k}&B_{k}\\\
B_{k}^{T}&G_{n}\end{bmatrix}$. An operator of the form

$P_{1}H^{\otimes n}P_{2}$ (4)

where $P_{1},P_{2}$ are phase polynomials implements $V$ if and only if

$P_{1}^{{\dagger}}=\sum_{x\in\\{0,1\\}^{n}}e^{i\frac{\pi}{2}x^{T}G_{n}x}\ket{A_{1}x}\bra{x}$
$P_{2}=\sum_{x\in\\{0,1\\}^{k}}e^{i\frac{\pi}{2}x^{T}G_{k}x}\ket{A_{2}x}\ket{0}^{\otimes
n-k}\bra{x}$

such that

$\begin{bmatrix}A_{2}^{T}&0\end{bmatrix}A_{1}=B_{k}$

where $A_{1}$ is $n\times n$, $A_{2}$ is $k\times k$.

###### Proof.

$P_{1}H^{\otimes n}P_{2}$ is a valid implementation of $V$ if and only if

$H^{\otimes n}P_{2}=P_{1}^{{\dagger}}V.$

We write

$P_{1}^{{\dagger}}=\left(\sum_{x\in\\{0,1\\}^{n}}e^{i\frac{\pi}{2}x^{T}\Gamma_{1}x}\ket{A_{1}x}\bra{x}\right),$
$P_{2}=\left(\sum_{x\in\\{0,1\\}^{k}}e^{i\frac{\pi}{2}x^{T}\Gamma_{2}x}\ket{A_{2}x}\ket{0}^{\otimes
n-k}\bra{x}\right),$

and we expand the two terms:

$\displaystyle P_{1}^{{\dagger}}V$
$\displaystyle=\left(\sum_{y\in\\{0,1\\}^{n}}e^{i\frac{\pi}{2}y^{T}\Gamma_{1}y}\ket{A_{1}y}\bra{y}\right)\left(\frac{1}{\sqrt{2}^{n}}\sum_{x\in\\{0,1\\}^{k}}\sum_{y\in\\{0,1\\}^{n}}e^{i\frac{\pi}{2}\left(x^{T}G_{k}x+y^{T}G_{n}y\right)+i\pi
x^{T}B_{k}y}\ket{y}\bra{x}\right)$
$\displaystyle=\frac{1}{\sqrt{2}^{n}}\left(\sum_{x\in\\{0,1\\}^{k}}\sum_{y\in\\{0,1\\}^{n}}e^{i\frac{\pi}{2}\left(x^{T}G_{k}x+y^{T}(G_{n}\oplus\Gamma_{1})y\right)+i\pi
x^{T}B_{k}y}\ket{A_{1}y}\bra{x}\right)$
$\displaystyle=\frac{1}{\sqrt{2}^{n}}\left(\sum_{x\in\\{0,1\\}^{k}}\sum_{y\in\\{0,1\\}^{n}}e^{i\frac{\pi}{2}\left(x^{T}G_{k}x+y^{T}A_{1}^{-1}(G_{n}\oplus\Gamma_{1})A_{1}^{-1}y\right)+i\pi
x^{T}B_{k}A_{1}^{-1}y}\ket{y}\bra{x}\right)$

$\displaystyle H^{\otimes n}P_{2}$
$\displaystyle=\frac{1}{\sqrt{2}^{n}}\left(\sum_{x\in\\{0,1\\}^{n}}\sum_{y\in\\{0,1\\}^{n}}e^{i\pi
x^{T}y}\ket{y}\bra{x}\right)\left(\sum_{x\in\\{0,1\\}^{k}}e^{i\frac{\pi}{2}x^{T}\Gamma_{2}x}\ket{A_{2}x}\ket{0}^{\otimes
n-k}\bra{x}\right)$
$\displaystyle=\frac{1}{\sqrt{2}^{n}}\left(\sum_{x\in\\{0,1\\}^{k}}\sum_{x^{\prime}\in\\{0,1\\}^{n-k}}\sum_{y\in\\{0,1\\}^{n}}e^{i\pi[A_{2}x;x^{\prime}]^{T}y}\ket{y}\bra{A_{2}x}\bra{x^{\prime}}\right)\left(\sum_{x\in\\{0,1\\}^{k}}e^{i\frac{\pi}{2}x^{T}\Gamma_{2}x}\ket{A_{2}x}\ket{0}^{\otimes
n-k}\bra{x}\right)$
$\displaystyle=\frac{1}{\sqrt{2}^{n}}\left(\sum_{x\in\\{0,1\\}^{k}}\sum_{y\in\\{0,1\\}^{n}}e^{i\pi
x^{T}A_{2}^{T}E_{k}y}e^{i\frac{\pi}{2}x^{T}\Gamma_{2}x}\ket{y}\bra{x}\right)$

We have the equality if and only if

$\forall x\in\\{0,1\\}^{k},\forall
y\in\\{0,1\\}^{n},e^{i\frac{\pi}{2}\left(x^{T}G_{k}x+y^{T}A_{1}^{-1}(G_{n}\oplus\Gamma_{1})A_{1}^{-1}y\right)+i\pi
x^{T}B_{k}A_{1}^{-1}y}=e^{i\pi
x^{T}A_{2}^{T}E_{k}y}e^{i\frac{\pi}{2}x^{T}\Gamma_{2}x}$

i.e

$G_{k}=\Gamma_{2},$ $G_{n}=\Gamma_{1},$

and

$\begin{bmatrix}A_{2}^{T}&0\end{bmatrix}A_{1}=B_{k}.$

∎

######  Corollary 3.

Let $\ket{G}$ be a graph state. Then we have

$\ket{G}=\left(\sum_{x}e^{i\frac{\pi}{2}\cdot
x^{T}Gx}\ket{Ax}\bra{x}\right)^{{\dagger}}H^{\otimes n}\ket{0}^{\otimes n}$

for any invertible boolean matrix $A$. In other words, the synthesis of a
graph state in the gate set $\\{CNOT,CZ,S\\}$ is equivalent to the synthesis
of a Clifford phase of a phase polynomial given by the graph matrix $G$
without any restriction on the final linear reversible operator applied.

###  4.3 Synthesis for an LNN architecture

######  Theorem 6.

Any $k$ to $n$ Clifford isometry can be executed in two-qubit depth $4n+3k$ on
an LNN architecture.

###### Proof.

Our proof mainly relies on the synthesis of CNOT circuits in depth $5n$ from
[32] and CZ circuits in depth $2n$ from [19]. First, we can reduce $G$ to

$G=\begin{bmatrix}G^{\prime}_{k}&B^{\prime}\\\ B^{\prime T}&0\end{bmatrix}$

with a CZ circuit of depth $2n$ using the technique from [19]. Then we need to
take a look at how the algorithm from [32] works. Given a linear reversible
operator $A$ on $n$ qubits they apply two circuits:

  * •

the first one of depth $2n$, applying an operator $C_{1}$ such that
$A^{\prime}=C_{1}A$ is northwest triangular. For instance on $5$ qubits,

$A^{\prime}=C_{1}A=\begin{bmatrix}*&*&*&*&1\\\ *&*&*&1&\\\ *&*&1&&\\\
*&1&&&\\\ 1&&&&\end{bmatrix}$

where $*$ stands for any boolean value, and the entries non specified are $0$.

  * •

the second circuit, of depth $3n$, implements an operator $C_{2}$ that
synthesizes the triangular operator:

$C_{2}A^{\prime}=I.$

Overall, we get $A=C_{1}^{-1}C_{2}^{-1}$ as a CNOT circuit of depth $5n$. For
the rest of the proof, we need to go into the details of the generation of
$C_{2}$. An example on $5$ qubits is given in Fig. 2. The general idea is to
give a label $a_{i}=n-i+1,i=1\ldots n$ to each row of $A^{\prime}$ and to sort
those labels with a LNN compliant sorting network as shown in Fig. 2a. Each
box will swap the rows (and the labels) and may perform a row operation
between the two swapped rows. Namely if a row with label $a_{i}$ is swapped
with a row of label $a_{j}$, $i<j$, the row with label $a_{j}$ may have a
nonzero $i$-th component and if so we perform the operation

$a_{j}\leftarrow a_{j}\oplus a_{i}$

to zero that component. Given the initial label positions, a label $a_{j}$
will have to "encounter" all labels $a_{i}$, $i<j$ during the sorting process
and we are ensured that the j-th row will eventually be the j-th canonical
vector.

Each box will therefore consist of either a SWAP operation or an operation of
the form:

$(u,v)\leftarrow(u\oplus v,u)$

or

$(u,v)\leftarrow(v,u\oplus v).$

The SWAP operation requires 3 CNOT gates while the SWAP+CNOT requires in fact
only 2 CNOT gates [32]. Therefore each box will be of depth at most $3$ and
the total circuit $C_{2}$, of depth $n$ as a box-based circuit, will be of
depth $3n$ as a CNOT-based circuit. Note also that, in any case, we always
have at some point during the execution of a box on two rows the sum of the
values of the two rows that appear on one row of $A^{\prime}$. This will be an
important property in our proof.

(a) The sorting network applied to the operator, as a box-based circuit.  (b)
The action of the sorting network on the operator for each layer.

Figure 2: Illustration of the second part of the algorithm from [32] to reduce
a northwest triangular linear reversible operator to the identity.

Coming back to our proof, with the first half of the construction from [32] we
are able to reduce the CNOT part $B^{\prime}$ to a northwest triangular matrix
$B^{\prime\prime}$ in depth $2n$ as well. At this point we have an operator of
the form

$G=\begin{bmatrix}G^{\prime\prime}_{k}&\begin{pmatrix}B^{\prime\prime}&0\end{pmatrix}\\\
\begin{pmatrix}B^{\prime\prime T}\\\ 0\end{pmatrix}&0\end{bmatrix}$

where $B^{\prime\prime}$ is $k\times k$ and northwest triangular.

We now show that we can reduce $B^{\prime\prime}$ to the identity and $G_{k}$
to zero in depth $3k$. In fact, we will show that we can solely insert
suitable $R_{x}(\pi/2)$ gates in the CNOT circuit reducing $B^{\prime\prime}$
to the identity matrix (taken from [32]) to reduce $G_{k}$ to $0$ as well.

With $G$ in the form $\begin{bmatrix}G_{k}&D\\\ D^{T}&0\end{bmatrix}$ with
arbitrary $D$, the action of an $R_{x}(\pi/2)$ gate on the output side is
equivalent to a rank-one modification of $G_{k}$ by a vector $u$ given by one
of the row of $D$. In other words, if we apply an $R_{x}(\pi/2)$ on qubit $j$,
then

$G_{k}\leftarrow G_{k}\oplus D[:,j]^{T}D[j,:].$

Therefore in our case we can reduce $G_{k}$ to 0 if the set

$S=\\{u^{T}u|{u\text{ appearing in $B^{\prime\prime}$ during the synthesis
}}\\}$

is a basis of the set of symmetric boolean matrices.

We prove by induction that $S$ generates the set

$P_{n}=\\{e_{i}e_{i}^{T}\;|\;i\in{[\\![}1,n{]\\!]}\\}\cup\\{e_{i}e_{j}^{T}\oplus
e_{j}e_{i}^{T}\;|\;i,j\in{[\\![}1,n{]\\!]},i\neq j\\}$

and therefore generates the set of symmetric boolean matrices.

This is trivial for $n=1$. Now suppose this is true for some $n$. We introduce
similar notations to the ones in [32]:

  * •

each line $i$ of $B^{\prime\prime}$ has a value $c_{i}$, i.e a boolean vector
of size $n+1$,

  * •

each line $i$ of $B^{\prime\prime}$ carries a label
$a_{i}\in{[\\![}1,n+1{]\\!]}$, independent of $c_{i}$.

For simplicity, at any moment during the algorithm from [32], we now refer as
parity $k$ the line of $B^{\prime\prime}$ that carries the label $a_{k}$, and
by extension the value of the line carrying the label $a_{k}$. The key is to
see the algorithm from [32] as moving parities in $B^{\prime\prime}$ and
during the SWAP of the parities we add or not some parities to the others. For
simplicity we also consider the reverse circuit, i.e, the one that transforms
the identity operator $I$ to $B^{\prime\prime}$. This does not change the set
$S$ but this will simplify the reasoning. We still refer as $B^{\prime\prime}$
the matrix at any point during the algorithm.

The first point is to notice that the $(n+1)$-th parity will never be added to
the other parities. So we can conclude that the first $n$ parities, apart from
their interactions with the $(n+1)$-th parity, will behave exactly as in the
case with $n$ qubits, therefore they satisfy the property and generates the
set $P_{n}$.

We only need to show that, with the new values obtained on the last parity, we
can generate $P_{n+1}$, i.e, we need to generate the set
$\\{e_{n+1}e_{n+1}^{T}\\}\cup\\{e_{n+1}e_{j}^{T}\oplus
e_{j}e_{n+1}^{T}\;|\;j\in{[\\![}1,n{]\\!]}\\}$.

Every value carried by the $(n+1)$-th parity is of the form

$e_{n+1}\oplus u_{k}$

for a family of boolean vectors $(u_{k})_{k}$ of size $n+1$ with the
$(n+1)$-th component always equal to $0$. Applying an $R_{x}$ in two occasions
gives the transformation

$A\leftarrow A\oplus(e_{n+1}\oplus u_{i})(e_{n+1}\oplus
u_{i})^{T}\oplus(e_{n+1}\oplus u_{j})(e_{n+1}\oplus u_{j})^{T}$ $A\leftarrow
A\oplus u_{i}u_{i}^{T}\oplus u_{i}e_{n+1}^{T}\oplus e_{n+1}u_{i}^{T}\oplus
u_{j}u_{j}^{T}\oplus u_{j}e_{n+1}^{T}\oplus e_{n+1}u_{j}^{T}$ $A\leftarrow
A\oplus\underbrace{u_{i}u_{i}^{T}\oplus u_{j}u_{j}^{T}}_{\in
P_{n}}\oplus(u_{i}\oplus u_{j})e_{n+1}^{T}\oplus e_{n+1}(u_{i}\oplus
u_{j})^{T}$

This means that, up to terms in $P_{n}$ that can be removed with suitable
$R_{x}$ gates on the first $n$ parities, we can generate the set
$e_{n+1}(\oplus_{k}\alpha_{k}u_{k})^{T}\oplus(\oplus_{k}\alpha_{k}u_{k})e_{n+1}^{T}$
for any $\alpha_{k}\in\\{0,1\\}$, i.e, any linear combination of the
$(u_{k})$’s. What remains is to show that the family of vectors $(u_{k})_{k}$
is a basis such that we can generate all the $e_{i}$’s and this concludes the
proof.

We show that any new $u_{p}$ appearing during the process is not a linear
combination of the previous $(u_{k})_{k=1\ldots p-1}$, given that we have $n$
such $u_{k}$ we get a basis $(u_{k})_{k=1\ldots n}$. By construction of the
algorithm the $(n+1)$-th parity is initially on the last row of
$B^{\prime\prime}$ and is equal to $e_{n+1}$. During the synthesis this parity
will be swapped, and sometimes added, with the parity "above".

In other words, if the $(n+1)$-th parity is currently on line $k$ of
$B^{\prime\prime}$, we have

$c_{k}=e_{n+1}\oplus v_{k-1}$

where $v_{k-1}$ is necessarily a linear combination of the set of parities
located lines $k+1\ldots n$, i.e, the lines "below". The family
$(u_{j})_{j=1\ldots k-1}$ also consists in linear combinations of the set of
parities located lines $k+1\ldots n$. During the swap/addition with the parity
above we necessarily create the value

$e_{n+1}\oplus v_{k-1}\oplus c_{k-1}$

and we set $u_{k}=v_{k-1}\oplus c_{k-1}$. $u_{k}$ is necessarily linearly
independent with the previous $(u_{j})_{j=1\ldots k-1}$ otherwise the lines
$k+1$ to $n$ and the $k-1$-th line of $B^{\prime\prime}$ are not linearly
independent which is not possible by invertibility of $B^{\prime\prime}$.

We set $v_{k}=v_{k-1}$ or $v_{k}=v_{k-1}\oplus c_{k+1}$, depending on the
value of the $(n+1)$-th parity of $B^{\prime\prime}$ and we pursue the
algorithm. ∎

######  Corollary 4.

Any n-qubit Clifford operator can be executed in two-qubit depth $7n$ on an
LNN architecture.

##  5 Practical algorithms for graph state synthesis and application to the
codiagonalization of Pauli rotations

We give two algorithms for the synthesis of graph states, a special case of
Clifford isometry where $k=0$. One algorithm optimizes the number of two-qubit
gates while the second one optimizes the depth of the circuit, both assuming
an all-to-all connectivity between the physical qubits. Then we use our
algorithms in quantum compilers that synthesize a sequence of Pauli rotations.
Usually such sequences are implemented by packing the rotations into groups of
commuting operators, each group is then codiagonalized with a Clifford circuit
and implemented with the synthesis of a phase polynomial. An efficient graph-
state synthesis algorithm will improve the codiagonalization part of this
process.

###  5.1 Practical algorithms: a variant of the syndrome decoding based
algorithm and a depth-optimized greedy algorithm

Following our framework, $G_{k}$ is a $0\times 0$ matrix and $B_{k}$ a
$0\times n$ matrix. Thus, the synthesis only consists in reducing a symmetric
$n\times n$ boolean matrix $G_{n}$ to the zero matrix with the following
operations:

  * •

flip entries $G_{n}[i,j]$ and $G_{n}[j,i]$,

  * •

add row $i$ to row $j$ and column $i$ to column $j$, $i\neq j$,

  * •

rank-one updates as described in Table 1.

We will restrict ourselves to the gate set $\\{CNOT,CZ,S\\}$ which means that
the rank-one updates are not available. The algorithms are variants of two
algorithms designed by some of the authors for the synthesis of CNOT circuits
[33, 34, 35]. We present a sketch of how the algorithms work by highlighting
the differences with CNOT circuits but more details can be found in the
original articles.

####  5.1.1 The syndrome decoding based algorithm [33, 34].

This algorithm aims at optimizing the total number of two-qubit gates in the
circuit. The algorithm is recursive, suppose we managed to reduce $G_{n}$ to

$G_{n}=\begin{bmatrix}0_{n-1}&s^{T}\\\ s&\star\end{bmatrix}$

where $0_{n-1}$ is the $n-1\times n-1$ zero matrix, $s$ is an arbitary vector
of size $n-1$ and $\star$ can be $0$ or $1$. We show how to efficiently zero
$s$ while keeping the $n-1\times n-1$ submatrix equal to $0$. Overall the
algorithm consists in:

  * •

a recursive call on a submatrix of $G_{n}$ of size $n-1$,

  * •

and a call to the procedure that will treat separately the last line and
column of $G_{n}$.

One key of the algorithm is to notice that at any time during the execution of
the circuit that zeroes the $n-1\times n-1$ submatrix we are free to do the
following operations:

  * •

flip any entry of $s$ with a CZ gate, by symmetry this will flip the same
entry in $s^{T}$,

  * •

add any row $1\leq i\leq n-1$ of $G_{n}$ to $s$ with a CNOT gate, by symmetry
the column operation will also modify $s^{T}$,

  * •

flip any diagonal entry $i$ of $G[1:n-1,1:n-1]$ with an S gate, then add row
$i$ to $s$ with a CNOT gate and flip again the $i-th$ diagonal entry.

These operations will only modify $s$ in $G_{n}$ and keep $G_{n}[1:n-1,1:n-1]$
unchanged and therefore $0$. All these operations have a two-qubit cost of
$1$. Overall any of these three operations we can be seen as adding a vector
to $s$. Therefore, the procedure to zero $s$ consists in two steps:

  1. 1.

scan the matrix $G[1:n-1,1:n-1]$ during its zeroing and store all the vectors
the can be added to $s$ in a matrix $H$. $H$ is eventually $m\times(n-1)$
where $m$ is the number of different parities encountered,

  2. 2.

solve $xH=s$ with $x$ of smallest Hamming weight possible. Each vector to add
costs one two-qubit gate so the smallest the Hamming weight of $x$, the
smallest the number of extra two-qubit gates.

Step 2 is also known as the syndrome decoding problem and we use a greedy
method to solve it: we choose the vector $v$ in $H$ that minimizes $v\oplus
s$, we set $s\leftarrow s\oplus v$ and we repeat this until $s$ is $0$. The
presence of the canonical vectors guarantees that the procedure eventually
terminates. To improve the efficiency of the greedy method, it is possible to
solve $xHP=sP$ for different invertible matrices $P$ and keep the best result.
This method is known as the Information Set Decoding strategy and significant
improvements can be obtained if sufficient iterations are done. The only
constraint on $P$ is that the canonical vectors must be present in $HP$.

####  5.1.2 A depth-optimized greedy algorithm.

We use the following greedy algorithm to optimize the depth. Until $G$ is zero
repeat the following procedure:

  1. 1.

initialize an empty list $L$ of used qubits and an empty set of operations
$O$.

  2. 2.

At each iteration choose the row or column operations among the non-used
qubits that reduces at most the Hamming weight of $G_{n}$. If the decrease in
the Hamming weight is strictly larger than $1$, then perform the operation,
add it to $O$ and add the two qubits to $L$.

  3. 3.

When no such operation is available, compute the set

$Q={[\\![}1,n{]\\!]}\setminus L,$

and consider the submatrix $G_{n}[Q,Q]$: this is the submatrix on which
entries can still be flipped without increasing the depth of $O$. To compute
the largest number of entries that can be flipped in depth $1$ see
$G_{n}[Q,Q]$ as the adjacency matrix of a graph. Each $1$ entry in $G[Q,Q]$ is
an edge in the graph. Then a maximum matching in this graph gives a set of
maximum size of entries that can be flipped.

  4. 4.

One step of this procedure produces a set $O$ of depth $1$. Add $O$ to the
full set of operations done on $G_{n}$.

We could have avoided the use of $O$ in the description of our algorithm but
we wanted to highlight the principle of the algorithm: at each step we compute
a set of operations that reduces the most the number of $1$ in $G_{n}$ and
that can be executed in depth $1$. The algorithm always terminates as at each
step we strictly reduce the number of nonzero elements in $G_{n}$.

###  5.2 Application to the codiagonalization of Pauli rotations

Given a set of $k$ Pauli operators on $n$-qubit
$\\{P_{1},P_{2},\ldots,P_{k}\\}$, if they all commute then there exists a
Clifford operator $C$ such that

$CP_{i}C^{{\dagger}}=Z^{a_{i}}=Z_{1}^{a_{i,1}}\otimes
Z_{2}^{a_{i,2}}\otimes\ldots\otimes Z_{n}^{a_{i,n}}\forall
i\in{[\\![}1,k{]\\!]},a_{i}\in\mathbb{F}_{2}^{n}.$

$C$ is not unique and we can look for an optimized one using our graph
synthesis framework. If we write our Pauli operators as a tableau

$\begin{bmatrix}Z\\\ X\end{bmatrix}\in\mathbb{F}_{2}^{n\times k},$

the codiagonalization problem is then equivalent to finding a Clifford
operator that will zero the $X$ part. We propose the following procedure:

  1. 1.

considering the following block structure of our tableau

$\begin{bmatrix}Z_{k}\\\ Z_{n-k}\\\ X_{k}\\\
X_{n-k}\end{bmatrix}\in\mathbb{F}_{2}^{n\times k}$

where $Z_{k},X_{k}$ are $k\times k$ and $Z_{n-k},X_{n-k}$ are $(n-k)\times k$.
Find a circuit of Hadamard gates and SWAP gates such that $X_{k}$ is full
rank.

  2. 2.

find a Clifford operator that zeroes $X_{n-k}$.

  3. 3.

with free column operations reduce $X_{k}$ to the identity operator,

  4. 4.

use the graph-state synthesis framework to zero $Z_{k}$,

  5. 5.

use Hadamard gates on the first $k$ qubits to commute $X_{k}$ with the zero
block

At the end of the procedure, we eventually have $X=0$. The main complexity of
this procedure lies in steps 2 and 4. The Hadamard layers do not increase
either the 2-qubit gate count or the 2-qubit gate depth. The SWAP gates can be
transfered at the end of the circuit and post-processed.

We already have algorithms for step 4, we now give methods to do step 2 as
well. Those methods are variants of the ones we already used for graph state
synthesis so we will address them quickly.

####  5.2.1 2-qubit count optimization with the syndrome decoding problem.

By assumption $X_{k}$ is full rank. With suitable column operations we can
have $X_{k}=I$. We zero each row of $X_{n-k}$ one by one starting from row $1$
to row $n-k$. During the $i$-th step we compute the rows that appeared in the
zeroing of $X_{n-k}[1:i-1]$ that we gather in a matrix $H$. We also add the
canonical vectors given in $X_{k}$. We similarly solve the syndrome decoding
problem $Hx=X_{n-k}[i,:]$ to have the smallest set of rows from $H$ one has to
add to $X_{n-k}[i,:]$ to zero the row. Those row operations can be performed
with suitable CNOT gates inserted in the current Clifford circuit. Note that
if we apply an Hadamard gate, resp. an $R_{x}(\pi/2)$ gate, on the $k+i$-th
qubit, the row to zero becomes $Z_{n-k}[i,:]$, resp. $X_{n-k}[i,:]\oplus
Z_{n-k}[i,:]$: we can solve the syndrome decoding problem with these three
possibilities and keep the best result at the cost of adding one-qubit gates.

####  5.2.2 Depth optimization with a greedy procedure.

This case is even closer to the CNOT case from [35] than the graph-state case.
Consider the matrix

$B=X_{n-k}X_{k}^{-1}.$

Any row operation on $X_{n-k}$ is equivalent to a row operation on $B$, any
row operation on $X_{k}$ is equivalent to a column operation on $B$ and adding
a row of $X_{k}$ to a row of $X_{n-k}$ is equivalent to shifting an entry of
$B$. Until $B$ is zero repeat the following procedure:

  1. 1.

initialize two sets of non-used qubits
$L_{1}={[\\![}1,k{]\\!]},L_{2}={[\\![}k+1,k+n{]\\!]}$,

  2. 2.

compute the row or column operation that reduces at most the number of $1$ in
$B$ if such row or column operation involves only qubits in $L_{1}$ or
$L_{2}$, perform this operation and remove the two used qubits from either
$L_{1}$ or $L_{2}$,

  3. 3.

when no more row or column operation can be done consider the submatrix
$B[L_{2},L_{1}]$, this is the adjacency matrix of a bipartite graph $G$.
Compute a maximum matching in $G$ that will give you the set of row operations
to perform between $X_{k}$ and $X_{n-k}$.

One iteration of the three steps above gives a CNOT circuit of depth $1$ that
tries to reduce at most the number of one entries in $B$. The procedure always
terminates as we can always remove the entry one by one during step 3 of the
procedure above.

####  5.2.3 Extra-optimization.

Note that if the number of rotations $k$ is close to $n$, it might be
preferable to complete the set of Pauli operators into $n$ operators that
commute and directly apply the graph state synthesis on $n$ qubits. In the
following benchmarks we will always try the two approaches and keep the best
results. We also do the codiagonalization multiple times with random qubits
permutation at the beginning of the algorithm, again we keep the best result
and we post-processed the selected permutation.

###  5.3 Benchmarks

In order to evaluate the performances of the two algorithms introduced in
section 5, we ran benchmarks over both random and structured instances.
Results are compared with the co-diagonalization heuristics described in [36].

Random instances: In the first benchmark, we simply pick some Clifford
Tableaux uniformily at random and co-diagonalize their Z outputs. In other
words, given some Clifford operator $C$, we use our heuristics to co-
diagonalize operators $\\{CZ_{i}C^{\dagger},\forall i\in[1,n]\\}$. We then
compare the entangling gate count and entangling depth of the output circuits.
Results are reported in Figures 3, 4, 5, 6. For full stabilizer state
synthesis, we can observe that the Syndrome algorithm asymptotically
outperforms the state-of-the-art method in both entangling gate count and
entangling depth. Interestingly, so does the Matching algorithm, while it only
aims at limiting the circuit’s depth without being conservative in the
entangling gate count. When using our heuristics to co-diagonalize incomplete
set of rotations (Figure 5 and 6), the Syndrome algorithm performs similarly
to the state-of-the-art heuristic until some break-point where it stagnates
and thus starts outperforming it. This behavior can be observed in both
entangling count and depth. The Matching algorithm is outperformed by the
other two in entangling count until it also starts stagnating and ends up
outperforming the state-of-the-art.

Figure 3: Left: Entangling count (as in CNOT equivalent count) as a function
of the number of qubits. Each point is generated by averaging the entangling
count of 40 random Clifford tableaux. Right: the same data, but normalized by
the entangling count obtained via the state-of-the-art method of [36].

Figure 4: Left: Entangling depth (as in CNOT equivalent depth) as a function
of the number of qubits. Each point is generated by averaging the entangling
depth of 40 random Clifford tableaux. Right: the same data, but normalized by
the entangling depth obtained via the state-of-the-art method of [36].

Figure 5: Left: Entangling count (as in CNOT equivalent count) as a function
of the number of rotations in a commuting group of rotations over 30 qubits.
Each point is generated by averaging the entangling count of 40 random
rotation groups. Right: the same data, but normalized by the entangling count
obtained via the state-of-the-art method of [36].

Figure 6: Left: Entangling depth (as in CNOT equivalent depth) as a function
of the number of rotations in a commuting group of rotations over 30 qubits.
Each point is generated by averaging the entangling depth of 40 random
rotation groups. Right: the same data, but normalized by the entangling depth
obtained via the state-of-the-art method of [36].

Structured instances: In order to assess the performances of these algorithms
over interesting use cases, we embedded them into the meta-heuristics
presented in [36] that tackles synthesis of sequences of Pauli rotations (up
to arbitrary commutation of these rotations). In this meta-heuristic, Pauli
rotations are first into buckets of pairwise commuting rotations. Then,
rotations in each bucket are co-diagonalized (using any co-diagonalization
routine), and finally synthesized via a phase polynomial synthesis routine
(GraySynth from [25] in the formulation of [36]). Our two algorithms, together
with the co-diagonalization routine from [36] effectively gives us three
different algorithms to synthesize sequences of Pauli rotations. We ran these
algorithm on the UCCSD (Unitary Coupled-Cluster Singles and Doubles) instances
provided in [36]. Once again, we measured the entangling gate count and depth
of the resulting co-diagonalization circuits produced during the synthesis,
and reported them in Tables 3,4,5.

As expected, the Syndrome algorithm systematically outfperforms the Cowtan et
al. approach. For large molecules, it reaches up to a $10\%$ CNOT count
reduction. Interestingly, on these particularly structures instances, the
Matching algorithm manages to significantly reduce the circuit depth (up to
$71\%$ depth reduction) while only adding $1\%$ CNOT gates. This opens up the
possibility of generating UCCSD Ansätze with a significatively lower CNOT
depth than the one proposed in [36], as long as one can also improve the
entangling depth of the phase polynomials in between the co-diagonalization
circuits.

|  |  |  |  | Cowtan et al. |  | Syndrome |  | Matching
---|---|---|---|---|---|---|---|---|---
mol. | orbitals | enc. | basis |  | count | depth |  | count | rel. count | depth | rel. depth |  | count | rel. count | depth | rel. depth
H2 | cmplt | P | sto3g |  | 0 | 0 |  | 0 | 0% | 0 | 0% |  | 0 | 0% | 0 | 0%
H2 | cmplt | BK | sto3g |  | 0 | 0 |  | 0 | 0% | 0 | 0% |  | 0 | 0% | 0 | 0%
H2 | cmplt | JW | sto3g |  | 8 | 4 |  | 8 | -0.00% | 4 | -0.00% |  | 8 | -0.00% | 4 | -0.00%
H2 | cmplt | P | 631g |  | 50 | 46 |  | 46 | -8.00% | 38 | -17.39% |  | 50 | -0.00% | 38 | -17.39%
H2 | cmplt | BK | 631g |  | 50 | 48 |  | 50 | -0.00% | 48 | -0.00% |  | 52 | 4.00% | 40 | -16.67%
H4 | cmplt | BK | sto3g |  | 66 | 38 |  | 64 | -3.03% | 40 | 5.26% |  | 68 | 3.03% | 40 | 5.26%
H2 | cmplt | JW | 631g |  | 68 | 64 |  | 68 | -0.00% | 64 | -0.00% |  | 68 | -0.00% | 46 | -28.12%
H4 | cmplt | P | sto3g |  | 76 | 50 |  | 76 | -0.00% | 50 | -0.00% |  | 88 | 15.79% | 62 | 24.00%
LiH | frz | P | sto3g |  | 98 | 90 |  | 92 | -6.12% | 82 | -8.89% |  | 98 | -0.00% | 74 | -17.78%
H4 | cmplt | JW | sto3g |  | 98 | 50 |  | 98 | -0.00% | 48 | -4.00% |  | 98 | -0.00% | 36 | -28.00%
LiH | frz | JW | sto3g |  | 120 | 114 |  | 118 | -1.67% | 110 | -3.51% |  | 120 | -0.00% | 80 | -29.82%
LiH | frz | BK | sto3g |  | 134 | 122 |  | 128 | -4.48% | 106 | -13.11% |  | 142 | 5.97% | 90 | -26.23%
NH | frz | JW | sto3g |  | 276 | 176 |  | 276 | -0.00% | 160 | -9.09% |  | 276 | -0.00% | 112 | -36.36%
NH | frz | P | sto3g |  | 334 | 242 |  | 330 | -1.20% | 206 | -14.88% |  | 368 | 10.18% | 178 | -26.45%
H2O | frz | JW | sto3g |  | 428 | 236 |  | 428 | -0.00% | 218 | -7.63% |  | 428 | -0.00% | 164 | -30.51%
NH | cmplt | JW | sto3g |  | 428 | 236 |  | 428 | -0.00% | 218 | -7.63% |  | 428 | -0.00% | 164 | -30.51%
LiH | cmplt | JW | sto3g |  | 440 | 220 |  | 440 | -0.00% | 208 | -5.45% |  | 440 | -0.00% | 160 | -27.27%
LiH | cmplt | P | sto3g |  | 480 | 302 |  | 470 | -2.08% | 266 | -11.92% |  | 532 | 10.83% | 248 | -17.88%
NH | frz | BK | sto3g |  | 486 | 426 |  | 452 | -7.00% | 274 | -35.68% |  | 524 | 7.82% | 196 | -53.99%
CH2 | frz | JW | sto3g |  | 496 | 232 |  | 496 | -0.00% | 206 | -11.21% |  | 516 | 4.03% | 136 | -41.38%
H2 | cmplt | P | ccpvdz |  | 520 | 510 |  | 484 | -6.92% | 446 | -12.55% |  | 522 | 0.38% | 374 | -26.67%
LiH | frz | P | 631g |  | 520 | 510 |  | 496 | -4.62% | 464 | -9.02% |  | 522 | 0.38% | 374 | -26.67%
H2O | frz | P | sto3g |  | 526 | 368 |  | 516 | -1.90% | 312 | -15.22% |  | 582 | 10.65% | 274 | -25.54%
NH | cmplt | P | sto3g |  | 526 | 368 |  | 512 | -2.66% | 298 | -19.02% |  | 582 | 10.65% | 278 | -24.46%
LiH | frz | JW | 631g |  | 554 | 528 |  | 554 | -0.00% | 526 | -0.38% |  | 556 | 0.36% | 376 | -28.79%
H2 | cmplt | JW | ccpvdz |  | 554 | 528 |  | 554 | -0.00% | 528 | -0.00% |  | 556 | 0.36% | 376 | -28.79%

Table 3: Entangling count and depth of the co-diagonalization circuits
produced by our algorithms (Syndrome and Matching) and the state-of-the-art
routine (Cowtan et al.). For the Syndrome and Matching algorithms, we
additionally display the improvement (or degradation) relative to the state of
the art.

|  |  |  |  | Cowtan et al. |  | Syndrome |  | Matching
---|---|---|---|---|---|---|---|---|---
mol. | orbitals | enc. | basis |  | count | depth |  | count | rel. count | depth | rel. depth |  | count | rel. count | depth | rel. depth
H2 | cmplt | BK | ccpvdz |  | 646 | 596 |  | 622 | -3.72% | 540 | -9.40% |  | 654 | 1.24% | 398 | -33.22%
LiH | frz | BK | 631g |  | 646 | 596 |  | 620 | -4.02% | 534 | -10.40% |  | 656 | 1.55% | 400 | -32.89%
H2O | cmplt | JW | sto3g |  | 776 | 490 |  | 774 | -0.26% | 452 | -7.76% |  | 790 | 1.80% | 322 | -34.29%
CH2 | frz | P | sto3g |  | 778 | 512 |  | 766 | -1.54% | 432 | -15.62% |  | 870 | 11.83% | 332 | -35.16%
NH | cmplt | BK | sto3g |  | 898 | 658 |  | 846 | -5.79% | 484 | -26.44% |  | 978 | 8.91% | 380 | -42.25%
H2O | frz | BK | sto3g |  | 898 | 658 |  | 846 | -5.79% | 500 | -24.01% |  | 978 | 8.91% | 378 | -42.55%
LiH | cmplt | BK | sto3g |  | 948 | 652 |  | 904 | -4.64% | 518 | -20.55% |  | 1074 | 13.29% | 380 | -41.72%
CH2 | cmplt | JW | sto3g |  | 1010 | 550 |  | 1004 | -0.59% | 464 | -15.64% |  | 1082 | 7.13% | 336 | -38.91%
H4 | cmplt | JW | 631g |  | 1024 | 524 |  | 1024 | -0.00% | 488 | -6.87% |  | 1024 | -0.00% | 376 | -28.24%
H2O | cmplt | P | sto3g |  | 1084 | 734 |  | 1030 | -4.98% | 594 | -19.07% |  | 1188 | 9.59% | 496 | -32.43%
CH2 | frz | BK | sto3g |  | 1094 | 710 |  | 1040 | -4.94% | 540 | -23.94% |  | 1188 | 8.59% | 362 | -49.01%
H4 | cmplt | P | 631g |  | 1134 | 690 |  | 1118 | -1.41% | 606 | -12.17% |  | 1228 | 8.29% | 552 | -20.00%
H4 | cmplt | BK | 631g |  | 1334 | 848 |  | 1302 | -2.40% | 690 | -18.63% |  | 1566 | 17.39% | 668 | -21.23%
H2O | cmplt | BK | sto3g |  | 1406 | 972 |  | 1278 | -9.10% | 736 | -24.28% |  | 1470 | 4.55% | 502 | -48.35%
CH2 | cmplt | P | sto3g |  | 1412 | 900 |  | 1356 | -3.97% | 728 | -19.11% |  | 1558 | 10.34% | 506 | -43.78%
H8 | cmplt | JW | sto3g |  | 1534 | 710 |  | 1518 | -1.04% | 574 | -19.15% |  | 1680 | 9.52% | 420 | -40.85%
LiH | frz | P | ccpvdz |  | 1808 | 1798 |  | 1748 | -3.32% | 1690 | -6.01% |  | 1810 | 0.11% | 1252 | -30.37%
H8 | cmplt | P | sto3g |  | 1858 | 1074 |  | 1812 | -2.48% | 856 | -20.30% |  | 2014 | 8.40% | 572 | -46.74%
LiH | frz | JW | ccpvdz |  | 1866 | 1808 |  | 1866 | -0.00% | 1806 | -0.11% |  | 1868 | 0.11% | 1256 | -30.53%
H8 | cmplt | BK | sto3g |  | 1894 | 1096 |  | 1812 | -4.33% | 908 | -17.15% |  | 2176 | 14.89% | 616 | -43.80%
LiH | frz | BK | ccpvdz |  | 2036 | 1952 |  | 1982 | -2.65% | 1828 | -6.35% |  | 2064 | 1.38% | 1326 | -32.07%
CH2 | cmplt | BK | sto3g |  | 2372 | 1486 |  | 2142 | -9.70% | 1154 | -22.34% |  | 2442 | 2.95% | 664 | -55.32%
LiH | cmplt | JW | 631g |  | 2482 | 1410 |  | 2474 | -0.32% | 1270 | -9.93% |  | 2526 | 1.77% | 958 | -32.06%
LiH | cmplt | P | 631g |  | 3682 | 2402 |  | 3572 | -2.99% | 1862 | -22.48% |  | 3986 | 8.26% | 1468 | -38.88%
NH | frz | JW | 631g |  | 4208 | 2636 |  | 4156 | -1.24% | 1966 | -25.42% |  | 4598 | 9.27% | 1368 | -48.10%
H2 | cmplt | P | ccpvtz |  | 4498 | 4488 |  | 4416 | -1.82% | 4328 | -3.57% |  | 4500 | 0.04% | 3074 | -31.51%

Table 4: See Table 3.

|  |  |  |  | Cowtan et al. |  | Syndrome |  | Matching
---|---|---|---|---|---|---|---|---|---
mol. | orbitals | enc. | basis |  | count | depth |  | count | rel. count | depth | rel. depth |  | count | rel. count | depth | rel. depth
H2 | cmplt | JW | ccpvtz |  | 4586 | 4488 |  | 4586 | -0.00% | 4488 | -0.00% |  | 4588 | 0.04% | 3076 | -31.46%
NH | frz | P | 631g |  | 4838 | 2894 |  | 4710 | -2.65% | 2216 | -23.43% |  | 5282 | 9.18% | 1508 | -47.89%
H2 | cmplt | BK | ccpvtz |  | 5056 | 4808 |  | 4932 | -2.45% | 4602 | -4.28% |  | 5066 | 0.20% | 3154 | -34.40%
LiH | cmplt | BK | 631g |  | 6600 | 4344 |  | 5954 | -9.79% | 2954 | -32.00% |  | 7170 | 8.64% | 1810 | -58.33%
NH | frz | BK | 631g |  | 6946 | 4380 |  | 6524 | -6.08% | 3132 | -28.49% |  | 7646 | 10.08% | 1832 | -58.17%
NH | cmplt | JW | 631g |  | 7014 | 3748 |  | 6904 | -1.57% | 2868 | -23.48% |  | 7880 | 12.35% | 2004 | -46.53%
H2O | frz | JW | 631g |  | 7436 | 3684 |  | 7318 | -1.59% | 2928 | -20.52% |  | 8546 | 14.93% | 2134 | -42.07%
NH | cmplt | P | 631g |  | 7522 | 4104 |  | 7212 | -4.12% | 3120 | -23.98% |  | 8128 | 8.06% | 1884 | -54.09%
H2O | frz | P | 631g |  | 8700 | 4834 |  | 8408 | -3.36% | 3666 | -24.16% |  | 9584 | 10.16% | 2236 | -53.74%
C2H4 | frz | JW | sto3g |  | 8854 | 3912 |  | 8564 | -3.28% | 3004 | -23.21% |  | 10472 | 18.27% | 1990 | -49.13%
LiH | cmplt | JW | ccpvdz |  | 9684 | 5480 |  | 9504 | -1.86% | 4748 | -13.36% |  | 10156 | 4.87% | 3748 | -31.61%
H4 | cmplt | JW | ccpvdz |  | 10162 | 5334 |  | 10148 | -0.14% | 4774 | -10.50% |  | 10766 | 5.94% | 3980 | -25.38%
H2O | frz | BK | 631g |  | 10746 | 6002 |  | 10040 | -6.57% | 4184 | -30.29% |  | 12168 | 13.23% | 2402 | -59.98%
NH | cmplt | BK | 631g |  | 11956 | 7418 |  | 10486 | -12.30% | 4762 | -35.80% |  | 12526 | 4.77% | 2546 | -65.68%
H2O | cmplt | JW | 631g |  | 12398 | 5948 |  | 12052 | -2.79% | 4674 | -21.42% |  | 14400 | 16.15% | 3082 | -48.18%
C2H4 | frz | P | sto3g |  | 12660 | 6820 |  | 11646 | -8.01% | 4620 | -32.26% |  | 13404 | 5.88% | 2556 | -62.52%
H4 | cmplt | P | ccpvdz |  | 13594 | 8446 |  | 13158 | -3.21% | 6580 | -22.09% |  | 14702 | 8.15% | 5198 | -38.46%
LiH | cmplt | P | ccpvdz |  | 13992 | 8630 |  | 13418 | -4.10% | 6434 | -25.45% |  | 15102 | 7.93% | 4738 | -45.10%
H4 | cmplt | BK | ccpvdz |  | 17058 | 10284 |  | 16328 | -4.28% | 7802 | -24.13% |  | 19360 | 13.50% | 6072 | -40.96%
H2O | cmplt | P | 631g |  | 18242 | 9642 |  | 16742 | -8.22% | 6584 | -31.72% |  | 19458 | 6.67% | 3674 | -61.90%
C2H4 | cmplt | JW | sto3g |  | 18734 | 9008 |  | 17538 | -6.38% | 6734 | -25.24% |  | 21654 | 15.59% | 4114 | -54.33%
LiH | cmplt | BK | ccpvdz |  | 18906 | 11342 |  | 17460 | -7.65% | 7942 | -29.98% |  | 21090 | 11.55% | 5410 | -52.30%
C2H4 | frz | BK | sto3g |  | 20720 | 9718 |  | 17730 | -14.43% | 6904 | -28.96% |  | 21914 | 5.76% | 3422 | -64.79%
C2H4 | cmplt | P | sto3g |  | 22402 | 11642 |  | 20142 | -10.09% | 7826 | -32.78% |  | 23576 | 5.24% | 4082 | -64.94%
H2O | cmplt | BK | 631g |  | 28008 | 14542 |  | 23914 | -14.62% | 9718 | -33.17% |  | 29076 | 3.81% | 4548 | -68.73%
C2H4 | cmplt | BK | sto3g |  | 41642 | 19966 |  | 34076 | -18.17% | 12622 | -36.78% |  | 42030 | 0.93% | 5774 | -71.08%

Table 5: See Table 3.

##  6 Conclusion

This article provides a generic compilation method for Clifford isometries.
The framework exploits the graph-state structure of Clifford operators already
exposed in previous works in the literature but with a minimal set of
theoretical requirements. Overall, the synthesis of Clifford isometries is
encoded as the reduction of a symmetric boolean matrix into a purposely
defined identity matrix. The available operations are elementary: row and
column operations, entries flip, and suitable rank-one updates. The
versatility of our framework is highlighted by its capability of rediscovering
almost every normal forms of the literature for Clifford operators and
stabilizer states. Our framework also highlights deeper understandings about
the role of phase polynomials and equivalent structures (namely CNOT + Rx
circuits) in the construction of Clifford circuits. One application is the
proof that any $n$-qubit Clifford circuit can be executed in two-qubit depth
$7n$ on an LNN architecture. We also practically improve the codiagonalization
of Pauli rotations and use it to optimize quantum circuits from quantum
chemistry.

Still, while being simple and accessible, our framework lacks some
universality. The Hadamard gate can only be applied in specific cases, and we
are constrained to keep our Clifford isometries in a graph-state form.
Therefore our framework can fail at offering the possibility to find optimal
Clifford circuits for one given operator. As a future work it would be
interesting to extend the graph-state formalism and see if a simple framework
as universal as the tableau formalism and as simple as the graph-state
approach can be derived.

## Acknowledgments

The authors thank Simon Perdrix for comments on an earlier version of this
article. This work has been supported by the French state through the ANR as a
part of _Plan France 2030_ , projects NISQ2LSQ (ANR-22-PETQ-0006) and EPiQ
(ANR-22-PETQ-0007), as well as the ANR project SoftQPro (ANR-17-CE25-0009).

## References

  * [1] Daniel Gottesman.  “Stabilizer codes and quantum error correction”.  PhD thesis.  Caltech.  (1997).
  * [2] E. Knill, D. Leibfried, R. Reichle, J. Britton, R. B. Blakestad, J. D. Jost, C. Langer, R. Ozeri, S. Seidelin, and D. J. Wineland.  “Randomized benchmarking of quantum gates”.  Physical Review A 77, 012307 (2008).
  * [3] Easwar Magesan, J. M. Gambetta, and Joseph Emerson.  “Scalable and Robust Randomized Benchmarking of Quantum Processes”.  Physical Review Letters 106, 180504 (2011).
  * [4] Sergey Bravyi and Alexei Kitaev.  “Universal quantum computation with ideal clifford gates and noisy ancillas”.  Phys. Rev. A 71, 022316 (2005).  url: https://doi.org/10.1103/PhysRevA.71.022316.
  * [5] E. Knill.  “Quantum computing with realistically noisy devices”.  Nature 434, 39–44 (2005).
  * [6] Charles H. Bennett, David P. DiVincenzo, John A. Smolin, and William K. Wootters.  “Mixed-state entanglement and quantum error correction”.  Physical Review A 54, 3824–3851 (1996).
  * [7] Scott Aaronson and Daniel Gottesman.  “Improved simulation of stabilizer circuits”.  Phys. Rev. A 70, 052328 (2004).
  * [8] Daniel Gottesman.  “The Heisenberg Representation of Quantum Computers” (1998).  arXiv:quant-ph/9807006.
  * [9] P. W. Shor.  “Fault-tolerant quantum computation”.  In Proceedings of 37th Conference on Foundations of Computer Science.  Pages 56–56.  IEEE Computer Society (1996).
  * [10] John Preskill.  “Fault-tolerant quantum computation”.  In Introduction to quantum computation and information.  Pages 213–269.  World Scientific (1998).
  * [11] John Preskill.  “Quantum Computing in the NISQ era and beyond”.  Quantum 2, 79 (2018).
  * [12] Riccardo Manenti, Eyob A. Sete, Angela Q. Chen, Shobhan Kulshreshtha, Jen-Hao Yeh, Feyza Oruc, Andrew Bestwick, Mark Field, Keith Jackson, and Stefano Poletto.  “Full control of superconducting qubits with combined on-chip microwave and flux lines”.  Applied Physics Letters 119, 144001 (2021).
  * [13] Jerry M. Chow, Jay M. Gambetta, Easwar Magesan, David W. Abraham, Andrew W. Cross, B. R. Johnson, Nicholas A. Masluk, Colm A. Ryan, John A. Smolin, Srikanth J. Srinivasan, and M. Steffen.  “Implementing a strand of a scalable fault-tolerant quantum computing fabric”.  Nature Communications 5, 4015 (2014).
  * [14] Christopher Chamberland, Guanyu Zhu, Theodore J. Yoder, Jared B. Hertzberg, and Andrew W. Cross.  “Topological and Subsystem Codes on Low-Degree Graphs with Flag Qubits”.  Physical Review X 10, 011022 (2020).
  * [15] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P. Harrigan, Michael J. Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S. Humble, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod R. McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, and John M. Martinis.  “Quantum supremacy using a programmable superconducting processor”.  Nature 574, 505–510 (2019).
  * [16] John van de Wetering.  “Constructing quantum circuits with global gates”.  New Journal of Physics 23, 043015 (2021).
  * [17] Dmitri Maslov and Yunseong Nam.  “Use of global interactions in efficient quantum circuit constructions”.  New Journal of Physics 20, 033018 (2018).
  * [18] Simon Martiel and Timothée Goubault de Brugière.  “Architecture aware compilation of quantum circuits via lazy synthesis”.  Quantum 6, 729 (2022).
  * [19] Dmitri Maslov and Martin Roetteler.  “Shorter stabilizer circuits via bruhat decomposition and quantum circuit transformations”.  IEEE Trans. Inf. Theory 64, 4729–4738 (2018).
  * [20] Ross Duncan, Aleks Kissinger, Simon Perdrix, and John Van De Wetering.  “Graph-theoretic simplification of quantum circuits with the zx-calculus”.  Quantum 4, 279 (2020).  url: https://doi.org/10.22331/q-2020-06-04-279.
  * [21] Sergey Bravyi and Dmitri Maslov.  “Hadamard-Free Circuits Expose the Structure of the Clifford Group”.  IEEE Transactions on Information Theory 67, 4546–4563 (2021).
  * [22] Marc Bataille.  “Reduced quantum circuits for stabilizer states and graph states” (2021).  arXiv:2107.00885.
  * [23] M. Van den Nest.  “Classical simulation of quantum computation, the gottesman-Knill theorem, and slightly beyond”.  Quantum Information and Computation 10, 258–271 (2010).
  * [24] Hector J. Garcia, Igor L. Markov, and Andrew W. Cross.  “On the geometry of stabilizer states”.  Quantum Information and Computation 14, 683–720 (2014).
  * [25] Matthew Amy, Parsiad Azimzadeh, and Michele Mosca.  “On the controlled-NOT complexity of controlled-NOT–phase circuits”.  Quantum Science and Technology 4, 015002 (2018).
  * [26] Vivien Vandaele, Simon Martiel, and Timothée Goubault de Brugière.  “Phase polynomials synthesis algorithms for NISQ architectures and beyond”.  Quantum Science and Technology 7, 045027 (2022).
  * [27] Sergey Bravyi, Joseph A. Latone, and Dmitri Maslov.  “6-qubit optimal Clifford circuits”.  npj Quantum Information 8, 1–12 (2022).
  * [28] Vadym Kliuchnikov and Dmitri Maslov.  “Optimization of Clifford circuits”.  Physical Review A 88, 052307 (2013).
  * [29] Sergey Bravyi, Ruslan Shaydulin, Shaohan Hu, and Dmitri Maslov.  “Clifford Circuit Optimization with Templates and Symbolic Pauli Gates”.  Quantum 5, 580 (2021).
  * [30] Sergey Bravyi and Alexei Kitaev.  “Universal quantum computation with ideal Clifford gates and noisy ancillas”.  Physical Review A 71, 022316 (2005).
  * [31] Sergey Bravyi and Jeongwan Haah.  “Magic-state distillation with low overhead”.  Physical Review A 86, 052329 (2012).
  * [32] Samuel A. Kutin, David Petrie Moulton, and Lawren M. Smithline.  “Computation at a distance” (2007).  arXiv:quant-ph/0701194.
  * [33] Timothée Goubault de Brugière, Marc Baboulin, Benoît Valiron, Simon Martiel, and Cyril Allouche.  “Quantum CNOT circuits synthesis for NISQ architectures using the syndrome decoding problem”.  In Ivan Lanese and Mariusz Rawski, editors, Reversible Computation - 12th International Conference, RC 2020, Oslo, Norway, July 9-10, 2020, Proceedings.  Volume 12227 of Lecture Notes in Computer Science, pages 189–205.  Springer (2020).
  * [34] Timothée Goubault de Brugière, Marc Baboulin, Benoît Valiron, Simon Martiel, and Cyril Allouche.  “Decoding techniques applied to the compilation of CNOT circuits for NISQ architectures”.  Science of Computer Programming 214, 102726 (2022).
  * [35] Timothée Goubault de Brugière, Marc Baboulin, Benoît Valiron, Simon Martiel, and Cyril Allouche.  “Reducing the Depth of Linear Reversible Quantum Circuits”.  IEEE Transactions on Quantum Engineering 2, 1–22 (2021).
  * [36] Alexander Cowtan, Will Simmons, and Ross Duncan.  “A Generic Compilation Strategy for the Unitary Coupled Cluster Ansatz” (2020).  arXiv:2007.10515.

## Action of the Clifford gates in the graph-state formalism

  1. 1.

$S$ on the output qubit $i$ ($1\leq i\leq n$)
We perform the row operation $M[i,:]=M[i,:]\oplus M[i+n,:]$. We get

$M=\left[\begin{array}[]{c|c}G_{n}B\oplus\tilde{e}_{ii}B&(B^{T})^{-1}\begin{pmatrix}I_{k}\\\
0\end{pmatrix}\oplus G_{n}B\begin{pmatrix}G_{k}\\\
0\end{pmatrix}\oplus\tilde{e}_{ii}B\begin{pmatrix}G_{k}\\\ 0\end{pmatrix}\\\
\hline\cr B&B\begin{pmatrix}G_{k}\\\ 0\end{pmatrix}\end{array}\right]$

and we have $G_{n}=G_{n}\oplus\tilde{e}_{ii}$. Equivalently we have

$G=G\oplus\tilde{e}_{i+k,i+k}$

  2. 2.

$S$ on the input qubit $i$ ($1\leq i\leq k$)
We perform the column operation $M[:,i+n]=M[:,i+n]\oplus M[:,i]$. We get

$M=\left[\begin{array}[]{c|c}G_{n}B&(B^{T})^{-1}\begin{pmatrix}I_{k}\\\
0\end{pmatrix}\oplus G_{n}B\begin{pmatrix}G_{k}\\\ 0\end{pmatrix}\oplus
G_{n}B\tilde{e}_{ii}\\\ \hline\cr B&B\begin{pmatrix}G_{k}\\\
0\end{pmatrix}\oplus B\tilde{e}_{ii}\end{array}\right]$

and we have $G_{k}=G_{k}\oplus\tilde{e}_{ii}$. Equivalently we have

$G=G\oplus\tilde{e}_{i,i}$

  3. 3.

$CZ$ on the output qubits $i,j$ ($1\leq i<j\leq n$)
We perform the row operations $M[i,:]=M[i,:]\oplus M[j+n,:]$ and
$M[j,:]=M[j,:]\oplus M[i+n,:]$. We get

$M=\left[\begin{array}[]{c|c}G_{n}B\oplus\tilde{e}_{ij}B&(B^{T})^{-1}\begin{pmatrix}I_{k}\\\
0\end{pmatrix}\oplus G_{n}B\begin{pmatrix}G_{k}\\\
0\end{pmatrix}\oplus\tilde{e}_{ij}B\begin{pmatrix}G_{k}\\\ 0\end{pmatrix}\\\
\hline\cr B&B\begin{pmatrix}G_{k}\\\ 0\end{pmatrix}\end{array}\right]$

and we have $G_{n}=G_{n}\oplus\tilde{e}_{ij}$. Equivalently we have

$G=G\oplus\tilde{e}_{i+k,j+k}$

  4. 4.

$CZ$ on the input qubits $i,j$ ($1\leq i<j\leq n$)
We perform the column operations $M[:,i+n]=M[:,i+n]\oplus M[:,j]$ and
$M[:,j+n]=M[:,j+n]\oplus M[:,i]$. We get

$M=\left[\begin{array}[]{c|c}G_{n}B&(B^{T})^{-1}\begin{pmatrix}I_{k}\\\
0\end{pmatrix}\oplus G_{n}B\begin{pmatrix}G_{k}\\\ 0\end{pmatrix}\oplus
G_{n}B\tilde{e}_{ij}\\\ \hline\cr B&B\begin{pmatrix}G_{k}\\\
0\end{pmatrix}\oplus B\tilde{e}_{ij}\end{array}\right]$

and we have $G_{k}=G_{k}\oplus\tilde{e}_{ij}$. Equivalently we have

$G=G\oplus\tilde{e}_{ij}$

  5. 5.

$CNOT$ on the output qubits with control $i$, target $j$ ($1\leq i<j\leq n$)
We perform the row operations $M[i,:]=M[i,:]\oplus M[j,:]$ and
$M[j+n,:]=M[j+n,:]\oplus M[i+n,:]$. We get

$M=\left[\begin{array}[]{c|c}E_{ij}G_{n}B&E_{ij}(B^{T})^{-1}\begin{pmatrix}I_{k}\\\
0\end{pmatrix}\oplus E_{ij}G_{n}B\begin{pmatrix}G_{k}\\\ 0\end{pmatrix}\\\
\hline\cr E_{ji}B&E_{ji}B\begin{pmatrix}G_{k}\\\
0\end{pmatrix}\end{array}\right].$

We write

$M=\left[\begin{array}[]{c|c}E_{ij}G_{n}E_{ji}\times
E_{ji}B&(E_{ji}B)^{-T}\begin{pmatrix}I_{k}\\\ 0\end{pmatrix}\oplus
E_{ij}G_{n}E_{ji}\times E_{ji}B\begin{pmatrix}G_{k}\\\ 0\end{pmatrix}\\\
\hline\cr E_{ji}B&E_{ji}B\begin{pmatrix}G_{k}\\\
0\end{pmatrix}\end{array}\right]$

and we get $G_{n}=E_{ij}G_{n}E_{ji}$ and $B=E_{ji}B$, i.e, $B_{k}=B_{k}E_{ji}$
or $B_{k}^{T}=E_{ij}B_{k}^{T}$. Equivalently we have

$G=E_{i+k,j+k}GE_{j+k,i+k}.$

  6. 6.

$CNOT$ on the input qubits with control $i$, target $j$ ($1\leq i<j\leq k$)
We perform the column operations $M[:,j]=M[:,j]\oplus M[:,i]$ and
$M[:,i+n]=M[:,i+n]\oplus M[:,j+n]$. We get

$M=\left[\begin{array}[]{c|c}G_{n}BE_{ij}&(B^{T})^{-1}\begin{pmatrix}I_{k}\\\
0\end{pmatrix}E_{ji}\oplus G_{n}B\begin{pmatrix}G_{k}\\\
0\end{pmatrix}E_{ji}\\\ \hline\cr BE_{ij}&B\begin{pmatrix}G_{k}\\\
0\end{pmatrix}E_{ji}\end{array}\right].$

We write

$M=\left[\begin{array}[]{c|c}G_{n}BE_{ij}&(BE_{ij})^{-T})\begin{pmatrix}I_{k}\\\
0\end{pmatrix}\oplus G_{n}BE_{ij}\begin{pmatrix}E_{ij}G_{k}E_{ji}\\\
0\end{pmatrix}\\\ \hline\cr BE_{ij}&BE_{ij}\begin{pmatrix}E_{ij}G_{k}E_{ji}\\\
0\end{pmatrix}\end{array}\right]$

and we get $G_{k}=E_{ij}G_{k}E_{ji}$ and $B=BE_{ij}$, i.e,
$B_{k}=E_{ij}B_{k}$. Equivalently we have

$G=E_{ij}GE_{ji}.$

  7. 7.

if $G_{n}[i,i]=0$, then we can apply an $R_{x}(\pi/2)$ on the output qubit
$i$, we get

$M=\left[\begin{array}[]{c|c}G_{n}B&(B^{T})^{-1}\begin{pmatrix}I_{k}\\\
0\end{pmatrix}\oplus G_{n}B\begin{pmatrix}G_{k}\\\ 0\end{pmatrix}\\\
\hline\cr(I+e_{ii}G_{n})B&(I+e_{ii}G_{n})B\begin{pmatrix}G_{k}\\\
0\end{pmatrix}\oplus e_{ii}(B^{T})^{-1}\begin{pmatrix}I_{k}\\\
0\end{pmatrix}\end{array}\right].$

One can check that $(I+e_{ii}G)^{2}=I$, therefore:

$M=\left[\begin{array}[]{c|c}G_{n}(I+e_{ii}G_{n})(I+e_{ii}G_{n})B&(((I+e_{ii}G_{n})(I+e_{ii}G_{n})B)^{T})^{-1}\begin{pmatrix}I_{k}\\\
0\end{pmatrix}\oplus
G_{n}(I+e_{ii}G_{n})(I+e_{ii}G_{n})B\begin{pmatrix}G_{k}\\\ 0\end{pmatrix}\\\
\hline\cr(I+e_{ii}G_{n})B&(I+e_{ii}G_{n})B\begin{pmatrix}G_{k}\\\
0\end{pmatrix}\oplus
e_{ii}(((I+e_{ii}G_{n})(I+e_{ii}G_{n})B)^{T})^{-1}\begin{pmatrix}I_{k}\\\
0\end{pmatrix}\end{array}\right].$

It is easy to see that we will have

$G_{n}\leftarrow G_{n}(I+e_{ii}G_{n}),$ $B\leftarrow(I+e_{ii}G_{n})B,$

but it is trickier to see the effect on $G_{k}$. First, let’s simplify the
formula by replacing by the new values of $B$ and $G_{n}$:

$M=\left[\begin{array}[]{c|c}G^{\prime}_{n}B^{\prime}&(I+e_{ii}G_{n})^{T}(B^{\prime
T})^{-1}\begin{pmatrix}I_{k}\\\ 0\end{pmatrix}\oplus
G^{\prime}_{n}B^{\prime}\begin{pmatrix}G_{k}\\\ 0\end{pmatrix}\\\ \hline\cr
B^{\prime}&B^{\prime}\begin{pmatrix}G_{k}\\\ 0\end{pmatrix}\oplus
e_{ii}(I+e_{ii}G_{n})^{T}(B^{\prime T})^{-1}\begin{pmatrix}I_{k}\\\
0\end{pmatrix}\end{array}\right].$

We have $e_{ii}(I+e_{ii}G_{n})^{T}=e_{ii}(I+G_{n}e_{ii})=e_{ii}$ because
$e_{ii}G_{n}e_{ii}=G_{n}[i,i]e_{ii}=0$, then

$M=\left[\begin{array}[]{c|c}G^{\prime}_{n}B^{\prime}&(B^{\prime
T})^{-1}\begin{pmatrix}I_{k}\\\ 0\end{pmatrix}\oplus G_{n}e_{ii}(B^{\prime
T})^{-1}\begin{pmatrix}I_{k}\\\ 0\end{pmatrix}\oplus
G^{\prime}_{n}B^{\prime}\begin{pmatrix}G_{k}\\\ 0\end{pmatrix}\\\ \hline\cr
B^{\prime}&B^{\prime}\begin{pmatrix}G_{k}\\\ 0\end{pmatrix}\oplus
e_{ii}(B^{\prime T})^{-1}\begin{pmatrix}I_{k}\\\
0\end{pmatrix}\end{array}\right].$

We remind that $G_{n}B=G^{\prime}_{n}B^{\prime}$, therefore
$G_{n}=G^{\prime}_{n}B^{\prime}B^{-1}$:

$M=\left[\begin{array}[]{c|c}G^{\prime}_{n}B^{\prime}&(B^{\prime
T})^{-1}\begin{pmatrix}I_{k}\\\ 0\end{pmatrix}\oplus
G^{\prime}_{n}B^{\prime}B^{-1}e_{ii}(B^{\prime T})^{-1}\begin{pmatrix}I_{k}\\\
0\end{pmatrix}\oplus G^{\prime}_{n}B^{\prime}\begin{pmatrix}G_{k}\\\
0\end{pmatrix}\\\ \hline\cr B^{\prime}&B^{\prime}\begin{pmatrix}G_{k}\\\
0\end{pmatrix}\oplus B^{\prime}B^{\prime-1}e_{ii}(B^{\prime
T})^{-1}\begin{pmatrix}I_{k}\\\ 0\end{pmatrix}\end{array}\right].$

We need to compute two last quantities:

$B^{-1}e_{ii}(B^{\prime T})^{-1}$

and

$B^{\prime-1}e_{ii}(B^{\prime T})^{-1}$

We recall that $e_{ii}(I+e_{ii}G_{n})^{T}=e_{ii}$, and similarly
$(I+e_{ii}G_{n})e_{ii}=e_{ii}$. So

$B^{-1}e_{ii}(B^{\prime
T})^{-1}=B^{-1}e_{ii}(I+e_{ii}G_{n})^{T}(B^{-1})^{T}=B^{-1}e_{ii}(B^{-1})^{T},$
$B^{\prime-1}e_{ii}(B^{\prime
T})^{-1}=B^{-1}(I+e_{ii}G_{n})e_{ii}(I+e_{ii}G_{n})^{T}(B^{-1})^{T}=B^{-1}e_{ii}(B^{-1})^{T}.$

Writing $b_{i}=B^{-1}[:,i]$, $B^{-1}e_{ii}(B^{-1})^{T}=b_{i}b_{i}^{T}$ and
finally we have

$M=\left[\begin{array}[]{c|c}G^{\prime}_{n}B^{\prime}&(B^{\prime
T})^{-1}\begin{pmatrix}I_{k}\\\ 0\end{pmatrix}\oplus
G^{\prime}_{n}B^{\prime}\left(b_{i}b_{i}^{T}\begin{pmatrix}I_{k}\\\
0\end{pmatrix}\oplus\begin{pmatrix}G_{k}\\\ 0\end{pmatrix}\right)\\\ \hline\cr
B^{\prime}&B^{\prime}\left(b_{i}b_{i}^{T}\begin{pmatrix}I_{k}\\\
0\end{pmatrix}\oplus\begin{pmatrix}G_{k}\\\
0\end{pmatrix}\right)\end{array}\right].$

i.e

$\begin{pmatrix}G_{k}\\\ 0\end{pmatrix}\leftarrow\begin{pmatrix}G_{k}\\\
0\end{pmatrix}\oplus b_{i}b_{i}^{T}\begin{pmatrix}I_{k}\\\ 0\end{pmatrix}$

and

$G_{k}\leftarrow G_{k}\oplus b_{i}[1:k]b_{i}[1:k]^{T}=G_{k}\oplus
B_{k}[:,i]B_{k}[:,i]^{T}.$

We do not care about the block below $G_{k}$ being modified as we can always
zero it with free column operations.

To summarize, we have

$G_{n}\leftarrow G_{n}(I+e_{ii}G_{n}),\text{ equivalently, }G_{n}\leftarrow
G_{n}\oplus G_{n}[:,i]G_{n}[:,i]^{T}$ $G_{k}\leftarrow G_{k}\oplus
B_{k}[:,i]B_{k}[:,i]^{T},$ $B^{-1}\leftarrow B^{-1}(I+e_{ii}G_{n}),\text{
equivalently, }B_{k}\leftarrow B_{k}\oplus B_{k}[:,i]G_{n}[:,i]^{T}.$

One can check that this is equivalent to

$G\leftarrow G\oplus G[:,k+i]G[:,k+i]^{T}.$

  8. 8.

A similar proof can be given to show the effect of an $R_{x}(\pi/2)$ gate on
the input qubits.

  9. 9.

For the Hadamard gates, simply write $H\sim SR_{x}(\pi/2)S$ and apply
successively the three gates to have the results.