Synthesis of CNOT-Dihedral circuits with optimal number
of two qubit gates
Shelly Garion
1
and Andrew W. Cross
2
1
IBM Quantum, IBM Research Haifa, Haifa University Campus, Mount Carmel, Haifa, 3498825, Israel
2
IBM Quantum, IBM T.J. Watson Research Center, Yorktown Heights, NY 10598, USA
In this note we present explicit canoni-
cal forms for all the elements in the two-
qubit CNOT-Dihedral group, with min-
imal numbers of controlled-S (CS) and
controlled-X (CX) gates, using the gener-
ating set of quantum gates [X, T, CX, CS].
We provide an algorithm to successively
construct the n-qubit CNOT-Dihedral
group, asserting an optimal number of
controlled-X (CX) gates. These results are
needed to estimate gate errors via non-
Clifford randomized benchmarking and
may have further applications to cir-
cuit optimization over fault-tolerant gate
sets.
1 Introduction
Randomized Benchmarking (RB) [2325] is a
well-known algorithm that provides an efficient
and reliable experimental estimation of an av-
erage error-rate for a set of quantum gate op-
erations, by running sequences of random gates
from the Clifford group that should return the
qubits to the initial state. RB techniques are
scalable to many qubits since the Clifford group
can be efficiently simulated (in polynomial time)
using a classical computer [1, 10, 20, 27]. RB
can also be used to characterize specific inter-
leaved gate errors [26], coherence errors [28, 31]
and leakage errors [32]. RB methods were gener-
alized to certain single qubit non-Clifford gates,
like the T -gate [12]. In [14] the authors presented
a scalable RB procedure to benchmark important
non-Clifford gates, such as the controlled-S gate
and controlled-controlled-Z gate, which belong to
a certain group called the CNOT-Dihedral group.
Certain CNOT-Dihedral groups have two key
Shelly Garion: shelly@il.ibm.com
Andrew W. Cross: awcross@us.ibm.com
characteristics in common with the Clifford
group. First, these groups have elements with
concise representations that can be efficiently
manipulated [4, 14]. Second, these groups are
the set of transversal (fault-tolerant) gates for
certain quantum error-correcting codes [6, 7, 9,
19, 22, 34]. Since the Clifford gates together with
the T gate form a universal set of gates, there are
many papers aiming to optimize the number of
T gates [11, 18, 21, 29, 30]. Additional methods
aim to minimize the count of controlled-X (CX)
gates in universal circuits [33], and in particular,
in controlled-X-phase circuits [3, 15].
In addition, as the Clifford gate together with
the controlled-S (CS) gate also forms a universal
set of gates, an algorithm has recently been intro-
duced to construct a circuit with an optimal num-
ber of CS gates given a two-qubit Clifford+CS
operator [17]. Another example is the controlled-
controlled-Z gate, which is equivalent to the Tof-
foli gate (up to single qubit gates), that can be
decomposed into 6 CX gates and single qubit
gates, but requires only 5 two-qubit gates in its
decomposition if the CS and CS
1
gates are also
available [5].
It is therefore important to efficiently present
the elements in the CNOT-Dihedral group us-
ing a minimal number of physical basic gates, in
particular, two-qubit gates like the controlled-X
(CX) and controlled-S (CS) gates.
Recall that X is the Pauli gate defined as
X =
0 1
1 0
!
Fix an integer m and define
T (m) =
1 0
0 e
2πi/m
!
By abuse of notation we will denote T = T (m),
although the T gate is usually defined as T (8) =
Accepted in Quantum 2020-11-30, click title to verify. Published under CC-BY 4.0. 1
arXiv:2006.12042v2 [quant-ph] 3 Dec 2020
1 0
0 e
2πi/8
!
.
The single-qubit Dihedral group is generated
by the X and T = T (m) gates (up to a global
phase) and contains 2m elements,
hX, T i/hλI : λ Ci =
{X
l
T
k
: l {0, 1}, k {0, . . . , m 1}}.
(1)
More generally, the CNOT-Dihedral group on
n qubits G = G(m) is generated by the gates X,
T = T (m) and controlled-X (CX), up to a global
phase (see [14] for details),
G = G(m) =hX
i
, T
i
, CX
i,j
:
i, j {0, . . . , n 1}i/
hλI : λ Ci,
(2)
where the controlled-X (CX) gate is defined as
CX =
1 0 0 0
0 1 0 0
0 0 0 1
0 0 1 0
When m is not a power of 2, the group G =
G(m) has double exponential order as a function
of the number of qubits n. In the special case
when m is a power of two, the group is only expo-
nentially large and we can represent its elements
efficiently (see [14]). Elements of G( m) belong to
level log
2
m of the Clifford hierarchy when m is
a power of two [19, 22] and this is related to the
fact that they are the transversal gates of certain
m-dimensional quantum codes [7].
Again, by abuse of notation we denote S =
T
2
= T (m)
2
=
1 0
0 e
4πi/m
!
, although the S gate
is usually defined as T (8)
2
= T (4) =
1 0
0 i
!
.
Observe that S has order m/2 if m is even, and
order m if m is odd, namely, S has order m/d
where d = gcd(m, 2).
The controlled-S (CS) gate belongs to G and
can be written as
CS
i,j
= T
i
T
j
· CX
i,j
· I
i
T
j
· CX
i,j
=
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 e
4πi/m
,
(3)
where T
i
T
j
means the tensor product T
i
T
j
.
In the case where m = 8, the CS gate is less
expensive to physically implement than one CX
gate
1
which makes it an alternative to CX for
improving circuit decompositions.
We focus on the case where n = 2. The fol-
lowing two Theorems provide canonical forms for
all the elements in the two-qubit CNOT-Dihedral
group, such that the numbers of CS and CX
gates are optimal. This is analogous to the de-
scription in [13] of the elements in the two-qubit
Clifford group.
Theorem 1. Consider the CS-Dihedral sub-
group on two qubits, namely the two-qubit group
generated by the gates X, T = T (m) and CS
(controlled-S), where S = T
2
, and denote d =
gcd(m, 2). Then this group has
4m
3
d
=
m
d
(2m)
2
elements of the following form:
U = CS
e
0,1
· X
k
0
X
k
0
1
· T
l
0
T
l
0
1
where k, k
0
{0, 1}, l, l
0
{0, . . . , m 1}, e
{0, 1, . . . , m/d 1} = {0, ±1, ±2, . . . , ±d
md
2d
e}.
Theorem 2. Let G be the two-qubit CNOT-
Dihedral group generated by the gates X, T =
T (m), CX and CS, where S = T
2
, and denote
d = gcd(m, 2). Then this group has 24 · m
3
/d
elements, divided into the following four classes.
1. The first class is the CS-Dihedral sub-
group described in Theorem 1 and has
4m
3
d
elements, that can be written with no CX
gates.
2. The second class, called the CX-like class,
consists of
8m
3
d
= 2 ·
m
d
· (2m)
2
elements,
and contains all the elements of the following
form, which require exactly one CX gate.
U = X
k
0
X
k
0
1
· T
l
0
T
l
0
1
· CX
i,j
· I
i
T
e
j
3. The third class, called the Double-CX-like
class, consists of
8m
3
d
= 2 ·
m
d
· (2m)
2
ele-
ments, and contains all the elements of the
following form, which require exactly two
CX gates.
U = X
k
0
X
k
0
1
· T
l
0
T
l
0
1
· CX
i,j
· CX
j,i
· I
i
T
e
j
1
Up to single-qubit rotations, the gate is equivalent to
controlled-
X gate, so it can be implemented by evolving
for half the duration of a controlled-X gate [16].
Accepted in Quantum 2020-11-30, click title to verify. Published under CC-BY 4.0. 2
4. The fourth class, called the Triple-CX-like
class, consists of
4m
3
d
=
m
d
· (2m)
2
elements,
and contains all the elements of the following
form, which require exactly three CX gates.
U = X
k
0
X
k
0
1
·T
l
0
T
l
0
1
·CX
0,1
·CX
1,0
·I
0
T
e
1
·CX
0,1
where k, k
0
{0, 1}, l, l
0
{0, . . . , m 1}, e
{0, . . . , m/d 1} and (i, j) {(0, 1), (1, 0)}.
The following Theorem provides an algorithm
to successively construct the n-qubit CNOT-
Dihedral group. It is analogous to [8] that
discusses the generation of the n-qubit Clifford
group. Case (1) of this Theorem shows that one
can successively construct the CNOT-Dihedral
group asserting an optimal number of CX gates,
with a bound on the space to search these group
elements (see Remark 4). Moreover, one can also
use the “meet in the middle” algorithm of [2]
to synthesize gate sequences for the non-Clifford
RB.
Theorem 3. Let G = G(m) be the CNOT-
Dihedral group on n qubits, and denote d =
gcd(m, 2).
1. Let F (r) be the subset of operators imple-
mentable by a circuit with r CX gates (and
any number of X and T gates). Suppose U
is in F (r + 1), then
U = I
i
T
l
j
· CX
i,j
· U
0
for some U
0
F (r), i, j {0, ..., n 1},
i 6= j, l {0, . . . , m/d 1}. In particular,
|F (r + 1)|
m(n
2
n)
d
|F (r)|
2. Let H(r) be the subset of operators imple-
mentable by a circuit with r CS or CS
gates
(and any number of X and T gates). Sup-
pose U is in H(r + 1), then
U = CS
e
i,j
· U
0
for some U
0
H(r), i, j {0, ..., n 1},
i < j, e {−1, 1}. In particular,
|H(r + 1)| (n
2
n)|H(r)|
Remark 4. We note that the bounds in The-
orem 3 are sharp and cannot generally be im-
proved, since there is an equality in certain cases.
Indeed, assume that n = 2. If H(r) is the sub-
set of operators implementable by a circuit with
r CS gates, then H(1) = 2 · H(0) (see Theo-
rem 1). If F (r) is the subset of operators im-
plementable by a circuit with r CX gates, then
F (1) =
2m
d
· F (0) (see Theorem 2).
Corollary 5. In order to generate all the ele-
ments in the n-qubit CNOT-Dihedral group G =
G(m) having at most r CX gates, the algorithm
generates at most
(2m)
n
·
m
d
r
· (n
2
n)
r
group elements.
2 Useful identities and the proof of
Theorem 3
Consider quantum circuits on a fixed number of
qubits n that are products of controlled-X gates
CX, bit-flip gates X, and single-qubit phase
gates T = T (m) satisfying T |ui := e
u/m
|ui.
When these gates are applied to each qubit or
pairs of qubits, they generate a group G = G(m)
of unitary operators that is an example of a
CNOT-dihedral group. An element U G acts
on the standard basis as
U|xi = e
p(x)
|f(x)i (4)
where p(x) = p(x
1
, . . . , x
n
) is a polynomial called
the phase polynomial and f(x) is an affine re-
versible function. Since x
j
F
2
, so x
2
j
= x
j
, the
phase polynomial is
p(x) =
X
α⊆{0,1}
n
p
α
x
α
(5)
where x
α
=
Q
jα
x
j
. Furthermore, the coef-
ficients can be chosen such that p
= 0 and
p
α
(2)
|α|−1
Z
2m
otherwise (see [14]).
Recall the following useful identities in the
Dihedral group defined in (1) generated by the
T = T (m) and X gates (up to a global phase),
T
=T
m1
XT X = T
T XT = X
T XT
= SX
(6)
We state here some useful identities in the
CNOT-Dihedral group defined in (2) regarding
Accepted in Quantum 2020-11-30, click title to verify. Published under CC-BY 4.0. 3
the controlled-S (CS) gate. According to the
definition of the CS gate in (3),
CS
i,j
= T
i
T
j
· CX
i,j
· I
i
T
j
· CX
i,j
= CX
i,j
· I
i
T
j
· CX
i,j
· T
i
T
j
(7)
We deduce that
CS
i,j
· CX
i,j
= T
i
T
j
· CX
i,j
· I
i
T
j
,
CX
i,j
· CS
i,j
= I
i
T
j
· CX
i,j
· T
i
T
j
(8)
Similarly,
CS
i,j
= T
i
T
j
· CX
i,j
· I
i
T
j
· CX
i,j
= CX
i,j
· I
i
T
j
· CX
i,j
· T
i
T
j
(9)
We note that according to their definition, the
CS and CS
gates (as well as their powers) are
symmetrical, namely,
CS
j,i
= CS
i,j
CS
j,i
= CS
i,j
(10)
T (and all its powers) commutes with the con-
trol and target of the CS gate, namely,
I
i
T
j
· CS
i,j
= CS
i,j
· I
i
T
j
,
T
i
I
j
· CS
i,j
= CS
i,j
· T
i
I
j
,
T
i
T
j
· CS
i,j
= CS
i,j
· T
i
T
j
(11)
In addition, we have the following relations be-
tween the CS and X gates,
X
i
I
j
· CS
i,j
· X
i
I
j
= CS
i,j
· I
i
S
j
= I
i
S
j
· CS
i,j
I
i
X
j
· CS
i,j
· I
i
X
j
= CS
i,j
· S
i
I
j
= S
i
I
j
· CS
i,j
X
i
X
j
· CS
i,j
· X
i
X
j
= CS
i,j
· S
i
S
j
= S
i
S
j
· CS
i,j
(12)
We shall moreover use the following identities
of the CX gate. T (and all its powers) commutes
with the control of CX, and X (and all its pow-
ers) commutes with the target of CX, namely,
I
i
X
j
· CX
i,j
= CX
i,j
· I
i
X
j
,
T
i
I
j
· CX
i,j
= CX
i,j
· T
i
I
j
(13)
In addition, we have the following relation be-
tween the control of CX and the X gate,
CX
i,j
· X
i
I
j
· CX
i,j
= X
i
X
j
(14)
Recall that the Z gate is defined as Z =
1 0
0 1
!
. Then we have the following useful re-
lation between the CX gate and the Z gate,
CX
i,j
· I
i
Z
j
· CX
i,j
= Z
i
Z
j
(15)
Finally, the product CX
i,j
· CX
j,i
, which is in
the iSWAP-like class of Clifford gates (see [13])),
satisfies the following relation,
I
i
T
j
· CX
i,j
· CX
j,i
= CX
i,j
· CX
j,i
· T
i
I
j
(16)
Based on the above identities we can now prove
Theorem 3.
Proof of Theorem 3. 1) There exists a product of
single qubit gates V = V
1
. . . V
n
, V
k
hX, T i such
that U = V · CX
i,j
· U
0
for some pair of qubits
i, j. Absorb V
k
for k / {i, j} into U
0
, namely,
U = X
k
i
X
k
0
j
· T
l
i
T
l
0
j
· CX
i,j
· U
0
for some k, k
0
, l, l
0
and U
0
F (r). Since T
l
i
com-
mutes with the control of CX
i,j
by (13), we can
absorb T
l
i
in U
0
. Since X
k
0
j
commutes with the
target of CX
i,j
by (13), we can also absorb X
k
0
j
in U
0
. Hence,
U = X
k
i
T
l
j
· CX
i,j
· U
0
for some k, l and U
0
F (r).
If k = 1 then according to (14), X
i
I
j
· CX
i,j
=
CX
i,j
· X
i
X
j
, so we can replace U by
I
i
T
l
j
· CX
i,j
· X
i
X
j
· U
0
= I
i
T
l
j
· CX
i,j
· U
00
where U
00
F (r). We can therefore assume that
k = 0.
If m is even and l m/2 then T
m/2
= Z, so
we can rewrite U as
U = I
i
T
l
j
· I
i
Z
j
· CX
i,j
· U
0
for some l < m/2. According to (15), I
i
Z
j
·
CX
i,j
= CX
i,j
· Z
i
Z
j
, so we can replace U by
I
i
T
l
j
· CX
i,j
· Z
i
Z
j
· U
0
= I
i
T
l
j
· CX
i,j
· U
00
where U
00
F (r). We can therefore assume that
l < m/2 as needed.
2) Similarly to (1) we can assume that
U = X
k
i
X
k
0
j
· T
l
i
T
l
0
j
· CS
e
i,j
· U
0
Accepted in Quantum 2020-11-30, click title to verify. Published under CC-BY 4.0. 4
for some k, k
0
, l, l
0
, e = ±1 and U
0
H(r). Since
T commutes with both control and target of CS
by (11), we can absorb T
l
i
T
l
0
j
in U
0
and so
U = X
k
i
X
k
0
j
· CS
e
i,j
· U
0
Now, by (10) we may assume that i < j, and
by (12) we can absorb X
k
i
X
k
0
j
in U
0
and assume
that U = CS
e
i,j
· U
0
for some i < j and e = ±1 as
needed.
3 The canonical forms and proofs of
Theorems 1 and 2
From now on we will now assume that G is the
CNOT-Dihedral group on two qubits {0, 1}, and
describe canonical forms of the elements in G.
This is analogous to the description in [13] of the
elements in the Clifford group on two qubits.
Proof of Theorem 1. The proof follows by induc-
tion on the number r of CS and CS
gates. Since
CS is of order m/d then necessarily r < d
md
2d
e.
Let r = 0, then any U H(0) can be written
as
U = X
k
0
X
k
0
1
· T
l
0
T
l
0
1
where k, k
0
{0, 1}, l, l
0
{0, . . . , m 1}, since
such an element belongs to the direct product of
the two single-qubit Dihedral groups.
Let r = 1, then according to Case (2) of The-
orem 3, any U H(1) can be written as
U = CS
e
0,1
· X
k
0
X
k
0
1
· T
l
0
T
l
0
1
where e {1, 1}, k, k
0
{0, 1}, l, l
0
{0, . . . , m 1}.
Now assume that the Theorem holds for H(r).
According to Case (2) of Theorem 3 and the in-
duction assumption, any element U H(r + 1)
can be written as
U = CS
e
0,1
· CS
e
0
0,1
· U
0
= CS
e+e
0
0,1
· U
0
where U
0
hT, Xi, e = ±1 and e
0
= ±r, as
needed.
Note that all the elements obtained in this pro-
cess are distinct, since an equality CS
e
0,1
· U =
CS
e
0
0,1
· U
0
for some e, e
0
{0, . . . , m/d 1} and
U, U
0
hT, Xi, implies that CS
ee
0
0,1
hT, Xi, so
necessarily e = e
0
and U = U
0
.
Lemma 6. Let G be the CNOT-Dihedral group
on two qubits. Then any element in G which has
exactly one CS gate and one CX gate can be
rewritten as an element with no CS gates and
exactly one CX gate.
Proof. According to Theorem 3 we may assume
w.l.o.g. that such an element U can be written as
a product
U = (U
0
· CX
0,1
· I
0
T
l
1
) · (CS
e
0,1
· U
00
)
where U
0
, U
00
hT, Xi, l {0, . . . , m/d 1}, e
{1, 1}.
Since T commutes with the control and target
of CS by (11), we may absorb T
1
into U
00
, and so
U can be rewritten as
U = U
0
· CX
0,1
· CS
e
0,1
· U
00
= U
0
· I
0
T
e
1
· CX
0,1
· T
e
0
T
e
1
· U
00
for some U
0
, U
00
by (8). Therefore, U = U
0
·CX
0,1
·
U
00
for some U
0
, U
00
, as needed.
Lemma 7. Let G be the CNOT-Dihedral group
on two qubits. Then any element in G which has
exactly one CX gate and no CS gates can be
written either as:
U = X
k
0
X
k
0
1
· T
l
0
T
l
0
1
· CX
0,1
· I
0
T
l
00
1
or:
U = X
k
0
X
k
0
1
· T
l
0
T
l
0
1
· CX
1,0
· T
l
00
0
I
1
where k, k
0
{0, 1}, l, l
0
{0, . . . , m 1} and
l
00
{0, . . . , m/d1}. In particular, G has
8m
3
d
=
2 ·
m
d
· (2m)
2
such elements.
Proof. The proof follows from Case (1) of Theo-
rem 3.
Note that all the elements obtained in this pro-
cess are indeed distinct.
First, an equality U · CX
0,1
· I
0
T
l
1
= U
0
·
CX
0,1
· I
0
T
l
0
1
for some U, U
0
hT, Xi and l, l
0
{0, . . . , m/d 1}, implies that CX
0,1
· I
0
T
l
0
l
1
·
CX
0,1
hT, Xi, hence either l = l
0
and U = U
0
;
or m is even and l l
0
= m/2, yielding a contra-
diction since l, l
0
< m/2.
Second, an equality U · CX
0,1
· I
0
T
l
1
= U
0
·
CX
1,0
· T
l
0
0
I
1
for some U, U
0
hT, Xi and l, l
0
{0, . . . , m/d 1}, implies that CX
0,1
· T
l
0
0
T
l
1
·
CX
1,0
hT, Xi, yielding a contradiction.
Accepted in Quantum 2020-11-30, click title to verify. Published under CC-BY 4.0. 5
Lemma 8. Let G be the CNOT-Dihedral group
on two qubits. Then any element in G which has
exactly two CX gates and no CS gates can be
written either as:
U = X
k
0
X
k
0
1
· T
l
0
T
l
0
1
· CX
0,1
· CX
1,0
· I
0
T
l
00
1
or:
U = X
k
0
X
k
0
1
· T
l
0
T
l
0
1
· CX
1,0
· CX
0,1
· T
l
00
0
I
1
where k, k
0
{0, 1}, l, l
0
{0, . . . , m 1} and
l
00
{0, . . . , m/d1}. In particular, G has
8m
3
d
=
2 ·
m
d
· (2m)
2
such elements.
Proof. According to Case (1) of Theorem 3 and
Lemma 7 we may assume w.l.o.g. that such an
element U can be written as
U = I
i
T
l
j
· CX
i,j
· I
0
T
l
0
1
· CX
0,1
· U
0
where U
0
hT, Xi, i, j {0, 1}, l, l
0
{0, ..., m/d 1}. Hence, there are two options,
either (i, j) = (0, 1) or (1, 0).
1) First, assume that (i, j) = (0, 1), then
U = I
0
T
l
1
· CX
0,1
· I
0
T
l
0
1
· CX
0,1
· U
0
If l
0
= 0 then U hX, T i and we are done.
Otherwise, according to (9), CX
0,1
· I
0
T
1
·
CX
0,1
= CS
0,1
· T
0
T
1
, implying that
CX
0,1
· I
0
T
l
0
1
· CX
0,1
= (CX
0,1
· I
0
T
1
· CX
0,1
)
l
0
= (CS
0,1
· T
0
T
1
)
l
0
= CS
l
0
0,1
· T
l
0
0
T
l
0
1
by (11). Thus we can write U as an element in
the subgroup generated by CS, X and T .
Then we are done by Theorem 1.
2) Now, assume that (i, j) = (1, 0), then we
can write U as
U = T
l
0
I
1
· CX
1,0
· I
0
T
l
0
1
· CX
0,1
· U
0
By (13), T
1
commutes with CX
1,0
, so we may
write U as
U = T
l
0
T
l
0
1
· CX
1,0
· CX
0,1
· U
0
According to (16), T
0
I
1
·CX
1,0
·CX
0,1
= CX
1,0
·
CX
0,1
· I
0
T
1
, so we can absorb T
0
in U
0
.
Therefore,
U = I
0
T
l
0
1
· CX
1,0
· CX
0,1
· U
0
for some U
0
hX, T i and l
0
{0, ..., m/d 1}
as needed.
Similar argument as in the proof of Lemma 7
shows that all the elements obtained in this pro-
cess are indeed distinct.
First, an equality U · CX
0,1
· CX
1,0
· I
0
T
l
1
=
U
0
· CX
0,1
· CX
1,0
· I
0
T
l
0
1
for some U, U
0
hT, Xi
and l, l
0
{0, . . . , m/d 1 }, implies that CX
0,1
·
CX
1,0
· I
0
T
l
0
l
1
· CX
1,0
· CX
0,1
hT, Xi, implying
that l = l and U = U
0
.
Second, an equality U · CX
0,1
· CX
1,0
· I
0
T
l
1
=
U
0
· CX
1,0
· CX
0,1
· T
l
0
0
I
1
for some U, U
0
hT, Xi
and l, l
0
{0, . . . , m/d 1 }, implies that CX
0,1
·
CX
1,0
· T
l
0
0
T
l
1
· CX
0,1
· CX
1,0
hT, Xi, yielding
a contradiction.
Lemma 9. Let G be the CNOT-Dihedral group
on two qubits. Then any element in G which has
exactly three CX gates and no CS gates can be
written as:
U = X
k
0
X
k
0
1
· T
l
0
T
l
0
1
· CX
0,1
· CX
1,0
· I
0
T
l
00
1
· CX
0,1
where k, k
0
{0, 1}, l, l
0
{0, . . . , m 1} and
l
00
{0, . . . , m/d1}. In particular, G has
4m
3
d
=
m
d
· (2m)
2
such elements.
Proof. According to Case (1) of Theorem 3 and
Lemma 8 we may assume w.l.o.g. that such an
element U can be written as
U = I
i
T
l
j
· CX
i,j
· I
0
T
l
0
1
· CX
1,0
· CX
0,1
· U
0
where U
0
hT, Xi, i, j {0, 1}, l, l
0
{0, ..., m/d 1}.
Hence, there are two options, either (i, j) =
(0, 1) or (1, 0).
1) First, assume that (i, j) = (1, 0), then
U = T
l
0
I
1
· CX
1,0
· I
0
T
l
0
1
· CX
1,0
· CX
0,1
· U
0
By (13), T
1
commutes with CX
1,0
, so we can
write U as
U = T
l
0
I
1
· I
0
T
l
0
1
· CX
1,0
· CX
1,0
· CX
0,1
· U
0
= T
l
0
T
l
0
1
· CX
0,1
· U
0
Then we actually have only one CX gate and
we are done by Lemma 7.
2) Now assume that (i, j) = (0, 1), then we can
write U as
U = I
0
T
l
1
· CX
0,1
· I
0
T
l
0
1
· CX
1,0
· CX
0,1
· U
0
Accepted in Quantum 2020-11-30, click title to verify. Published under CC-BY 4.0. 6
for some U
0
, U
00
, l, l
0
.
By (13), T
1
commutes with CX
1,0
, so we can
rewrite U as
U = I
0
T
l
1
· CX
0,1
· CX
1,0
· I
0
T
l
0
1
· CX
0,1
· U
0
According to (16), I
0
T
1
·CX
0,1
·CX
1,0
= CX
0,1
·
CX
1,0
· T
0
I
1
, therefore,
U = CX
0,1
· CX
1,0
· T
l
0
T
l
0
1
· CX
0,1
· U
0
for some l, l
0
{0, ..., m/d 1}.
Now, by (13), T
0
commutes with CX
0,1
and so
we can absorb T
0
in U
0
, thus
U = CX
0,1
· CX
1,0
· I
0
T
l
0
1
· CX
0,1
· U
0
= CX
0,1
· I
0
T
l
0
1
· CX
1,0
· CX
0,1
· U
0
by using (13) again.
The same argument as in the proof of Lemma 8
shows that all the elements obtained in this pro-
cess are indeed distinct.
Proof of Theorem 2. According to Corollary 1
in [14], the CNOT-Dihedral group G = G(m)
on two qubits has exactly 24 · m
3
/d elements.
By Lemma 6, there are no elements with both
CX and CS gates. The cases where there are
only CS gates were handled in Theorem 1. The
remaining cases where there are only CX gates
were proved in Lemmas 7, 8 and 9.
References
[1] Scott Aaronson and Daniel Gottesman.
Improved simulation of stabilizer cir-
cuits. Phys. Rev. A, 70:052328, Nov 2004.
DOI: 10.1103/PhysRevA.70.052328. URL
https://link.aps.org/doi/10.1103/
PhysRevA.70.052328.
[2] M. Amy, D. Maslov, M. Mosca, and
M. Roetteler. A meet-in-the-middle algo-
rithm for fast synthesis of depth-optimal
quantum circuits. IEEE Transactions on
Computer-Aided Design of Integrated Cir-
cuits and Systems, 32(6):818–830, 2013.
DOI: 10.1109/TCAD.2013.2244643.
[3] Matthew Amy, Parsiad Azimzadeh, and
Michele Mosca. On the controlled-NOT
complexity of controlled-NOT–phase cir-
cuits. Quantum Science and Technology, 4
(1):015002, sep 2018. DOI: 10.1088/2058-
9565/aad8ca. URL https://doi.org/10.
1088%2F2058-9565%2Faad8ca.
[4] Matthew Amy, Jianxin Chen, and Neil J.
Ross. A finite presentation of cnot-dihedral
operators. Electronic Proceedings in The-
oretical Computer Science, 266:84–97,
2018. DOI: 10.4204/eptcs.266.5. URL
https://app.dimensions.ai/details/
publication/pub.1101260386andhttps:
//arxiv.org/pdf/1701.00140.
[5] Adriano Barenco, Charles H. Bennett,
Richard Cleve, David P. DiVincenzo,
Norman Margolus, Peter Shor, Tycho
Sleator, John A. Smolin, and Harald We-
infurter. Elementary gates for quantum
computation. Phys. Rev. A, 52:3457–
3467, Nov 1995. DOI: 10.1103/Phys-
RevA.52.3457. URL https://link.aps.
org/doi/10.1103/PhysRevA.52.3457.
[6] H. Bombin and M. A. Martin-Delgado.
Topological computation without braiding.
Phys. Rev. Lett., 98:160502, Apr 2007. DOI:
10.1103/PhysRevLett.98.160502. URL
https://link.aps.org/doi/10.1103/
PhysRevLett.98.160502.
[7] ector Bomb´ın. Gauge color codes: opti-
mal transversal gates and gauge fixing in
topological stabilizer codes. New Journal
of Physics, 17(8):083002, aug 2015. DOI:
10.1088/1367-2630/17/8/083002. URL
https://doi.org/10.1088%2F1367-2630%
2F17%2F8%2F083002.
[8] Sergey Bravyi. Compiling clifford operators.
[9] Sergey Bravyi and Robert onig. Clas-
sification of topologically protected gates
for local stabilizer codes. Phys. Rev.
Lett., 110:170503, Apr 2013. DOI:
10.1103/PhysRevLett.110.170503. URL
https://link.aps.org/doi/10.1103/
PhysRevLett.110.170503.
[10] Sergey Bravyi and Dmitri Maslov.
Hadamard-free circuits expose the struc-
ture of the clifford group, 2020. URL
https://arxiv.org/abs/2003.09412.
[11] Earl T. Campbell and Mark Howard. Unify-
ing gate synthesis and magic state distilla-
tion. Phys. Rev. Lett., 118:060501, Feb 2017.
DOI: 10.1103/PhysRevLett.118.060501.
URL https://link.aps.org/doi/10.
1103/PhysRevLett.118.060501.
[12] Arnaud Carignan-Dugas, Joel J. Wall-
man, and Joseph Emerson. Charac-
terizing universal gate sets via dihe-
Accepted in Quantum 2020-11-30, click title to verify. Published under CC-BY 4.0. 7
dral benchmarking. Phys. Rev. A, 92:
060302, Dec 2015. DOI: 10.1103/Phys-
RevA.92.060302. URL https://link.aps.
org/doi/10.1103/PhysRevA.92.060302.
[13] A. D. orcoles, Jay M. Gambetta, Jerry M.
Chow, John A. Smolin, Matthew Ware,
Joel Strand, B. L. T. Plourde, and
M. Steffen. Process verification of
two-qubit quantum gates by random-
ized benchmarking. Phys. Rev. A, 87:
030301, Mar 2013. DOI: 10.1103/Phys-
RevA.87.030301. URL https://link.aps.
org/doi/10.1103/PhysRevA.87.030301.
[14] Andrew W Cross, Easwar Magesan, Lev S
Bishop, John A Smolin, and Jay M Gam-
betta. Scalable randomised benchmark-
ing of non-clifford gates. npj Quan-
tum Information, 2(1), 2016. DOI:
10.1038/npjqi.2016.12. URL https://doi.
org/10.1038/npjqi.2016.12.
[15] Meuli G., Soeken M., and De Micheli G. Sat-
based {CNOT, T} quantum circuit synthe-
sis. Kari J., Ulidowski I. (eds) Reversible
Computation. RC 2018. Lecture Notes in
Computer Science, 11106, 2018. DOI:
10.1007/978-3-319-99498-7˙12.
[16] Shelly Garion, Naoki Kanazawa, Haggai
Landa, David C. McKay, Sarah Sheldon,
Andrew W. Cross, and Christopher J.
Wood. Experimental implementation of
non-clifford interleaved randomized bench-
marking with a controlled-s gate, 2020. URL
https://arxiv.org/abs/2007.08532.
[17] Andrew N. Glaudell, Neil J. Ross, and Ja-
cob M. Taylor. Optimal two-qubit circuits
for universal fault-tolerant quantum com-
putation, 2020. URL https://arxiv.org/
abs/2001.05997.
[18] David Gosset, Vadym Kliuchnikov, Michele
Mosca, and Vincent Russo. An algorithm
for the t-count. Quantum Info. Com-
put., 14(15–16):1261–1276, November 2014.
ISSN 1533-7146. URL https://dl.acm.
org/doi/10.5555/2685179.2685180.
[19] Daniel Gottesman and Isaac L. Chuang.
Demonstrating the viability of universal
quantum computation using teleportation
and single-qubit operations. Nature, 402:
390–393, 1999. ISSN 1476-4687. DOI:
10.1038/46503. URL https://doi.org/
10.1038/46503.
[20] Daniel Eric Gottesman. Stabilizer codes
and quantum error correction, 1997.
URL https://resolver.caltech.edu/
CaltechETD:etd-07162004-113028.
[21] Luke E Heyfron and Earl T Campbell. An
efficient quantum compiler that reduces t
count. Quantum Science and Technology, 4
(1):015004, sep 2018. DOI: 10.1088/2058-
9565/aad604. URL https://doi.org/10.
1088%2F2058-9565%2Faad604.
[22] Tomas Jochym-O’Connor, Aleksander Ku-
bica, and Theodore J. Yoder. Disjoint-
ness of stabilizer codes and limitations on
fault-tolerant logical gates. Phys. Rev. X,
8:021047, May 2018. DOI: 10.1103/Phys-
RevX.8.021047. URL https://link.aps.
org/doi/10.1103/PhysRevX.8.021047.
[23] E. Knill, D. Leibfried, R. Reichle, J. Brit-
ton, R. B. Blakestad, J. D. Jost, C. Langer,
R. Ozeri, S. Seidelin, and D. J. Wineland.
Randomized benchmarking of quantum
gates. Phys. Rev. A, 77:012307, Jan 2008.
DOI: 10.1103/PhysRevA.77.012307. URL
https://link.aps.org/doi/10.1103/
PhysRevA.77.012307.
[24] Easwar Magesan, J. M. Gambetta,
and Joseph Emerson. Scalable and
robust randomized benchmarking
of quantum processes. Phys. Rev.
Lett., 106:180504, May 2011. DOI:
10.1103/PhysRevLett.106.180504. URL
https://link.aps.org/doi/10.1103/
PhysRevLett.106.180504.
[25] Easwar Magesan, Jay M. Gambetta,
and Joseph Emerson. Characterizing
quantum gates via randomized benchmark-
ing. Phys. Rev. A, 85:042311, Apr 2012.
DOI: 10.1103/PhysRevA.85.042311. URL
https://link.aps.org/doi/10.1103/
PhysRevA.85.042311.
[26] Easwar Magesan, Jay M. Gambetta, B. R.
Johnson, Colm A. Ryan, Jerry M. Chow,
Seth T. Merkel, Marcus P. da Silva,
George A. Keefe, Mary B. Rothwell,
Thomas A. Ohki, Mark B. Ketchen,
and M. Steffen. Efficient measurement
of quantum gate error by interleaved
randomized benchmarking. Phys. Rev.
Lett., 109:080505, Aug 2012. DOI:
10.1103/PhysRevLett.109.080505. URL
Accepted in Quantum 2020-11-30, click title to verify. Published under CC-BY 4.0. 8
https://link.aps.org/doi/10.1103/
PhysRevLett.109.080505.
[27] D. Maslov and M. Roetteler. Shorter
stabilizer circuits via bruhat decompo-
sition and quantum circuit transforma-
tions. IEEE Transactions on Informa-
tion Theory, 64(7):4729–4738, 2018. DOI:
10.1109/TIT.2018.2825602.
[28] David C. McKay, Stefan Filipp, Antonio
Mezzacapo, Easwar Magesan, Jerry M.
Chow, and Jay M. Gambetta. Universal
gate for fixed-frequency qubits via a tunable
bus. Phys. Rev. Applied, 6:064007, Dec 2016.
DOI: 10.1103/PhysRevApplied.6.064007.
URL https://link.aps.org/doi/10.
1103/PhysRevApplied.6.064007.
[29] Yunseong Nam, Neil J. Ross, Yuan Su,
Andrew M. Childs, and Dmitri Maslov.
Automated optimization of large quan-
tum circuits with continuous parameters.
4:23, 2018. ISSN 2056-6387. DOI:
10.1038/s41534-018-0072-4. URL https://
doi.org/10.1038/s41534-018-0072-4.
[30] Neil J. Ross and Peter Selinger. Op-
timal ancilla-free clifford + t approxima-
tion of z-rotations. Quantum Info. Com-
put., 16(11–12):901–953, September 2016.
ISSN 1533-7146. URL https://dl.acm.
org/doi/abs/10.5555/3179330.3179331.
[31] Joel Wallman, Chris Granade, Robin
Harper, and Steven T Flammia. Estimating
the coherence of noise. New Journal of
Physics, 17(11):113020, nov 2015. DOI:
10.1088/1367-2630/17/11/113020. URL
https://doi.org/10.1088%2F1367-2630%
2F17%2F11%2F113020.
[32] Christopher J. Wood and Jay M. Gam-
betta. Quantification and characteriza-
tion of leakage errors. Phys. Rev. A, 97:
032306, Mar 2018. DOI: 10.1103/Phys-
RevA.97.032306. URL https://link.aps.
org/doi/10.1103/PhysRevA.97.032306.
[33] Ed Younis, Koushik Sen, Katherine Yelick,
and Costin Iancu. Qfast: Quantum syn-
thesis using a hierarchical continuous cir-
cuit space, 2020. URL https://arxiv.org/
abs/2003.04462.
[34] B. Zeng, A. Cross, and I. L. Chuang.
Transversality versus universality for addi-
tive quantum codes. IEEE Transactions on
Information Theory, 57(9):6272–6284, 2011.
DOI: 10.1109/TIT.2011.2161917.
Accepted in Quantum 2020-11-30, click title to verify. Published under CC-BY 4.0. 9