# Clifford Circuit Optimization with Templates
and Symbolic Pauli Gates

Sergey Bravyi1, Ruslan Shaydulin2, Shaohan Hu3, and Dmitri Maslov1

(1IBM Quantum, IBM Thomas J. Watson Research Center, Yorktown Heights, NY
10598
2Mathematics and Computer Science Division, Argonne National Laboratory,
Lemont, IL 60439
3JPMorgan Chase & Co., New York, NY 10017
)

###### Abstract

The Clifford group is a finite subgroup of the unitary group generated by the
Hadamard, the cnot, and the Phase gates. This group plays a prominent role in
quantum error correction, randomized benchmarking protocols, and the study of
entanglement. Here we consider the problem of finding a short quantum circuit
implementing a given Clifford group element. Our methods aim to minimize the
entangling gate count assuming all-to-all qubit connectivity. First, we
consider circuit optimization based on template matching and design Clifford-
specific templates that leverage the ability to factor out Pauli and SWAP
gates. Second, we introduce a symbolic peephole optimization method. It works
by projecting the full circuit onto a small subset of qubits and optimally
recompiling the projected subcircuit via dynamic programming. cnot gates
coupling the chosen subset of qubits with the remaining qubits are expressed
using symbolic Pauli gates. Software implementation of these methods finds
circuits that are only 0.2% away from optimal for 6 qubits and reduces the
two-qubit gate count in circuits with up to 64 qubits by 64.7% on average,
compared with the Aaronson–Gottesman canonical form [9].

##  1 Introduction

One of the central challenges in quantum computation is the problem of
generating a short schedule of physically implementable quantum gates
realizing a given unitary operation, otherwise known as the quantum circuit
synthesis/optimization problem. In this paper, we focus on a restricted class
of quantum circuits belonging to the Clifford group, which is a subgroup of
the group of all unitary transformations. Clifford group elements play a
crucial role in quantum error correction [1], quantum state distillation [2,
3], randomized benchmarking [4, 5], study of entanglement [1, 6], and, more
recently, shadow tomography [7, 8], to name some application areas. Clifford
group elements are important and frequently encountered subsets of physical-
level and fault-tolerant quantum circuits; sometimes, an entire quantum
algorithm can be a Clifford circuit (e.g., Bernstein–Vazirani [1]).

Earlier studies of the synthesis of $n$-qubit Clifford circuits resulted in
the construction of asymptotically optimal (i.e., optimal up to a constant
factor) implementations in the number of gates used. Specifically, the
canonical form introduced by Aaronson and Gottesman [9] accomplishes this
using $\Theta\left(n^{2}/\log(n)\right)$ gates [10]. Recently Bravyi and
Maslov [11] reported a depth-$9n$ implementation over Linear Nearest Neighbor
architecture and introduced a canonical parameterization of the Clifford group
by quantum circuits with the exactly minimal number of the degrees of freedom.
In contrast, in this paper we focus on the practical aspects of Clifford
circuit optimization—our goal is to implement a given Clifford unitary by a
circuit with the smallest possible number of entangling gates.

Current approaches to the synthesis of exactly optimal Clifford circuits are
prohibitively expensive even for small parameters: the largest number of
qubits for which optimal Clifford circuits are known is six [13]. Using these
exhaustive tools leaves little hope of scaling optimal implementations beyond
six qubits. Thus, efficient heuristics are desirable for practical
applicability. Here we focus on the synthesis and optimization of Clifford
circuits that cannot be obtained optimally, namely, circuits with $n\,{>}\,6$
qubits.

Here we develop heuristic approaches for the synthesis and optimization of
Clifford circuits. Our algorithms and their implementation bridge the gap
between nonscalable methods for the synthesis of exactly optimal Clifford
circuits and the suboptimal (albeit asymptotically optimal) synthesis methods.
Our circuit synthesizer is based on the reduction of the tableau matrix
representing Clifford unitary to the identity, while applying gates on both
the input and output sides. Our optimization approach is based on the
extension and modification of two circuit optimization techniques: template
matching [14] and peephole optimization [15]. To generate an optimized circuit
for a specific Clifford unitary, we first compile it using the tableau
representation and then apply the optimization techniques to the compiled
circuit. We note that the optimization techniques can be applied independently
of the synthesizer considered in this paper.

The first optimization technique we develop is a Clifford-specific extension
of the template matching method [14]. We discuss previous results on template
matching in depth in Subsection 2.1. We introduce a three-stage approach that
leverages the observation that in Clifford circuits Pauli gates can always be
“pushed” to the end of the circuit without changing the non-Pauli Clifford
gates (i.e., Hadamard, controlled-NOT, and Phase gates) and that all swap
gates can be factored out of any quantum circuit by qubit relabeling. We thus
partition the circuit into “compute,” “swap,” and “Pauli” stages by “pushing”
Pauli and swap gates to the end of the circuit. Next we optimize the “compute”
stage using templates. Then we optimize the “swap” stage by exploiting the
fact that a swap gate can be implemented at the effective cost of one
entangling gate if it can be merged with a cnot or a cz gate.

The second technique we develop is symbolic peephole optimization. It is
inspired by the peephole optimization method first introduced in the context
of reversible computations [15]. At each step, the symbolic peephole algorithm
considers subcircuits spanning a small set of qubits (2 and 3 in this paper)
by introducing symbolic Pauli gates (SPGs) to replace the two-qubit gates that
entangle qubits in the chosen set with a qubit outside of it. The resulting
Clifford+SPG subcircuit is optimized via dynamic programming using a library
of optimal circuits.

We numerically evaluate the proposed methods using two sets of benchmarks. The
first benchmark is based on the database of optimal Clifford circuits
constructed in [13]. We consider a selection of 1,003 randomly sampled 6-qubit
Clifford unitaries, conditional on the optimal cnot gate implementation cost
being higher than 4 (otherwise, it is easy to implement such a unitary
optimally). The set of tools developed in this work is able to recover an
optimal (in terms of the cnot count) implementation for $97.9\%$ of the
circuits, while producing circuits no more than one cnot away from the optimal
count in the worst case. Second, to evaluate the performance on “large”
circuits, we consider a toy model of Hamiltonian evolution with a graph state
Hamiltonian, defined as follows. For a given graph with $n$ nodes, the
Hamiltonian evolution performs the transformation
$(\textsc{cz}\,{\cdot}\,\textsc{h})^{t}$, where cz gates apply to graph edges,
h gates apply to graph nodes (individual qubits), and $t$ is the evolution
time. At integer times, the evolution by such a Hamiltonian is described by a
Clifford unitary. Implementing it as a circuit
$\textsc{cz}\,{\cdot}\,\textsc{h}$ repeated $t$ times turns out to be less
efficient than implementing it by using the techniques reported here. The
methods we developed are evaluated on a collection of 2,264 circuits and shown
to reduce the average cnot gate count by 64.7% compared with the methods
proposed by Aaronson and Gottesman in [9]. We make the full benchmark and the
raw results available online [16].

The rest of the paper is organized as follows. We begin by briefly revisiting
relevant concepts and defining the notations (Section 2). We next discuss
previous results that our work is based on (Subsection 2.1, Subsection 2.2).
Following this discussion, we describe the proposed methods (Section 3),
report numerical results, and evaluate the performance (Section 4). We
conclude with a short summary (Section 5).

##  2 Background

We assume basic familiarity with quantum computing concepts, stabilizer
formalism, and Clifford circuits. Below we briefly introduce relevant concepts
and notations. For detailed discussion, the reader is referred to [1] and [9].

Clifford circuits (also known as stabilizer circuits) consist of Hadamard (h),
Phase (s, also known as p gate), and controlled-NOT (cnot) gates, as well as
Pauli x, y, and z gates. We use $I$ to denote the identity gate/matrix. We
also utilize the controlled-z (cz) gate, which can be constructed as a circuit
with Hadamard and cnot gates as follows,

$\raisebox{14.22636pt}{ \lx@xy@svg{\hbox{\raise 0.0pt\hbox{\kern
0.0pt\hbox{\ignorespaces\ignorespaces\ignorespaces\hbox{\vtop{\kern
0.0pt\offinterlineskip\halign{\entry@#!@&&\entry@@#!@\cr&&&&&&&&\\\&&&&&&&&\\\&&&&&&&&\crcr}}}\ignorespaces{\hbox{\kern
0.0pt\raise 0.0pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 5.0pt\raise
0.0pt\hbox{\hbox{\kern-1.27777pt\raise-2.47217pt\hbox{$\textstyle{\bullet}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
12.44446pt\raise 0.0pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
24.33339pt\raise 0.0pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 36.22232pt\raise
0.0pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern 47.00014pt\raise
0.0pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
60.65569pt\raise
0.0pt\hbox{\hbox{\kern-1.27777pt\raise-2.47217pt\hbox{$\textstyle{\bullet}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
76.75569pt\raise 0.0pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
87.53351pt\raise 0.0pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise
0.0pt\hbox{$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
0.0pt\raise-10.49013pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
6.22223pt\raise-10.49013pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
12.44446pt\raise-10.49013pt\hbox{\hbox{\kern-3.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
17.44446pt\raise-10.49013pt\hbox{\hbox{\kern 0.0pt\raise
4.2679pt\hbox{$\textstyle{\rule{3.00003pt}{0.0pt}\raisebox{-8.53581pt}{=}\rule{3.00003pt}{0.0pt}}$}}}}}{\hbox{\kern
36.22232pt\raise-10.49013pt\hbox{\hbox{\kern-3.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
47.00014pt\raise-10.49013pt\hbox{\hbox{\kern-3.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
61.87791pt\raise-10.49013pt\hbox{\hbox{\kern-3.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
76.75569pt\raise-10.49013pt\hbox{\hbox{\kern-3.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
87.53351pt\raise-10.49013pt\hbox{\hbox{\kern-3.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
0.0pt\raise-33.85802pt\hbox{\hbox{\kern-3.0pt\raise 0.0pt\hbox{\hbox{\kern
3.0pt\raise 0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
5.0pt\raise-33.85802pt\hbox{\hbox{\kern-1.27777pt\raise-2.47217pt\hbox{$\textstyle{\bullet}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
12.44446pt\raise-33.85802pt\hbox{\hbox{\kern-3.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
24.33339pt\raise-33.85802pt\hbox{\hbox{\kern-3.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
36.22232pt\raise-33.85802pt\hbox{\hbox{\kern-3.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{}$}}}}}}}{\hbox{\kern
41.22232pt\raise-33.85802pt\hbox{\hbox{\kern
3.00003pt\raise-3.47223pt\hbox{$\textstyle{\textsc{h}}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
57.77795pt\raise-33.85802pt\hbox{\hbox{\kern 0.10002pt\raise
0.0pt\hbox{$\textstyle{\lx@xy@svgnested{\hbox{\raise 0.0pt\hbox{\kern
3.99994pt\hbox{\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx<EMAIL_ADDRESS>0.0pt\hbox{\hbox{\kern 0.0pt\raise-13.99997pt\hbox{\hbox{\vbox{\vskip
3.99994pt\hbox to7.99988pt{\hfill\lx@xy@buildcircle@\hfill}\vskip
3.99994pt}}}}}}}}}}}}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
70.97787pt\raise-33.85802pt\hbox{\hbox{\kern
3.00003pt\raise-3.47223pt\hbox{$\textstyle{\textsc{h}}$}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces{\hbox{\lx@xy@droprule}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx@xy@droprule}}{\hbox{\kern
87.53351pt\raise-33.85802pt\hbox{\hbox{\kern-3.0pt\raise
0.0pt\hbox{\hbox{\kern 3.0pt\raise
0.0pt\hbox{$\textstyle{\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$}}}}}}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces{}{\hbox{\lx@xy@droprule}}\ignorespaces{}{\hbox{\lx@xy@droprule}}{\hbox{\lx<EMAIL_ADDRESS>(1)

Clifford circuits acting on $n$ qubits generate a finite group ${\cal C}_{n}$,
known as the Clifford group. An important property of Clifford circuits is
that Clifford gates h, s, and cnot map tensor product of Pauli matrices into
tensor products of Pauli matrices. This property can be employed to “push”
Pauli gates through the Clifford gates h, s, and cnot as follows:

$\displaystyle\textsc{h}\textsc{x}=\textsc{z}\textsc{h},\quad\textsc{h}\textsc{y}=-\textsc{y}\textsc{h},\quad\textsc{h}\textsc{z}=\textsc{x}\textsc{h},\quad\textsc{s}\textsc{x}=\textsc{y}\textsc{s},$
(2)
$\displaystyle\quad\textsc{s}\textsc{y}=-\textsc{x}\textsc{s},\quad\textsc{s}\textsc{z}=\textsc{z}\textsc{s},$
(3)
$\displaystyle\textsc{cnot}_{1,2}\textsc{x}_{1}=\textsc{x}_{1}\textsc{x}_{2}\textsc{cnot}_{1,2},\;\textsc{cnot}_{1,2}\textsc{x}_{2}=\textsc{x}_{2}\textsc{cnot}_{1,2},$
(4)
$\displaystyle\textsc{cnot}_{1,2}\textsc{z}_{2}=\textsc{z}_{1}\textsc{z}_{2}\textsc{cnot}_{1,2},\;\textsc{cnot}_{1,2}\textsc{z}_{1}=\textsc{z}_{1}\textsc{cnot}_{1,2}.$
(5)

Our approach combines two building blocks: Clifford-specific extension of
template matching and symbolic peephole optimization. Below we briefly review
these techniques. While the developed methods reduce both single- and two-
qubit gate count, in this paper we focus on the optimization of the number of
two-qubit gates it takes to implement a Clifford group element. The reason for
our focus is that the leading quantum information processing technologies,
trapped ions [17] and superconducting circuits [18], both feature two-qubit
gates that take longer time and have higher error rates compared with those of
single-qubit gates.

###  2.1 Template Matching

A size $m$ template [14] is a sequence of $m$ gates that implements the
identity function:

$T=G_{0}G_{1}\ldots G_{m-1}=I.$

The templates can be used to optimize a target circuit as follows. First, a
subcircuit $G_{i}G_{i+1\pmod{m}}\ldots G_{i+p-1\pmod{m}}$ of the template is
matched with a subcircuit in the given circuit. If the gates in the target
circuit can be moved together, this sequence of gates can be replaced with the
inverse of the other $m{-}p$ gates in the template. The larger the length $p$
of the matched sequence is, the more beneficial it is to perform the
replacement, and for any $p\,{>}\,\frac{m}{2}$ the gate count is reduced. The
exact criteria for the application of the template depends on the choice of
the objective optimization criteria (e.g., depth, total gate count, 2-qubit
gate count). More formally, for parameter $p$, $\frac{m}{2}{\leq}p{\leq}m$,
the template $T$ can be applied in two directions as follows,

Forward: $\displaystyle G_{i}G_{i+1\pmod{m}}\ldots
G_{i+p-1\pmod{m}}\rightarrow
G_{i-1\pmod{m}}^{\dagger}G_{i-2\pmod{m}}^{\dagger}\ldots
G_{i+p\pmod{m}}^{\dagger},$ (6) Backward: $\displaystyle
G_{i}^{\dagger}G_{i-1\pmod{m}}^{\dagger}\ldots
G_{i-p+1\pmod{m}}^{\dagger}\rightarrow
G_{i+1\pmod{m}}^{\dagger}G_{i+2\pmod{m}}^{\dagger}\ldots
G_{i-p\pmod{m}}^{\dagger}.$

Any template $T$ of size $m$ should be independent of smaller templates; that
is, an application of a smaller template should not decrease the number of
gates in $T$ or make it equal to another template. Circuit optimization using
template matching is an iterative procedure where at each step we start at an
index gate and attempt to match a given template by considering gates left to
the index gate in the target circuit. If the matched gates can be moved
together and the substitution is beneficial, the template is applied as
defined above. This step is repeated by incrementing the position of the index
gate by one when no match is found until the last gate is reached.

Circuit optimization with templates was originally proposed in [14]. This work
has been extended with the introduction of graph-based matching techniques
[19]. While the methods in these references are applicable to Clifford
circuits since they are defined for universal quantum circuits, neither of
them leverages the particular structure Clifford circuits have for
optimization.

###  2.2 Peephole Optimization of Quantum Circuits

Peephole optimization [15] is an iterative local optimization technique that
optimizes a circuit by considering subcircuits spanning small subsets of
qubits $A$ and attempting to replace them with an optimized version drawn from
a database (or synthesized on the spot in some other versions). At each step,
for a given gate all subcircuits on a fixed small number of qubits (e.g.,
$|A|{=}4$ in [12]) including that gate are considered. For each subcircuit,
its cost and the optimal cost (retrieved from the database of precomputed
optimal circuits) of the unitary it implements are compared. If a substitution
is beneficial, the given subcircuit is replaced with its optimal
implementation. The step is repeated for all gates until a convergence
criterion is satisfied. Peephole optimization of reversible circuits was
introduced in [15] and identified to be complementary to template matching.
Since its introduction in the context of reversible computations, this
approach has been applied to Clifford circuits [12].

The performance of the standard peephole optimization is limited by the need
to store the entire database of optimal circuits in memory and to perform
$O\left({n-2\choose|A|-2}g^{3}\right)$ lookups, where $g$ is the number of
gates in the circuit [15]. Furthermore, since the size of the $n$-qubit
Clifford group (inclusive of the Pauli group) equals
${2^{2n+n^{2}}\prod\limits_{j=1}^{n}(2^{2j}{-}1)}$ and grows very quickly with
$n$, it is unlikely that all optimal circuits can be found and stored in a
suitable database for more than $6$ qubits [13].

##  3 Algorithms

$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$
(a)

$\textstyle{\bullet}$$\textstyle{\bullet}$s$\textstyle{\bullet}$$\textstyle{\bullet}$h$\textstyle{\bullet}$h$\textstyle{\textsc{s}^{\dagger}}$$\textstyle{H}$$\textstyle{\bullet}$hs
(b)

hh (c)

$\textstyle{\bullet}$h$\textstyle{\bullet}$h$\textstyle{\bullet}$$\textstyle{\times}$h$\textstyle{\bullet}$h$\textstyle{\bullet}$h$\textstyle{\bullet}$h$\textstyle{\times}$
(d)

$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$h$\textstyle{\bullet}$h$\textstyle{\bullet}$h$\textstyle{\bullet}$h$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$
(e)

shshsh (f)

ssz (g)

s$\textstyle{\bullet}$$\textstyle{\bullet}$$\textstyle{\bullet}$sh$\textstyle{\bullet}$h$\textstyle{\textsc{s}^{\dagger}}$h$\textstyle{\bullet}$h$\textstyle{\bullet}$
(h)

---
h
$\textstyle{\bullet}$h$\textstyle{\rule{3.00003pt}{0.0pt}\mapsto\rule{3.00003pt}{0.0pt}}$$\textstyle{\bullet}$$\textstyle{\bullet}$
(i)

Figure 1:  Templates LABEL:sub@fig:tm1–LABEL:sub@fig:tm8 are used for template
matching. The rewriting rule LABEL:sub@fig:tmhp is used for Hadamard gate
pushing.

We introduce two algorithms for Clifford circuit optimization and apply them
to the problem of compiling optimized Clifford circuits. The first algorithm
is a Clifford-specific extension of the template matching technique, which we
describe in Subsection 3.2. The second algorithm is symbolic peephole
optimization, detailed in Subsection 3.3.

These optimizations can be applied in at least the following two ways. First,
if the input is a Clifford unitary, we begin by synthesizing a circuit using a
“greedy” compiler (described in Subsection 3.1) and then reduce the gate count
by our proposed circuit optimization techniques. Second, if the input is
already a Clifford circuit, we can either resynthesize it or apply the circuit
optimizations directly. The gate count in the final circuit can be further
decreased at the cost of increasing the runtime by a constant factor if the
circuit is resynthesized $k$ times using a randomized version of the “greedy”
compiler, the $k$ circuits are optimized individually, and the best of the $k$
results is picked. Note that the $k$ repetitions can be done in parallel.

###  3.1 “Greedy” Compiler

Suppose $U\,{\in}\,{\cal C}_{n}$ is a Clifford unitary to be compiled and
$L\,{\in}\,{\cal C}_{n}$ is an operator that reproduces the action of $U$ on a
single pair of Pauli operators, $\textsc{x}_{j}$ and $\textsc{z}_{j}$. In
other words, $UPU^{-1}=LPL^{-1}$ for
$P\,{\in}\,\\{\textsc{x}_{j},\textsc{z}_{j}\\}$. The requisite operator $L$,
as well as a Clifford circuit with $O(n)$ cnots implementing $L$, can be
easily constructed for any given qubit $j$ by using the standard stabilizer
formalism [9]. Then the operator $L^{-1}U$ acts trivially on the $j$th qubit
and can be considered as an element of the Clifford group ${\cal C}_{n-1}$.
The greedy compiler applies this operation recursively such that each step
reduces the number of qubits by one. A qubit $j$, picked at each recursion
step, is chosen such that the operator $L$ has the minimum cnot count. In the
randomized version of the algorithm, qubit $j$ is picked randomly. The
compiler runs in time $O(n^{3})$ and outputs a circuit with the cnot count at
most $3n^{2}/4+O(n)$. We also developed and employ a bidirectional version of
the greedy compiler that follows the same strategy as above except that each
recursion step applies a transformation $U\leftarrow L^{-1}UR^{-1}$, where
$L,R\,{\in}\,{\cal C}_{n}$ are chosen such that after the transformation $U$
acts trivially on the $j$th qubit and the combined cnot count of $L$ and $R$
is minimized. In Section 4, we use the bidirectional version of the greedy
compiler as it leads to lower cnot costs of optimized circuits. We include a
detailed description of the greedy compilers in Appendix A.

###  3.2 Template Matching for Clifford Circuits

We extend template matching, described in Subsection 2.1, by introducing a
three-stage approach that takes advantage of the observation that Clifford
gates map tensor products of Pauli matrices into tensor products of Pauli
matrices. Below we describe the features used in the proposed three-stage
approach. In Subsection 3.4, we combine this approach with symbolic peephole
optimization.

First, we partition the circuit into three stages, “compute,” “swap,” and
“Pauli”, by pushing swap and Pauli gates to the end of the circuit. Paulis are
“pushed” according to the rules in Eqs. (2, 3, 4, 5). This step results in the
construction of the “compute” stage consisting of h, s, cnot, and cz gates
only.

Second, we apply the template matching to the “compute” stage. We further
simplify template matching by converting all two-qubit gates into cz gates (at
the cost of introducing two Hadamard gates when the cnot is considered) before
performing template optimization. Templates are applied as described in
Subsection 2.1. The list of templates is given in Fig. 1a-1h.

We reduce the single-qubit gate count and increase the opportunities for
template application by introducing Hadamard and Phase gate pushing.
Specifically, assuming that a circuit was optimized with templates, the idea
is then to “push” Hadamard and Phase gates to one side of the two-qubit gates
as far as possible. “Pushing” a gate through a two-qubit gate is implemented
as the application of a template where a fixed subsequence must be matched.
For example, the rule in Fig. 1i can be used to push a Hadamard to the right
of the cnot gate.

Note that once the circuit is optimized in terms of the two-qubit gate count,
template matching can be applied to reduce the single-qubit gate count by
restricting the set of templates and how they are applied. This can be
accomplished by applying templates spanning a single qubit and considering
certain applications of templates with an even number of two-qubit gates.

Third, we consider swap gate optimization as a separate problem. swap
optimization is performed by observing that a swap gate can be implemented at
the effective cost of one two-qubit gate if it is aligned with a two-qubit
gate (cnot or cz) as, for example, in the following.

---
$\textstyle{\bullet}$$\textstyle{\times}$$\textstyle{\bullet}$
$\textstyle{\rule{3.00003pt}{0.0pt}=\rule{3.00003pt}{0.0pt}}$
$\textstyle{\times}$ $\textstyle{\bullet}$

In order to reduce the number of swaps, the swap stage is resynthesized with
the goal of aligning as many swaps as possible with the two-qubit gates in the
“compute” stage.

###  3.3 Symbolic Peephole Optimization

As outlined in Subsection 2.2, various methods were proposed to create a
database of optimal few-qubit Clifford circuits; some employ such databases to
perform peephole optimization of larger Clifford circuits. However, these
methods are limited to few-qubit subcircuits that must be completely decoupled
from the remaining qubits. To address this limitation, we introduce a modified
approach to Clifford circuit optimization, _symbolic_ peephole optimization.

Figure 2: Example of symbolic peephole optimization. Purple arrow: each
entangling cnot gate is replaced with a symbolic Pauli gate (SPG)
$\textsc{x}^{v}$, where $v\in\\{0,1\\}$. Now the subcircuit acting on $A$ is
isolated from the remaining qubits. Green arrow: The subcircuit acting on $A$
is optimized to reduce the number of SPGs. Here we used the commutation rules
$\textsc{h}\textsc{x}^{v}\,{=}\,\textsc{z}^{v}\textsc{h}$,
$\textsc{x}^{v}\textsc{z}^{v}\,{=}\,(-i\textsc{y})^{v}$, and
$\textsc{s}\textsc{y}^{v}\,{=}\,-\textsc{x}^{v}\textsc{s}$. Yellow arrow: The
subcircuits acting on $A$ and $B$ are merged by replacing the SPG
$\textsc{x}^{v}$ with the cnot. The phase factor $i^{v}$ is replaced with the
phase gate s acting on $B$.

Consider a circuit $U\,{\in}\,\mathcal{C}_{n}$ and a small subset of qubits
$A\,{\subseteq}\,[n]$. Our goal is to meaningfully define and optimize the
restriction of $U$ onto $A$. Let $B\,{=}\,[n]{\setminus}A$ be the complement
of $A$. We say that a cnot gate is _entangling_ if it couples $A$ and $B$.
Assume without loss of generality that each entangling cnot has its target
qubit in the set $A$ (otherwise, switch the control and the target by adding
extra Hadamards). Partition entangling cnots into groups such that all cnots
in the same group have the same control bit. Let $k$ be the number of groups.
Expanding each entangling cnot as
${\left|{0}\right\rangle}{\left\langle{0}\right|}\otimes
I+{\left|{1}\right\rangle}{\left\langle{1}\right|}\otimes X$, one can write

$U=\sum_{v\in\\{0,1\\}^{k}}U_{A}(v)\otimes U_{B}(v),$

where $U_{A}(v)$ is a Clifford circuit obtained from $U$ by retaining all
gates acting on $A$ and replacing each entangling cnot from the $i$th group
with the Pauli gate $X^{v_{i}}$ acting on the target qubit of the respective
cnot. Likewise, $U_{B}(v)$ is a (nonunitary) circuit obtained from $U$ by
retaining all gates acting on $B$ and replacing each entangling cnot from the
$i$th group with the projector
${\left|{v_{i}}\right\rangle}{\left\langle{v_{i}}\right|}$ acting on the
control qubit of the respective cnot. We refer to the single-qubit gates
$\textsc{x}^{v_{i}}$, $\textsc{y}^{v_{i}}$, and $\textsc{z}^{v_{i}}$ as
_Symbolic Pauli Gates (SPGs)_. These are similar to controlled Pauli gates
except that the control qubit is replaced by a symbolic variable
$v_{i}\,{\in}\,\\{0,1\\}$.

A symbolic Clifford circuit $U_{A}(v)$ can be optimized as a regular Clifford
circuit on $|A|$ qubits with the following caveats. First, $U_{A}(v)$ must be
expressed by using the Clifford+SPG gate set. The cost of $U_{A}(v)$ should be
defined as the number of CNOTs plus the number of SPGs. Second, the
optimization must respect the temporal order of SPGs. In other words, if
$i{<}j$, then all SPGs controlled by $v_{i}$ must be applied before SPGs
controlled by $v_{j}$. Third, the optimization must preserve the overall phase
of $U_{A}(v)$ modulo phase factors $(-1)^{v_{j}}$ or $i^{v_{j}}$. The phase
factors can be generated by single-qubit gates z or s applied to control
qubits of the entangling cnots. These conditions guarantee that the optimized
circuit $U_{A}(v)$ can be lifted to a full circuit
$U^{\prime}\,{\in}\,\mathcal{C}_{n}$ that is functionally equivalent to $U$. A
toy optimization example is shown in Fig. 2.

We now describe the optimization of $U_{A}(v)$ in more detail. Let ${\cal
P}_{A}$ and ${\cal C}_{A}$ be the groups of Pauli and Clifford operators
acting on $A$, respectively. The circuit $U_{A}(v)$ can be compactly specified
by a $k$-tuple of Pauli operators $P_{1},P_{2},\ldots,P_{k}\in{\cal P}_{A}$
and a Clifford operator $R\,{\in}\,{\cal C}_{A}$ such that
$U_{A}(v)=P_{k}^{v_{k}}\cdots P_{2}^{v_{2}}P_{1}^{v_{1}}R$ for all
$v\in\\{0,1\\}^{k}$. Indeed, any SPG can be commuted to the left since
Clifford gates map Pauli operators to Pauli operators. The most general
Clifford+SPG circuit that implements $U_{A}(v)$ can be parameterized as

$U_{A}(v)=(U_{k}^{-1}Q_{k}^{v_{k}}U_{k})\cdots(U_{2}^{-1}Q_{2}^{v_{2}}U_{2})(U_{1}^{-1}Q_{1}^{v_{1}}U_{1})R$
(7)

for some Clifford operators $U_{j}\,{\in}\,{\cal C}_{A}$ and Pauli operators
$Q_{j}=U_{j}P_{j}U_{j}^{-1}\in{\cal P}_{A}$. The cost of the circuit in Eq. 7
includes the cnot count of subcircuits $U_{j}U_{j-1}^{-1}$ and the SPG count
of controlled Pauli operators $Q_{j}^{v_{j}}$. Note that $Q_{j}^{v_{j}}$ is a
product of $|Q_{j}|$ single-qubit SPGs, where $|Q_{j}|$ is the Hamming weight
of $Q_{j}$. Denoting $U_{0}{:=}R^{-1}$, one can express the cost of the
circuit in Eq. (7) as

$f=\$(U_{k})+\sum_{i=1}^{k}\$(U_{i}U_{i-1}^{-1})+\sum_{i=1}^{k}|U_{i}P_{i}U_{i}^{-1}|.$
(8)

Here $\$(V)$ is the cnot cost of a Clifford operator $V\,{\in}\,{\cal C}_{A}$.
Our goal is to minimize the cost function $f$ over all $k$-tuples
$U_{1},U_{2},\ldots,U_{k}\in{\cal C}_{A}$. We claim that the global minimum of
$f$ can be computed in time $O(k)$, as long as $|A|\,{=}\,O(1)$. The key
observation is that the function $f$ is a sum of terms that depend on at most
two consecutive variables $U_{i}$ and $U_{i-1}$. Such functions can be
minimized efficiently using the dynamic programming method; see, for example,
[20]. Indeed, define intermediate cost functions
$f_{1},f_{2},\ldots,f_{k}:{\cal C}_{A}\to\mathbb{Z}_{+}$ such that $f_{j}$ is
obtained from $f$ by removing the term $\$(U_{k})$, retaining the first $j$
terms in the sums over $i$, and taking the minimum over
$U_{1},U_{2},\ldots,U_{j-1}$. More formally,

$f_{1}(U_{1})=\$(U_{1}R)+|U_{1}P_{1}U_{1}^{-1}|$ (9)

and

$f_{j}(U_{j})=\min_{U_{1},U_{2},\ldots,U_{j-1}\in{\cal
C}_{A}}\;\;\sum_{i=1}^{j}\$(U_{i}U_{i-1}^{-1})+\sum_{i=1}^{j}|U_{i}P_{i}U_{i}^{-1}|$

for $j=2,3,\ldots,k$. Using the induction in $j$, one can easily check that

$f_{j}(U_{j})=|U_{j}P_{j}U_{j}^{-1}|+\min_{U_{j-1}\in{\cal
C}_{A}}\;f_{j-1}(U_{j-1})+\$(U_{j}U_{j-1}^{-1})$ (10)

for $j=2,3,\ldots,k$. Below we assume that a lookup table specifying the cnot
cost $\$(V)$ for all $V\,{\in}\,{\cal C}_{A}$ is available. Then one can
compute a lookup table of $f_{1}$ by iterating over all $U_{1}\,{\in}\,{\cal
C}_{A}$ and evaluating the right-hand side of Eq. (9). Proceeding inductively,
one can compute a lookup table of $f_{j}$ with $j=2,3,\ldots,k$ by iterating
over all $U_{j}\,{\in}\,{\cal C}_{A}$ and evaluating the right-hand side of
Eq. (10). Each step takes time roughly $|{\cal C}_{A}|^{2}\,{=}\,O(1)$ since
we assumed that $|A|\,{=}\,O(1)$. Finally, use the identity

$\min_{U_{1},U_{2},\ldots,U_{k}\in{\cal
C}_{A}}f(U_{1},U_{2},\ldots,U_{k})=\min_{U_{k}\in{\cal
C}_{A}}\$(U_{k})+f_{k}(U_{k})$ (11)

to compute the global minimum of $f$. Thus, the full computation takes time
$O(k)$.

To make the above algorithm more practical, we exploited symmetries of the
cost function, Eq. (8). Namely, function $f$ is invariant under multiplying
$U_{j}$ on the left by any element of the local subgroup ${\cal
C}_{A}^{0}\,{\subseteq}\,{\cal C}_{A}$ generated by the single-qubit gates
$\textsc{h}_{a}$ and $\textsc{s}_{a}$ with $a\,{\in}\,A$. In other words,
$f(U_{1},U_{2},\ldots,U_{k})$ depends only on the right cosets of the local
subgroup ${\cal C}_{A}^{0}U_{j}$. Thus one can restrict the minimizations in
Eqs. (10,11) to some fixed set of coset representatives ${\cal
R}\,{\subset}\,{\cal C}_{A}$ such that each coset ${\cal C}_{A}^{0}V$ has a
unique representative $r(V){\,\in}\,{\cal R}$. We chose $r(V)$ as the left-
reduced form of $V$ defined in [13, Lemma 2]. This lemma provides an algorithm
for computing $r(V)$ with the runtime $O(|A|^{2})$. Now each variable $U_{i}$
takes only $|{\cal R}|\,{=}\,|{\cal C}_{A}|/|{\cal C}_{A}^{0}|\,{=}\,|{\cal
C}_{A}|/24^{|A|}$ values. For example, $|{\cal R}|{=}20$ and $|{\cal
R}|{=}6720$ for $|A|{=}2$ and $|A|{=}3$, respectively. Likewise, it suffices
to compute the lookup table for the cnot cost $\$(V)$ only for
$V\,{\in}\,{\cal R}$. This computation was performed using the breadth-first
search on the Clifford group ${\cal C}_{A}$.

An important open question concerns the selection of the subsets $A$ to be
considered. From numerical experiments with $|A|\,{\in}\,\\{2,3\\}$, our most
successful strategy turned out to be the random subset selection.
Specifically, we generate a list of all ${n\choose 2}$ pairs and ${n\choose
3}$ triples of qubits. We run passes of the symbolic peephole method first on
pairs of qubits and next on triples of qubits until no further improvement can
be obtained. At each pass of the symbolic peephole optimization, we randomly
reshuffle both lists and run optimization on all the subsets in the reshuffled
order. We continue passes until either the optimal cnot count is reached (for
circuits for which the optimal cnot count is known) or there is no improvement
between two consecutive passes.

###  3.4 Full Algorithm

We combine the components described above in the following way. We begin by
synthesizing the circuit using the “greedy” compiler described in Subsection
3.1. Then the synthesized circuit is optimized as follows. First, the circuit
is partitioned into three stages. Second, template matching and swap gate
merging is performed until a pass yields no further optimization. Third,
symbolic peephole optimization is performed, as described in Subsection 3.3.
Lastly, a single pass of template matching is performed to reduce the single-
qubit gate count.

##  4 Experimental Results

We ran two sets of computational experiments designed to test the performance
of our synthesis and optimization algorithms, detailed in the next two
subsections. In addition, we compared the two-qubit gate count in 8-qubit t
gate free circuits from [21] to the implementations obtained by our software.
The comparison reads $24.4529$ (obtained using $10{,}000$ random samples) to
$50{+}$ in [21, Figure 3].

###  4.1 Recovering Optimal CNOT Count for Clifford Unitaries on Six Qubits

First we compare the proposed heuristic methods with the optimal Clifford
compiler for $n\,{\leq}\,6$ qubits [13]. The latter uses breadth-first search
on the Clifford group to construct a database specifying the optimal cnot gate
count of each Clifford operator. As shown in [13], the optimal cnot gate count
for $6$-qubit Clifford operators takes values $0,1,\ldots,15$. We generate
1,003 uniformly sampled random Clifford unitaries with the cnot gate counts
between 5 and 15. We consider only unitaries with the cnot gate count
${\geq}5$ because one needs at least 5 cnots to entangle all 6 qubits. For the
cnot gate counts from 5 to 14, we consider 100 circuits for each cost value.
For the cnot gate count of $15$, there are only 3 Clifford circuits (modulo
single-qubit Cliffords on the left and on the right and modulo qubit
permutations) to consider [13].

For each Clifford unitary, we start by synthesizing it using the bidirectional
“greedy” compiler. The optimization is run as described in Subsection 3.4. The
circuit is then resynthesized by using the randomized version of the compiler,
and the resynthesized circuit is optimized. This process is repeated until the
time limit is reached, and the circuit with the lowest cnot count is chosen as
the output. Note that we also stop the peephole optimization when the time
limit is reached, but we allow template matching to complete. The reason is
that template matching is fast as compared to peephole optimization and
allowing it to complete results in the actual running time above the time
limit by only $0.66\%$ of the instances considered.

The quality of the solution obtained by the implemented methods as a function
of the time limit is shown in Fig. 3. Our algorithm converges before
exhausting the time limit on most instances. Fig. 3 shows actual observed mean
running time as a function of the time limit. We note that the combination of
the iterative nature of symbolic peephole optimization and the randomized
resynthesis allows the user to trade off the quality of the optimization and
the running time as desired.

(a) The ratio of circuits for which the implemented methods recover optimal cnot count. The “nonsmoothness” of the line for the cnot count of 15 is due to only 3 circuits being considered. |
---|---
(b) Mean running time of the implemented methods. Note that the actual running times are significantly lower than the time limit (black line) for most instances. |
Figure 3: Quality of the solution (a) and the mean running time (b) for 6-qubit circuits with known optimal cnot gate count. To demonstrate the trade-off between running time and the quality of the solution, we consider 20 time limits between 100 seconds and 15 hours. We observe that for all problems there exists a time limit at which the ratio of the recovered optimal circuits and the mean running time stops increasing. This value depends on the hardness of the circuits; for the hardest circuits (optimal gate count of 12) the metrics are saturated at ${\approx}4$ hours. With this time limit we recover the optimal cnot count for 97.9% of the circuits and observe the difference of 0.2% between the average optimal cnot count and the average cnot count recovered by our software. Small deviations from monotonic growth of running time and quality with the time limit are due to the experiments being performed on a heterogeneous computing cluster and the random nature of the algorithm implementation. The mean running time being above the time limit for time limit $100$s is due to letting template matching complete even after the time limit is triggered. Type | $n_{q}$ | $t_{\max}$ | $C_{\text{orig}}$ | $C_{\text{A-G}}$ | $C_{\text{greedy}}$ | $C_{\text{opt}}$ |  $r$ (%)
---|---|---|---|---|---|---|---
Path graph | 5 | 12 | 26.00 | 12.00 | 11.50 | 7.58 | 36.81
Path graph | 15 | 32 | 231.00 | 69.72 | 73.06 | 37.22 | 46.62
Path graph | 25 | 52 | 636.00 | 159.27 | 146.15 | 72.73 | 54.33
Path graph | 35 | 72 | 1241.00 | 270.79 | 224.67 | 109.78 | 59.46
Path graph | 45 | 92 | 2046.00 | 421.72 | 305.65 | 148.40 | 64.81
Path graph | 55 | 112 | 3051.00 | 589.71 | 384.27 | 188.29 | 68.07
Cycle graph | 5 | 10 | 27.50 | 19.60 | 12.90 | 7.80 | 60.20
Cycle graph | 15 | 30 | 232.50 | 163.17 | 76.00 | 45.90 | 71.87
Cycle graph | 25 | 50 | 637.50 | 424.60 | 155.56 | 88.12 | 79.25
Cycle graph | 35 | 70 | 1242.50 | 796.24 | 236.14 | 133.07 | 83.29
Cycle graph | 45 | 90 | 2047.50 | 1279.60 | 321.24 | 179.00 | 86.01
Cycle graph | 55 | 110 | 3052.50 | 1872.48 | 407.36 | 227.57 | 87.85
Square lattice | 4 | 4 | 10.00 | 6.00 | 5.00 | 3.50 | 41.67
Square lattice | 9 | 8 | 54.00 | 35.25 | 33.12 | 16.50 | 53.19
Square lattice | 16 | 12 | 156.00 | 95.42 | 93.17 | 40.08 | 57.99
Square lattice | 25 | 24 | 500.00 | 254.12 | 206.50 | 97.38 | 61.68
Square lattice | 36 | 36 | 1110.00 | 621.36 | 409.89 | 239.50 | 61.46
Square lattice | 49 | 16 | 714.00 | 858.44 | 553.12 | 320.19 | 62.70
Square lattice | 64 | 252 | 14168.00 | 2189.41 | 1237.07 | 887.38 | 59.47
Triangular lattice | 3 | 6 | 10.50 | 2.83 | 3.33 | 2.83 | 0.00
Triangular lattice | 6 | 10 | 49.50 | 22.60 | 18.60 | 9.70 | 57.08
Triangular lattice | 10 | 36 | 333.00 | 72.58 | 60.36 | 29.78 | 58.97
Triangular lattice | 15 | 90 | 1365.00 | 187.18 | 128.17 | 65.44 | 65.04
Triangular lattice | 21 | 24 | 562.50 | 303.08 | 211.67 | 117.33 | 61.29
Triangular lattice | 28 | 300 | 9481.50 | 726.63 | 418.46 | 272.20 | 62.54
Triangular lattice | 36 | 60 | 2562.00 | 928.92 | 556.60 | 356.87 | 61.58
Triangular lattice | 45 | 300 | 16254.00 | 1909.62 | 1023.72 | 801.87 | 58.01
Triangular lattice | 55 | 72 | 4927.50 | 2195.36 | 1229.04 | 968.68 | 55.88
Hexagonal lattice | 6 | 6 | 21.00 | 15.33 | 14.00 | 8.00 | 47.83
Hexagonal lattice | 24 | 24 | 375.00 | 285.88 | 197.25 | 101.83 | 64.38
Hexagonal lattice | 54 | 120 | 4356.00 | 1711.33 | 874.77 | 585.89 | 65.76
Heavy hexagon lattice | 12 | 12 | 78.00 | 79.50 | 58.92 | 28.42 | 64.26
Heavy hexagon lattice | 54 | 120 | 3630.00 | 1747.48 | 899.80 | 609.90 | 65.10
Table 1: Optimization results for Hamiltonian evolution circuits. For each
graph on $n_{q}$ qubits, we generate and optimize $t_{\max}$ circuits
corresponding to all integer numbers of steps between $1$ and
$t_{\max}=\min(t_{p},300)$. $C_{\text{orig}}$ is the average cnot gate count
in the original circuits, $C_{\text{A-G}}$ is the average cnot gate count of
the circuits in Aaronson–Gottesman canonical form [9], $C_{\text{greedy}}$ is
the average cnot gate count of the circuits produced by the bidirectional
“greedy” compiler, $C_{\text{opt}}$ is the average cnot gate count of the
optimized circuits, and
$r\,{=}\,(C_{\text{A-G}}{-}C_{\text{opt}})/C_{\text{A-G}}$ is the improvement
in the average cnot gate count over the Aaronson–Gottesman canonical form. We
note that the “greedy” compiler by itself (without any further optimization)
reduces the cnot gate count by $48.6\%$ compared to [9].

###  4.2 Circuits for Hamiltonian Evolution

To evaluate the performance of the proposed methods on circuits with $n{>}6$
qubits, we consider a toy model of Hamiltonian time evolution. Suppose
$G\,{=}\,(V,E)$ is a fixed graph with $n$ vertices. We place a qubit at each
vertex of $G$. Define a Hamiltonian evolution circuit with time $t$ as

$\left(\prod_{(i,j)\in
E}\textsc{cz}_{i,j}\prod_{j=1}^{n}\textsc{h}_{j}\right)^{t}.$

The layers of Hadamard and cz gates model time evolution under an external
magnetic field and nearest neighbor two-qubit interactions, respectively. We
consider several choices for the interaction graph. First, we take instances
of the path and cycle graphs with the number of qubits
$n\in\\{5,15,25,35,45,55\\}$. Second, we include all three regular plane
tessellations (by triangles, squares, and hexagons). We choose the numbers of
vertices between $6$ and $64$ such that the convex hull spanned by the centers
of masses of individual tiles in the gapless regular tiling is congruent to
the basic tile. Third, we consider a heavy hexagon grid, obtained from
hexagonal tessellation by adding a node in the middle of each edge. This set
includes some of the frequently appearing qubit-to-qubit
connectivities/architectures. We consider the number of layers
$1\,{\leq}\,t\,{\leq}\,t_{\max}=\min(t_{p},300)$, where $t_{p}$ is the period
such that the Hamiltonian evolution with the number of layers $t_{p}$ produces
the identity transformation. For each interaction graph $G$ we compute the
cnot gate count of optimized circuits averaged over the number of layers
$t\,{=}\,1,2,\ldots,t_{\max}$. The total number of circuits considered is
2,264. We set the time limit to 36 hours and stop both peephole optimization
and template matching when the time limit is reached, only allowing the
current pass of template matching to complete. Allowing the current pass of
template matching to complete results in only a small ratio of problems
($4.5\%$) to significantly (${\geq}10\%$) exceed the time limit. The results
are reported in Table 1. The maximum graph size in these experiments is
$n{=}64$ because we represent $n$-qubit Pauli operators by a pair of $64$-bit
integers in our C++ implementation; this limitation can be easily removed by
revising the data structure.

##  5 Conclusion

We reported a bidirectional synthesis approach and two circuit optimization
techniques that extend known approaches to Clifford circuits by exploiting the
unique properties of the Clifford group. We demonstrate the effectiveness of
these methods by recovering optimal cnot gate count for $98.9\%$ 6-qubit
circuits (over 1,003 samples) and by reducing the cnot gate count by 64.7% on
average for Hamiltonian evolution circuits with up to 64 qubits (2,264
circuits considered), compared to Aaronson–Gottesman canonical form [9]. We
show evidence of the improvement in the gate count by a factor of 2 compared
to other techniques, such as [21].

## Appendix A

In this section, we describe greedy synthesizers that we developed to obtain
initial circuits implementing the Clifford unitaries considered. There are two
versions of the synthesizer: unidirectional and bidirectional.

Let us start with the unidirectional version. Suppose $C$ is an $n$-qubit
Clifford operator. The greedy compiler sequentially constructs Clifford
circuits $L_{1},L_{2},\ldots,L_{n}$ such that $C=L_{1}L_{2}\cdots L_{j}C_{j}$,
where $C_{j}$ acts trivially on the first $j$ qubits. The circuit $L_{j}$ has
the cnot cost $\$(L_{j})\leq 3(n{-}j)/2+O(1)$. By assumption, $C_{n}$ acts
trivially on all $n$ qubits, that is, $C_{n}$ is proportional to the identity.
In other words, $C=\omega L_{1}L_{2}\cdots L_{n}$ for some irrelevant phase
factor $\omega$. This gives a circuit implementing $C$ with the cnot cost

$\sum_{j=1}^{n}\$(L_{j})\leq\sum_{j=1}^{n}\left(3(n-j)/2+O(1)\right)=3n^{2}/4+O(n).$

The desired circuits $L_{j}$ are constructed using the following lemma.

######  Lemma 1.

There exists an algorithm that takes as input anti-commuting $n$-qubit Pauli
operators $O$ and $O^{\prime}$ and outputs a Clifford circuit $L\,{\in}\,{\cal
C}_{n}$ such that

$L^{-1}OL=\textsc{x}_{1}\quad\mbox{and}\quad
L^{-1}O^{\prime}L=\textsc{z}_{1}.$ (12)

The circuit $L$ has the cnot cost $\$(O,O^{\prime}):=\$(L)\leq 3n/2+O(1)$. The
algorithm has runtime $O(n)$.

We refer to a Clifford operator $L$ satisfying Eq. (12) as a disentangler for
the pair $(O,O^{\prime})$.

To implement a Clifford operator $C$ as a circuit, apply the lemma to Pauli
operators $O\,{=}\,C\textsc{x}_{1}C^{-1}$ and
$O^{\prime}\,{=}\,C\textsc{z}_{1}C^{-1}$. Let $L$ be the corresponding
disentangler and $C_{1}\,{=}\,L^{-1}C$. From Eq. (12) we obtain
$C_{1}\textsc{x}_{1}\,{=}\,\textsc{x}_{1}C_{1}$ and
$C_{1}\textsc{z}_{1}\,{=}\,\textsc{z}_{1}C_{1}$. This means that $C_{1}$
commutes with all Pauli operators on the first qubit, which is possible only
if $C_{1}$ acts trivially on the first qubit. We can now apply the lemma to
$C_{1}$. Ignoring the trivial action of $C_{1}$ on the first qubit, one can
regard $C_{1}$ as an element of the smaller Clifford group ${\cal C}_{n-1}$,
thereby reducing the number of qubits that need to be considered by one. After
$n$ applications of the lemma we obtain the desired disentanglers
$L_{1},L_{2},\ldots,L_{n}$.

###### Proof of Lemma 1.

Let us say that Pauli operators $O$ and $O^{\prime}$ are in the standard form
if their action on any qubit $j$ falls into one of the five cases shown below.

Case | $A$ | $B$ | $C$ | $D$ | $E$
---|---|---|---|---|---
$O_{j}$ | x | x | x | i | i
$O_{j}^{\prime}$ | z | x | i | z | i

Recall that the single-qubit Clifford group ${\cal C}_{1}$ acts by
permutations on the Pauli operators $\textsc{x},\textsc{y},$ and z. Thus one
can transform any Pauli pair $(O,O^{\prime})$ into the standard form by
applying a layer of single-qubit Clifford operators. This gives rise to a
partition of $n$ qubits into five disjoint subsets $A,B,C,D,$ and $E$. Note
that $A$ has odd size since otherwise $O$ and $O^{\prime}$ would commute. Let
$A(j)$ be the $j$-th qubit of $A$. Consider the following circuit.

Algorithm 1 Disentangling circuit

1:if $1\notin A$ then

2: $\textsc{swap}_{1,A(1)}$

3:end if$\triangleright$ Now $O_{1}=\textsc{x}$ and
$O_{1}^{\prime}=\textsc{z}$

4:for $j\in C$ do $\triangleright$ Clean $O$ from $C$

5: $\textsc{cnot}_{1,j}$

6:end for

7:for $j\in D$ do $\triangleright$ Clean $O^{\prime}$ from $D$

8: $\textsc{cnot}_{j,1}$

9:end for

10:$i\leftarrow$ first qubit of $B$

11:for $j\in B\setminus\\{i\\}$ do $\triangleright$ Clean $(O,O^{\prime})$
from $B{\setminus}\\{i\\}$

12: $\textsc{cnot}_{i,j}$

13:end for

14:$\textsc{cnot}_{i,1}\textsc{h}_{i}\textsc{cnot}_{1,i}$ $\triangleright$
Clean $(O,O^{\prime})$ from $i$

15:$k\leftarrow(|A|-1)/2$ $\triangleright$ Due to anticommutativity, $|A|$ is
odd; group all but qubit 1 in pairs

16:for $j=1$ to $k$ do$\triangleright$ Clean $(O,O^{\prime})$ from
$A{\setminus}\\{1\\}$

17: $\textsc{cnot}_{A(2j+1),A(2j)}$

18: $\textsc{cnot}_{A(2j),A(1)}$

19: $\textsc{cnot}_{A(1),A(2j+1)}$$\triangleright$ Perform simultaneous
mapping $\textsc{x}\textsc{x}\textsc{x}\mapsto\textsc{x}\textsc{i}\textsc{i}$
and $\textsc{z}\textsc{z}\textsc{z}\mapsto\textsc{z}\textsc{i}\textsc{i}$

20:end for

Let $L$ be the operator realized by the above circuit combined with the
initial layer of single-qubit Cliffords. Direct inspection shows that $L$ has
the desired property, Eq. (12), up to sign factors. The latter can be fixed by
applying Pauli $\textsc{x}_{1}$ or $\textsc{y}_{1}$ or $\textsc{z}_{1}$ as the
first gate of $L$. Simple algebra shows that $L$ has the cnot gate count of at
most $(3/2)|A|+|B|+|C|+|D|+O(1)\leq 3n/2+O(1)$. ∎

Below we use the notation $\$(O,O^{\prime})$ for the cnot gate count of the
disentangling circuit constructed in Algorithm 1.

Our implementation of the greedy compiler optimizes the order in which the
qubits are disentangled. Namely, suppose that at some step $j$ of the compiler
a subset of qubits $S_{j}$ has been disentangled such that $|S_{j}|\,{=}\,j$
and $C=L_{1}L_{2}\cdots L_{j}C_{j}$, where $C_{j}$ acts trivially on $S_{j}$.
Let

$p=\arg\min_{p\notin
S_{j}}\$(C_{j}\textsc{x}_{p}C_{j}^{-1},C_{j}\textsc{z}_{p}C_{j}^{-1})$

be a qubit with the smallest disentangling cost. Let $L$ be the circuit
disentangling $C_{j}\textsc{x}_{p}C_{j}^{-1}$ and
$C_{j}\textsc{z}_{p}C_{j}^{-1}$. Set $S_{j+1}=S\cup\\{p\\}$ and
$L_{j+1}=L\cdot\mathsf{SWAP}_{1,p}$. Then $C=L_{1}L_{2}\cdots L_{j+1}C_{j+1}$,
where $C_{j+1}$ acts trivially on $S_{j+1}$. Thus one can proceed inductively.
The extra swap gates are isolated and incorporated back into the compiled
circuit as described in Subsection 3.2.

The greedy synthesizer described above has the runtime $O(n^{3})$. Indeed,
consider the first step of the synthesis. Since the disentangling cost
$\$(O,O^{\prime})$ can be computed in time $O(n)$, picking a qubit with the
smallest disentangling cost takes time $O(n^{2})$. Computing the disentangling
circuit $L$ and the product $L^{-1}C$ takes time $O(n^{2})$ since $L$ contains
$O(n)$ gates and the action of a single gate can be simulated in time $O(n)$
using the stabilizer formalism [9]. Thus the full runtime of the greedy
synthesizer is $O(n^{3})$.

The bidirectional greedy synthesizer sequentially constructs Clifford circuits
$L_{1},L_{2},\ldots,L_{n}$ and $R_{1},R_{2},\ldots,R_{n}$ such that

$C=(L_{1}L_{2}\cdots L_{j})C_{j}(R_{j}\cdots R_{2}R_{1}),$

where $C_{j}$ acts trivially on the first $j$ qubits. This gives a circuit
implementing $C$ with the cnot cost at most

$\sum_{j=1}^{n}\$(L_{j})+\$(R_{j}).$

Consider the first step, $j{=}1$. Let us construct the circuits
$L\,{=}\,L_{1}$ and $R\,{=}\,R_{1}$ (all subsequent steps are analogous). Our
goal is to minimize the combined cost $\$(L)+\$(R)$ subject to the constraint
that $C_{1}=L^{-1}CR^{-1}$ acts trivially on the first qubit. Equivalently,
$C_{1}$ should commute with the Pauli operators $\textsc{x}_{1}$ and
$\textsc{z}_{1}$. Define $n$-qubit Pauli operators

$P:=R^{-1}\textsc{x}_{1}R,\;P^{\prime}:=R^{-1}\textsc{z}_{1}R,\;O:=CPC^{-1},\text{
and }O^{\prime}:=CP^{\prime}C^{-1}.$

By definition, $R^{-1}$ is a disentangler for the pair $(P,P^{\prime})$.
Simple algebra shows that $C_{1}$ commutes with the Pauli operators
$\textsc{x}_{1}$ and $\textsc{z}_{1}$ if and only if $L$ is a disentangler for
the pair $(O,O^{\prime})$. The above shows that minimizing the combined cost
$\$(L)+\$(R)$ subject to the constraint that $C_{1}=L^{-1}CR^{-1}$ acts
trivially on the first qubit is equivalent to minimizing the function

$f(P,P^{\prime})=\$(P,P^{\prime})+\$(CPC^{-1},CP^{\prime}C^{-1})$

over all pairs of $n$-qubit anti-commuting Pauli operators $P$ and
$P^{\prime}$. Note that $f(P,P^{\prime})$ can be computed in time $O(n)$ for a
given pair $(P,P^{\prime})$. Once the optimal pair $(P,P^{\prime})$ is found,
one chooses $L$ and $R^{-1}$ as disentanglers for the Pauli pairs
$(O,O^{\prime})$ and $(P,P^{\prime})$, respectively. Since the total number of
$n$-qubit anti-commuting Pauli pairs grows exponentially with $n$, the global
minimum of $f(P,P^{\prime})$ cannot be computed exactly for large $n$. To make
the problem tractable, we restricted the minimization to Pauli operators
$P,P^{\prime}$ with weight at most two. The number of such pairs
$(P,P^{\prime})$ is at most $O(n^{3})$ since the anti-commutativity condition
implies that the supports of $P$ and $P^{\prime}$ must overlap on at least one
qubit. Now the minimum of $f(P,P^{\prime})$ can be computed in time
$O(n^{4})$, and thus the full runtime of the compiler is $O(n^{5})$. Note that
the unidirectional greedy compiler described earlier corresponds to $R{=}I$,
that is, $P\,{=}\,\textsc{x}_{1}$ and $P^{\prime}\,{=}\,\textsc{z}_{1}$. Thus
the bidirectional compiler subsumes the unidirectional one, even with the
restricted minimization domain.

## Disclaimer

This paper was prepared for information purposes with contributions from the
Future Lab for Applied Research and Engineering (FLARE) Group of JPMorgan
Chase & Co. and its affiliates, and is not a product of the Research
Department of JPMorgan Chase & Co. JPMorgan Chase & Co. makes no explicit or
implied representation and warranty, and accepts no liability, for the
completeness, accuracy or reliability of information, or the legal,
compliance, tax or accounting effects of matters contained herein. This
document is not intended as investment research or investment advice, or a
recommendation, offer or solicitation for the purchase or sale of any
security, financial instrument, financial product or service, or to be used in
any way for evaluating the merits of participating in any transaction.

## Acknowledgments

This work was supported in part by the U.S. Department of Energy (DOE), Office
of Science, Office of Advanced Scientific Computing Research AIDE-QC and FAR-
QC projects and by the Argonne LDRD program under contract number DE-
AC02-06CH11357. Clemson University is acknowledged for generous allotment of
compute time on the Palmetto cluster. SB is partially supported by the IBM
Research Frontiers Institute.

## References

  * [1] M. A. Nielsen and I. L. Chuang, _Quantum Computation and Quantum Information_ , Cambridge University Press, 2002.
  * [2] S. Bravyi and A. Kitaev, “Universal quantum computation with ideal Clifford gates and noisy ancillas,” _Phys. Rev. A_ , vol. 71, no. 2, p. 022316, 2005.
  * [3] E. Knill, “Quantum computing with realistically noisy devices,” _Nature_ , vol. 434, no. 7029, pp. 39–44, 2005.
  * [4] 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,” _Phys. Rev. A_ , vol. 77, no. 1, p. 012307, 2008.
  * [5] E. Magesan, J. M. Gambetta, and J. Emerson, “Scalable and robust randomized benchmarking of quantum processes,” _Phys. Rev. Lett._ , vol. 106, no. 18, p. 180504, 2011.
  * [6] C. H. Bennett, D. P. DiVincenzo, J. A. Smolin, and W. K. Wootters, “Mixed-state entanglement and quantum error correction,” _Phys. Rev. A_ , vol. 54, no. 5, p. 3824, 1996.
  * [7] S. Aaronson, “Shadow tomography of quantum states,” _SIAM J. on Comput._ , no. 0, pp. STOC18–368–STOC18–394, 2020.
  * [8] H.-Y. Huang, R. Kueng, and J. Preskill, “Predicting many properties of a quantum system from very few measurements,” _Nature Phys._ , vol. 16, pp. 1050––1057, 2020.
  * [9] S. Aaronson and D. Gottesman, “Improved simulation of stabilizer circuits,” _Phys. Rev. A_ , vol. 70, no. 5, 2004.
  * [10] K. N. Patel, I. L. Markov, and J. P. Hayes, “Optimal synthesis of linear reversible circuits,” _Quantum Info. Comput._ , vol. 8, no. 3, p. 282–294, 2008.
  * [11] S. Bravyi and D. Maslov, “Hadamard-free circuits expose the structure of the Clifford group,” arXiv:2003.09412, 2020.
  * [12] V. Kliuchnikov and D. Maslov, “Optimization of Clifford circuits,” _Phys. Rev. A_ , vol. 88, no. 5, 2013.
  * [13] S. Bravyi, J. A. Latone, and D. Maslov, “6-qubit optimal Clifford circuits”, arXiv:2012.06074, 2020.
  * [14] D. Maslov, G. W. Dueck, D. M. Miller, and C. Negrevergne, “Quantum circuit simplification and level compaction,” _IEEE Trans. CAD_ , vol. 27, no. 3, pp. 436–444, 2008.
  * [15] A. K. Prasad, V. V. Shende, I. L. Markov, J. P. Hayes, and K. N. Patel, “Data structures and algorithms for simplifying reversible circuits,” _ACM JETC_ , vol. 2, no. 4, pp. 277–293, 2006.
  * [16] S. Bravyi, R. Shaydulin, S. Hu, and D. Maslov. https://github.com/rsln-s/Clifford_Circuit_Optimization_with_Templates_and_Symbolic_Pauli_Gates, 2021.
  * [17] S. Debnath, N. M. Linke, C. Figgatt, K. A. Landsman, K. Wright, and C. Monroe, “Demonstration of a small programmable quantum computer with atomic qubits,” _Nature_ , vol. 536, no. 7614, pp. 63–66, 2016.
  * [18] IBM, “IBM Quantum Experience,”, https://quantum-computing.ibm.com/, last accessed 4/26/2021.
  * [19] R. Iten, R. Moyard, T. Metger, D. Sutter, and S. Woerner, “Exact and practical pattern matching for quantum circuit optimization,” arXiv:1909.05270, 2019.
  * [20] D. Aharonov, I. Arad, and S. Irani, “Efficient algorithm for approximating one-dimensional ground states,” _Phys. Rev. A_ , vol. 82, no. 1, p. 012315, 2010.
  * [21] R. Duncan, A. Kissinger, S. Perdrix, and J. Van De Wetering, “Graph-theoretic simplification of quantum circuits with the ZX-calculus,” _Quantum_ , vol. 4, p. 279, 2020.