# T-count and T-depth of _any_ multi-qubit unitary

Vlad Gheorghiu<EMAIL_ADDRESS>Institute for Quantum Computing,
University of Waterloo, Waterloo ON, Canada  Dept. of Combinatorics and
Optimization, University of Waterloo, Waterloo ON, Canada  softwareQ Inc.,
Kitchener ON, Canada  Michele Mosca<EMAIL_ADDRESS>Institute for
Quantum Computing, University of Waterloo, Waterloo ON, Canada  Dept. of
Combinatorics and Optimization, University of Waterloo, Waterloo ON, Canada
Perimeter Institute for Theoretical Physics, Waterloo ON, Canada  softwareQ
Inc., Kitchener ON, Canada  Priyanka Mukhopadhyay
<EMAIL_ADDRESS><EMAIL_ADDRESS>Institute for Quantum
Computing, University of Waterloo, Waterloo ON, Canada  Dept. of Combinatorics
and Optimization, University of Waterloo, Waterloo ON, Canada

###### Abstract

While implementing a quantum algorithm it is crucial to reduce the quantum
resources, in order to obtain the desired computational advantage. For most
fault-tolerant quantum error-correcting codes the cost of implementing the
non-Clifford gate is the highest among all the gates in a universal fault-
tolerant gate set.

In this paper we design provable algorithm to determine T-count of any
$n$-qubit ($n\geq 1$) unitary $W$ of size $2^{n}\times 2^{n}$, over the
Clifford+T gate set. The space and time complexity of our algorithm are
$\text{poly}(2^{n})$ and
$\text{poly}\left(\left(2^{n}\right)^{m_{\epsilon}}\right)$ respectively.
$m_{\epsilon}$ (_$\epsilon$ -T-count_) is the T-count of an exactly
implementable unitary $U$ i.e. $\mathcal{T}(U)$, such that
$d(U,W)\leq\epsilon$ and $\mathcal{T}(U)\leq\mathcal{T}(U^{\prime})$ where
$U^{\prime}$ is any exactly implementable unitary with
$d(U^{\prime},W)\leq\epsilon$. $d(.,.)$ is the global phase invariant
distance. Our algorithm can also be used to determine T-depth of any multi-
qubit unitary and the asymptotic complexity has similar dependence on $n$ and
_$\epsilon$ -T-depth_. This is the first algorithm that gives T-count or
T-depth of _any_ multi-qubit ($n\geq 1$) unitary (considering any distance).
For small enough $\epsilon$, we can synthesize the T-count and T-depth-optimal
circuits.

Our results can be used to determine optimal count (or depth) of non-Clifford
gates required to implement any multi-qubit unitary with a universal gate set
consisting of Clifford and non-Clifford gates like Clifford+CS, Clifford+V,
etc. To the best of our knowledge, there were no resource-optimal synthesis
algorithm for arbitrary multi-qubit unitaries in any universal gate set.

##  1 Introduction

The vision of Feynman [Fey82] that a quantum computer can be used to overcome
the limitations of classical computers, gained momentum with the design of
quantum algorithms that outperform their classical counterparts for popular
challenging problems like factorization [Sho94, Sho99], unstructured search
[Gro96]. Quantum circuits is one of the most popular way for describing and
implementing quantum algorithms. These consist of a series of elementary
operations or gates belonging to a universal set and dictated by the
implementing technologies. Like their classical counterpart, circuit synthesis
and optimization is a significant part of any quantum computer compilation
process. A compiler primarily translates from a human readable input
(programming language) into instructions that can be executed directly on a
hardware. An integral part of this process is quantum circuit synthesis, whose
aim is to decompose a unitary operation into a sequence of gates from a
universal set. Often, additional constraints are imposed on a synthesis task,
like minimization of a certain resource. Such algorithms are called resource-
optimal synthesis algorithm.

Our work primarily focuses on the “Clifford+T” gate set, a popular universal
fault-tolerant set. Fault-tolerant quantum error correction [ZLC00, BK05] is
required to control the accumulation of errors due to noise on quantum
information, faulty quantum gates, faulty quantum state preparation, faulty
measurements, etc. This is especially important for long computations, else
the errors will make negligible the likelihood of obtaining a reliable and
useful answer. The non-Clifford T gate has known constructions in most of the
error correction schemes and the cost of fault-tolerantly implementing it
exceeds the cost of the Clifford group gates by as much as a factor of hundred
or more [FSG09, AGP06]. It has been shown in [BG16] that quantum circuits
composed of Clifford gates and $t$ T-gates can be simulated on a classical
computer in time which is exponential in $t$. The minimum number of T-gates
required to implement certain unitaries is a quantifier of difficulty in many
algorithms [BG16, BSS16] that try to classically simulate quantum computation.
So, even though alternative fault-tolerance methods such as completely
transversal Clifford+T scheme [PR13] and anyonic quantum computing [Kit03] are
also being explored, minimization of the number of T gates (or T-count) in
quantum circuits remain an important and widely studied goal. It has been
argued in [Fow12, ADMG+16, DMGM20] that it is also important to reduce the
maximum number of T gates in any circuit path (or T-depth).

The Solovay-Kitaev algorithm [Kit97, DN06] guarantees that given an $n$-qubit
unitary $W$, we can generate a circuit with a universal gate set like
Clifford+T, such that the unitary $U$ implemented by the circuit is at most a
certain distance from $W$. A unitary is called exactly implementable by a gate
set if there exists a quantum circuit with these gates, that implements it (up
to some global phase). Otherwise, it is approximately implementable.
Accordingly, a synthesis algorithm can be (a) _exact_ when $U=e^{i\phi}W$
($\phi$ is the global phase); or (b) _approximate_ when $d(U,W)\leq\epsilon$
for some $\epsilon\geq 0$. $d(.)$ is a distance metric. For an unitary $U$
that is exactly implementable by the Clifford+T set, its T-count (denoted by
$\mathcal{T}(U)$) is the minimum number of T-gates required to implement it,
while its T-depth (denoted by $\mathcal{T}_{d}(U)$) is the minimum T-depth of
any circuit that implements it. These definitions can be generalized for
approximately implementable unitaries and have been described in Section 2.2.
In this paper we give algorithm for the following two problems.

#####  $\epsilon$-T-COUNT :

Given an $n$-qubit unitary $W$ and $\epsilon\in\operatorname{\mathbb{R}}_{\geq
0}$, determine the T-count of a unitary $U$ such that
$\mathcal{T}(U)\leq\mathcal{T}(U^{\prime})$, where $U,U^{\prime}$ are
$n$-qubit exactly implementable unitaries and
$d(U,W),d(U^{\prime},W)\leq\epsilon$.

#####  $\epsilon$-T-DEPTH :

Given an $n$-qubit unitary $W$ and $\epsilon\in\operatorname{\mathbb{R}}_{\geq
0}$, determine the T-depth of a unitary $U$ such that
$\mathcal{T}_{d}(U)\leq\mathcal{T}_{d}(U^{\prime})$, where $U,U^{\prime}$ are
$n$-qubit exactly implementable unitaries and
$d(U,W),d(U^{\prime},W)\leq\epsilon$.

$\mathcal{T}(U)$ and $\mathcal{T}_{d}(U)$ are called the $\epsilon$-T-count
and $\epsilon$-T-depth of $W$, respectively. The T-count and T-depth-optimal
circuits of $U$ are called $\epsilon$-T-count-optimal and $\epsilon$-T-depth-
optimal circuit for $W$, respectively. In this paper we use the global phase
invariant distance (Section 2) as the distance metric and not the operator
norm. This is because the global phase invariant distance ignores the global
phase and hence avoids unnecessarily long approximating sequences that achieve
a specific global phase. This can be the reason for the fact that the bound on
T-count of single-qubit z-rotations is less in [KMM15], which works with this
distance, compared to [Sel15, RS16], that work with operator norm. (More
comparisons can be found in [Muk21].) This distance has also been used to
synthesize unitaries in other models like topological quantum computation
[KBS14, JS21]. It is not hard to see that if $\epsilon=0$ then we get the
problem of synthesizing T-count and T-depth-optimal circuits for exactly
implementable unitaries. In this case, both provable [GKMR14, MM21, GMM21] and
much more efficient heuristic [MM21, GMM21] algorithms have been developed
(see Table 1 for a comparison).

Any synthesis algorithm will have complexity at least $O(2^{n})$, the input
size. Placing further optimality constraint makes the problem even harder, in
fact impractical to synthesize on a PC after a certain value of $n$. So re-
synthesis algorithms have been developed which takes a circuit implementing a
unitary and then tries to _reduce_ (not _minimize_) a certain resource (see
for example [AMM14, GLMM20, HS20]). In literature, usually these algorithms do
not account for the complexity of synthesizing the circuit and claim a running
time of $\text{poly}(n)$. A detail study about the relative merit and de-merit
of synthesis and re-synthesis algorithms, is beyond the scope of this work.
But we would like to point out that the importance of designing better
(optimal) synthesis algorithms or studying their complexity cannot be
undermined, not only for theoretical reasons but also for the various
applications they can have. Apart from guaranteeing optimality, they can be
used as sub-routines in compiling large unitaries [HRS18, MSRH20, Muk21],
assess the quality of re-synthesis algorithms, etc.

To the best of our knowledge, before this paper there was no algorithm to
determine $\epsilon$-T-count or $\epsilon$-T-depth of arbitrary multi-qubit
($n\geq 1$) unitaries, considering any distance metric. Previous algorithms
like [KMM15, Sel15, RS16] synthesize $\epsilon$-T-count-optimal circuits for
single qubit Z-rotations. In fact, even if we consider other universal gate
sets like Clifford+V or Clifford+CS, there are no algorithms that work for
arbitrary multi-qubit unitaries and do resource-optimal synthesis. However,
our results can be applied in these alternate bases whenever there is a well-
defined decomposition of an exactly implementable unitary with a trailing
Clifford, as explained in the next section.

Resource |  Type of synthesis |  Type of
algorithm |  Distance | Reference |  $\\#$Qubits ($n$) | Space complexity | Time complexity
---|---|---|---|---|---|---|---
T-count |  Exact |  Provable |  - | [GKMR14] | $>0$ | $O\left(\left(2^{n}\right)^{m}\right)$ | $O\left(\left(2^{n}\right)^{m}\right)$
[MM21] | $>0$ | $O\left(\left(2^{n}\right)^{2\lceil\frac{m}{c}\rceil}\right)$ | $O\left(\left(2^{n}\right)^{2(c-1)\lceil\frac{m}{c}\rceil}\right)$
Heuristic |  - | [MM21] | $>0$ | $\text{poly}(m,2^{n})$ | $\text{poly}(m,2^{n})$
Approx |  Provable |  Op. norm | [RS16] |  $=1$ ($R_{z}$) | $\text{poly}(2^{n})$ | $\text{poly}(\log(1/\epsilon))$
Global Ph. Inv. | [KMM15] |  $=1$ ($R_{z}$) | $\text{poly}(2^{n})$ | $\exp(1/\epsilon)$
Global Ph. Inv. | This work | $>0$ | $\text{poly}(2^{n})$ | $O\left(\left(2^{n}\right)^{m_{\epsilon}}\right)$
T-depth |  Exact |  Provable |  - | [GMM21] | $>0$ | $O\left(\left(12^{n}\right)^{\lceil\frac{d}{c}\rceil}\right)$ | $O\left(\left(12^{n}\right)^{(c-1)\lceil\frac{d}{c}\rceil}\right)$
Heuristic |  - | [GMM21] | $>0$ | $\text{poly}(d,12^{n})$ | $\text{poly}(d,12^{n})$
Approx |  Provable |  Global Ph. Inv. | This work | $>0$ | $\text{poly}(12^{n})$ | $O\left(\left(12^{n}\right)^{d_{\epsilon}}\right)$
Depth |  Exact |  Provable |  - | [AMMR13] | $>0$ | $O\left(\left(2^{kn^{2}}\right)^{d^{\prime}/2}\right)$ | $O\left(\left(2^{kn^{2}}\right)^{d^{\prime}/2}\right)$
[GMM21] | $>0$ | $O\left(\left(2^{kn^{2}}\right)^{\lceil\frac{d^{\prime}}{c}\rceil}\right)$ | $O\left(\left(2^{kn^{2}}\right)^{\lceil(c-1)\frac{d^{\prime}}{c}\rceil}\right)$
Table 1: Comparison of some state-of-the-art optimal synthesis algorithms. The
first column specifies the resouce to be optimized. In the fourth column Op.
norm and Global Ph. Inv. denote the operator norm and global phase invariant
distance respectively. In the sixth column [RS16] and [KMM15] give optimal
results only for 1-qubit $R_{z}(\theta)$ gates. In the last two columns $c\geq
2$ and $k$ are constants. $m_{\epsilon}$ and $d_{\epsilon}$ are the
$\epsilon$-T-count and $\epsilon$-T-depth of an approximately implementable
unitary respectively. The corresponding terms for exactly implementable
unitaries ($\epsilon=0$) are $m$ and $d$ respectively.

###  1.1 Our contributions

In this paper we give algorithms that can be used to synthesize provably
$\epsilon$-T-count and $\epsilon$-T-depth-optimal circuits. We treat
arithmetic operations on the entries of a unitary at unit cost and we do not
account for the bit-complexity associated with specifying or manipulating
them. Suppose the input $n$-qubit unitary is $V$, having size $2^{n}\times
2^{n}$. Then the space complexity of our algorithms, described in Section 3,
is $\text{poly}(2^{n})$. The time complexity is
$\text{poly}\left(\left(2^{n}\right)^{m_{\epsilon}}\right)$, where
$m_{\epsilon}=\mathcal{T}_{\epsilon}(V)$ or $\mathcal{T}_{d\epsilon}(V)$ while
synthesizing $\epsilon$-T-count or $\epsilon$-T-depth optimal circuit
respectively.

For the design and analysis of our algorithm the following results (Section 3)
have been crucial. Suppose $E$ is a unitary that is close to $\mathbb{I}$ in
the global phase invariant distance i.e. $d(E,\mathbb{I})\leq\epsilon$.
$C_{0}$ is an $n$-qubit Clifford operator. $EC_{0}$ _behaves almost like
Clifford_ $C_{0}$ i.e. it _approximately inherits_ some characteristics from
$C_{0}$. First, expanding both $EC_{0}$ and $C_{0}$ in the Pauli basis, we can
see that the absolute value of the coefficients (at each point) are _almost
equal_ (amplitude test). Second, if we expand $(EC_{0})P(EC_{0})^{\dagger}$ in
the Pauli basis then the absolute value of the coefficients is almost $1$ at
$P^{\prime}$ if $C_{0}PC_{0}^{\dagger}=P^{\prime}$, and nearly zero at other
points (conjugation test). These results may be of independent interest and
can be used for resource-optimal synthesis in other bases as described below.

Most universal gate sets consist of Clifford gates and one non-Clifford gate.
Consider one such set Clifford+A, where A is a non-Clifford gate and let
$U_{A}$ is a unitary exactly implementable by this set. Since usually the cost
of fault-tolerantly implementing the non-Clifford gate is higher, so we are
required to optimize the A-count or A-depth, which are defined analogous to
T-count and T-depth. One of the tricks in many resource-optimal-synthesis
algorithms is to find a nice generating set $\mathcal{G}$ such that it has
finite cardinality and $U_{A}$ can be decomposed as follows.

$\displaystyle U_{A}$ $\displaystyle=$ $\displaystyle
e^{i\phi}\left(\prod_{i=m}^{1}G_{i}\right)C_{0}\qquad
G_{i}\in\mathcal{G},C_{0}\in\mathcal{C}_{n},\phi\in[0,2\pi),m=\text{A-count/A-depth}$
(1)

Each $G_{i}\in\mathcal{G}$ has a specific property : A-count 1 or A-depth 1.
Then we design a search algorithm to search for products of $G_{i}$ such that,
we get $U_{A}C_{0}^{-1}$ (up to a global phase), or rather
$U_{A}\left(\prod_{i}G_{i}\right)^{-1}$ is a Clifford. We know that for any
universal gate set not all unitaries are exactly implementable. Let $V_{A}$ is
one such unitary. $U_{A}$ is a unitary such that $d(U_{A},V_{A})\leq\epsilon$
and it has the minimum A-count or A-depth among all exactly implementable
unitaries within $\epsilon$ distance of $V_{A}$. Then we can perform amplitude
test (Theorem 3.1) and conjugation test (Theorem 3.3, Corollary 3.1) and get
an $\epsilon$-A-count-optimal or $\epsilon$-A-depth-optimal decomposition of
$V_{A}$. So for other bases the main task remains to find such nice generating
set, as has been found for Clifford+T [GKMR14] (T-count), [GMM21] (T-depth)
and Clifford+CS [GRT21] (CS-count, only for 2-qubit unitaries). One simple way
of constructing $\mathcal{G}$ for count-optimality is to write $U_{A}$ as
follows.

$\displaystyle U_{A}$ $\displaystyle=$ $\displaystyle
e^{i\phi}C_{1}A_{(q_{1})}C_{2}A_{(q_{2})}C_{3}\ldots C_{m}A_{(q_{m})}C_{0}$
$\displaystyle=$ $\displaystyle
e^{i\phi}\left(C_{1}A_{(q_{1})}C_{1}^{\dagger}\right)\left(C_{1}C_{2}A_{(q_{2})}C_{2}^{\dagger}C_{1}^{\dagger}\right)\ldots\left(C_{1}\ldots
C_{m}A_{(q_{m})}C_{m}^{\dagger}\ldots C_{1}^{\dagger}\right)C_{1}\ldots
C_{m}C_{0}$ $\displaystyle=$ $\displaystyle
e^{i\phi}\left(C_{1}A_{(q_{1})}C_{1}^{\dagger}\right)\left(C_{2}^{\prime}A_{(q_{2})}C_{2}^{\prime\dagger}\right)\ldots\left(C_{m}^{\prime}A_{(q_{m})}C_{m}^{\prime\dagger}\right)C_{0}^{\prime}$

In the above $A_{(q_{i})}$ denotes the A-gate applied on qubit $q_{i}$.
$C_{0},\ldots,C_{m},C_{0}^{\prime}\ldots,C_{m}^{\prime}\in\mathcal{C}_{n}$. So
$\mathcal{G}=\\{CA_{(q_{i})}C^{\dagger}:C\in\mathcal{C}_{n},i\in[n]\\}$, which
is obviously finite since the Clifford group is finite [Ozo08]. But exploiting
some other algebraic properties, maybe we can do much better. A generating set
for depth-optimality can be constructed by conjugating products of at least
$n$ A-gates on distinct qubits by Clifford, as has been done in [GMM21].

We implemented our algorithm to obtain the T-count of controlled
$R_{z}(\theta)$ ($cR_{z}(\theta)$) gate, Givens rotation ($G(\theta)$), 2 and
3-qubit Quantum Fourier Transform (QFT). From Table 1 we see that for exactly
implementable unitaries the provable algorithms like [GKMR14, MM21, GMM21] had
an exponential dependence on T-count and T-depth. Significant improvements
were achieved in [MM21, GMM21], where heuristics were designed that led to
algorithms with a polynomial dependence on T-count and T-depth. The algorithm
in our paper also suffer from exponential dependence on $\epsilon$-T-count and
$\epsilon$-T-depth, which usualy have an inverse dependence on $\epsilon$ i.e.
$\mathcal{T}_{\epsilon},\mathcal{T}_{d\epsilon}\propto f(1/\epsilon)$. We
conjecture that for approximately implementable unitaries it is not possible
to have algorithms with a polynomial dependence on these parameters.

######  Conjecture 1.

It is not possible to have $\epsilon$-T-count or $\epsilon$-T-depth-optimal
synthesis algorithms with complexity
$\text{poly}\left(2^{n},\mathcal{T}_{\epsilon}\right)$ or
$\text{poly}\left(2^{n},\mathcal{T}_{d\epsilon}\right)$ respectively.

However, from the improvements in T-count obtained by us, we feel it is
important to design efficient multi-qubit resource-optimal synthesis
algorithms. In many practical quantum algorithms it is not too difficult to
decompose a large unitary into smaller ones. We can apply composability rules
(for example see [Muk21] for global phase invariant distance) and distribute
the errors among these small unitaries, such that the overall error remains
within the desired bound. The complexity of resource-optimal synthesis
algorithms will determine the maximum size of the component unitaries in a
decomposition.

###  1.2 Related work

Much work has been done to synthesize a circuit for any multi-qubit unitary
(without provable optimality on any resource). Many of them use the Solovay-
Kitaev algorithm [Kit97, KSVV02, DN06, NC10], which is based on a geometric
method of successive approximations. The best bound on the number of gates,
using such methods, has been achieved by Kitaev et al.[KSVV02], which is
$O\left(\log^{c}(1/\epsilon)\right)$, for $c=3+\delta$, where $\delta>0$ is
any positive real number. Several techniques have been developed using
decomposition methods like QR factorization [dBBVA20] or number-theoretic
techniques [KMM13, Sel15]. The latter work for single-qubit unitaries,
achieving a circuit size of $O\left(\log(1/\epsilon)\right)$ and
$\text{poly}(1/\epsilon)$ running time. The numerical exhaustive search
procedure of Fowler [Fow11] works for multi-qubit unitaries, but has
complexity at least $\text{poly}\left((2^{kn^{2}})^{O(1/\epsilon)}\right)$
($k$ is a constant).

Comparitively little has been done for multi-qubit unitaries, when additional
constraints are imposed, like minimizing the T-count or T-depth. A comparison
of some state-of-the-art optimal synthesis algorithms has been given in Table
1. To the best of our knowledge, all the previous works have been exclusively
for single-qubit unitaries, in fact specifically for $R_{z}(\theta)$ gates. A
result of Matsumoto and Amano [MA08] implies that the decomposition of a
typical SU(2) operator into the Clifford+T gate set with accuracy $\epsilon$
requires T-count at least $K+3\log_{2}(1/\epsilon)$, where $K$ is a constant.
The algorithm of Selinger [Sel15] achieves a T-count of
$K+4\log_{2}(1/\epsilon)$ for approximating arbitrary z-rotations. Ross and
Selinger [RS16] developed a probabilistic algorithm that is optimal, given a
factoring oracle or near optimal and has an expected runtime
$O\left(\text{poly}\log(1/\epsilon)\right)$ under some number-theoretic
assumptions. Kliuchnikov, Maslov and Mosca [KMM15] combines search-based and
other methods to achieve optimal T-count, but has runtime $\exp(1/\epsilon)$
that makes it feasible only for precisions up to $\epsilon\approx 10^{-17}$.

However, considerable amount of work has been done to synthesize T-count and
T-depth-optimal circuits for exactly implementable ($\epsilon=0$) multi-qubit
unitaries. These include algorithms with provable optimality like [GKMR14,
MM21, GMM21] that employ meet-in-the-middle (MITM) and nested MITM techniques,
as well as more efficient heuristic algorithms whose optimality depend on some
conjecture [MM21, GMM21].

Work has also been done to approximate single-qubit unitaries in Clifford+V
[Ros15, BGS13, BBG15, KBRY15] basis and perform a CS-count-optimal (exact)
synthesis [GRT21] of two-qubit unitaries in Clifford+CS basis.

###  1.3 Organization

Some necessary preliminary definitions and results have been given in Section
2. We describe our algorithm in Section 3 and provide implementation results
in Section 4. In Section 5 we discuss about T-depth-optimality. Finally we
conclude in Section 6.

##  2 Preliminaries

We write $[K]=\\{1,2,\ldots,K\\}$. We denote the $n\times n$ identity matrix
by $\mathbb{I}_{n}$ or $\mathbb{I}$ if dimension is clear from the context. We
denote the set of $n$-qubit unitaries by $\mathcal{U}_{n}$. The size of an
$n$-qubit unitary is $N\times N$ where $N=2^{n}$. We have given detail
description about the n-qubit Pauli operators ($\mathcal{P}_{n}$), Clifford
group ($\mathcal{C}_{n}$) and the group ($\mathcal{J}_{n}$) generated by the
Clifford and T gates in Appendix A.1 and A.2. In this section we give some
additional definitions and results required for the rest of the paper.

###  2.1 The group generated by Clifford and T gates

We observe the following when expanding a Clifford in the Pauli basis.

######  Fact 2.1 ([BS10]).

If $C\in\mathcal{C}_{n}$ then $\exists r_{P}\in\mathbb{C}$, such that
$C=\sum_{P\in\mathcal{P}_{n}}r_{P}P$. Further, if $r_{P},r_{P^{\prime}}\neq 0$
then $|r_{P}|=|r_{P^{\prime}}|=r$.

######  Fact 2.2.

Let $Q=\sum_{P\in\mathcal{P}_{n}}q_{P}P$ be the expansion of a matrix $Q$ in
the Pauli basis. Then

$q_{P}=\text{Tr}\left(QP\right)/N.$

Further, if $Q$ is a unitary then
$\sum_{P\in\mathcal{P}_{n}}\left|q_{P}\right|^{2}=1$

The proof has been given in Appendix A.1 (Fact A.2) Now consider a Clifford
$C$ which has an expansion, as given in Fact 2.1. Let there be $M$ ($\leq
N^{2}$) such non-zero coefficients. Since $C$ is a unitary, so we apply Fact
2.2 and get the following.

$\displaystyle Mr^{2}=1\quad\implies r=\frac{1}{\sqrt{M}}\geq\frac{1}{N}.$ (2)

A unitary $U$ is exactly implementable if there exists a Clifford+T circuit
that implements it (up to some global phase), else it is approximately
implementable. Specifically, we say $W$ is $\epsilon$-approximately
implementable if there exists an exactly implementable unitary $U$ such that
$d(U,W)\leq\epsilon$. We denote the set of exactly implementable unitaries by
$\mathcal{J}_{n}$. In this paper we use the following distance measure
$d(.,.)$, which has been used in previous works like [Fow11, KMM15] (qubit
based computing), [KBS14, JS21] (topological quantum computing).

######  Definition 2.1 (Global phase invariant distance).

Given two unitaries $U,W\in\mathcal{U}_{n}$, we define the global phase
invariant distance between them as follows.

$\displaystyle
d(U,W)=\sqrt{1-\frac{\left|\text{Tr}\left(U^{\dagger}W\right)\right|}{N}}$

Composability of this distance with respect to tensor product and
multiplication of unitaries, has been derived in [Muk21] (Appendix A.3).

###  2.2 T-count of circuits and unitaries

#### T-count and T-depth of circuits

The _T-count of a circuit_ is the number of T-gates in it.

#### T-count of exactly implementable unitaries

The _T-count of an exactly implementable unitary_ $U\in\mathcal{J}_{n}$,
denoted by $\mathcal{T}(U)$, is the minimum number of T-gates required to
implement it (up to a global phase).

In [GKMR14] the authors proved the following decomposition result, by which
any exactly implementable unitary over the Clifford+T set can be written as a
product of T-count 1 unitaries.

######  Theorem 2.1 (Proposition 1 in [GKMR14] (re-stated)).

For any $U\in\mathcal{J}_{n}$ there exists a phase $\phi\in[0,2\pi)$,
Cliffords $C_{i}\in\mathcal{C}_{n}$ and Paulis
$P_{i}\in\mathcal{P}_{n}\setminus\\{\mathbb{I}\\}$ for $i\in[\mathcal{T}(U)]$
such that

$\displaystyle
U=e^{i\phi}\Big{(}\prod_{i=\mathcal{T}(U)}^{1}R(P_{i})\Big{)}C_{0}$ (3)

where
$R(P_{i})=C_{i}T_{(q_{i})}C_{i}^{\dagger}=\frac{1}{2}(1+e^{\frac{i\pi}{4}})\mathbb{I}+\frac{1}{2}(1-e^{\frac{i\pi}{4}})C_{i}Z_{(q_{i})}C_{i}^{\dagger}=\frac{1}{2}(1+e^{\frac{i\pi}{4}})\mathbb{I}+\frac{1}{2}(1-e^{\frac{i\pi}{4}})P_{i}$.

Using Fact A.1, given $P$ and $Z_{(q_{i})}$ we can compute (circuit for)
$C_{i}$ efficiently such that $P=C_{i}Z_{(q_{i})}C_{i}^{\dagger}$. A
decomposition of $U$, as in Theorem 2.1, with the minimum number of T-gates is
called a _T-count-optimal decomposition_ of $U$.

####  $\epsilon$-T-count of approximately implementable unitaries

Let $W\in\mathcal{U}_{n}$ be an approximately implementable unitary. The
_$\epsilon$ -T-count_ of $W$, denoted by $\mathcal{T}_{\epsilon}(W)$, is equal
to $\mathcal{T}(U)$, the T-count of an exactly implementable unitary
$U\in\mathcal{J}_{n}$ such that $d(U,W)\leq\epsilon$ and
$\mathcal{T}(U)\leq\mathcal{T}(U^{\prime})$ for any
$U^{\prime}\in\mathcal{J}_{n}$ and $d(U^{\prime},W)\leq\epsilon$. We call a
T-count-optimal circuit for any such $U$ as the _$\epsilon$ -T-count-optimal_
circuit for $W$.

It is not hard to see that the above definitions are very general and can be
applied to any unitary $W\in\mathcal{U}_{n}$, exactly or approximately
implementable. If a unitary is exactly implementable then $\epsilon=0$. In
fact, nearly all the following results can be deduced for the special case of
exactly implementable unitaries by applying $\epsilon=0$.

##  3 An exponential time and polynomial space algorithm

In this section we describe an algorithm for determining the
$\epsilon$-T-count of an $n$-qubit unitary $W\in\mathcal{U}_{n}$. This
algorithm is provably optimal and has space and time complexity
$\text{poly}\left(2^{n}\right)$ and
$\text{poly}\left(\left(2^{n}\right)^{\mathcal{T}_{\epsilon}(W)}\right)$.
First we derive some results that will help us design our algorithm.

Let $U$ be an exactly synthesizable unitary such that $d(U,W)\leq\epsilon$.

$\displaystyle
d(W,U)=\sqrt{1-\frac{|\text{Tr}(W^{\dagger}U)|}{N}}\leq\epsilon\implies|\text{Tr}(W^{\dagger}U)|\geq
N(1-\epsilon^{2})$ (4)

Let $U=\left(\prod_{i=t}^{1}R(P_{i})\right)C_{0}e^{i\phi}$ for some
$C_{0}\in\mathcal{C}_{n}$ and global phase $\phi$. And $W=UE$. Then from
Equation 4 we have

$\displaystyle\left|\text{Tr}\left(E^{\dagger}\right)\right|=\left|\text{Tr}\left(E\right)\right|\geq
N(1-\epsilon^{2}).$ (5)

We have

$\displaystyle\left|\text{Tr}\left(W^{\dagger}\left(\prod_{i=t}^{1}R(P_{i})\right)\right)\right|$
$\displaystyle=$
$\displaystyle\left|\text{Tr}\left(E^{\dagger}U^{\dagger}\left(\prod_{i=t}^{1}R(P_{i})\right)\right)\right|$
$\displaystyle=$
$\displaystyle\left|\text{Tr}\left(E^{\dagger}e^{-i\phi}C_{0}^{\dagger}\left(\prod_{i=1}^{t}R^{\dagger}(P_{i})\right)\left(\prod_{i=t}^{1}R(P_{i})\right)\right)\right|$
$\displaystyle=$
$\displaystyle\left|\text{Tr}\left(E^{\dagger}C_{0}^{\dagger}\right)\right|=\left|\text{Tr}\left(EC_{0}\right)\right|$

and similarly

$\displaystyle\left|\text{Tr}\left(W^{\dagger}\left(\prod_{i=t}^{1}R(P_{i})\right)P_{1}\right)\right|=\left|\text{Tr}\left(E^{\dagger}C_{0}^{\dagger}P_{1}\right)\right|=\left|\text{Tr}\left(EC_{0}P_{1}\right)\right|\qquad[P_{1}\in\mathcal{P}_{n}]$
(6)

We now study some properties of $\left|\text{Tr}(EC_{0}P_{1})\right|$, which
will help us check if we have identified a correct $\prod_{i=t}^{1}R(P_{i})$.
For this, we prove the following theorem.

######  Theorem 3.1.

Let $E\in\mathcal{U}_{n}$ be such that
$\left|\text{Tr}\left(E\right)\right|\geq N\left(1-\epsilon^{2}\right)$, for
some $\epsilon\geq 0$. $C_{0}=\sum_{P\in\mathcal{P}_{n}}r_{P}P$ is an
$n$-qubit Clifford. If $\left|\left\\{P:r_{P}\neq 0\right\\}\right|=M$ then

$\displaystyle\frac{1-\epsilon^{2}}{\sqrt{M}}-\sqrt{M}\sqrt{2\epsilon^{2}-\epsilon^{4}}$
$\displaystyle\leq$
$\displaystyle\left|\text{Tr}\left(EC_{0}P_{1}\right)/N\right|\leq\frac{1}{\sqrt{M}}+\sqrt{M}\sqrt{2\epsilon^{2}-\epsilon^{4}}\quad[\text{if
}r_{P_{1}}\neq 0]$ (7) $\displaystyle\text{and}\quad 0$ $\displaystyle\leq$
$\displaystyle\left|\text{Tr}\left(EC_{0}P_{1}\right)/N\right|\leq\sqrt{M}\sqrt{2\epsilon^{2}-\epsilon^{4}}\quad[\text{if
}r_{P_{1}}=0]$ (8)

###### Proof.

Since $E$ is unitary, we can expand it in the Pauli basis as

$\displaystyle E=\sum_{P\in\mathcal{P}_{n}}e_{P}P$ (9)

where $e_{P}=\text{Tr}\left(EP\right)/N$ and
$\sum_{P}\left|e_{P}\right|^{2}=1$ (Fact 2.2). Thus

$\displaystyle|e_{\mathbb{I}}|$ $\displaystyle=$
$\displaystyle\left|\text{Tr}\left(E\right)/N\right|\geq(1-\epsilon^{2})\qquad[\text{From
inequality \ref{eqn:trE}}]$ (10) $\displaystyle\text{and
}\sum_{P\neq\mathbb{I}}|e_{P}|^{2}$ $\displaystyle\leq$ $\displaystyle
1-(1-\epsilon^{2})^{2}=2\epsilon^{2}-\epsilon^{4}$ (11)
$\displaystyle\implies|e_{P}|$ $\displaystyle\leq$
$\displaystyle\sqrt{2\epsilon^{2}-\epsilon^{4}}\qquad[\forall
P\neq\mathbb{I}]$ (12)

Since $C_{0}=\sum_{P\in\mathcal{P}_{n}}r_{P}P$, from Fact 2.1 and Equation 2,
we know that $|r_{P}|=r=\frac{1}{\sqrt{M}}$ or $r_{P}=0$. Then

$\displaystyle EC_{0}$ $\displaystyle=$
$\displaystyle\sum_{P\in\mathcal{P}_{n}}r_{P}EP=\sum_{\begin{subarray}{c}P\in\mathcal{P}_{n}\\\
r_{P}\neq 0\end{subarray}}r_{P}EP$ $\displaystyle\text{ and }EC_{0}P_{1}$
$\displaystyle=$ $\displaystyle
r_{P_{1}}E+\sum_{\begin{subarray}{c}P\in\mathcal{P}_{n}\setminus\\{P_{1}\\}\\\
r_{P}\neq 0\end{subarray}}r_{P}EP_{1}^{\prime}\quad\text{where
}P_{1}\in\mathcal{P}_{n}\setminus\\{\mathbb{I}\\}\text{ and
}PP_{1}=P_{1}^{\prime}\neq\mathbb{I}.$

So

$\displaystyle\left|\text{Tr}\left(EC_{0}P_{1}\right)\right|$ $\displaystyle=$
$\displaystyle\left|r_{P_{1}}\text{Tr}\left(E\right)+\sum_{\begin{subarray}{c}P\in\mathcal{P}_{n}\setminus\\{P_{1}\\}\\\
r_{P}\neq 0\end{subarray}}r_{P}\text{Tr}\left(EP_{1}^{\prime}\right)\right|$
$\displaystyle=$
$\displaystyle\left|\left(r_{P_{1}}e_{\mathbb{I}}+\sum_{\begin{subarray}{c}P\in\mathcal{P}_{n}\setminus\\{P_{1}\\}\\\
r_{P}\neq
0\end{subarray}}r_{P}e_{P_{1}^{\prime}}\right)\right|N\quad[\text{Using Fact
\ref{fact:trCoeff}}]$ $\displaystyle\leq$
$\displaystyle\left|r_{P_{1}}\right|\left|e_{\mathbb{I}}\right|N+\sum_{\begin{subarray}{c}P\in\mathcal{P}_{n}\setminus\\{P_{1}\\}\\\
r_{P}\neq
0\end{subarray}}\left|r_{P}\right|\left|e_{P_{1}^{\prime}}\right|N\quad[\because|e_{\mathbb{I}}|\leq
1]$ $\displaystyle\leq$
$\displaystyle\left|r_{P_{1}}\right|N+\sum_{\begin{subarray}{c}P\in\mathcal{P}_{n}\setminus\\{P_{1}\\}\\\
r_{P}\neq
0\end{subarray}}r\sqrt{2\epsilon^{2}-\epsilon^{4}}N\qquad[\text{Using
inequality \ref{eqn:absE}}]$ (14)

From equation 3 we can also obtain the following lower bound.

$\displaystyle\left|\text{Tr}\left(EC_{0}P_{1}\right)\right|$
$\displaystyle\geq$
$\displaystyle\left|r_{P_{1}}\right|\left|e_{\mathbb{I}}\right|N-\sum_{\begin{subarray}{c}P\in\mathcal{P}_{n}\setminus\\{P_{1}\\}\\\
r_{P}\neq 0\end{subarray}}\left|r_{P}\right|\left|e_{P_{1}^{\prime}}\right|N$
(15) $\displaystyle\geq$
$\displaystyle\left|r_{P_{1}}\right|(1-\epsilon^{2})N-\sum_{\begin{subarray}{c}P\in\mathcal{P}_{n}\setminus\\{P_{1}\\}\\\
r_{P}\neq
0\end{subarray}}r\sqrt{2\epsilon^{2}-\epsilon^{4}}N\quad[\text{Inequality
\ref{eqn:absE} and \ref{eqn:eI}}]$

Since $r=\frac{1}{\sqrt{M}}$, we prove the following inequalities.

$\displaystyle\frac{1-\epsilon^{2}}{\sqrt{M}}-\sqrt{M}\sqrt{2\epsilon^{2}-\epsilon^{4}}$
$\displaystyle\leq$
$\displaystyle\left|\text{Tr}\left(EC_{0}P_{1}\right)/N\right|\leq\frac{1}{\sqrt{M}}+\sqrt{M}\sqrt{2\epsilon^{2}-\epsilon^{4}}\quad[\text{if
}r_{P_{1}}\neq 0]$ $\displaystyle\text{and}\quad 0$ $\displaystyle\leq$
$\displaystyle\left|\text{Tr}\left(EC_{0}P_{1}\right)/N\right|\leq\sqrt{M}\sqrt{2\epsilon^{2}-\epsilon^{4}}\quad[\text{if
}r_{P_{1}}=0]$

∎

Basically this theorem says that if $E$ is close to identity then distribution
of absolute-value-coefficients of $EC_{0}$ and $C_{0}$ in the Pauli basis
expansion, is almost similar. In fact, we can have a more general theorem that
can be deduced from the calculations in Theorem 3.1.

######  Theorem 3.2.

Let $E\in\mathcal{U}_{n}$ be such that
$\left|\text{Tr}\left(E\right)\right|\geq N\left(1-\epsilon^{2}\right)$, for
some $\epsilon\geq 0$. $Q=\sum_{P\in\mathcal{P}_{n}}q_{P}P$ is an $n$-qubit
unitary. Then for each $P^{\prime}\in\mathcal{P}_{n}$,

$\displaystyle(1-\epsilon^{2})|q_{P^{\prime}}|-\sum_{P\in\mathcal{P}_{n}\setminus\\{P^{\prime}\\}}|q_{P}|\sqrt{2\epsilon^{2}-\epsilon^{4}}$
$\displaystyle\leq$
$\displaystyle\left|\text{Tr}\left(EQP^{\prime}\right)/N\right|\leq|q_{P^{\prime}}|+\sum_{P\in\mathcal{P}_{n}\setminus\\{P^{\prime}\\}}|q_{P}|\sqrt{2\epsilon^{2}-\epsilon^{4}}.$

So we can define two sets $\mathcal{S}_{1}$ and $\mathcal{S}_{0}$ as follows.

$\displaystyle\mathcal{S}_{1}$ $\displaystyle=$
$\displaystyle\left\\{\left|\text{Tr}\left(EC_{0}P_{1}\right)/N\right|:r_{P_{1}}\neq
0\right\\}$ (16) $\displaystyle\mathcal{S}_{0}$ $\displaystyle=$
$\displaystyle\left\\{\left|\text{Tr}\left(EC_{0}P_{1}\right)/N\right|:r_{P_{1}}=0\right\\}$
(17)

From our results so far, it follows that for small enough $\epsilon$ (which is
usually the case in nearly all applications) the values in $\mathcal{S}_{1}$
are nearly equal, while those in $\mathcal{S}_{0}$ are nearly $0$. Let
$\Delta=\max_{t_{1}\in\mathcal{S}_{1},t_{0}\in\mathcal{S}_{0}}(t_{1}-t_{0})$.
Then to get a positive difference we have the following.

$\displaystyle\Delta$ $\displaystyle\geq$
$\displaystyle\frac{1-\epsilon^{2}}{\sqrt{M}}-2\sqrt{M(2\epsilon^{2}-\epsilon^{4})}>0$
$\displaystyle\implies$
$\displaystyle\epsilon^{4}-2\epsilon^{2}+\frac{1}{1+4M^{2}}\geq 0$

Solving this we obtain the following conditions.

$\displaystyle\epsilon^{2}\geq
1+\sqrt{1-\frac{1}{1+4M^{2}}}\quad\text{or}\quad\epsilon^{2}\leq
1-\sqrt{1-\frac{1}{1+4M^{2}}}$ (18)

Since usually $\epsilon<1$, so we consider the second inequality. Expanding
the term in the square root we obtain

$\displaystyle\epsilon^{2}\leq\frac{1}{2}\cdot\frac{1}{1+4M^{2}}+\frac{1}{2!}\cdot\frac{1}{2\cdot
2}\left(\frac{1}{1+4M^{2}}\right)^{2}+\frac{1}{3!}\cdot\frac{3}{2\cdot 2\cdot
2}\left(\frac{1}{1+4M^{2}}\right)^{3}+\ldots$

Since this function decreases with $M$ and $1\leq M\leq N^{2}$, so we can say
that

$\displaystyle\epsilon^{2}\leq 0.105572809\quad\implies\epsilon\leq
0.3249196962.$ (19)

For all practical purposes, the value of $\epsilon$ is much smaller than this.
So we can easily distinguish the sets $\mathcal{S}_{0}$ and $\mathcal{S}_{1}$.

###  3.1 Algorithm

Now we are in a position to describe our algorithms. First we describe an
algorithm, $\mathcal{A}_{MIN}$ (Algorithm 1), that determines the
$\epsilon$-T-count of a unitary $W\in\mathcal{U}_{n}$. This is an iterative
procedure, where in every iteration we decide if $\mathcal{T}_{\epsilon}(W)=m$
for increasing values of a variable $m$. The for loop (steps 2-8) tests if $W$
is $\epsilon$-close to a Clifford.

1

Input: (i) $W\in\mathcal{U}_{n}$, (ii) $\epsilon\geq 0$.

2

Output: $\mathcal{T}_{\epsilon}(W)$.

3

4$\mathcal{S}_{c}\leftarrow\\{\left|\text{Tr}\left(W^{\dagger}P\right)/N\right|:P\in\mathcal{P}_{n}\\}$
and sort this set in descending order ;

5 for  _$M=1,2\ldots N^{2}$ _ do

6 $\mathcal{S}_{1}\leftarrow$ First $M$ terms in $\mathcal{S}_{c}$ ;

7 $\mathcal{S}_{0}=\mathcal{S}_{c}\setminus\mathcal{S}_{1}$ ;

8 if  _each term in
$\mathcal{S}_{1}\in\left[\frac{1-\epsilon^{2}}{\sqrt{M}}-\sqrt{M(2\epsilon^{2}-\epsilon^{4})},\frac{1}{\sqrt{M}}+\sqrt{M(2\epsilon^{2}-\epsilon^{4})}\right]$
and each term in
$\mathcal{S}_{0}\in\left[0,\sqrt{M(2\epsilon^{2}-\epsilon^{4})}\right]$_ then

9 return $0$ if $W$ passes conjugation test;

10

11 end if

12

13 end for

14$m\leftarrow 1$, $decision\leftarrow\text{NO}$ ;

15 while  _(1)_ do

16 $decision\leftarrow\mathcal{A}_{DECIDE}(W,m,\epsilon)$ ;

17 if  _$decision==\text{YES}$_ then

18 return $m$ ;

19

20 else

21 $m\leftarrow m+1$ ;

22

23 end if

24

25 end while

26

Algorithm 1 $\mathcal{A}_{MIN}$

1

Input: (i) $W\in\mathcal{U}_{n}$, (ii) integer $m>0$, (iii) $\epsilon\geq 0$.

2

Output: YES if $\exists U\in\mathcal{J}_{n}$ such that $d(U,W)\leq\epsilon$
and $\mathcal{T}(U)\leq m$; else NO.

3

4$\mathcal{S}\leftarrow\\{R(P):P\neq\mathbb{I}\\}$ ;

5

6for  _every $\widetilde{U}=\prod_{i=m}^{1}U_{j}$ such that
$U_{i}\in\mathcal{S}$ and $U_{i}\neq U_{i+1}$_ do

7 $W^{\prime}=W^{\dagger}\widetilde{U}$ ;

8
$\mathcal{S}_{c}\leftarrow\\{\left|\text{Tr}\left(W^{\prime}P\right)/N\right|:P\in\mathcal{P}_{n}\\}$
and sort this set in descending order ;

9 for  _$M=1,2\ldots N^{2}$_ do

10 $\mathcal{S}_{1}\leftarrow$ First $M$ terms in $\mathcal{S}_{c}$ ;

11 $\mathcal{S}_{0}=\mathcal{S}_{c}\setminus\mathcal{S}_{1}$ ;

12 if  _each term in
$\mathcal{S}_{1}\in\left[\frac{1-\epsilon^{2}}{\sqrt{M}}-\sqrt{M(2\epsilon^{2}-\epsilon^{4})},\frac{1}{\sqrt{M}}+\sqrt{M(2\epsilon^{2}-\epsilon^{4})}\right]$
and each term in
$\mathcal{S}_{0}\in\left[0,\sqrt{M(2\epsilon^{2}-\epsilon^{4})}\right]$_ then

13 return YES if $W^{\prime}$ passes conjugation test;

14

15 end if

16

17 end for

18

19 end for

20return NO;

Algorithm 2 $\mathcal{A}_{DECIDE}$

The main idea to solve the decision version is as follows. Suppose we have to
test if $\mathcal{T}_{\epsilon}(W)=m$. From the definitions given in Section
2.2, we know that if this is true then $\exists U\in\mathcal{J}_{n}$ such that
$\mathcal{T}(U)=m$. Let $U=\left(\prod_{i=m}^{1}U_{i}\right)C_{0}$ where
$C_{0}\in\mathcal{C}_{n}$ and $U_{i}\in\\{R(P):P\neq\mathbb{I}\\}$. Let
$\widetilde{U}=\prod_{i=m}^{1}U_{i}$. To test if we have guessed the correct
$\widetilde{U}$, we can apply the results deduced in the previous section.
Specifically we calculate $W^{\prime}=W^{\dagger}\widetilde{U}$ and then
calculate the set
$\mathcal{S}_{c}=\left\\{|\text{Tr}(W^{\prime}P)/N|:P\in\mathcal{P}_{n}\right\\}$,
of coefficients. Then we check if we can distinguish two subsets
$\mathcal{S}_{0}$ and $\mathcal{S}_{1}$, as shown in Equation 16 and 17, for
some $1\leq M\leq N^{2}$. Further details have been given in Algorithm 2. Let
us call this the amplitude test. After passing this test we have a unitary of
the form $E^{\dagger}Q$ where $Q$ is a unitary. This test sort of _filters
out_ the approximate values of the coefficients of $Q$ in the Pauli basis
(Theorem 3.2). So after passing this test $Q$ will be a unitary with _equal_
or _nearly equal_ amplitudes or coefficients (absolute value) at some points
and zero or nearly zero at other points.

To ensure $Q$ is a Clifford we perform the conjugation test for further
verification. We calculate $(E^{\dagger}Q)P^{\prime}(E^{\dagger}Q)^{\dagger}$,
for each $P^{\prime}\in\mathcal{P}_{n}$. Now we prove the following result.

######  Theorem 3.3.

Let $Q$ be an $n$-qubit unitary and
$P^{\prime}\in\mathcal{P}_{n}\setminus\\{\mathbb{I}\\}$ such that
$QP^{\prime}Q^{\dagger}=\sum_{\hat{P}}\alpha_{\hat{P}}\hat{P}$, where
$\alpha_{\hat{P}}\in\mathbb{C}$. Then

$\displaystyle|\alpha_{\hat{P}}|(1-3\epsilon^{2}+\epsilon^{4})$
$\displaystyle\leq$
$\displaystyle\left|\text{Tr}\left((E^{\dagger}QP^{\prime}Q^{\dagger}E)\overline{P}\right)\right|/N\leq|\alpha_{\hat{P}}|\qquad\text{if
}\overline{P}=\hat{P}\text{ such that }\alpha_{\hat{P}}\neq 0$ $\displaystyle
0$ $\displaystyle\leq$
$\displaystyle\left|\text{Tr}\left((E^{\dagger}QP^{\prime}Q^{\dagger}E)\overline{P}\right)\right|/N\leq\max_{\hat{P}:\alpha_{\hat{P}}\neq
0}|\alpha_{\hat{P}}|\cdot(2\epsilon^{2}-\epsilon^{4})\qquad\text{else }$

###### Proof.

We have the following.

$\displaystyle E^{\dagger}(QP^{\prime}Q^{\dagger})E$ $\displaystyle=$
$\displaystyle\sum_{P}|e_{P}|^{2}P\left(\sum_{\hat{P}}\alpha_{\hat{P}}\hat{P}\right)P+\sum_{P\neq\tilde{P}}\overline{e_{P}}e_{\tilde{P}}P\left(\sum_{\hat{P}}\alpha_{\hat{P}}\hat{P}\right)\tilde{P}$
(20) $\displaystyle=$
$\displaystyle|e_{\mathbb{I}}|^{2}\sum_{\hat{P}}\alpha_{\hat{P}}\hat{P}+\sum_{P\neq\mathbb{I},\hat{P}}|e_{P}|^{2}\alpha_{\hat{P}}P\hat{P}P+\sum_{P\neq\tilde{P},\hat{P}}\overline{e_{P}}e_{\tilde{P}}\alpha_{\hat{P}}P\hat{P}\tilde{P}$

If $\overline{P}=\hat{P}$ such that $\alpha_{\hat{P}}\neq 0$ then we have

$\displaystyle(E^{\dagger}QP^{\prime}Q^{\dagger}E)\overline{P}$
$\displaystyle=$
$\displaystyle|e_{\mathbb{I}}|^{2}\alpha_{\hat{P}}\mathbb{I}+\sum_{P\neq\mathbb{I}}|e_{P}|^{2}\alpha_{\hat{P}}(\pm\mathbb{I})$
$\displaystyle\text{So,
}\text{Tr}\left((E^{\dagger}QP^{\prime}Q^{\dagger}E)\overline{P}\right)/N$
$\displaystyle\leq$
$\displaystyle\alpha_{\hat{P}}\sum_{P}|e_{P}|^{2}=\alpha_{\hat{P}}\qquad[\text{Fact
}\ref{fact:trCoeff}]$

The lower bound follows from Equations 10 and 11.

If $\overline{P}=\hat{P}$ such that $\alpha_{\hat{P}}=0$ then after taking
trace we can have a non-zero value only from the third summand in Equation 20.
Thus the bounds follow from Equations 11 and 12.

∎

And we have the following corollary.

######  Corollary 3.1.

Let $Q\in\mathcal{C}_{n}$ and $P^{\prime}\in\mathcal{P}_{n}$ such that
$QPQ^{\dagger}=P^{\prime\prime}\in\mathcal{P}_{n}$. Then

$\displaystyle(1-3\epsilon^{2}+\epsilon^{4})$ $\displaystyle\leq$
$\displaystyle\left|\text{Tr}\left((E^{\dagger}QP^{\prime}Q^{\dagger}E)\overline{P}\right)\right|/N\leq
1\qquad\text{if }\overline{P}=P^{\prime\prime}$ $\displaystyle 0$
$\displaystyle\leq$
$\displaystyle\left|\text{Tr}\left((E^{\dagger}QP^{\prime}Q^{\dagger}E)\overline{P}\right)\right|/N\leq(2\epsilon^{2}-\epsilon^{4})\qquad\text{else
}$

The above theorem and corollary basically says that $EC_{0}$ (or
$E^{\dagger}C_{0}$) _approximately_ inherits the conjugation property of
$C_{0}$. For each $P\in\mathcal{P}_{n}$, if we expand $C_{0}PC_{0}^{\dagger}$
in the Pauli basis then the absolute value of the coefficients has value 1 at
one point, 0 in the rest. If we expand $EC_{0}PC_{0}^{\dagger}E^{\dagger}$ in
the Pauli basis then one of the coefficients (absolute value) will be almost 1
and the rest will be almost 0.

This pattern will not show for at least one Pauli $P\in\mathcal{P}_{n}$ if we
have $E^{\dagger}Q$, where $Q\notin\mathcal{C}_{n}$, after the amplitude test.
If $Q=\sum_{P}q_{P}P$ then we have

$\displaystyle QP^{\prime}Q^{\dagger}$ $\displaystyle=$
$\displaystyle\sum_{P}|q_{P}|^{2}PP^{\prime}P+\sum_{P\neq\tilde{P}}q_{p}\overline{q_{\tilde{P}}}PP^{\prime}\tilde{P}=\sum_{\hat{P}}\alpha_{\hat{P}}\hat{P}\quad[\text{Following
Theorem }\ref{thm:conj}]$

Now $PP^{\prime}P\neq PP^{\prime}\tilde{P}$, since $P\neq\tilde{P}$. If
$\hat{P}=PP^{\prime}P$ such that $q_{P}\neq 0$ then
$\alpha_{\hat{P}}=|q_{P}|^{2}\in\operatorname{\mathbb{R}}$. Since $Q$ passed
the amplitude test and is not a Clifford so $\alpha_{\hat{P}}$ is close to
$\frac{1}{M}$ in at least $M>1$ points i.e. $\hat{P}=PP^{\prime}P$ where
$q_{P}\neq 0$. Thus $\exists P\in\mathcal{P}_{n}$ such that if we expand
$EQPQ^{\dagger}E^{\dagger}$ or $E^{\dagger}QPQ^{\dagger}E$ in the Pauli basis
then the _spike in the amplitudes_ will be in at least two points.

###  3.2 Synthesizing T-count and T-depth optimal circuits

So far we have been able to determine $\mathcal{T}_{\epsilon}(W)$ for any
$W\in\mathcal{U}_{n}$. We now describe how we can synthesize
$\epsilon$-T-count-optimal circuit for $W$, using the above algorithms. It is
easy to see that $\mathcal{A}_{DECIDE}$ can return a sequence
$\\{U_{m},\ldots,U_{1}\\}$ of unitaries such that
$U=\left(\prod_{i=m}^{1}U_{i}\right)C_{0}$ (for some
$C_{0}\in\mathcal{C}_{n}$) and $\mathcal{T}(U)=\mathcal{T}_{\epsilon}(W)$. We
can efficiently construct circuits for each $U_{i}=\prod_{j}R(P_{j})$ using
Fact A.1 in Section 2. So what remains, is to determine $C_{0}$. Then we can
efficiently construct a circuit for it, for example, by using results in
[AG04].

If $W=UE$ then at step 2 of Algorithm 2 we calculate
$W^{\prime}=W^{\dagger}\widetilde{U}=E^{\dagger}C_{0}^{\dagger}$, where
$\widetilde{U}=\prod_{i=m}^{1}U_{i}$. From Algorithm 2 we can also obtain the
following information : (1) set $\mathcal{S}_{1}$ as defined in Equation 16,
(2) $M=|\mathcal{S}_{1}|$. Thus we can calculate $r=\frac{1}{\sqrt{M}}$ and
from step 2 we can actucally calculate the set
$\widetilde{\mathcal{S}_{1}}=\left\\{(t_{P},P):|t_{P}|=|\text{Tr}(W^{\prime}P)/N|\in\mathcal{S}_{1}\right\\}$.
From Equation 3 we can say that for small enough $\epsilon$ (say
$<<\frac{1}{M}$) we have

$\displaystyle\frac{\text{Tr}\left(E^{\dagger}C_{0}^{\dagger}P_{1}\right)}{\text{Tr}\left(E^{\dagger}C_{0}^{\dagger}P_{2}\right)}$
$\displaystyle\approx$
$\displaystyle\frac{\overline{r_{P_{1}}}}{\overline{r_{P_{2}}}}$ (21)

We perform the following steps.

  1. 1.

Calculate
$a_{P}=\frac{t_{P}}{t_{\mathbb{I}}}=\frac{\text{Tr}(W^{\prime}P)}{\text{Tr}(W^{\prime})}$,
where $(t_{P},P)\in\widetilde{\mathcal{S}_{1}}$ (or equivalently
$|t_{P}|\in\mathcal{S}_{1}$). We must remember that
$(t_{\mathbb{I}},\mathbb{I})\in\widetilde{\mathcal{S}_{1}}$.

We explained that from Equation 3,
$a_{P}\approx\frac{\overline{r_{P}}}{\overline{r_{\mathbb{I}}}}$. From Fact
2.1 we know that
$\frac{|\overline{r_{P}}|}{|\overline{r_{\mathbb{I}}}|}=\frac{|r_{P}|}{|r_{\mathbb{I}}|}=1$.
So we adjust the fractions such that their absolute value is $1$. For small
enough $\epsilon$ this adjustment is not much and so with a slight abuse we
use the same notation for the adjusted values.

  2. 2.

Select $c,d\in\operatorname{\mathbb{R}}$ such that $c^{2}+d^{2}=r^{2}$. Let
$\widetilde{r_{\mathbb{I}}}=c+di$. Then we claim that the Clifford
$\widetilde{C_{0}}=\widetilde{r_{\mathbb{I}}}\sum_{P:r_{P}\neq
0}\overline{a_{P}}P$ is sufficient for our purpose.

It is not hard to see that $\widetilde{C_{0}}=e^{i\phi}C_{0}$ for some
$\phi\in[0,2\pi)$. Thus if
$U^{\prime}=\left(\prod_{i=m}^{1}U_{i}\right)\widetilde{C_{0}}$, then
$\mathcal{T}(U^{\prime})=\mathcal{T}(U)$ and $d(U^{\prime},W)\leq\epsilon$.

### Complexity

We know $\left|\left\\{R(P):P\in\mathcal{P}_{n}\right\\}\right|=N^{2}=2^{2n}$.
It is not too hard to see that the time complexity of $\mathcal{A}_{MIN}$ is
$O\left(\left(4^{n}\right)^{\mathcal{T}_{\epsilon}(W)}\right)$. The space
complexity is $O\left(4^{n}\right)$ since we need to store the set of $R(P)$.

##  4 Implementation results

We implemented our algorithm $\mathcal{A}_{MIN}$ in standard C++17 on an
Intel(R) Core(TM) i7-7700K CPU at 4.2GHz, with 8 cores and 16 GB RAM, running
Debian Linux 9.13. We used OpenMP [Ope] for parallelization and the Eigen 3
matrix library [Eig] for some of the matrix operations.

$\epsilon$ | Avg. $\mathcal{T}^{\epsilon}(cR_{z}(\theta))$ | Avg. $\mathcal{T}^{\epsilon}(R_{z}(\theta))$ | Avg. $\\#$T by Eq. 23
---|---|---|---
$10^{-2}$ | 3.8 | 16.055 | 23.055
$5\times 10^{-3}$ | 4.6 | 19.12 | 26.12
$3\times 10^{-3}$ | 5.7 | 21.382 | 28.382
Table 2: Comparison of T-count of $cR_{z}(\theta)$ obtained by our algorithm,
with the upper bound on number of T-gates obtained by Equation 23. The third
column gives the T-count of $R_{z}(\theta)$, obtained by [KMM15]. All values
are averaged over $\theta$.

##### Controlled rotation :

We implemented $\mathcal{A}_{MIN}$ to return the T-count optimal decomposition
of control $R_{z}(\theta)$ gates, $cR_{z}(\theta)$ (Equation 27), where
$\theta=\frac{2\pi k}{1000}$ and $k$ varies from $1$ to $1000$ in steps of
$50$. Control $R_{z}(\theta)$ gates appear in many important quantum
algorithms like Quantum Fourier Transform (QFT), phase estimation,
factorization, order finding, hidden subgroup problem, Grover’s search [NC10],
quantum simulations [JWM+12, SBW+21]. Before our work there was no algorithm
for T-count of multi-qubit approximately implementable unitaries. If possible
they were decomposed into a sequence of $R_{z}(\theta)$ gates, for which we
know the following empirical formula from [KMM15], where the T-count is
averaged over $\theta$.

$\displaystyle\mathcal{T}^{\epsilon}(R_{z}(\theta))$ $\displaystyle=$
$\displaystyle 3.067\log_{2}\left(1/\epsilon\right)-4.322$ (22)

Then an upper bound was given by adding the T-count of component unitaries.
For example, $cR_{z}(\theta)$ can be implemented by reducing to Fredkin gate
(T-count=7 [GKMR14]) and $R_{z}(\theta)$. So an upper bound on the T-count of
$cR_{z}(\theta)$, averaged over $\theta$ is as follows.

$\displaystyle\\#\text{T}(cR_{z}(\theta))=3.067\log_{2}\left(1/\epsilon\right)-4.322+7=3.067\log_{2}\left(1/\epsilon\right)+2.678$
(23)

In Table 2 we have compared the T-count obtained by our algorithm with the
upper bound in Equation 23. All the values are averaged over the angle
$\theta$, for a given $\epsilon$. We find that the T-count obtained by us is
much less. We could consider till $\epsilon=3\times 10^{-3}$ due to resource-
constraints. For lower precision, the time taken would be very large. The
numerical results of this subsection, together with instructions on how to
reproduce them, are available online at https://github.com/vsoftco/t-depth.
Here we emphasize that there are other formulas, for example in [Sel15, RS16],
that relate the T-count of $R_{z}(\theta)$ with $\epsilon$ in operator norm.
But these bounds are worse than in [KMM15], which considers $\epsilon$ in
global phase invariant distance, like we do.

##### Givens rotation :

Givens rotation appears in a number of quantum chemistry aplications
[ADMQ+21]. We have implemented $\mathcal{A}_{MIN}$ to return the T-count
optimal decomposition of 2-qubit Givens rotation, $G(\theta)$ (Equation 28),
where $\theta=\frac{2\pi k}{1000}$ and $k$ varies from 1 to 1000 in steps of
50. A plot of the T-count of $cR_{z}(\theta)$ and $G(\theta)$ for different
values of $\theta$ has been given in Figure 1 of Appendix B.

##### Quantum Fourier Transform (QFT) :

We implemented $\mathcal{A}_{MIN}$ to return the T-count optimal decomposition
of 2 and 3-qubit QFT. We used Quantum$\\#$ [Ghe18] to obtain the unitary from
the circuit given in [NC10] (Figure 2 in Appendix B). The $\epsilon$-T-count
obtained for various values of $\epsilon$ have been given in Table 3.

$\\#$Qubits | $\epsilon$ |  $\epsilon$-T-count
---|---|---
2 | $\geq 10^{-17}$ | $3$
$10^{-18}$ | $5$
$10^{-19}$ | $5$
3 | $10^{-2}$ | $0$
$10^{-3}$ | $3$
| $10^{-4}$ | $4$
Table 3: $\epsilon$-T-count of 2 and 3 qubit QFT.

### Number of T-gates required for Quantum Fourier Transform (QFT)

To illustrate further, let us consider the $n$-qubit circuit of Quantum
Fourier Transform [NC10], which has $N_{R}=\frac{n(n-1)}{2}$ 2-qubit
controlled unitaries, each of which can be realized by $cR_{z}(\theta)$ gates.
We assume that the circuit has $N_{R}$ such $cR_{z}(\theta)$ gates. If we
allot $\epsilon_{r}=3\times 10^{-3}$ error to each gate then after composing
[Muk21] the error of the overall QFT circuit is given by Equation 26 in
Appendix A.3.

$\displaystyle\epsilon$ $\displaystyle\approx$
$\displaystyle\sqrt{N_{R}\cdot\epsilon_{r}^{2}+2\sum_{i=2}^{N_{R}}\epsilon_{r}(i-1)\epsilon_{r}\sqrt{\max\\{0,1-\epsilon_{r}^{2}-((i-1)\epsilon_{r})^{2}\\}}}=0.545137$

considering $n=20$ and hence $N_{R}=190$. Number of T-gates required to
implement this circuit with error $\epsilon=0.545137$ is about $N_{R}\times
5.7\approx 1083$ (Table 2). If we would have first decomposed each
$cR_{z}(\theta)$ gate into $R_{z}(\theta)$ gate then estimate on the number of
T-gates would be $N_{R}\times 28.382\approx 5393>1083$.

##  5 Discussion : T-depth-optimal synthesis

The algorithms 1 ($\mathcal{A}_{MIN}$) and 2 ($\mathcal{A}_{DECIDE}$) can be
used for T-depth-optimal-synthesis of any multi-qubit unitary, since we know
there is a finite generating set [GMM21] such that any exactly implementable
unitary can be written as a product of elements from this set and a Clifford.
We first give some definitions.

#### T-depth of circuits

Suppose the unitary $U$ implemented by a circuit is written as a product
$U=U_{m}U_{m-1}\ldots U_{1}$ such that each $U_{i}$ can be implemented by a
circuit in which all the gates can act in parallel or simultaneously. We say
$U_{i}$ has depth 1 and $m$ is the _depth_ of the circuit. The _T-depth of a
circuit_ is the number of unitaries $U_{i}$ where the
$\text{T}/\text{T}^{\dagger}$ gate is the only non-Clifford gate and all the
$\text{T}/\text{T}^{\dagger}$ gates can act in parallel111The remaining
Clifford gates within each $U_{i}$ may not act in parallel..

#### T-depth of exactly implementable unitaries

The _T-depth_ or _min-T-depth of an exactly synthesizable unitary_
$U\in\mathcal{J}_{n}$, denoted by $\mathcal{T}_{d}(U)$, is the minimum T-depth
of a Clifford+T circuit that implements it (up to a global phase).

In [GMM21] a subset,
$\mathbb{V}_{n}=\\{\prod_{i\in[n]}C\overline{T}_{(i)}C^{\dagger},C\in\mathcal{C}_{n},\overline{T}\in\\{\text{T},\text{T}^{\dagger},\mathbb{I}\\}\\}$,
of T-depth-1 unitaries has been defined. An equivalent constructive definition
has been given in Appendix A.4. It has been shown that $|\mathbb{V}_{n}|\leq
2n\cdot 12^{n}$ and any unitary $U\in\mathcal{J}_{n}$ can be written as

$\displaystyle
U=e^{i\phi}\left(\prod_{i=d}^{1}V_{i}\right)C_{0}\qquad\text{where
}V_{i}\in\mathbb{V}_{n}\text{ and }C_{0}\in\mathcal{C}_{n}$ (24)

We call each $V_{i}$, with T-depth 1, as a _(parallel) block_ and it can be
written as product of $R(P)$ or $R^{\dagger}(P)$, where
$P\in\pm\mathcal{P}_{n}$. A decomposition which has the minimum number of
parallel blocks is called a _T-depth-optimal decomposition_. A circuit
implementing $U$ with the minimum T-depth is called a _T-depth-optimal
circuit_.

####  $\epsilon$-T-depth of approximately implementable unitaries

The _$\epsilon$ -T-depth_ of an approximately implementable unitary
$W\in\mathcal{U}_{n}$, denoted by $\mathcal{T}_{d\epsilon}(W)$, is equal to
$\mathcal{T}_{d}(U)$, the T-depth of an exactly implementable unitary
$U\in\mathcal{J}_{n}$ such that $d(U,W)\leq\epsilon$ and
$\mathcal{T}_{d}(U)\leq\mathcal{T}_{d}(U^{\prime})$ for any
$U^{\prime}\in\mathcal{J}_{n}$ and $d(U^{\prime},W)\leq\epsilon$. We call a
T-count-optimal (or T-depth-optimal) circuit for any such $U$ as the
_$\epsilon$ -T-count-optimal_ (or _$\epsilon$ -T-depth-optimal_ respectively)
circuit for $W$.

Since the set $\mathbb{V}_{n}$ is finite, so it is not hard to see that
algorithms $\mathcal{A}_{MIN}$ and $\mathcal{A}_{DECIDE}$ can be applied to
find T-depth-optimal decomposition of any unitary $W\in\mathcal{U}_{n}$.
Replace step 2 of Algorithm 2 by $\mathcal{S}\leftarrow\mathbb{V}_{n}$.
Suppose $W=UE$ for some exactly implementable unitary $U$ such that
$\mathcal{T}_{d\epsilon}(W)=\mathcal{T}_{d}(U)$ and $d(W,U)\leq\epsilon$. Then
we can decompose $U$ as in Equation 24. If we have guessed the correct
$V_{1},\ldots,V_{d}$ then after multiplying $\prod_{i}V_{i}$ with
$W^{\dagger}$ we are left with $EC_{0}$. Now the amplitude test and
conjugation test can be applied to check if we have the correct guess.
Alternatively, from definition each element of $\mathbb{V}_{n}$ can be written
as a product of $R(P)$ (Definition A.1 in Appendix A.4). So from here also, we
can see why we can apply similar algorithms for T-depth-optimal synthesis.

The space complexity of this (slightly modified) algorithm is
$O\left(|\mathbb{V}_{n}|\right)$ i.e. $O\left(n12^{n}\right)$ and the time
complexity is $O\left(\left(2n\cdot
12^{n}\right)^{\mathcal{T}_{d\epsilon}(W)}\right)$. In this paper we do not
implement our algorithm to determine $\epsilon$-T-depth. For small enough
$\epsilon$, we can use the procedure chalked out in Section 3.2 to synthesize
a T-depth-optimal circuit.

##  6 Conclusion

In this paper we have developed results and algorithms that can be used to
determine the optimal count or depth of non-Clifford gates required to
implement any multi-qubit unitary with the gates of a universal gate set, that
consists of Clifford and non-Clifford gates like Clifford+V, Clifford+CS, etc.
Our primary focus has been the Clifford+T set. Given an $2^{n}\times 2^{n}$
unitary $W$, the space complexity of our algorithm is $\text{poly}(2^{n})$.
The time complexity has an exponential dependence on both $n$ and
$\mathcal{T}_{\epsilon}(W)$ or $\mathcal{T}_{d\epsilon}(W)$, while determining
T-count and T-depth-respectively. For small enough $\epsilon$, we show how we
can synthesize the $\epsilon$-T-count or $\epsilon$-T-depth-optimal circuit.

To the best of our knowledge, we give the first algorithm that works for
arbitrary multi-qubit unitaries (exactly or approximately implementable) and
any universal gate set. We think it is unlikely that we can have a
$\text{poly}(2^{n},m_{\epsilon})$ complexity algorithm for synthesizing
$\epsilon$-T-count or $\epsilon$-T-depth-optimal circuit of approximately
implementable unitaries. A complexity theoretic argument to prove or disprove
Conjecture 1 will throw theoretical insights into the complexity of these
problems. It might be possible to decrease the exponent in the time complexity
by applying techniques like meet-in-the-middle [GKMR14] or nested meet-in-the-
middle [MM21, GMM21]. It is not hard to see that our algorithm can be
parallelized. It will be interesting to investigate if additional tricks can
be used, for example, Monte Carlo approach. Another interesting question is to
find more compact generating sets for other universal gate sets for multi-
qubit unitaries.

## Acknowledgement

We thank Vern I. Paulsen and Adina Goldberg for useful discussions. The
authors wish to thank NTT Research for their financial and technical support.
This work was supported in part by Canada’s NSERC. Research at IQC is
supported in part by the Government of Canada through Innovation, Science and
Economic Development Canada. The Perimeter Institute (PI) is supported in part
by the Government of Canada and Province of Ontario (PI).

## References

  * [ADMG+16] Matthew Amy, Olivia Di Matteo, Vlad Gheorghiu, Michele Mosca, Alex Parent, and John Schanck.  Estimating the cost of generic quantum pre-image attacks on SHA-2 and SHA-3.  In International Conference on Selected Areas in Cryptography, pages 317–337. Springer, 2016.
  * [ADMQ+21] Juan Miguel Arrazola, Olivia Di Matteo, Nicolás Quesada, Soran Jahangiri, Alain Delgado, and Nathan Killoran.  Universal quantum circuits for quantum chemistry.  arXiv preprint arXiv:2106.13839, 2021.
  * [AG04] Scott Aaronson and Daniel Gottesman.  Improved simulation of stabilizer circuits.  Physical Review A, 70(5):052328, 2004.
  * [AGP06] Panos Aliferis, Daniel Gottesman, and John Preskill.  Quantum accuracy threshold for concatenated distance-3 codes.  Quantum Information & Computation, 6(2):97–165, 2006.
  * [AMM14] Matthew Amy, Dmitri Maslov, and Michele Mosca.  Polynomial-time T-depth optimization of clifford+T circuits via matroid partitioning.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 33(10):1476–1489, 2014.
  * [AMMR13] Matthew Amy, Dmitri Maslov, Michele Mosca, and Martin Roetteler.  A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 32(6):818–830, 2013.
  * [BBG15] Andreas Blass, Alex Bocharov, and Yuri Gurevich.  Optimal ancilla-free Pauli+V circuits for axial rotations.  Journal of Mathematical Physics, 56(12):122201, 2015.
  * [BG16] Sergey Bravyi and David Gosset.  Improved classical simulation of quantum circuits dominated by Clifford gates.  Physical review letters, 116(25):250501, 2016.
  * [BGS13] Alex Bocharov, Yuri Gurevich, and Krysta M Svore.  Efficient decomposition of single-qubit gates into V basis circuits.  Physical Review A, 88(1):012313, 2013.
  * [BK05] Sergey Bravyi and Alexei Kitaev.  Universal quantum computation with ideal Clifford gates and noisy ancillas.  Physical Review A, 71(2):022316, 2005.
  * [BS10] Salman Beigi and Peter W Shor.  C_3, semi-Clifford and genralized semi-Clifford operations.  Quantum Information and Computation, 10(1-2):41–59, 2010.
  * [BSS16] Sergey Bravyi, Graeme Smith, and John A Smolin.  Trading classical and quantum computational resources.  Physical Review X, 6(2):021043, 2016.
  * [dBBVA20] Timothée Goubault de Brugière, Marc Baboulin, Benoît Valiron, and Cyril Allouche.  Quantum circuits synthesis using Householder transformations.  Computer Physics Communications, 248:107001, 2020.
  * [DMGM20] Olivia Di Matteo, Vlad Gheorghiu, and Michele Mosca.  Fault-tolerant resource estimation of quantum random-access memories.  IEEE Transactions on Quantum Engineering, 1:1–13, 2020.
  * [DN06] CM Dawson and MA Nielsen.  The Solovay-Kitaev algorithm.  Quantum Information and Computation, 6(1):81–95, 2006.
  * [Eig] Eigen: a C++ template library for linear algebra.  http://eigen.tuxfamily.org.
  * [Fey82] Richard P Feynman.  Simulating physics with computers.  Int. J. Theor. Phys, 21(6/7), 1982.
  * [Fow11] Austin G Fowler.  Constructing arbitrary Steane code single logical qubit fault-tolerant gates.  Quantum Information & Computation, 11(9-10):867–873, 2011.
  * [Fow12] Austin G Fowler.  Time-optimal quantum computation.  arXiv preprint arXiv:1210.4626, 2012.
  * [FSG09] Austin G Fowler, Ashley M Stephens, and Peter Groszkowski.  High-threshold universal quantum computation on the surface code.  Physical Review A, 80(5):052312, 2009.
  * [Ghe18] Vlad Gheorghiu.  Quantum++: A modern C++ quantum computing library.  PloS one, 13(12):e0208073, 2018.
  * [GKMR14] David Gosset, Vadym Kliuchnikov, Michele Mosca, and Vincent Russo.  An algorithm for the T-count.  Quantum Information & Computation, 14(15-16):1261–1276, 2014.
  * [GLMM20] Vlad Gheorghiu, Sarah Meng Li, Michele Mosca, and Priyanka Mukhopadhyay.  Reducing the Cnot count for Clifford+T circuits on NISQ architectures.  arXiv preprint arXiv:2011.12191, 2020.
  * [GMM21] Vlad Gheorghiu, Michele Mosca, and Priyanka Mukhopadhyay.  A quasi-polynomial time heuristic algorithm for synthesizing T-depth optimal circuits.  arXiv preprint arXiv:2101.03142, 2021.
  * [Gro96] Lov K Grover.  A fast quantum mechanical algorithm for database search.  In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pages 212–219, 1996.
  * [GRT21] Andrew N Glaudell, Neil J Ross, and Jacob M Taylor.  Optimal two-qubit circuits for universal fault-tolerant quantum computation.  npj Quantum Information, 7(1):1–11, 2021.
  * [HRS18] Thomas Häner, Martin Roetteler, and Krysta M Svore.  Managing approximation errors in quantum programs.  arXiv preprint arXiv:1807.02336, 2018.
  * [HS20] Thomas Häner and Mathias Soeken.  Lowering the T-depth of quantum circuits by reducing the multiplicative depth of logic networks.  arXiv preprint arXiv:2006.03845, 2020.
  * [JS21] Emil Génetay Johansen and Tapio Simula.  Fibonacci anyons versus Majorana fermions: A Monte Carlo approach to the compilation of braid circuits in $SU(2)_{k}$ anyon models.  PRX Quantum, 2(1):010334, 2021.
  * [JWM+12] N Cody Jones, James D Whitfield, Peter L McMahon, Man-Hong Yung, Rodney Van Meter, Alán Aspuru-Guzik, and Yoshihisa Yamamoto.  Faster quantum chemistry simulation on fault-tolerant quantum computers.  New Journal of Physics, 14(11):115023, 2012.
  * [KBRY15] Vadym Kliuchnikov, Alex Bocharov, Martin Roetteler, and Jon Yard.  A framework for approximating qubit unitaries.  arXiv preprint arXiv:1510.03888, 2015.
  * [KBS14] Vadym Kliuchnikov, Alex Bocharov, and Krysta M Svore.  Asymptotically optimal topological quantum compiling.  Physical review letters, 112(14):140504, 2014.
  * [Kit97] Aleksei Yur’evich Kitaev.  Quantum computations: algorithms and error correction.  Uspekhi Matematicheskikh Nauk, 52(6):53–112, 1997.
  * [Kit03] A Yu Kitaev.  Fault-tolerant quantum computation by anyons.  Annals of Physics, 303(1):2–30, 2003.
  * [KMM13] Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca.  Asymptotically optimal approximation of single qubit unitaries by Clifford and T circuits using a constant number of ancillary qubits.  Physical review letters, 110(19):190502, 2013.
  * [KMM15] Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca.  Practical approximation of single-qubit unitaries by single-qubit quantum Clifford and T circuits.  IEEE Transactions on Computers, 65(1):161–172, 2015.
  * [KSVV02] Alexei Yu Kitaev, Alexander Shen, Mikhail N Vyalyi, and Mikhail N Vyalyi.  Classical and quantum computation.  Number 47. American Mathematical Soc., 2002.
  * [MA08] Ken Matsumoto and Kazuyuki Amano.  Representation of quantum circuits with Clifford and $\pi/8$ gates.  arXiv preprint arXiv:0806.3834, 2008.
  * [MM21] Michele Mosca and Priyanka Mukhopadhyay.  A polynomial time and space heuristic algorithm for T-count.  arXiv:2006.12440,  Quantum Science and Technology, 2021.
  * [MSRH20] Giulia Meuli, Mathias Soeken, Martin Roetteler, and Thomas Häner.  Enabling accuracy-aware quantum compilers using symbolic resource estimation.  Proceedings of the ACM on Programming Languages, 4(OOPSLA):1–26, 2020.
  * [Muk21] Priyanka Mukhopadhyay.  Composability of global phase invariant distance and its application to approximation error management.  arXiv preprint arXiv:2106.07099, 2021.
  * [NC10] Michael A Nielsen and Isaac L Chuang.  Quantum Computation and Quantum Information.  Cambridge University Press, 2010.
  * [Ope] The OpenMP API specification for parallel programming.  https://www.openmp.org/.
  * [Ozo08] Maris Ozols.  Clifford group.  Essays at University of Waterloo, Spring, 2008.
  * [PR13] Adam Paetznick and Ben W Reichardt.  Universal fault-tolerant quantum computation with only transversal gates and error correction.  Physical review letters, 111(9):090505, 2013.
  * [Ros15] Neil J Ross.  Optimal ancilla-free clifford+V approximation of Z-rotations.  Quantum Information & Computation, 15(11-12):932–950, 2015.
  * [RS16] Neil J Ross and Peter Selinger.  Optimal ancilla-free Clifford+T approximation of Z-rotations.  Quantum Information & Computation, 16(11-12):901–953, 2016.
  * [SBW+21] Yuan Su, Dominic W Berry, Nathan Wiebe, Nicholas Rubin, and Ryan Babbush.  Fault-tolerant quantum simulations of chemistry in first quantization.  arXiv preprint arXiv:2105.12767, 2021.
  * [Sel15] Peter Selinger.  Efficient Clifford+T approximation of single-qubit operators.  Quantum Information & Computation, 15(1-2):159–180, 2015.
  * [Sho94] Peter W Shor.  Algorithms for quantum computation: Discrete logarithms and factoring.  In Proceedings 35th annual symposium on foundations of computer science, pages 124–134. Ieee, 1994.
  * [Sho99] Peter W Shor.  Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer.  SIAM review, 41(2):303–332, 1999.
  * [ZLC00] Xinlan Zhou, Debbie W Leung, and Isaac L Chuang.  Methodology for quantum logic gate construction.  Physical Review A, 62(5):052316, 2000.

##  Appendix A Some additional preliminaries

###  A.1 Cliffords and Paulis

The _single qubit Pauli matrices_ are as follows:

$\displaystyle\text{X}=\begin{bmatrix}0&1\\\
1&0\end{bmatrix}\qquad\text{Y}=\begin{bmatrix}0&-i\\\
i&0\end{bmatrix}\qquad\text{Z}=\begin{bmatrix}1&0\\\ 0&-1\end{bmatrix}$

Parenthesized subscripts are used to indicate qubits on which an operator acts
For example, $\text{X}_{(1)}=\text{X}\otimes\mathbb{I}^{\otimes(n-1)}$ implies
that Pauli X matrix acts on the first qubit and the remaining qubits are
unchanged.

The _$n$ -qubit Pauli operators_ are : $\mathcal{P}_{n}=\\{Q_{1}\otimes
Q_{2}\otimes\ldots\otimes
Q_{n}:Q_{i}\in\\{\mathbb{I},\text{X},\text{Y},\text{Z}\\}\\}.$

The _single-qubit Clifford group_ $\mathcal{C}_{1}$ is generated by the
Hadamard and phase gates : $\mathcal{C}_{1}=\braket{\text{H},\text{S}}$ where

$\displaystyle\text{H}=\frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\\
1&-1\end{bmatrix}\qquad\text{S}=\begin{bmatrix}1&0\\\ 0&i\end{bmatrix}$

When $n>1$ the _$n$ -qubit Clifford group_ $\mathcal{C}_{n}$ is generated by
these two gates (acting on any of the $n$ qubits) along with the two-qubit
$\text{CNOT}=\ket{0}\bra{0}\otimes\mathbb{I}+\ket{1}\bra{1}\otimes\text{X}$
gate (acting on any pair of qubits).

The Clifford group is special because of its relationship to the set of
$n$-qubit Pauli operators. Cliffords map Paulis to Paulis, up to a possible
phase of $-1$, i.e. for any $P\in\mathcal{P}_{n}$ and any
$C\in\mathcal{C}_{n}$ we have $CPC^{\dagger}=(-1)^{b}P^{\prime}$ for some
$b\in\\{0,1\\}$ and $P^{\prime}\in\mathcal{P}_{n}$. In fact, given two Paulis
(neither equal to the identity), it is always possible to efficiently find a
Clifford which maps one to the other.

######  Fact A.1 ([GKMR14]).

For any $P,P^{\prime}\in\mathcal{P}_{n}\setminus\\{\mathbb{I}\\}$ there exists
a Clifford $C\in\mathcal{C}_{n}$ such that $CPC^{\dagger}=P^{\prime}$. A
circuit for $C$ over the gate set $\\{\text{H},\text{S},\text{CNOT}\\}$ can be
computed efficiently (as a function of $n$).

######  Fact A.2.

Let $Q=\sum_{P\in\mathcal{P}_{n}}q_{P}P$ be the expansion of a matrix $Q$ in
the Pauli basis. Then

$q_{P}=\text{Tr}\left(QP\right)/N\qquad[N=2^{n}].$

Further, if $Q$ is a unitary then

$\sum_{P\in\mathcal{P}_{n}}\left|q_{P}\right|^{2}=1$

###### Proof.

If $Q=\sum_{P\in\mathcal{P}_{n}}q_{P}P$, then taking trace on both sides and
dividing by $N$ we get the first equation.

If $Q$ is unitary then we get the following.

$\displaystyle
QQ^{\dagger}=\mathbb{I}=\left(\sum_{P}q_{P}P\right)\left(\sum_{P}\overline{q_{P}}P\right)=\sum_{P}|q_{P}|^{2}\mathbb{I}+\sum_{P\neq
P^{\prime}}q_{P}\overline{q_{P^{\prime}}}PP^{\prime}$

Now taking trace on both sides and dividing by $N$, we get the second
equation. ∎

###  A.2 The group generated by Clifford and T gates

The group $\mathcal{J}_{n}$ is generated by the $n$-qubit Clifford group along
with the T gate, where

$\displaystyle\text{T}=\begin{bmatrix}1&0\\\
0&e^{i\frac{\pi}{4}}\end{bmatrix}$ (25)

Thus for a single qubit $\mathcal{J}_{1}=\braket{\text{H},\text{T}}$ and for
$n>1$ qubits

$\displaystyle\mathcal{J}_{n}=\braket{\text{H}_{(i)},\text{T}_{(i)},\text{CNOT}_{(i,j)}:i,j\in[n]}.$

It can be easily verified that $\mathcal{J}_{n}$ is a group, since the H and
CNOT gates are their own inverses and $\text{T}^{-1}=\text{T}^{7}$. Here we
note $\text{S}=\text{T}^{2}$.

###  A.3 Composibility of global phase invariant distance

We state the composibility of the global phase invariant distance with respect
to the tensor product and multiplication of unitaries [Muk21].

######  Lemma A.1.

Let $V=\bigotimes_{i=m}^{1}V_{i}\in\mathcal{U}_{n}$, such that
$V_{i}\in\mathcal{U}_{n_{i}}$ and $\sum_{i=m}^{1}n_{i}=n$. For each $i$,
$U_{i}$ is an $n_{i}$-qubit unitary such that
$D_{P}(U_{i},V_{i})\leq\epsilon_{i}$, for some $0\leq\epsilon_{i}<1$. If
$U=\bigotimes_{i=m}^{1}U_{i}\in\mathcal{U}_{n}$, then

$D_{P}(U,V)\leq\sqrt{1-\prod_{i=1}^{m}\left(1-\epsilon_{i}^{2}\right)}<\sum_{i=1}^{m}\epsilon_{i}$

######  Lemma A.2.

Let $V_{1},V_{2},U_{1},U_{2}\in\mathcal{U}_{n}$ such that
$D_{P}(U_{1},V_{1})\leq\epsilon_{1}$ and $D_{P}(U_{2},V_{2})\leq\epsilon_{2}$,
where $0\leq\epsilon_{1},\epsilon_{2}<1$. If $V=V_{2}V_{1}$ and $U=U_{2}U_{1}$
then

$\displaystyle
D_{P}(U,V)\leq\min\left\\{1,\sqrt{1-\left(1-\epsilon_{1}^{2}\right)\left(1-\epsilon_{2}^{2}\right)+2\epsilon_{1}\epsilon_{2}\sqrt{\left(1-\frac{\epsilon_{1}^{2}}{2}\right)\left(1-\frac{\epsilon_{2}^{2}}{2}\right)}}\right\\}<\epsilon_{1}+\epsilon_{2}$

To get a compact expression that is more convenient to work with, we can have
the following approximation. Let
$V=\prod_{i=m}^{1}V_{i},U=\prod_{i=m}^{1}U_{i}\in\mathcal{U}_{n}$ and
$D_{P}(U_{i},V_{i})\leq\epsilon_{i}$, then

$\displaystyle D_{P}(U,V)$ $\displaystyle\leq$
$\displaystyle\min\\{1,\epsilon\\}$ $\displaystyle\text{where }\epsilon^{2}$
$\displaystyle\approx$
$\displaystyle\sum_{i=1}^{m}\epsilon_{i}^{2}+2\sum_{i=2}^{m}\epsilon_{i}\left(\sum_{j<i}\epsilon_{j}\right)\sqrt{\max\\{0,1-\epsilon_{i}^{2}-(\sum_{j<i}\epsilon_{j})^{2}\\}}<\left(\sum_{i=1}^{m}\epsilon_{i}\right)^{2}.$
(26)

###  A.4 The set $\mathbb{V}_{n}$

In this section we give a constructive definition of the set $\mathbb{V}_{n}$
[GMM21]. Given a set $S$ of qubits there are $(3^{|S|}-1)$ possible ways of
placing a $\text{T}/\text{T}^{\dagger}/\mathbb{I}$ gate in each qubit. We call
each such placement as a _configuration_ of $\overline{T}$ gates and denote it
by $\overline{T}_{S}$.

######  Definition A.1.

We define $\mathbb{V}_{n}$, a subset of $n$-qubit unitaries with T-depth 1,
that is constructed as follows.

  1. 1.

For each $P\in\pm\mathcal{P}_{n}\setminus\\{\mathbb{I}\\}$, for each $q\in[n]$
and for each $\widetilde{R}\in\\{R,R^{\dagger}\\}$ do the following.

    1. (a)

Determine a Clifford $C$ such that $P=CZ_{(q)}C^{\dagger}$.

      1. i.

For each configuration $\overline{T}_{[n]\setminus\\{q\\}}$ do the following.

        1. A.

$V\leftarrow\widetilde{R}(P)$.

        2. B.

For each $i\in[n]\setminus\\{q\\}$ do the following.
If $\overline{T}_{(i)}\neq\mathbb{I}$ then determine $P=CZ_{(i)}C^{\dagger}$.
If $\overline{T}=\text{T}$ then $V\leftarrow V\cdot R(P)$, else if
$\overline{T}=\text{T}^{\dagger}$ then $V\leftarrow V\cdot R^{\dagger}(P)$.

        3. C.

Include $V$ in $\mathbb{V}_{n}$ if it did not already exist.

The following theorem from [GMM21] proves that $\mathbb{V}_{n}$ can generate
the T-depth-optimal decomposition of any exactly implementable unitary (up to
a Clifford).

######  Theorem A.1.

Any $U\in\mathcal{J}_{n}$ with T-depth $d$ can be written as follows :
$U=e^{i\phi}\left(\prod_{i=d}^{1}V_{i}\right)C_{0}$, where
$V_{i}\in\mathbb{V}_{n}$ and $C_{0}\in\mathcal{C}_{n}$.

######  Fact A.3 ([GMM21]).

$|\mathbb{V}_{n}|\leq 2n\cdot 12^{n}.$

##  Appendix B Unitaries implemented in this paper

In this section we give the matrix of the unitaries implemented in Section 4.
The two-qubit controlled z-rotation ($cR_{Z}(\theta)$) unitary is as follows.

$\displaystyle cR_{z}(\theta)=\begin{bmatrix}1&0&0&0\\\ 0&1&0&0\\\
0&0&e^{-i\theta/2}&0\\\ 0&0&0&e^{i\theta/2}\end{bmatrix}$ (27)

The two-qubit Givens rotation ($G(\theta)$) is as follows.

$\displaystyle G(\theta)=\begin{bmatrix}1&0&0&0\\\
0&\cos\theta&-\sin\theta&0\\\ 0&\sin\theta&\cos\theta&0\\\
0&0&0&1\end{bmatrix}$ (28)

Figure 1: A plot of $\mathcal{T}^{\epsilon}(cR_{z}(\theta))$ and
$\mathcal{T}^{\epsilon}(G(\theta))$ at $\theta=\frac{2\pi k}{1000}$ where $k$
varies from 1 to 1000 in steps of 50. The red, blue and green curves are for
$\epsilon=10^{-2},5\times 10^{-3}$ and $3\times 10^{-3}$ respectively. Figure
2: Quantum Fourier Transform circuit given in [NC10]