# Clifford+$T$-gate Decomposition with Limited Number of $T$ gates, its Error
Analysis, and Performance of Unitary Coupled Cluster Ansatz in Pre-FTQC Era

Kohdai Kuroiwa<EMAIL_ADDRESS>Institute for Quantum Computing,
University of Waterloo, Ontario, Canada, N2L 3G1  Department of Combinatorics
and Optimization, University of Waterloo  Perimeter Institute for Theoretical
Physics, Ontario, Canada, N2L 2Y5  QunaSys Inc., Aqua Hakusan Building 9F,
1-13-7 Hakusan, Bunkyo, Tokyo 113-0001, Japan  Yuya O. Nakagawa
<EMAIL_ADDRESS>QunaSys Inc., Aqua Hakusan Building 9F, 1-13-7 Hakusan,
Bunkyo, Tokyo 113-0001, Japan

###### Abstract

Fault-tolerant quantum computation (FTQC) is essential to robustly implement
quantum algorithms and thus to maximize advantages of quantum computers. In
this context, a quantum circuit is decomposed into universal gates that can be
fault-tolerantly implemented, for example, Clifford+$T$ gates. Here, $T$ gate
is usually regarded as an essential resource for quantum computation because
its action cannot be simulated efficiently on classical computers.
Practically, it is highly likely that only a limited number of $T$ gates are
available in the near future due to its experimental difficulty of fault-
tolerant implementation. In this paper, considering this Pre-FTQC era, we
investigate Clifford+$T$ decomposition with a limited budget of $T$ gates and
propose a new model of the error of such decomposition. More concretely, we
propose an algorithm to generate the most accurate Clifford+$T$-gate
decomposition of a given single-qubit rotation gate with a fixed number of $T$
gates. We also propose to model the error of Clifford+$T$ decomposition using
well-known depolarizing noise by considering the average of the effects of the
error. We numerically verified our model successfully explains the
decomposition error for a wide variety of molecules using our decomposition
algorithm. Thus, we shed light on a first-stage application of quantum
computers from a practical point of view and fuel further research towards
what quantum computation can achieve in the upcoming future.

##  1 Introduction

Quantum computers are expected to exhibit superior performance over classical
computers. For example, Shor’s factoring algorithm [1] shows an exponential
speed-up over ever-known classical algorithms, and Grover’s searching
algorithm [2] achieves an quadratic speed-up. Recently, with advancement of
technology, experimental implementation of quantum computers has been
attempted, and the quantum supremacy was even argued using these devices [3,
4, 5, 6, 7, 8]. Noisy intermediate-scale quantum (NISQ) devices [9] are
currently largely investigated as a promising pioneer of quantum computational
technologies. However, in the future, we aim to perform relatively complex
quantum algorithms such as the phase estimation algorithm [10, 11] and
factoring algorithm [1], which show substantial quantum speed-ups. It is
inevitable that circuits required in these algorithms become highly deep, and
noise occurring during the computation has substantial effects without error
correction. Thus, we need fault-tolerant quantum computation (FTQC) using
quantum error correction to maximize the benefit of quantum computers.

Fault-tolerant implementation of quantum circuits requires fault-tolerant
realization of universal gates [12, 13], e.g., the transversal implementation
of Clifford gates and the gate teleportation of $T$ gate [14, 15, 16, 17, 18,
19]. Here, $T$ gate is considered as a crucial resource in FTQC because its
fault-tolerant implementation, associating the magic state distillation [20],
is the most costly part in terms of both time and space overhead with current
practical error-correcting codes. Let us also note that Gottesman-Knill
Theorem [21, 22] states that quantum circuits consisting only of Clifford
gates are efficiently simulatable by classical computers.

Solovay-Kitaev (SK) theorem [23, 24] gives an algorithm that generates
decomposition of a given quantum gate into some universal gate set that is
closed under inversion, e.g.,  Clifford+$T$ gates. Thus, with SK theorem, one
can evaluate the number of $T$ gates, $T$-count, needed to achieve a target
quantum gate to desired accuracy by giving a decomposition into Clifford+$T$
gate. In this paper, we refer to a gate decomposition into Clifford+$T$ gate
as SK decomposition. After this first proposal, improvements of the algorithm
have been subsequently investigated. For example, Bouland and Tyron [25]
recently proposed an algorithm by improving the prior work by Refs. [26, 27],
which successfully removed the requirement that the universal gate set we
consider must be closed under inversion. Also, Refs. [28, 29, 30, 31, 32, 33]
provided efficient algorithms for particular gate sets; in particular, Ross
and Selinger [28] proposed an efficient and almost-optimal SK algorithm for
single-qubit $z$-rotation gate.

However, practically, it is highly likely that we do not have a sufficient
number of $T$ gates in the near future due to its difficulty of
implementation. In such an early stage of FTQC, Pre-FTQC era, we will need to
implement a given quantum circuit with a limited number of $T$ gates. Various
techniques in the Pre-FTQC era have recently been proposed, including
algorithms with less auxiliary qubits [34] and improved noise robustness [35],
error reduction using error mitigation methods [36], and techniques shortening
the circuit depth [37]. Nevertheless, there are two primary issues that have
not yet been inspected: SK decomposition with a limited number of $T$ gates
and precise error estimation of SK decomposition.

The question of what is the best accuracy we can achieve only using the
available number of $T$ gates leads to estimation of how many $T$ gates will
be necessary to achieve desired computation. Algorithm that gives the best
(the most accurate) Clifford+$T$-gate decomposition under a given $T$-gate
budget has not been investigated before to the best of our knowledge.
Moreover, the accuracy of the decomposition of quantum circuits by SK theorem
was usually evaluated by summing up the error of each gate decomposition using
the triangle inequality. As one might notice, the evaluation by this method
might not be tight when the size of the given quantum circuit is large.
Practical resource estimation in Pre-FTQC era may well demand more precise
error estimation, which requires another way to evaluate the error.

In this paper, we propose a method to provide a decomposition of a given
quantum gate when the maximum number of $T$ gates available is limited. Our
method yields a decomposition of a single qubit $z$-rotation that has the
smallest error within a given fixed number of $T$ gates. With this method, we
can obtain an estimation of minimum error when the budget of $T$ gates is
limited. Moreover, we propose to average the effects of the error caused by
the SK decomposition, SK error, when the given circuit is sufficiently large.
By our method, we may model the effects of SK error by a single-qubit
depolarizing channel, which makes the analysis of the total error easier. We
obtain another form of estimate SK error than the previous one obtained by the
naive application of the triangle inequality. Furthermore, we apply this
method to Unitary Coupled Cluster (UCC) ansatz [38] for numerical verification
of the proposed algorithm and the new SK error estimation. The UCC ansatz has
been recognized as a good parametrized state for quantum chemistry problems in
near-term quantum computing. This ansatz can also be applied in the Pre-FTQC
era, for example, for preparation of an initial state of quantum phase
estimation [10, 11]. Therefore, evaluation of the performance of the UCC
ansatz within our framework of Pre-FTQC should be practically beneficial. We
analyzed SK error of the UCC ansatz using the averaging method discussed
above, and show that SK error in this case can be expressed by a simple
formula. We numerically verified this analysis for a wide variety of molecules
by implementing our decomposition algorithm. In addition, with these numerical
simulations, we investigate how many $T$-gates are needed to achieve desired
accuracy.

Thus, we open up a practical perspective to implement a quantum circuit in the
Pre-FTQC era. Our analysis and estimation will be useful to assess how many
$T$ gates are needed to realize a given target quantum state in the Pre-FTQC
era. In this sense, we newly pave a way to develop an application of Pre-FTQC
from a practical point of view, in which the number of $T$-gates available is
fairly restricted.

The rest of this paper is organized as follows. In Sec. 2, we introduce our
algorithm of generating the best Clifford+$T$-gate decomposition within some
given number of $T$ gates, and compare this algorithm with the one by Ref.
[28] on which it is based. In Sec. 3, we show our method of averaging unitary
SK error into the depolarizing noise. In Sec. 4, we apply our analysis to the
UCC ansatz; in Sec. 4.1, we show the concrete SK error estimation for the UCC
ansatz using our averaging method, and in Sec. 4.2, we perform numerical
experiments to verify our algorithm and error analysis using the UCC ansatz
for various molecules in quantum chemistry. Finally, in Sec. 5, we summarize
our results and discuss future directions.

##  2 Algorithm of $T$-Count Fixed Gate Decomposition

In this section, we explain our algorithm to obtain a decomposition of a given
single-qubit $z$-rotation with a fixed number of $T$ gates. Our algorithm is
based on the one proposed in Ref. [28], which yields a decomposition of a
given $z$-rotation with the minimal number of $T$ gates within a fixed
accuracy.

First, we introduce notations and background materials for the algorithm. Let
$\omega$ denote a complex number $\mathrm{e}^{i\tfrac{\pi}{4}}$. We define the
following rings, which are given as extensions of the ring of the integers
$\mathbb{Z}$.

######  Definition 1.

The ring $\mathbb{Z}[\omega]$ is defined by

$\mathbb{Z}[\omega]\coloneqq\left\\{a\omega^{3}+b\omega^{2}+c\omega+d\middle|a,b,c,d\in\mathbb{Z}\right\\}.$
(1)

The ring $\mathbb{D}$ is defined by

$\mathbb{D}\coloneqq\left\\{\dfrac{a}{2^{k}}\middle|a\in\mathbb{Z},k=0,1,2,\ldots\right\\}.$
(2)

The ring $\mathbb{D}[\omega]$ is defined by

$\mathbb{D}[\omega]\coloneqq\left\\{a\omega^{3}+b\omega^{2}+c\omega+d\middle|a,b,c,d\in\mathbb{D}\right\\}.$
(3)

######  Definition 2.

Let $t\in\mathbb{D}[\omega]$ and $k\in\mathbb{N}.$ If
$\sqrt{2^{k}}t\in\mathbb{Z}[\omega]$, then we say that $k$ is a _denominator
exponent_ of $t$. The smallest such $k\geq 0$ is the _least denominator
exponent_ of $t$.

Now, let us describe our gate decomposition algorithm. Due to Lemmas 7.2 and
7.3 of Ref. [28], the task of finding a good approximation of a given
$z$-rotation $R_{z}(\theta)=e^{-i\frac{\theta}{2}Z}$ within a given number
$N_{T}$ of $T$-gates can be reduced to the following searching problem.

######  Problem 1.

Let $\theta\in[0,2\pi)$ be a given angle of $z$-rotation, and let $N_{T}$ be a
positive integer representing the maximum number of $T$ gates available. Find
a pair of $t,u\in\mathbb{D}[\omega]$ maximizing
$\mathrm{Re}(u\mathrm{e}^{-i\theta/2})$ under the following constraints:

  1. (a)

$tt^{\dagger}+uu^{\dagger}=1$,

  2. (b)

and $u$ has a denominator exponent
$\left\lfloor\tfrac{N_{T}}{2}\right\rfloor$.

Once a pair of $(t,u)$ are obtained, the unitary matrix

$U(t,u)\coloneqq\left(\begin{array}[]{cc}u&-t^{\dagger}\\\
t&u^{\dagger}\end{array}\right)$ (4)

serves as a good approximation of the given $z$-rotation $R_{z}(\theta)$.
There exists an efficient algorithm to obtain the exact decomposition of
$U(t,u)$ into $H$, $S$, and $T$ gates [39]. In this exact decomposition
algorithm, the number of $T$ gates used is given by $2k-2$ with the least
denominator exponent $k$ of $u$ when $k>0$, and $T$-count is zero when $k=0$.
Simple calculation shows that SK error is indeed given by

$\epsilon\coloneqq\|U(t,u)-R_{z}(\theta)\|=\sqrt{2(1-\mathrm{Re}(u\mathrm{e}^{-i\theta/2}))},$
(5)

where $\|\cdot\|$ is the operator norm.

Now, we show an algorithm to have the best approximate decomposition of a
given $z$ rotation within a given cost of $T$-gates.

######  Algorithm 1.

Suppose that an angle $\theta$, the maximum number $N_{T}$ of $T$ gates, and
an estimate of SK error $\tilde{\epsilon}>0$ are given. By using Lemma 7.4 and
Proposition 5.21 of Ref. [28], we can efficiently enumerate the candidates of
$u\in\mathbb{D}[\omega]$ with the denominator exponent
$\left\lfloor\tfrac{N_{T}}{2}\right\rfloor$ that satisfy
$tt^{\dagger}+uu^{\dagger}=1$ and $\mathrm{Re}(u\mathrm{e}^{-i\theta/2})\geq
1-\tilde{\epsilon}^{2}/2$. Let $\mathbb{U}_{\textup{cand}}$ be the set of such
candidates $u$. If no such $u$ was found, that is,
$\mathbb{U}_{\textup{cand}}=\emptyset$, we set $\tilde{\epsilon}\leftarrow
2\tilde{\epsilon}$, and try with this new error estimate.

  1. (i)

Set $\epsilon_{\textup{tmp}}=2$, and for each candidate
$u\in\mathbb{U}_{\textup{cand}}$, we run the following procedure:
Use Theorem 6.2 of Ref. [28] to solve $tt^{\dagger}=1-uu^{\dagger}$ with
respect to $t$. If there is no solution or
$\epsilon=\sqrt{2-2\mathrm{Re}(u\mathrm{e}^{-i\theta/2})}\geq\epsilon_{\textup{tmp}}$,
then skip to the next candidate in $\mathbb{U}_{\textup{cand}}$. Otherwise,
set

$\displaystyle t_{\textup{tmp}}\leftarrow t,\leavevmode\nobreak\
\leavevmode\nobreak\ u_{\textup{tmp}}\leftarrow u,\leavevmode\nobreak\
\leavevmode\nobreak\ \epsilon_{\textup{tmp}}\leftarrow\epsilon$ (6)

and continue with the next $u$.

  2. (ii)

After examining all the candidates, use the exact synthesis algorithm of Ref.
[39] to find decomposition of $U(t_{\textup{tmp}},u_{\textup{tmp}})$ into $H$,
$S$, and $T$ gates.

  3. (iii)

Output the circuit $U(t_{\textup{tmp}},u_{\textup{tmp}})$ and SK error
$\epsilon_{\textup{tmp}}$, and stop.

######  Remark 1 (Error Estimate $\tilde{\epsilon}$).

Algorithm 1 searches all the Clifford+$T$-gate decompositions within estimate
error $\tilde{\epsilon}$, and then outputs the one with the smallest error.
Thus, in theory, a sufficiently large $\tilde{\epsilon}$, say,
$\tilde{\epsilon}=2$, guarantees the smallest-error decomposition is obtained
through this algorithm. Practically, smaller $\tilde{\epsilon}$ may be
preferable in terms of (classical) computational efficiency since the search
region $\mathbb{U}_{\textup{cand}}$ is smaller when we take smaller
$\epsilon$. Hence, we consider inputting some small enough error estimate or
desired accuracy as an initial $\tilde{\epsilon}$, and updating
$\tilde{\epsilon}\leftarrow 2\tilde{\epsilon}$ when no decomposition is
obtained. Since the algorithm returns the smallest-error decomposition anyway,
the choice of the initial estimated error will not affect the validity of the
algorithm.

######  Remark 2 (Comparison with the algorithm in Ref. [28]).

The algorithm proposed in Ref. [28] provides a Clifford+$T$-gate decomposition
with the minimum $T$-count under given SK error $\epsilon$. Thus, in that
algorithm, one enumerates the candidate of $u$ with the smallest possible
denominator exponent $k$, say $k=1$, that satisfies
$tt^{\dagger}+uu^{\dagger}=1$ and $\mathrm{Re}(u\mathrm{e}^{-i\theta/2})\geq
1-\epsilon^{2}$ with the fixed given $\epsilon$. If no such pair $(t,u)$ was
found, then one increments the denominator exponent $k$ by $1$, and repeat the
same procedure until such a pair is found. Once a pair of $(t,u)$ is found,
then one produces the corresponding Clifford+$T$-gate decomposition using the
exact synthesis algorithm [39]. The primary difference between these two
algorithms is that we fix $N_{T}$ and seek the best $\epsilon$ while they
fixed $\epsilon$ and sought the best $N_{T}$.

######  Remark 3 (Necessity of Prime Factorization).

Similar to the algorithm by Ross and Selinger [28], our algorithm demands
prime factorization of some integer when we solve
$tt^{\dagger}+uu^{\dagger}=1$. Although factoring is in , for which a
computationally efficient algorithm has not been found, factoring in this
algorithm can be done fast practically by the brute-force method since the
integer which we want to perform factorization is relatively small, as also
indicated in Ref. [28].

##  3 Averaging of Solovay-Kitaev Error on a large circuit

In this section, we analyze an averaged effect of Solovay-Kitaev (SK) error,
the error coming from the decomposition of a $z$-rotation gate by Algorithm 1.
Following this analysis, one may model the effective behavior of SK error by a
depolarizing channel. The averaged effect we derive is expected to be valid
when there are a large number of gates to be decomposed so that SK error will
be well-averaged considering the whole circuit. For example, this analysis
explains SK error for a large quantum circuit with many single-qubit
rotations, such as a parametrized quantum circuit with a high depth.

Let $R_{z}(\theta)$ be the desired $z$ rotation with angle $\theta$, and
suppose that we have a unitary gate $U$ as an approximation of $R_{z}(\theta)$
to accuracy $\epsilon>0$, that is,

$\leavevmode\nobreak\ \|U-R_{z}(\theta)\|\leq\epsilon.$ (7)

When we try to apply the gate $R_{z}(\theta)$, we actually apply the noisy
gate $U=(UR_{z}^{\dagger}(\theta))R_{z}(\theta)$. Thus,
$UR_{z}^{\dagger}(\theta)$ is considered to represent the unitary noise
induced by the decomposition. Since any single-qubit unitary is equivalent to
some single-qubit rotation gate $R_{\bm{n}}(\varphi)$ along axis
$\bm{n}=(n_{x},n_{y},n_{z})$ with angle $\varphi$ up to some global phase
$\mathrm{e}^{i\alpha}$, we can express the unitary noise as
$UR_{z}^{\dagger}(\theta)=\mathrm{e}^{i\alpha}R_{\bm{n}}(\varphi)$ using real
numbers $\alpha,\varphi\in(-\pi,\pi]$ and a normalized real vector $\bm{n}$.
Since the operator norm is unitary-invariant, from Eq. (7), we have

$\leavevmode\nobreak\
\|I-\mathrm{e}^{i\alpha}R_{\bm{n}}(\varphi)\|\leq\epsilon.$ (8)

Intuitively, to satisfy this condition, it should hold that $\alpha\approx 0$
and $\varphi\approx 0$. In the following, we show the range of $\alpha$,
$\varphi$, and $\bm{n}$ for which Eq. (8) is satisfied.

To satisfy Eq. (8), all the singular values of
$I-\mathrm{e}^{i\alpha}R_{\bm{n}}(\varphi)$ must be upper bounded by
$\epsilon$. Consider the following positive matrix:

$\displaystyle(I-\mathrm{e}^{i\alpha}R_{\bm{n}}(\varphi))(I-\mathrm{e}^{i\alpha}R_{\bm{n}}(\varphi))^{\dagger}$
(9)
$\displaystyle=2I-\mathrm{e}^{i\alpha}R_{\bm{n}}(\varphi)-\mathrm{e}^{-i\alpha}R_{\bm{n}}^{\dagger}(\varphi)$
$\displaystyle=2\left(\begin{array}[]{cc}1-\cos\alpha\cos\tfrac{\varphi}{2}-n_{z}\sin\alpha\sin\tfrac{\varphi}{2}&-(n_{x}-in_{y})\sin\alpha\sin\tfrac{\varphi}{2}\\\
-(n_{x}+in_{y})\sin\alpha\sin\tfrac{\varphi}{2}&1-\cos\alpha\cos\tfrac{\varphi}{2}+n_{z}\sin\alpha\sin\tfrac{\varphi}{2}\end{array}\right).$

The eigenvalues of this matrix are

$2\left(1-\cos\left(\frac{\varphi}{2}\pm\alpha\right)\right).$ (10)

Therefore, for Eq. (8) to be satisfied, the following must hold:

$\displaystyle
1-\cos\left(\frac{\varphi}{2}+\alpha\right)\leq\frac{\epsilon^{2}}{2},$ (11)
$\displaystyle
1-\cos\left(\frac{\varphi}{2}-\alpha\right)\leq\frac{\epsilon^{2}}{2}.$ (12)

Define $\delta\coloneqq\cos^{-1}(1-\epsilon^{2}/2)$. By this definition, when
$\epsilon\approx 0$, we also have $\delta\approx 0$. Since
$\alpha,\varphi\in(-\pi,\pi]$, these conditions, Eq. (11) and (12), are
equivalent to

$\displaystyle-\delta-2\alpha\leq\varphi\leq\delta-2\alpha,$ (13)
$\displaystyle-\delta+2\alpha\leq\varphi\leq\delta+2\alpha,$ (14)

that is,

$\leavevmode\nobreak\ -\delta+2|\alpha|\leq\varphi\leq\delta-2|\alpha|.$ (15)

In order that such $\varphi$ exists, $\alpha$ must satisfy

$-\delta+2|\alpha|\leq\delta-2|\alpha|,$ (16)

which can be solved as

$\leavevmode\nobreak\ |\alpha|\leq\frac{\delta}{2}.$ (17)

Therefore, $\alpha$ and $\varphi$ must satisfy Eqs. (15) and (17). Note that
$\bm{n}$ is not constrained; that is, it can be any axis.

Now, we analyze the average effect of the error caused by the approximation of
a single qubit $z$-rotation. We show the effect of the noise
$UR_{z}^{\dagger}(\theta)=\mathrm{e}^{i\alpha}R_{\bm{n}}(\varphi)$ averaged
over the parameters is indeed equivalent to the depolarizing noise. The
average effect of $R_{\bm{n}}(\varphi)$ on a single qubit operator $A$ can be
expressed as

$\frac{1}{\delta}\int^{\tfrac{\delta}{2}}_{-\tfrac{\delta}{2}}d\alpha\frac{1}{2\delta}\int^{\delta}_{-\delta}d\varphi\frac{1}{4\pi}\int_{|\bm{n}|=1}dn_{x}dn_{y}dn_{z}R_{\bm{n}}(\varphi)AR_{\bm{n}}^{\dagger}(\varphi),$
(18)

where $\delta$, $2\delta$ and $4\pi$ are normalization factors. Since the
integrand does not depend on $\alpha$, the first integral is just an integral
of a constant and equal to $\delta$. In addition, since the second integral
represents the surface integral on the unit ball, we can rewrite as
$\bm{n}=(\sin\beta\cos\gamma,\sin\beta\sin\gamma,\cos\gamma)$ with
$\beta\in[0,2\pi)$ and $\gamma\in[0,\pi]$. Thus, we have the following
equivalent expression:

$\leavevmode\nobreak\
\frac{1}{2\delta}\frac{1}{4\pi}\int^{\delta}_{-\delta}d\varphi\int^{2\pi}_{0}d\beta\int^{\pi}_{0}\sin\gamma
d\gamma R_{\bm{n}}(\varphi)AR_{\bm{n}}^{\dagger}(\varphi).$ (19)

To compute Eq. (19) for an arbitrary single-qubit operator $A$, it suffices to
compute the expression for $A=|x\rangle\langle y|$ with $x,y=0,1$ by
linearity. When $A=|0\rangle\langle 0|$, we have that

$\displaystyle R_{\bm{n}}(\varphi)AR_{\bm{n}}^{\dagger}(\varphi)$ (20)
$\displaystyle=R_{\bm{n}}(\varphi)|0\rangle\langle
0|R_{\bm{n}}^{\dagger}(\varphi)$ (21)
$\displaystyle=\left(\begin{array}[]{cc}\cos^{2}\tfrac{\varphi}{2}+\sin^{2}\tfrac{\varphi}{2}\cos^{2}\gamma&(\cos\tfrac{\varphi}{2}-i\sin\tfrac{\varphi}{2}\cos\gamma)\sin\tfrac{\varphi}{2}\sin\gamma\mathrm{e}^{-i\left(\beta-\tfrac{\pi}{2}\right)}\\\
(\cos\tfrac{\varphi}{2}+i\sin\tfrac{\varphi}{2}\cos\gamma)\sin\tfrac{\varphi}{2}\sin\gamma\mathrm{e}^{i\left(\beta-\tfrac{\pi}{2}\right)}&\sin^{2}\tfrac{\varphi}{2}\sin^{2}\gamma\end{array}\right)$
(24)

Observe that when taking integral with respect to $\beta$, the off-diagonal
elements vanish. Computing Eq. (19), we have

$\frac{1}{2\delta}\int_{-\delta}^{\delta}d\varphi\left(\begin{array}[]{cc}\cos^{2}\tfrac{\varphi}{2}+\tfrac{1}{3}\sin^{2}\tfrac{\varphi}{2}&0\\\
0&\tfrac{2}{3}\sin^{2}\tfrac{\varphi}{2}\end{array}\right)=\left(\begin{array}[]{cc}\tfrac{2}{3}+\tfrac{1}{3}\Delta&0\\\
0&\tfrac{1}{3}-\tfrac{1}{3}\Delta\end{array}\right),$ (25)

where

$\Delta\coloneqq\dfrac{\sin\delta}{\delta}.$ (26)

Similarly, when we take $A=|0\rangle\langle 1|$, we have

$\left(\begin{array}[]{cc}0&\tfrac{1}{3}+\tfrac{2}{3}\Delta\\\
0&0\end{array}\right);$ (27)

when we take $A=|1\rangle\langle 0|$, we have

$\left(\begin{array}[]{cc}0&0\\\
\tfrac{1}{3}+\tfrac{2}{3}\Delta&0\end{array}\right);$ (28)

when we take $A=|1\rangle\langle 1|$, we have

$\left(\begin{array}[]{cc}\tfrac{1}{3}-\tfrac{1}{3}\Delta&0\\\
0&\tfrac{2}{3}+\tfrac{1}{3}\Delta\end{array}\right).$ (29)

Therefore, the average effect on $A$ can be written as

$A\mapsto\dfrac{1+2\Delta}{3}A+\dfrac{2}{3}(1-\Delta)\operatorname{\mathrm{Tr}}(A)\dfrac{I}{2};$
(30)

that is, the effect is equivalent to the single-qubit depolarizing noise with
error probability $2(1-\Delta)/3$. Using Taylor series

$\displaystyle\sin x$ $\displaystyle=x-\frac{x^{3}}{6}+O(x^{5}),$ (31)
$\displaystyle\cos^{-1}(1-x)$ $\displaystyle=\sqrt{2x}+O(x^{3/2}),$ (32)

we have the following relation:

$\Delta=1-O(\delta^{2})=1-O(\epsilon^{2}),$ (33)

which holds with high accuracy when $\epsilon>0$ is small. Thus, the error
probability $p$ of this depolarizing channel is

$p\coloneqq\frac{2(1-\Delta)}{3}=O(\epsilon^{2}).$ (34)

Thus, when averaged, the unitary gate-decomposition error of size $\epsilon$
is represented as depolarizing error whose magnitude is $O(\epsilon^{2})$.
Note that the naive estimation by the triangle inequality gives $O(\epsilon)$
[13]; thus we obtained a completely new error formula by averaging.

We believe that this averaged error appropriately models the effects of SK
error of a large quantum circuit, which consists of many single-qubit
rotations. SK error originated from the Clifford+$T$ decomposition of each
single-qubit rotation gate is absolutely unitary by definition. At the same
time, when we look at the effects of all of these unitary errors over the
large circuit, it is expected that their effects look to be averaged.
Therefore, from our analysis here, we anticipate that SK error of a large
quantum circuit with many single-qubit rotations is well-modeled by the
single-qubit depolarizing noise. In the next section, we numerically examine
this using Unitary Coupled Cluster (UCC) ansatz.

##  4 Application to Unitary Coupled Cluster (UCC) ansatz

In this section, we investigate SK error of the UCC ansatz both theoretically
and numerically, as an illustration of our results. In Sec. 4.1, we analyze
how the averaged SK error on the UCC ansatz behaves based on the theoretical
argument of Sec. 3. Then, in Sec. 4.2, we numerically investigate SK error on
the UCC ansatz for various molecular systems in quantum chemistry when the
number of $T$ gates is restricted. The averaged SK error well describes the
numerical results and we also estimate the actual number of the $T$ gates
required to represent a quantum state with sufficient accuracy for the first
time.

In the Pre-FQTC era, while we cannot perform powerful quantum algorithms that
require tremendous amounts of resources, we may still wish to prepare specific
quantum states that are impossible to realize on near-term quantum devices
without error correction, e.g., parametrized quantum states realized by a
relatively deep ansatz circuit. In quantum chemistry, although the quantum
phase estimation [10, 11] is expected to compute the ground state energy of a
given molecular Hamiltonian efficiently, its realization will require about
$O(10^{10})\sim O(10^{15})$ $T$ gates for molecules of practical interest [40,
41, 42, 43, 44, 45]. It is then natural to consider using early FTQC with a
smaller number of $T$-gates, such as the variational quantum eigensolver [46]
with an ansatz with a deep quantum circuit, at some point in time. In the
context of near-term quantum computation, the UCC ansatz [38], which is based
on the coupled cluster theory [47], has been considered as a nice parametrized
state (ansatz state) to represent a ground state of a molecular Hamiltonian.
While the application of the UCC ansatz has been primarily discussed for near-
term quantum devices so far, we believe that this ansatz will rather be
beneficial in the Pre-FTQC era because its circuit tends to be pretty deep in
general and typically beyond the capability of near-term quantum devices 111
The UCC singles and doubles ansatz, which is used in the numerical simulation
below, requires $O(N^{4})$ gates for $N$ molecular orbitals in a naive
implementation. . We also note that the UCC ansatz with some fixed parameters
can serve as an initial state of quantum phase estimation, which may overcome
the problem of the poor overlap between the initial state and the exact ground
state of the molecular Hamiltonian [48]. We summarize the definition and
properties of the UCC ansatz in Appendix A (see also Ref. [38] for more
details).

###  4.1 Averaged effects of SK error on UCC ansatz

We evaluate SK error of the UCC ansatz with large number of qubits by using
the average effects of SK error derived in Sec. 3. Observing that quantum
gates in the UCC ansatz can be expressed as a composition of $H$ gates, $S$
gates, CNOT gates, and parametrized single-qubit $z$-rotation gates, (see
Appendix A for the case of UCC singles and doubles ansatz), we know that SK
error arises only when we approximate the $z$-rotation by the Clifford+$T$
gate decomposition. Suppose that we have a UCC ansatz circuit with $L$
$z$-rotation gates. Then, the UCC ansatz circuit with averaged SK error can be
modeled as a quantum operation

$\mathcal{N}_{\textup{UCC}}\coloneqq\mathcal{E}_{L}\circ\mathcal{U}_{L}\circ\mathcal{E}_{L-1}\circ\cdots\circ\mathcal{E}_{2}\circ\mathcal{U}_{2}\circ\mathcal{E}_{1}\circ\mathcal{U}_{1},$
(35)

where $\mathcal{E}_{i}$ is the single-qubit depolarizing channel acting on the
single-qubit system to which the $i$th $z$-rotation is applied, and
$\mathcal{U}_{i}$ is a unitary operation composed of $H$, $S$, $T$, and CNOT
gates, for all $1\leq i\leq L$. Denoting the initial input to this ansatz
$\rho_{0}$, the total effects of SK error can be evaluated by

$\epsilon_{\textup{tot}}\coloneqq\|\mathcal{N}_{\textup{UCC}}(\rho_{0})-\mathcal{U}_{\textup{UCC}}(\rho_{0})\|_{1},$
(36)

where

$\mathcal{U}_{\textup{UCC}}\coloneqq\mathcal{U}_{L}\circ\cdots\circ\mathcal{U}_{2}\circ\mathcal{U}_{1}$
(37)

is the given UCC ansatz circuit and $\|\cdot\|_{1}$ is the trace norm. Observe
that

$\displaystyle\mathcal{N}_{\textup{UCC}}(\rho_{0})$
$\displaystyle=\mathcal{E}_{L}\circ\mathcal{U}_{L}\circ\mathcal{E}_{L-1}\circ\cdots\circ\mathcal{E}_{2}\circ\mathcal{U}_{2}\circ\mathcal{E}_{1}\circ\mathcal{U}_{1}(\rho_{0})$
$\displaystyle=\mathcal{E}_{L}\circ\mathcal{U}_{L}\circ\mathcal{E}_{L-1}\circ\cdots\circ\mathcal{E}_{2}\circ\mathcal{U}_{2}\circ\left((1-p)\mathcal{U}_{1}(\rho_{0})+p\Delta_{1}\circ\mathcal{U}_{1}(\rho_{0})\right)$
$\displaystyle=(1-p)\mathcal{E}_{L}\circ\mathcal{U}_{L}\circ\mathcal{E}_{L-1}\circ\cdots\circ\mathcal{E}_{2}\circ\mathcal{U}_{2}\circ\mathcal{U}_{1}(\rho_{0})$
$\displaystyle\quad\quad+p\mathcal{E}_{L}\circ\mathcal{U}_{L}\circ\mathcal{E}_{L-1}\circ\cdots\circ\mathcal{E}_{2}\circ\Delta_{1}\circ\mathcal{U}_{1}(\rho_{0})$
$\displaystyle=(1-p)\mathcal{E}_{L}\circ\mathcal{U}_{L}\circ\mathcal{E}_{L-1}\circ\cdots\circ\mathcal{E}_{2}\circ\mathcal{U}_{2}\circ\mathcal{U}_{1}(\rho_{0})+p\rho_{1}$
$\displaystyle=(1-p)\mathcal{E}_{L}\circ\mathcal{U}_{L}\circ\mathcal{E}_{L-1}\circ\cdots\circ\mathcal{E}_{3}\circ\mathcal{U}_{3}\left((1-p)\mathcal{U}_{2}\circ\mathcal{U}_{1}(\rho_{0})+p\Delta_{2}\circ\mathcal{U}_{2}\circ\mathcal{U}_{1}(\rho_{0})\right)+p\rho_{1}$
$\displaystyle=(1-p)^{2}\mathcal{E}_{L}\circ\mathcal{U}_{L}\circ\mathcal{E}_{L-1}\circ\cdots\circ\mathcal{E}_{3}\circ\mathcal{U}_{3}\circ\mathcal{U}_{2}\circ\mathcal{U}_{1}(\rho_{0})$
$\displaystyle\quad\quad+p(1-p)\mathcal{E}_{L}\circ\mathcal{U}_{L}\circ\mathcal{E}_{L-1}\circ\cdots\circ\mathcal{E}_{3}\circ\Delta_{2}\circ\mathcal{U}_{2}\circ\mathcal{U}_{1}(\rho_{0})+p\rho_{1}$
$\displaystyle=(1-p)^{2}\mathcal{E}_{L}\circ\mathcal{U}_{L}\circ\mathcal{E}_{L-1}\circ\cdots\circ\mathcal{E}_{3}\circ\mathcal{U}_{3}\circ\mathcal{U}_{2}\circ\mathcal{U}_{1}(\rho_{0})+p(1-p)\rho_{2}+p\rho_{1}$
$\displaystyle=\cdots$
$\displaystyle=(1-p)^{L}\mathcal{U}_{\textup{UCC}}(\rho_{0})+\sum_{i=1}^{L}p(1-p)^{i-1}\rho_{i},$

where, for each $1\leq i\leq L$, $\rho_{i}$ is a quantum state defined as

$\rho_{i}\coloneqq(\mathcal{E}_{L}\circ\mathcal{U}_{L})\circ(\mathcal{E}_{L-1}\circ\mathcal{U}_{L-1})\circ\cdots(\mathcal{E}_{i+1}\circ\mathcal{U}_{i+1})\circ\Delta_{i}\circ\mathcal{U}_{i}\circ\mathcal{U}_{i-1}\circ\cdots\circ\mathcal{U}_{2}\circ\mathcal{U}_{1}(\rho_{0})$
(38)

with the completely depolarizing channel $\Delta_{i}$ on the system on which
$\mathcal{E}_{i}$ acts. Then, we have the following chain of inequalities:

$\leavevmode\nobreak\ \begin{aligned}
\epsilon_{\textup{tot}}&=\|\mathcal{N}_{\textup{UCC}}(\rho_{0})-\mathcal{U}_{\textup{UCC}}(\rho_{0})\|_{1}\\\
&=\left\|\left[(1-p)^{L}-1\right]\mathcal{U}_{\textup{UCC}}(\rho_{0})+\sum_{i=1}^{L}p(1-p)^{i-1}\rho_{i}\right\|_{1}\\\
&\leq 1-(1-p)^{L}+\sum_{i=1}^{L}p(1-p)^{i-1}\\\ &=2\left(1-(1-p)^{L}\right)\\\
&\sim L*O(\epsilon^{2}).\end{aligned}$ (39)

Therefore, since $p=O(\epsilon^{2})$ for the averaged SK error where
$\epsilon$ is SK error for a single-qubit $z$-rotation [Eq. (5)], the error
$\epsilon_{\textup{tot}}$ caused by SK error can be modeled by a function

$2\left(1-\left(1-O(\epsilon^{2})\right)^{L}\right).$ (40)

Since SK error $\epsilon_{\textup{tot}}$ above is given in the trace norm, it
is also easy to estimate the error of an expectation value for some
observable. Suppose that we evaluate the energy of a given Hamiltonian $H$
with the UCC ansatz. When the ansatz circuit is “noisy”, or approximated, due
to the Clifford+$T$ decomposition, the energy $\tilde{E}$ we obtain under such
situation is given by

$\tilde{E}\coloneqq\operatorname{\mathrm{Tr}}(\mathcal{N}_{\textup{UCC}}(\rho_{0})H).$
(41)

The difference of the expectation values of $H$ between the ideal ansatz
state,

$E_{*}=\operatorname{\mathrm{Tr}}(\mathcal{U}_{\textup{UCC}}(\rho_{0})H),$
(42)

and the approximated (Clifford+$T$ decomposed) state is bounded by

$\leavevmode\nobreak\ \begin{aligned}
|\tilde{E}-E_{*}|&=\left|\operatorname{\mathrm{Tr}}(\mathcal{N}_{\textup{UCC}}(\rho_{0})H)-\operatorname{\mathrm{Tr}}(\mathcal{U}_{\textup{UCC}}(\rho_{0})H)\right|\\\
&\leq\|\mathcal{N}_{\textup{UCC}}(\rho_{0})-\mathcal{U}_{\textup{UCC}}(\rho_{0})\|_{1}\|H\|\\\
&\leq 2\|H\|\left(1-\left(1-O(\epsilon^{2})\right)^{L}\right).\end{aligned}$
(43)

The Hölder’s inequality [49] is used at the first inequality. The second
inequality follows from Eq. (39). Hence, the error of the energy obtained by
the Clifford+$T$ decomposition is expected to depend also on $\epsilon^{2}$ as
shown in Eq. (43).

######  Remark 4.

The analysis conducted in this subsection is applicable not only to the UCC
ansatz, but to a broader class of parametrized quantum circuits, in which only
$z$-rotation gates are parametrized. Since Clifford+$z$-rotation gates form a
universal gate set, we can convert any given parametrized circuit into this
form. Thus, in theory, we may use this analysis for an arbitrary ansatz
circuit. Practically, this method can be helpful when the
Clifford+$z$-rotation expression of a given ansatz circuit can be easily
obtained.

###  4.2 Numerical experiments for the UCC ansatz

Here we numerically illustrate the theoretical analysis on the average SK
error above by actually decomposing the quantum circuit of the UCC ansatz
using the algorithm described in Sec. 2.

Our setup for numerical simulations is as follows. We consider a wide variety
of molecules shown in Table 1. We adopt the STO-3G minimal basis set, and
construct the fermionic second-quantized Hamiltonians for electrons with the
Hartree-Fock orbitals by using the numerical libraries PySCF [50] and
OpenFermion [51]. We then employ Jordan-Wigner transformation [52] to map the
fermionic Hamiltonians into qubit Hamiltonians [53, 54]. We consider
decomposing the unitary coupled cluster singles and doubles (UCCSD) ansatz
circuit for those molecules, which is explicitly defined in Appendix A, into
Clifford+$T$-gate circuit by using the algorithm in Sec. 2. In the simulation,
we do not optimize the parameters in the UCCSD ansatz. We instead use the
amplitudes of the coupled cluster singles and doubles (CCSD) [47] computed on
classical computers with PySCF [50] as parameters of the UCCSD ansatz.
Hereafter, we call this state the UCCSD’ state. We generate Clifford+$T$-gate
decomposition of the UCC’ ansatz for each molecule with various $T$-count
$N_{T}$, which stands for the maximum number of $T$-gates used in Algorithm 1
in Sec. 2. We consider $22\leq N_{T}\leq 50$ in the simulation. All
simulations for quantum circuits are performed by the high-speed quantum
circuit simulator Qulacs [55]. We do not include any noise for quantum circuit
simulations.

Table 1: Geometries of molecules used in the numerical simulations. “$(\mathrm{X},(x,y,z))$” denotes three dimensional coordinates $x,y,z$ of atom X in units of Å.  Molecule | # of Qubits | Geometry
---|---|---
H2 | 4 | (H, (0, 0, 0)), (H, (0, 0, 0.735))
Hi | $2*i$ | (H,($0,0,j-1$)) for the $j$th H atom ($j=1,2,\ldots,i$).
($i=4,6,8,10$) |  |
H2O | 14 | (O, (0, 0, 0.137)), (H, (0,0.769,-0.546)), (H, (0,-0.769,-0.546))
LiH | 12 | (Li, (0, 0, 0)), (H, (0, 0, 1.548))
BeH2 | 14 | (Be, (0, 0, 0)), (H, (0, 0, -1.304)), (H, (0, 0, 1.304))
H2S | 22 | (S, (0, 0, 0.1030)), (H, (0, 0.9616, -0.8239)),
|  | (H, (0, -0.9616, -0.8239))
CH4 | 18 | (C, (0, 0, 0)),
|  | (H, (0.6276, 0.6276, 0.6276)), (H, (0.6276, -0.6276, -0.6276)),
|  | (H, (-0.6276, 0.6276, -0.6276)), (H, (-0.6276, -0.6276, 0.6276))
C2H2 | 24 | (C, (0, 0, 0.6013)), (C, (0, 0, -0.6013)),
|  | (H, (0, 0, 1.6644)), (H, (0, 0, -1.6644))
CO | 20 | (C, (0, 0, 0)), (O, (0, 0, 1.128))
N2 | 20 | (N, (0, 0, 0)), (N, (0, 0, 1.5))
NH3 | 16 | (N, (0,0,0.149)), (H, (0,0.947,-0.348)),
|  | (H, (0.821,-0.474,-0.348)), (H, (-0.821,-0.474,-0.348))

First, we examine the SK error analysis proposed in Sec. 3. We calculate the
energy expectation values of the approximate UCCSD’ state under Clifford+$T$
decomposition with the single-gate $T$-count $N_{T}$. Recalling that the
average effects of SK error on the UCC ansatz is given by Eq. (43), we model
the energy expectation value for a given $N_{T}$ as

$\leavevmode\nobreak\
f(N_{T})=E_{*}+2E_{*}\left(1-\left(1-c\cdot(\epsilon(N_{T}))^{2}\right)^{L}\right),$
(44)

where $\epsilon(N_{T})\coloneqq 10^{-\tfrac{N_{T}}{10}}$ is the single-gate SK
error, $L$ is the total number of $z$ rotations in the UCCSD ansatz, $E_{*}$
is the energy expectation value for the original UCCSD ansatz (not decomposed
into Clliford+$T$), and $c$ is a fitting parameter. Here, the functional form
of the single-gate SK error $10^{-\tfrac{N_{T}}{10}}$ is assumed by following
the numerical observation in Ref. [28]. For each molecule, the data of the
energy expectation values versus $N_{T}$ is fitted by performing the (non-
linear) regression to this model (44). We take the range of $32\leq N_{T}\leq
50$ for the fitting to see the accuracy of the model for relatively large
$N_{T}$. The results for $\ce{C_{2}H_{2}}$ and $\ce{NH_{3}}$ molecules, which
exhibit representative behaviors, are shown in Fig. 1. The whole results for
all molecules in Table 1 are given in Appendix B. As one may see, the model
(44) explains the total SK error well while the previous error estimate by the
triangle inequality gives much worse upper bound of the energy (see the
captions). This is an illustration of the validity of the average error
analysis presented in Sec. 3. Indeed, compared with the naive estimation using
the triangle inequality (see the caption and subcaptions of Fig. 1), our model
gives a more precise estimation of energy expectation values.

Next, we evaluate the threshold for the $T$-count $N_{T}$ with which we can
guarantee sufficient accuracy to represent the UCCSD’ state. In Fig. 2, we
plot the fidelity between the exact ground state of the Hamiltonian and the
approximate (Clifford+$T$-gate-decomposed) UCCSD’ state with respect to the
$T$-count. As expected, the larger $N_{T}$ results in higher fidelity. We
determine the threshold for $T$-count to represent the UCCSD’ state with high
accuracy by requiring that the following quantity,

$\leavevmode\nobreak\
\delta_{\textup{rel}}\coloneqq\dfrac{|F(N_{T})-F_{\textup{ideal}}|}{F_{\textup{ideal}}},$
(45)

satisfies $\delta_{\textup{rel}}<10^{-4}$, where $F(N_{T})$ is the fidelity
between the approximated UCCSD’ state and the exact ground state of the
Hamiltonian and $F_{\textup{ideal}}$ is the fidelity between the original
(not-decomposed) UCCSD’ state and the exact ground state.
$\delta_{\textup{del}}$ means the relative error of the fidelity with respect
to the exact ground state of the Hamiltonian. The results for the total
threshold $T$-counts, ((the per-gate threshold $T$-counts obtained in Fig. 2)
$\times$ (the number of $z$-rotation gates)), for various molecules are
summarized in Fig. 3. Indeed, the total threshold $T$-count mostly increases
quartically with respect to the number of qubits. In Fig. 3, we also show the
results of fitting of the total threshold $T$-count versus the number of
qubits obtained by performing the linear regression using a quartic function
$an^{4}$ with fitting parameter $a$ and the number $n$ of qubits. The fitting
explains the data pretty well with fitting result $a=0.07795(1)$. This $n^{4}$
dependence is natural when one considers there are $O(n^{4})$ multi-qubit
Pauli rotation gates in the UCCSD ansatz.

This result implies that the usage of variational quantum algorithms with a
deep ansatz such as the UCC ansatz can be beneficial in the Pre-FTQC era. For
example, consider the FeMo cofactor of the nitrogenase enzyme Fe7MoS9C, known
as FeMoco. There are two active space models considered conventionally for
this molecule, one proposed by Reiher et al. [40] with the number of qubit
$n=104$ (RWSWT orbital) and the other one proposed by Li et al. [56] with
$n=154$ (LLDUC orbital). The current best resource estimation for the quantum
phase estimation of FeMoco, as far as we are aware of, is obtained using
tensor hypercontraction by Lee et al. [44], and the estimate Toffoli count is
$5.3\times 10^{9}$ for RWSWT FeMoco and $3.2\times 10^{10}$ for LLDUC FeMoco.
The most straightforward way to estimate $T$-count from Toffoli count is to
simply transform the Toffoli gate into a quantum circuit using
Clifford+$T$-gates, and this can be done using $7$ $T$ gates [13]. Or,
recently, a magic-state factory construction based on the surface code was
proposed [57], implying one Toffoli gate is roughly twice as costly as one $T$
gate. With these estimations, for both active space models, the $T$-count
needed to perform the quantum phase estimation to FeMoco is roughly
$O(10^{10})\sim O(10^{11})$ at best. On the other hand, with our estimation,
the $T$-count for realizing the UCCSD’ state with the accuracy
$\delta_{\textup{rel}}<10^{-4}$ is $an^{4}\approx 0.078\times(154)^{4}\approx
4\times 10^{7}$ even for the larger active space of LLDUC FeMoco, which is
smaller than the estimate $T$-count for the quantum phase estimation by three
orders of magnitude. In addition, the tensor hypercontraction demands enormous
auxiliary qubits [44]; if we do not use auxiliary qubits, adopting the
Trotter-based methods, we have the estimate $T$-count of roughly
$O(10^{14})\sim O(10^{16})$. In this case, the $T$-count for the UCCSD’ state
is even smaller by seven-to-nine orders of magnitude. Thus, it can be
practically usuful to use the UCCSD’ state as an initial state of the quantum
phase estimation since the preparation of the UCCSD’ state is much more
resource-efficient considering the estimate cost of the quantum phase
estimation.

(a) The energy expectation values of C_2H_2. The fitting parameter is
$c=0.6106(2)$. On the other hand, the triangle inequality gives energy upper
bound $-75.52\,\mathrm{Ha}$ at $N_{T}=50$.

(b) The energy expectation values of NH_3. The fitting parameter is
$c=0.779(2)$. The triangle inequality gives energy upper bound
$-55.45\,\mathrm{Ha}$ at $N_{T}=50$.

Figure 1: Energy expectation values of Clifford+$T$-gate decomposed UCCSD’
states with $T$-gate budget $32\leq N_{T}\leq 50$. In each panel, the orange
curve represents the expectation values of the UCCSD’ state that are
decomposed by Algorithm 1. The purple horizontal line indicates the true
UCCSD’ state energy obtained by the UCCSD ansatz without SK decomposition. The
blue curve is the fitting of the orange curve modeled by Eq. (44). As
indicated in each subcaption, the naive analysis by the triangle inequality is
substantially rougher than our method.

(a) Fidelity of the UCCSD’ states of C_2H_2 to the exact ground state.

(b) Fidelity of the UCCSD’ states of NH3 to the exact ground state.

Figure 2: The fidelity between the exact ground state of the Hamiltonian and
the Clifford+$T$-gate decomposed UCCSD’ states with $T$-gate budget $22\leq
N_{T}\leq 50$. In each panel, the blue curve represents the fidelity between
the exact ground state and the UCCSD’ state that is decomposed by Algorithm 1.
The pink horizontal line indicates the fidelity between the exact ground state
and the true UCCSD’ state obtained by the UCCSD ansatz without SK
decomposition. The orange vertical line represents the $T$-count threshold
that achieves Eq. (45). Figure 3: Number of qubits vs Total threshold
$T$-count. The red curve is the fitting of the data of the total threshold
$T$-count versus the number of qubits by a quartic function $an^{4}$ with the
fitting result $a=0.07795(1)$, where $n$ is the number of qubits.

##  5 Summary and outlook

In this paper, we propose a Clifford+$T$-gate decomposition algorithm to
provide the most accurate approximation of a given single-qubit $z$-rotation
gate when the available number of $T$ gates is restricted. We also propose a
method of averaging the effects of the unitary SK error into the depolarizing
noise when a given circuit is sufficiently large, which makes the analysis of
the total SK error easier. We apply this method to Unitary Coupled Cluster
(UCC) ansatz. We numerically verified our proposal for a wide variety of
molecules, and with the numerical simulations, we reveal the threshold
$T$-counts to achieve desired accuracy.

Hence, we shed a new light for the Pre-FTQC era, where only a restricted
number of $T$ gates are practically available. We believe that our proposal
and analysis lead to more accurate resource estimation in the framework of
Pre-FTQC. As a future direction, it would be interesting to investigate our
algorithm and averaging method for another setup, e.g., quantum phase
estimation algorithm, and estimate SK error or threshold $T$-count in that
case.

## Acknowledgement

The authors are grateful to Yasunori Lee for valuable discussions and comments
on the manuscript. We also thank Keita Kanno for fruitful discussions on the
early stage of this work. We would like to express our deep appreciation to
Hayata Morisaki for providing us with useful codes of the SK decomposition
algorithm of Ref. [28]. The numerical simulations of this work are largely
inspired by his implementation.

KK is supported by a Mike and Ophelia Lazaridis Fellowship, the Funai
Foundation, and a Perimeter Residency Doctoral Award.

## References

  * Shor [1997] Peter W. Shor.  Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer.  _SIAM J. Comput._ , 26(5):1484–1509, Oct 1997\.  ISSN 1095-7111.  doi: 10.1137/s0097539795293172.  URL http://dx.doi.org/10.1137/S0097539795293172.
  * Grover [1996] Lov K. Grover.  A Fast Quantum Mechanical Algorithm for Database Search.  In _Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing_ , STOC ’96, page 212–219, New York, NY, USA, 1996. Association for Computing Machinery.  ISBN 0897917855.  doi: 10.1145/237814.237866.  URL https://doi.org/10.1145/237814.237866.
  * Arute et al. [2019] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando G. S. L. Brandao, David A. Buell, Brian Burkett, Yu Chen, Zijun Chen, Ben Chiaro, Roberto Collins, William Courtney, Andrew Dunsworth, Edward Farhi, Brooks Foxen, Austin Fowler, Craig Gidney, Marissa Giustina, Rob Graff, Keith Guerin, Steve Habegger, Matthew P. Harrigan, Michael J. Hartmann, Alan Ho, Markus Hoffmann, Trent Huang, Travis S. Humble, Sergei V. Isakov, Evan Jeffrey, Zhang Jiang, Dvir Kafri, Kostyantyn Kechedzhi, Julian Kelly, Paul V. Klimov, Sergey Knysh, Alexander Korotkov, Fedor Kostritsa, David Landhuis, Mike Lindmark, Erik Lucero, Dmitry Lyakh, Salvatore Mandrà, Jarrod R. McClean, Matthew McEwen, Anthony Megrant, Xiao Mi, Kristel Michielsen, Masoud Mohseni, Josh Mutus, Ofer Naaman, Matthew Neeley, Charles Neill, Murphy Yuezhen Niu, Eric Ostby, Andre Petukhov, John C. Platt, Chris Quintana, Eleanor G. Rieffel, Pedram Roushan, Nicholas C. Rubin, Daniel Sank, Kevin J. Satzinger, Vadim Smelyanskiy, Kevin J. Sung, Matthew D. Trevithick, Amit Vainsencher, Benjamin Villalonga, Theodore White, Z. Jamie Yao, Ping Yeh, Adam Zalcman, Hartmut Neven, and John M. Martinis.  Quantum supremacy using a programmable superconducting processor.  _Nature_ , 574(7779):505–510, Oct 2019.  ISSN 1476-4687.  doi: 10.1038/s41586-019-1666-5.  URL https://doi.org/10.1038/s41586-019-1666-5.
  * Zhong et al. [2020] Han-Sen Zhong, Hui Wang, Yu-Hao Deng, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Jian Qin, Dian Wu, Xing Ding, Yi Hu, Peng Hu, Xiao-Yan Yang, Wei-Jun Zhang, Hao Li, Yuxuan Li, Xiao Jiang, Lin Gan, Guangwen Yang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Chao-Yang Lu, and Jian-Wei Pan.  Quantum computational advantage using photons.  _Science_ , 370(6523):1460–1463, 2020.  doi: 10.1126/science.abe8770.  URL https://www.science.org/doi/abs/10.1126/science.abe8770.
  * Zhong et al. [2021] Han-Sen Zhong, Yu-Hao Deng, Jian Qin, Hui Wang, Ming-Cheng Chen, Li-Chao Peng, Yi-Han Luo, Dian Wu, Si-Qiu Gong, Hao Su, Yi Hu, Peng Hu, Xiao-Yan Yang, Wei-Jun Zhang, Hao Li, Yuxuan Li, Xiao Jiang, Lin Gan, Guangwen Yang, Lixing You, Zhen Wang, Li Li, Nai-Le Liu, Jelmer J. Renema, Chao-Yang Lu, and Jian-Wei Pan.  Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light.  _Phys. Rev. Lett._ , 127:180502, Oct 2021.  doi: 10.1103/PhysRevLett.127.180502.  URL https://link.aps.org/doi/10.1103/PhysRevLett.127.180502.
  * Wu et al. [2021] Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, Ming Gong, Cheng Guo, Chu Guo, Shaojun Guo, Lianchen Han, Linyin Hong, He-Liang Huang, Yong-Heng Huo, Liping Li, Na Li, Shaowei Li, Yuan Li, Futian Liang, Chun Lin, Jin Lin, Haoran Qian, Dan Qiao, Hao Rong, Hong Su, Lihua Sun, Liangyuan Wang, Shiyu Wang, Dachao Wu, Yu Xu, Kai Yan, Weifeng Yang, Yang Yang, Yangsen Ye, Jianghan Yin, Chong Ying, Jiale Yu, Chen Zha, Cha Zhang, Haibin Zhang, Kaili Zhang, Yiming Zhang, Han Zhao, Youwei Zhao, Liang Zhou, Qingling Zhu, Chao-Yang Lu, Cheng-Zhi Peng, Xiaobo Zhu, and Jian-Wei Pan.  Strong Quantum Computational Advantage Using a Superconducting Quantum Processor.  _Phys. Rev. Lett._ , 127:180501, Oct 2021.  doi: 10.1103/PhysRevLett.127.180501.  URL https://link.aps.org/doi/10.1103/PhysRevLett.127.180501.
  * Daley et al. [2022] Andrew J. Daley, Immanuel Bloch, Christian Kokail, Stuart Flannigan, Natalie Pearson, Matthias Troyer, and Peter Zoller.  Practical quantum advantage in quantum simulation.  _Nature_ , 607(7920):667–676, Jul 2022.  ISSN 1476-4687.  doi: 10.1038/s41586-022-04940-6.  URL https://doi.org/10.1038/s41586-022-04940-6.
  * Madsen et al. [2022] Lars S. Madsen, Fabian Laudenbach, Mohsen Falamarzi. Askarani, Fabien Rortais, Trevor Vincent, Jacob F. F. Bulmer, Filippo M. Miatto, Leonhard Neuhaus, Lukas G. Helt, Matthew J. Collins, Adriana E. Lita, Thomas Gerrits, Sae Woo Nam, Varun D. Vaidya, Matteo Menotti, Ish Dhand, Zachary Vernon, Nicolás Quesada, and Jonathan Lavoie.  Quantum computational advantage with a programmable photonic processor.  _Nature_ , 606(7912):75–81, Jun 2022.  ISSN 1476-4687.  doi: 10.1038/s41586-022-04725-x.  URL https://doi.org/10.1038/s41586-022-04725-x.
  * Preskill [2018] John Preskill.  Quantum Computing in the NISQ era and beyond.  _Quantum_ , 2:79, August 2018.  ISSN 2521-327X.  doi: 10.22331/q-2018-08-06-79.  URL https://doi.org/10.22331/q-2018-08-06-79.
  * Kitaev [1995] A. Yu. Kitaev.  Quantum measurements and the Abelian Stabilizer Problem, 1995.  URL https://arxiv.org/abs/quant-ph/9511026.
  * Cleve et al. [1998] R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca.  Quantum algorithms revisited.  _Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences_ , 454(1969):339–354, 1998.  doi: 10.1098/rspa.1998.0164.  URL https://royalsocietypublishing.org/doi/abs/10.1098/rspa.1998.0164.
  * Gottesman [2010] Daniel Gottesman.  _An Introduction to Quantum Error Correction and Fault-Tolerant Quantum Computation_ , volume 68, pages 13–58.  American Mathematical Society, 2010.
  * Nielsen and Chuang [2010] Michael A. Nielsen and Isaac L. Chuang.  _Quantum Computation and Quantum Information: 10th Anniversary Edition_.  Cambridge University Press, 2010.  doi: 10.1017/CBO9780511976667.
  * Shor [1996] P.W. Shor.  Fault-tolerant quantum computation.  In _Proceedings of 37th Conference on Foundations of Computer Science_ , pages 56–65, 1996.  doi: 10.1109/SFCS.1996.548464.
  * Steane [1997] A. M. Steane.  Active Stabilization, Quantum Computation, and Quantum State Synthesis.  _Phys. Rev. Lett._ , 78:2252–2255, Mar 1997.  doi: 10.1103/PhysRevLett.78.2252.  URL https://link.aps.org/doi/10.1103/PhysRevLett.78.2252.
  * Knill [2005] E. Knill.  Quantum computing with realistically noisy devices.  _Nature_ , 434(7029):39–44, Mar 2005.  ISSN 1476-4687.  doi: 10.1038/nature03350.  URL https://doi.org/10.1038/nature03350.
  * Gottesman [1998a] Daniel Gottesman.  Theory of fault-tolerant quantum computation.  _Phys. Rev. A_ , 57:127–137, Jan 1998a.  doi: 10.1103/PhysRevA.57.127.  URL https://link.aps.org/doi/10.1103/PhysRevA.57.127.
  * Gottesman and Chuang [1999] Daniel Gottesman and Isaac L. Chuang.  Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations.  _Nature_ , 402(6760):390–393, Nov 1999.  ISSN 1476-4687.  doi: 10.1038/46503.  URL https://doi.org/10.1038/46503.
  * Zhou et al. [2000] Xinlan Zhou, Debbie W. Leung, and Isaac L. Chuang.  Methodology for quantum logic gate construction.  _Phys. Rev. A_ , 62:052316, Oct 2000.  doi: 10.1103/PhysRevA.62.052316.  URL https://link.aps.org/doi/10.1103/PhysRevA.62.052316.
  * Bravyi and Kitaev [2005] Sergey Bravyi and Alexei Kitaev.  Universal quantum computation with ideal clifford gates and noisy ancillas.  _Phys. Rev. A_ , 71:022316, Feb 2005.  doi: 10.1103/PhysRevA.71.022316.  URL https://link.aps.org/doi/10.1103/PhysRevA.71.022316.
  * Gottesman [1998b] D Gottesman.  The Heisenberg representation of quantum computers.  In S. P. Corney, R. Delbourgo, and P. D. Jarvis, editors, _Proceedings of the XXII International Colloquium on Group Theoretical Methods in Physics_ , pages 32–43, 1998b.
  * Aaronson and Gottesman [2004] Scott Aaronson and Daniel Gottesman.  Improved simulation of stabilizer circuits.  _Phys. Rev. A_ , 70:052328, Nov 2004.  doi: 10.1103/PhysRevA.70.052328.  URL https://link.aps.org/doi/10.1103/PhysRevA.70.052328.
  * Kitaev [1997] A Yu Kitaev.  Quantum computations: algorithms and error correction.  _Russian Math. Surveys_ , 52(6):1191, dec 1997\.  doi: 10.1070/RM1997v052n06ABEH002155.  URL https://dx.doi.org/10.1070/RM1997v052n06ABEH002155.
  * Dawson and Nielsen [2005] Christopher M. Dawson and Michael A. Nielsen.  The Solovay-Kitaev algorithm, 2005.  URL https://arxiv.org/abs/quant-ph/0505030.
  * Bouland and Giurgica-Tiron [2021] Adam Bouland and Tudor Giurgica-Tiron.  Efficient Universal Quantum Compilation: An Inverse-free Solovay-Kitaev Algorithm, 2021.  URL https://arxiv.org/abs/2112.02040.
  * Sardharwalla et al. [2016] Imdad S. B. Sardharwalla, Toby S. Cubitt, Aram W. Harrow, and Noah Linden.  Universal Refocusing of Systematic Quantum Noise, 2016.  URL https://arxiv.org/abs/1602.07963.
  * Bouland and Ozols [2018] Adam Bouland and Maris Ozols.  Trading Inverses for an Irrep in the Solovay-Kitaev Theorem.  In Stacey Jeffery, editor, _13th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2018)_ , volume 111 of _Leibniz International Proceedings in Informatics (LIPIcs)_ , pages 6:1–6:15, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  ISBN 978-3-95977-080-4.  doi: 10.4230/LIPIcs.TQC.2018.6.  URL http://drops.dagstuhl.de/opus/volltexte/2018/9253.
  * Ross and Selinger [2016] Neil J. Ross and Peter Selinger.  Optimal Ancilla-Free Clifford+T Approximation of z-Rotations.  _Quantum Info. Comput._ , 16(11–12):901–953, sep 2016.  ISSN 1533-7146.
  * Kliuchnikov et al. [2016] Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca.  Practical Approximation of Single-Qubit Unitaries by Single-Qubit Quantum Clifford and T Circuits.  _IEEE Trans. Comput._ , 65(1):161–172, 2016.  doi: 10.1109/TC.2015.2409842.
  * Selinger [2015] Peter Selinger.  Efficient Clifford+T Approximation of Single-Qubit Operators.  _Quantum Info. Comput._ , 15(1–2):159–180, jan 2015.  ISSN 1533-7146.
  * Bocharov et al. [2015] Alex Bocharov, Martin Roetteler, and Krysta M. Svore.  Efficient Synthesis of Universal Repeat-Until-Success Quantum Circuits.  _Phys. Rev. Lett._ , 114:080502, Feb 2015.  doi: 10.1103/PhysRevLett.114.080502.  URL https://link.aps.org/doi/10.1103/PhysRevLett.114.080502.
  * Forest et al. [2015] Simon Forest, David Gosset, Vadym Kliuchnikov, and David McKinnon.  Exact synthesis of single-qubit unitaries over Clifford-cyclotomic gate sets.  _J. Math. Phys._ , 56(8):082201, 2015.  doi: 10.1063/1.4927100.  URL https://doi.org/10.1063/1.4927100.
  * Parzanchevski and Sarnak [2018] Ori Parzanchevski and Peter Sarnak.  Super-Golden-Gates for PU(2).  _Adv. Math._ , 327:869–901, 2018.  ISSN 0001-8708.  doi: https://doi.org/10.1016/j.aim.2017.06.022.  URL https://www.sciencedirect.com/science/article/pii/S0001870817301640.  Special volume honoring David Kazhdan.
  * Lin and Tong [2022] Lin Lin and Yu Tong.  Heisenberg-Limited Ground-State Energy Estimation for Early Fault-Tolerant Quantum Computers.  _PRX Quantum_ , 3:010318, Feb 2022.  doi: 10.1103/PRXQuantum.3.010318.  URL https://link.aps.org/doi/10.1103/PRXQuantum.3.010318.
  * Kshirsagar et al. [2022] Rutuja Kshirsagar, Amara Katabarwa, and Peter D. Johnson.  On proving the robustness of algorithms for early fault-tolerant quantum computers, 2022.  URL https://arxiv.org/abs/2209.11322.
  * Suzuki et al. [2022] Yasunari Suzuki, Suguru Endo, Keisuke Fujii, and Yuuki Tokunaga.  Quantum Error Mitigation as a Universal Error Reduction Technique: Applications from the NISQ to the Fault-Tolerant Quantum Computing Eras.  _PRX Quantum_ , 3:010345, Mar 2022.  doi: 10.1103/PRXQuantum.3.010345.  URL https://link.aps.org/doi/10.1103/PRXQuantum.3.010345.
  * Ding and Lin [2022] Zhiyan Ding and Lin Lin.  Even shorter quantum circuit for phase estimation on early fault-tolerant quantum computers with applications to ground-state energy estimation, 2022.  URL https://arxiv.org/abs/2211.11973.
  * Anand et al. [2022] Abhinav Anand, Philipp Schleich, Sumner Alperin-Lea, Phillip W. K. Jensen, Sukin Sim, Manuel Díaz-Tinoco, Jakob S. Kottmann, Matthias Degroote, Artur F. Izmaylov, and Alán Aspuru-Guzik.  A quantum computing view on unitary coupled cluster theory.  _Chem. Soc. Rev._ , 51:1659–1684, 2022.  doi: 10.1039/D1CS00932J.  URL http://dx.doi.org/10.1039/D1CS00932J.
  * Kliuchnikov et al. [2013] Vadym Kliuchnikov, Dmitri Maslov, and Michele Mosca.  Fast and Efficient Exact Synthesis of Single-Qubit Unitaries Generated by Clifford and T Gates.  _Quantum Info. Comput._ , 13(7–8):607–630, jul 2013.  ISSN 1533-7146.
  * Reiher et al. [2017] Markus Reiher, Nathan Wiebe, Krysta M. Svore, Dave Wecker, and Matthias Troyer.  Elucidating reaction mechanisms on quantum computers.  _Proceedings of the National Academy of Sciences_ , 114(29):7555–7560, 2017.  doi: 10.1073/pnas.1619152114.  URL https://www.pnas.org/doi/abs/10.1073/pnas.1619152114.
  * Babbush et al. [2018] Ryan Babbush, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Alexandru Paler, Austin Fowler, and Hartmut Neven.  Encoding Electronic Spectra in Quantum Circuits with Linear T Complexity.  _Phys. Rev. X_ , 8:041015, Oct 2018.  doi: 10.1103/PhysRevX.8.041015.  URL https://link.aps.org/doi/10.1103/PhysRevX.8.041015.
  * Berry et al. [2019] Dominic W. Berry, Craig Gidney, Mario Motta, Jarrod R. McClean, and Ryan Babbush.  Qubitization of Arbitrary Basis Quantum Chemistry Leveraging Sparsity and Low Rank Factorization.  _Quantum_ , 3:208, December 2019.  ISSN 2521-327X.  doi: 10.22331/q-2019-12-02-208.  URL https://doi.org/10.22331/q-2019-12-02-208.
  * von Burg et al. [2021] Vera von Burg, Guang Hao Low, Thomas Häner, Damian S. Steiger, Markus Reiher, Martin Roetteler, and Matthias Troyer.  Quantum computing enhanced computational catalysis.  _Phys. Rev. Research_ , 3:033055, Jul 2021.  doi: 10.1103/PhysRevResearch.3.033055.  URL https://link.aps.org/doi/10.1103/PhysRevResearch.3.033055.
  * Lee et al. [2021] Joonho Lee, Dominic W. Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, and Ryan Babbush.  Even More Efficient Quantum Computations of Chemistry Through Tensor Hypercontraction.  _PRX Quantum_ , 2:030305, Jul 2021.  doi: 10.1103/PRXQuantum.2.030305.  URL https://link.aps.org/doi/10.1103/PRXQuantum.2.030305.
  * Yoshioka et al. [2022] Nobuyuki Yoshioka, Tsuyoshi Okubo, Yasunari Suzuki, Yuki Koizumi, and Wataru Mizukami.  Hunting for quantum-classical crossover in condensed matter problems.  _arXiv preprint arXiv:2210.14109_ , 2022.
  * Peruzzo et al. [2014] Alberto Peruzzo, Jarrod McClean, Peter Shadbolt, Man-Hong Yung, Xiao-Qi Zhou, Peter J. Love, Alán Aspuru-Guzik, and Jeremy L. O’Brien.  A variational eigenvalue solver on a photonic quantum processor.  _Nature Communications_ , 5(1):4213, Jul 2014\.  ISSN 2041-1723.  doi: 10.1038/ncomms5213.  URL https://doi.org/10.1038/ncomms5213.
  * Bartlett and Musiał [2007] Rodney J. Bartlett and Monika Musiał.  Coupled-cluster theory in quantum chemistry.  _Rev. Mod. Phys._ , 79:291–352, Feb 2007.  doi: 10.1103/RevModPhys.79.291.  URL https://link.aps.org/doi/10.1103/RevModPhys.79.291.
  * Lee et al. [2022] Seunghoon Lee, Joonho Lee, Huanchen Zhai, Yu Tong, Alexander M. Dalzell, Ashutosh Kumar, Phillip Helms, Johnnie Gray, Zhi-Hao Cui, Wenyuan Liu, Michael Kastoryano, Ryan Babbush, John Preskill, David R. Reichman, Earl T. Campbell, Edward F. Valeev, Lin Lin, and Garnet Kin-Lic Chan.  Is there evidence for exponential quantum advantage in quantum chemistry?, 2022.  URL https://arxiv.org/abs/2208.02199.
  * Watrous [2018] John Watrous.  _The Theory of Quantum Information_.  Cambridge University Press, 2018.  doi: 10.1017/9781316848142.
  * Sun et al. [2018] Qiming Sun, Timothy C. Berkelbach, Nick S. Blunt, George H. Booth, Sheng Guo, Zhendong Li, Junzi Liu, James D. McClain, Elvira R. Sayfutyarova, Sandeep Sharma, Sebastian Wouters, and Garnet Kin-Lic Chan.  PySCF: the Python-based simulations of chemistry framework.  _WIREs Comput. Mol. Sci._ , 8(1):e1340, 2018.  URL https://onlinelibrary.wiley.com/doi/abs/10.1002/wcms.1340.
  * McClean et al. [2017] Jarrod R. McClean, Kevin J. Sung, Ian D. Kivlichan, Yudong Cao, Chengyu Dai, E. Schuyler Fried, Craig Gidney, Brendan Gimby, Pranav Gokhale, Thomas Häner, Tarini Hardikar, Vojtěch Havlíček, Oscar Higgott, Cupjin Huang, Josh Izaac, Zhang Jiang, Xinle Liu, Sam McArdle, Matthew Neeley, Thomas O’Brien, Bryan O’Gorman, Isil Ozfidan, Maxwell D. Radin, Jhonathan Romero, Nicholas Rubin, Nicolas P. D. Sawaya, Kanav Setia, Sukin Sim, Damian S. Steiger, Mark Steudtner, Qiming Sun, Wei Sun, Daochen Wang, Fang Zhang, and Ryan Babbush.  OpenFermion: The Electronic Structure Package for Quantum Computers, 2017.  URL https://arxiv.org/abs/1710.07629.
  * Jordan and Wigner [1928] P. Jordan and E. Wigner.  Über das Paulische Äquivalenzverbot.  _Zeitschrift für Physik_ , 47(9):631–651, Sep 1928.  ISSN 0044-3328.  doi: 10.1007/BF01331938.  URL https://doi.org/10.1007/BF01331938.
  * McArdle et al. [2020] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin, and Xiao Yuan.  Quantum computational chemistry.  _Rev. Mod. Phys._ , 92:015003, Mar 2020.  doi: 10.1103/RevModPhys.92.015003.  URL https://link.aps.org/doi/10.1103/RevModPhys.92.015003.
  * Cao et al. [2019] Yudong Cao, Jonathan Romero, Jonathan P. Olson, Matthias Degroote, Peter D. Johnson, Mária Kieferová, Ian D. Kivlichan, Tim Menke, Borja Peropadre, Nicolas P. D. Sawaya, Sukin Sim, Libor Veis, and Alán Aspuru-Guzik.  Quantum Chemistry in the Age of Quantum Computing.  _Chem. Rev._ , 119(19):10856–10915, Oct 2019\.  ISSN 0009-2665.  doi: 10.1021/acs.chemrev.8b00803.  URL https://doi.org/10.1021/acs.chemrev.8b00803.
  * Suzuki et al. [2021] Yasunari Suzuki, Yoshiaki Kawase, Yuya Masumura, Yuria Hiraga, Masahiro Nakadai, Jiabao Chen, Ken M. Nakanishi, Kosuke Mitarai, Ryosuke Imai, Shiro Tamiya, Takahiro Yamamoto, Tennin Yan, Toru Kawakubo, Yuya O. Nakagawa, Yohei Ibe, Youyuan Zhang, Hirotsugu Yamashita, Hikaru Yoshimura, Akihiro Hayashi, and Keisuke Fujii.  Qulacs: a fast and versatile quantum circuit simulator for research purpose.  _Quantum_ , 5:559, October 2021.  ISSN 2521-327X.  doi: 10.22331/q-2021-10-06-559.  URL https://doi.org/10.22331/q-2021-10-06-559.
  * Li et al. [2019] Zhendong Li, Junhao Li, Nikesh S. Dattani, C. J. Umrigar, and Garnet Kin-Lic Chan.  The electronic complexity of the ground-state of the femo cofactor of nitrogenase as relevant to quantum simulations.  _J. Chem. Phys._ , 150(2):024302, 2019.  doi: 10.1063/1.5063376.  URL https://doi.org/10.1063/1.5063376.
  * Gidney and Fowler [2019] Craig Gidney and Austin G. Fowler.  Efficient magic state factories with a catalyzed $|CCZ\rangle$ to $2|T\rangle$ transformation.  _Quantum_ , 3:135, April 2019.  ISSN 2521-327X.  doi: 10.22331/q-2019-04-30-135.  URL https://doi.org/10.22331/q-2019-04-30-135.

##  Appendix A Unitary coupled-cluster singles and doubles ansatz

In the numerical simulations in the main text, we employed unitary coupled-
cluster singles and doubles (UCCSD) ansatz [38]. The UCCSD ansatz is defined
by

$\displaystyle\hat{U}_{\mathrm{UCCSD}}(\bm{\theta})$
$\displaystyle=\mathrm{e}^{\hat{T}_{s}-\hat{T}_{s}^{\dagger}}\mathrm{e}^{\hat{T}_{d1}-\hat{T}_{d1}^{\dagger}}\mathrm{e}^{\hat{T}_{d2}-\hat{T}_{d2}^{\dagger}},$
(46) $\displaystyle\hat{T}_{s}$
$\displaystyle=\sum_{o,v}\theta_{ov}^{(s)}\left(\hat{a}_{v\uparrow}^{\dagger}\hat{a}_{o\uparrow}+\hat{a}_{v\downarrow}^{\dagger}\hat{a}_{o\downarrow}\right),$
(47) $\displaystyle\hat{T}_{d1}$
$\displaystyle=\sum_{o,v}\theta^{(d1)}_{ov}\hat{a}_{v\uparrow}^{\dagger}\hat{a}_{o\uparrow}\hat{a}_{v\downarrow}^{\dagger}\hat{a}_{o\downarrow},$
(48) $\displaystyle\hat{T}_{d2}$
$\displaystyle=\sum_{(o_{1},v_{1})\neq(o_{2},v_{2})}\sum_{\sigma,\tau=\uparrow,\downarrow}\theta_{o_{1}o_{2}v_{1}v_{2}}^{(d2)}\hat{a}_{v_{1}\sigma}^{\dagger}\hat{a}_{o_{1}\sigma}\hat{a}_{v_{2}\tau}^{\dagger}\hat{a}_{o_{2}\tau},$
(49)

where $a_{p\sigma}(a_{p\sigma}^{\dagger})$ is an annihilation (creation)
operator of electron in an orbital $p$ with spin $\sigma$ and $o,o_{1},o_{2}$
($v,v_{1},v_{2}$) are the occupied (virtual) orbitals in the Hartree-Fock
state. The circuit parameters of this ansatz are
$\bm{\theta}=(\theta_{ov}^{(s)})_{ov}\cup(\theta_{ov}^{(d1)})_{ov}\cup(\theta_{o_{1}o_{2}v_{1}v_{2}}^{(d2)})_{o_{1}o_{2}v_{1}v_{2}}$.
To transform this ansatz into qubit operators, we performed the Jordan-Wigner
transformation [52] for
$\hat{T}_{s}-\hat{T}_{s}^{\dagger},\hat{T}_{d1}-\hat{T}_{d1}^{\dagger}$ and
$\hat{T}_{d2}-\hat{T}_{d2}^{\dagger}$. For example, if
$\hat{T}_{s}-\hat{T}_{s}^{\dagger}$ is transformed into the sum of multiqubit
Pauli operators $i\sum_{ov}\theta_{ov}^{(s)}\sum_{k}\hat{P}_{k}^{(ov)}$, we
(approximately) implement $e^{\hat{T}_{s}-\hat{T}_{s}^{\dagger}}$ by the
Trotterization:

$\prod_{ov}\prod_{k}\exp[i\theta_{ov}^{(s)}\hat{P}_{k}^{(ov)}].$ (50)

The operators $e^{\hat{T}_{d1}-\hat{T}_{d1}^{\dagger}}$ and
$e^{\hat{T}_{d2}-\hat{T}_{d2}^{\dagger}}$ were implemented as qubit operators
in the same way.

Note that every multi-qubit Pauli rotation
$\exp[i\theta_{ov}^{(s)}\hat{P}_{k}^{(ov)}]$ can be expressed as a composite
of Clifford gates and a single-qubit $z$-rotation with the same angle
$\theta_{ov}$ [38]. Therefore, it suffices to give the Clifford+$T$
decomposition of the corresponding $z$-rotation to obtain the decomposition of
$\exp[i\theta_{ov}^{(s)}\hat{P}_{k}^{(ov)}]$.

##  Appendix B Results of Numerical Experiments

In this section, we show the whole results of our numerical experiments, which
are partly shown in Sec. 4.2. We consider the molecules shown in Table 1.

In Fig. 4, we show the energy curve of each molecule, and in Fig. 5 we show
the fidelity curve and indicate the threshold $T$-count to achieve the
relative error $\delta_{\textup{rel}}<10^{-4}$.

|  |
---|---|---
|  |
|  |

(a) H_8. The fitting parameter is $c=51(2)$.

(b) H_10. The fitting parameter is $c=40(2)$.

(c) H_2O. The fitting parameter is $c=0.3799(5)$.

(d) CH_4. The fitting parameter is $c=3.730(5)$.

(e) C_2H_2. The fitting parameter is $c=0.6106(2)$.

(f) CO. The fitting parameter is $c=0.5196(1)$.

(g) N_2. The fitting parameter is $c=0.10216(3)$.

(h) NH_3. The fitting parameter is $c=0.779(2)$.

Figure 4: Energy expectation values of Clifford+$T$-gate decomposed UCCSD’
states with $T$-gate budget $32\leq N_{T}\leq 50$. In each panel, the orange
curve represents the expectation values of the UCCSD’ state that are
decomposed by Algorithm 1. The horizontal purple line indicates the true
UCCSD’ state energy obtained by the UCCSD ansatz without SK decomposition. The
blue curve is the fitting of the orange curve modeled by Eq. (44).

|  |
---|---|---
|  |
|  |
|  |

(a) H_2

(b) H_4

(c) H_6

(d) H_8

(e) H_10

(f) H_2O

(g) LiH

(h) BeH_2

(i) H_2S

(j) CH_4

(k) C_2H_2

(l) CO

|  |
---|---|---

(m) N_2

(n) NH_3

Figure 5: The fidelity between the exact ground state of the Hamiltonian and
the Clifford+$T$-gate decomposed UCCSD’ states with $T$-gate budget $22\leq
N_{T}\leq 50$. In each panel, the blue curve represents the fidelity between
the exact ground state and the UCCSD’ state that is decomposed by Algorithm 1.
The horizontal pink line indicates the fidelity between the exact ground state
and the true UCCSD’ state obtained by the UCCSD ansatz without SK
decomposition. The orange vertical line represents the $T$-count threshold
that achieves Eq. (45).