$(2n^{2}-1)+(2(n-1)^{2}-1)$ ANDs222The cost of multiplying 2 $n$-bit numbers
is $2n^{2}-1$ many logical ANDs., and the addition $2n-1$ ANDs. Adding all
these, the cost of $U_{initial}$ is $4n^{2}+2n-6$ ANDs. Since the cost of
$U_{initial}^{\dagger}$ is the same, these operations cost a total of
$2|\Omega|\left(4n^{2}+2n-6\right)$ ANDs, which equals
$8|\Omega|\left(4n^{2}+2n-6\right)$ T gates.

The ancilla count for $U_{initial}$ is given by the number of ancillae used to
store values, as well as those used in the $\ket{scratch}$ register actually
used to compute the values. Those used to store values are given by

  * •

$\log_{2}{(2k^{2})}$ (for the comparison)

  * •

$\log_{2}{(k)}$ (store $\ket{k}$)

  * •

$\log_{2}{(2k)}$ (copy $\ket{\phi}_{a}$)

  * •

$\log_{2}{(k)}$ (copy $\ket{k}$)

  * •

$2\log_{2}{(2k)}$ (product of two $\log_{2}{(2k)}$ numbers)

  * •

$2\log_{2}{(k)}$ (product of two $\log_{2}{(k)}$ numbers)

In addition, the number of ancillae used in $\ket{scratch}$ to actually carry
out the various computations in $U_{initial}$ is given by

  * •

$\log_{2}{(2k^{2})}-1$ ($U_{P+1}$)

  * •

$\log_{2}{(2k)}-1$ ($U_{\phi_{a}+1}$)

  * •

$\log_{2}{(2k)}$ ($U_{\phi-k}$)

  * •

$\left[\log_{2}{(2k)}+1\right]\left[2\log_{2}{(2k)}-1\right]+1$
($U_{\phi\times\phi_{anc},\phi_{anc}^{2}}$)

  * •

$\left[\log_{2}{(k)}+1\right]\left[2\log_{2}{(k)}-1\right]+1$ ($U_{K\times
K_{anc},K^{2}}$)

  * •

$2\log_{2}{(2k)}$ ($\phi_{anc}^{2}+K_{anc}^{2}$)

Once we have run $U_{initial}$, we then run the following series of
operations.

$\displaystyle\left(\frac{1}{\sqrt{2k^{2}}}\sum_{i=0}^{2k^{2}-1}\ket{i+1}\right)\left(\sum_{j_{1}\dots
j_{a}\dots j_{|\Omega|}=0}^{2k-1}c_{j_{1}\dots j_{a}\dots
j_{|\Omega|}}\ket{j_{1}\dots j_{a}+1-k\dots j_{|\Omega|}}\ket{k}\right.$
$\displaystyle\qquad\left.\ket{j_{a}+1-k}\ket{k}\ket{k^{2}+(j_{a}+1-k)^{2}}\ket{k^{2}}\right)\ket{0}\ket{scratch}$
$\displaystyle\xrightarrow{\texttt{CMP}}$
$\displaystyle\left(\frac{1}{\sqrt{2k^{2}}}\sum_{i=0}^{2k^{2}-1}\ket{i+1}\right)\left(\sum_{j_{1}\dots
j_{a}\dots j_{|\Omega|}=0}^{2k-1}c_{j_{1}\dots j_{a}\dots
j_{|\Omega|}}\ket{j_{1}\dots j_{a}+1-k\dots j_{|\Omega|}}\ket{k}\right.$
$\displaystyle\qquad\left.\ket{j_{a}+1-k}\ket{k}\ket{k^{2}+(j_{a}+1-k)^{2}}\ket{k^{2}}\ket{\Theta(i-k^{2}-(k-j-1)^{2})}_{anc}\right)\ket{scratch}$
$\displaystyle\xrightarrow{Z_{anc}}$
$\displaystyle\left(\frac{1}{\sqrt{2k^{2}}}\sum_{i=0}^{2k^{2}-1}\ket{i+1}\right)\left(\sum_{j_{1}\dots
j_{a}\dots j_{|\Omega|}=0}^{2k-1}c_{j_{1}\dots j_{a}\dots
j_{|\Omega|}}\left[1-2\Theta(i-k^{2}-(k-j-1)^{2})\right]\ket{j_{1}\dots
j_{a}+1-k\dots j_{|\Omega|}}\ket{k}\right.$
$\displaystyle\qquad\left.\ket{j_{a}+1-k}\ket{k}\ket{k^{2}+(j_{a}+1-k)^{2}}\ket{k^{2}}\ket{\Theta(i-k^{2}-(k-j-1)^{2})}_{anc}\right)\ket{scratch}$
$\displaystyle=$
$\displaystyle\left(\frac{1}{\sqrt{2k^{2}}}\sum_{i=0}^{2k^{2}-1}\ket{i+1}\right)\left(\sum_{j_{1}\dots
j_{a}\dots j_{|\Omega|}=0}^{2k-1}c_{j_{1}\dots j_{a}\dots
j_{|\Omega|}}\left[2\Theta(k^{2}+(k-j-1)^{2})-i-1\right]\ket{j_{1}\dots
j_{a}+1-k\dots j_{|\Omega|}}\ket{k}\right.$
$\displaystyle\qquad\left.\ket{j_{a}+1-k}\ket{k}\ket{k^{2}+(j_{a}+1-k)^{2}}\ket{k^{2}}\ket{\Theta(i-k^{2}-(k-j-1)^{2})}_{anc}\right)\ket{scratch}$
$\displaystyle\xrightarrow{\texttt{CMP}^{\dagger}}$
$\displaystyle\left(\frac{1}{\sqrt{2k^{2}}}\sum_{i=0}^{2k^{2}-1}\ket{i+1}\right)\left(\sum_{j_{1}\dots
j_{a}\dots j_{|\Omega|}=0}^{2k-1}c_{j_{1}\dots j_{a}\dots
j_{|\Omega|}}\left[2\Theta(k^{2}+(k-j-1)^{2})-i-1\right]\ket{j_{1}\dots
j_{a}+1-k\dots j_{|\Omega|}}\ket{k}\right.$
$\displaystyle\qquad\left.\ket{j_{a}+1-k}\ket{k}\ket{k^{2}+(j_{a}+1-k)^{2}}\ket{k^{2}}\right)\ket{0}_{anc}\ket{scratch}$
$\displaystyle\xrightarrow{U_{initial}^{\dagger}}$
$\displaystyle\left(\frac{1}{\sqrt{2k^{2}}}\sum_{i=0}^{2k^{2}-1}\ket{i}\right)\left(\sum_{j_{1}\dots
j_{a}\dots j_{|\Omega|}=0}^{2k-1}c_{j_{1}\dots j_{a}\dots
j_{|\Omega|}}\left[2\Theta(k^{2}+(k-j-1)^{2})-i-1\right]\ket{j_{1}\dots
j_{a}\dots j_{|\Omega|}}\right)\ket{k}$
$\displaystyle\qquad\ket{0}^{\otimes\log_{2}{2k}}\ket{0}^{\otimes\log_{2}{k}}\ket{0}^{\otimes
2\log_{2}{2k}-1}\ket{0}^{\otimes 2\log_{2}{k}-1}\ket{scratch}$

With a similar analysis as before, we see that with the identifications

$\displaystyle U_{PREP}$ $\displaystyle=$ $\displaystyle H^{\otimes\left\lceil
1+2\log_{2}{k}\right\rceil}\otimes\mathbb{I}$ $\displaystyle U_{SELECT}$
$\displaystyle=$ $\displaystyle
U_{initial}^{\dagger}\texttt{CMP}^{\dagger}Z_{anc}\texttt{CMP}U_{initial}$
(366)

we have

$U_{PREP}^{\dagger}U_{SELECT}U_{PREP}\overline{\ket{0}}\ket{\phi}\ket{0}_{anc}=\left(\overline{\ket{0}}\frac{\hat{\phi}^{2}}{|\phi_{max}|^{2}}\ket{\phi}+\ket{\Phi^{\perp}}\right)\ket{0}_{anc}$
(367)

where $\left(|\overline{0}\rangle\langle\overline{0}|\otimes
I\right)|\Phi^{\perp}\rangle=0$, and we obtain the state
$\hat{\phi}^{2}|\phi\rangle$ with probability
$\frac{|\hat{\phi}^{2}|\phi\rangle|^{2}}{|\phi_{max}|^{4}}$ upon post-
selection.

The $\texttt{CMP}^{\prime}$ operation (and its inverse), replacing the CMP
operation as before, compares two $\log_{2}{2k^{2}}$-qubit numbers and costs
$\log_{2}{2k^{2}}$ many logical ANDs. Thus, the comparisons require
$|\Omega|\log_{2}{2k^{2}}$ many logical ANDs across the entire lattice,
contributing to a T gate count of $4|\Omega|\log_{2}{2k^{2}}$.

In addition, we have $|\Omega|$ many multi-controlled $Z$ gates to apply
across the entire lattice, which incurs a cost of $4|\Omega|-4$ T gates using
the unary iteration method of [70].

In all, the total T gate count for this family of terms is given by the
following, as also noted in the main text in Eq. (121)

$\displaystyle Count(T)_{\phi^{2}}$ $\displaystyle=$ $\displaystyle
8|\Omega|\left(4\log_{2}^{2}{k}+11\log_{2}{k}+1\right)-4$ (368)

#####  $\text{SELECT}_{\Phi^{4}}$ term

In much the same way as for the $\phi^{2}$ term, we can construct an LCU for
$\hat{\phi}^{4}$ as

$\displaystyle\left(\frac{\hat{\phi}}{\Delta\phi}\right)^{4}$ $\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{i=0}^{2k^{4}-1}U^{(i)},\qquad\text{where}$
$\displaystyle U^{(i)}$ $\displaystyle=$
$\displaystyle\sum_{j=0}^{2k-1}\left[2\Theta(k^{4}+(k-j-1)^{4}-i-1)-1\right]\ket{j}\bra{j}$
(369)

with essentially the same method for $\hat{\phi}^{2}$ as described above,
except that $U_{initial}$ is modified as follows.

$\displaystyle\ket{+}^{\otimes\log_{2}{2k^{4}}}\ket{\phi}\ket{k}\ket{0}^{\otimes\log_{2}{2k}}\ket{0}^{\otimes\log_{2}{k}}\ket{0}^{\otimes
2\log_{2}{2k}-1}\ket{0}^{\otimes 2\log_{2}{2k}-1}\ket{0}^{\otimes
2\log_{2}{k}-1}\ket{0}^{\otimes 2\log_{2}{k}-1}$
$\displaystyle\ket{0}^{\otimes 4\log_{2}{2k}-3}\ket{0}^{\otimes
4\log_{2}{k}-2}\qquad\ket{scratch}$ $\displaystyle=$
$\displaystyle\left(\frac{1}{\sqrt{2k^{4}}}\sum_{i=0}^{2k^{4}-1}\ket{i}\right)\left(\sum_{j_{1}\dots
j_{a}\dots j_{|\Omega|}=0}^{2k-1}c_{j_{1}\dots j_{a}\dots
j_{|\Omega|}}\ket{j_{1}\dots j_{a}\dots j_{|\Omega|}}\right)\ket{k}$
$\displaystyle\qquad\ket{0}^{\otimes\log_{2}{2k}}\ket{0}^{\otimes\log_{2}{k}}\ket{0}^{\otimes
2\log_{2}{2k}-1}\ket{0}^{\otimes 2\log_{2}{2k}-1}\ket{0}^{\otimes
2\log_{2}{k}-1}\ket{0}^{\otimes 2\log_{2}{k}-1}$
$\displaystyle\qquad\ket{0}^{\otimes 4\log_{2}{2k}-3}\ket{0}^{\otimes
4\log_{2}{k}-2}\ket{scratch}$ $\displaystyle\xrightarrow{U_{P+1}}$
$\displaystyle\left(\frac{1}{\sqrt{2k^{4}}}\sum_{i=0}^{2k^{4}-1}\ket{i+1}\right)\left(\sum_{j_{1}\dots
j_{a}\dots j_{|\Omega|}=0}^{2k-1}c_{j_{1}\dots j_{a}\dots
j_{|\Omega|}}\ket{j_{1}\dots j_{a}\dots j_{|\Omega|}}\right)\ket{k}$
$\displaystyle\qquad\ket{0}^{\otimes\log_{2}{2k}}\ket{0}^{\otimes\log_{2}{k}}\ket{0}^{\otimes
2\log_{2}{2k}-1}\ket{0}^{\otimes 2\log_{2}{2k}-1}\ket{0}^{\otimes
2\log_{2}{k}-1}\ket{0}^{\otimes 2\log_{2}{k}-1}$
$\displaystyle\qquad\ket{0}^{\otimes 4\log_{2}{2k}-3}\ket{0}^{\otimes
4\log_{2}{k}-2}\ket{scratch}$ $\displaystyle\xrightarrow{U_{\phi_{a}+1}}$
$\displaystyle\left(\frac{1}{\sqrt{2k^{4}}}\sum_{i=0}^{2k^{4}-1}\ket{i+1}\right)\left(\sum_{j_{1}\dots
j_{a}\dots j_{|\Omega|}=0}^{2k-1}c_{j_{1}\dots j_{a}\dots
j_{|\Omega|}}\ket{j_{1}\dots j_{a}+1\dots j_{|\Omega|}}\right)\ket{k}$
$\displaystyle\qquad\ket{0}^{\otimes\log_{2}{2k}}\ket{0}^{\otimes\log_{2}{k}}\ket{0}^{\otimes
2\log_{2}{2k}-1}\ket{0}^{\otimes 2\log_{2}{2k}-1}\ket{0}^{\otimes
2\log_{2}{k}-1}\ket{0}^{\otimes 2\log_{2}{k}-1}$
$\displaystyle\qquad\ket{0}^{\otimes 4\log_{2}{2k}-3}\ket{0}^{\otimes
4\log_{2}{k}-2}\ket{scratch}$ $\displaystyle\xrightarrow{U_{\phi-k}}$
$\displaystyle\left(\frac{1}{\sqrt{2k^{4}}}\sum_{i=0}^{2k^{4}-1}\ket{i+1}\right)\left(\sum_{j_{1}\dots
j_{a}\dots j_{|\Omega|}=0}^{2k-1}c_{j_{1}\dots j_{a}\dots
j_{|\Omega|}}\ket{j_{1}\dots j_{a}+1-k\dots j_{|\Omega|}}\ket{k}\right)$
$\displaystyle\qquad\ket{0}^{\otimes\log_{2}{2k}}\ket{0}^{\otimes\log_{2}{k}}\ket{0}^{\otimes
2\log_{2}{2k}-1}\ket{0}^{\otimes 2\log_{2}{2k}-1}\ket{0}^{\otimes
2\log_{2}{k}-1}\ket{0}^{\otimes 2\log_{2}{k}-1}$
$\displaystyle\qquad\ket{0}^{\otimes 4\log_{2}{2k}-3}\ket{0}^{\otimes
4\log_{2}{k}-2}\ket{scratch}$
$\displaystyle\xrightarrow{\text{CNOT}_{\phi,\phi_{anc}}\otimes\text{CNOT}_{K,K_{anc}}}$
$\displaystyle\left(\frac{1}{\sqrt{2k^{4}}}\sum_{i=0}^{2k^{4}-1}\ket{i+1}\right)\left(\sum_{j_{1}\dots
j_{a}\dots j_{|\Omega|}=0}^{2k-1}c_{j_{1}\dots j_{a}\dots
j_{|\Omega|}}\ket{j_{1}\dots j_{a}+1-k\dots j_{|\Omega|}}\ket{k}\right.$
$\displaystyle\qquad\left.\ket{j_{a}+1-k}\ket{k}\right)\ket{0}^{\otimes
2\log_{2}{2k}-1}\ket{0}^{\otimes 2\log_{2}{2k}-1}\ket{0}^{\otimes
2\log_{2}{k}-1}\ket{0}^{\otimes 2\log_{2}{k}-1}$
$\displaystyle\qquad\ket{0}^{\otimes 4\log_{2}{2k}-3}\ket{0}^{\otimes
4\log_{2}{k}-2}\ket{scratch}$
$\displaystyle\xrightarrow{U_{\phi\times\phi_{anc},\phi_{anc}^{2}}\otimes
U_{K\times K_{anc},K_{anc}^{2}}}$
$\displaystyle\left(\frac{1}{\sqrt{2k^{4}}}\sum_{i=0}^{2k^{4}-1}\ket{i+1}\right)\left(\sum_{j_{1}\dots
j_{a}\dots j_{|\Omega|}=0}^{2k-1}c_{j_{1}\dots j_{a}\dots
j_{|\Omega|}}\ket{j_{1}\dots j_{a}+1-k\dots j_{|\Omega|}}\ket{k}\right.$
$\displaystyle\qquad\left.\ket{j_{a}+1-k}\ket{k}\ket{(j_{a}+1-k)^{2}}\ket{0}^{\otimes
2\log_{2}{2k}-1}\ket{k^{2}}\ket{0}^{\otimes 2\log_{2}{k}-1}\right)$
$\displaystyle\qquad\ket{0}^{\otimes 4\log_{2}{2k}-3}\ket{0}^{\otimes
4\log_{2}{k}-2}\ket{scratch}$ $\displaystyle\xrightarrow{\text{CNOT
ladder}\otimes\text{CNOT ladder}}$
$\displaystyle\left(\frac{1}{\sqrt{2k^{4}}}\sum_{i=0}^{2k^{4}-1}\ket{i+1}\right)\left(\sum_{j_{1}\dots
j_{a}\dots j_{|\Omega|}=0}^{2k-1}c_{j_{1}\dots j_{a}\dots
j_{|\Omega|}}\ket{j_{1}\dots j_{a}+1-k\dots j_{|\Omega|}}\ket{k}\right.$
$\displaystyle\qquad\left.\ket{j_{a}+1-k}\ket{k}\ket{(j_{a}+1-k)^{2}}\ket{(j_{a}+1-k)^{2}}\ket{k^{2}}\ket{k^{2}}\right)$
$\displaystyle\qquad\ket{0}^{\otimes 4\log_{2}{2k}-3}\ket{0}^{\otimes
4\log_{2}{k}-2}\ket{scratch}$
$\displaystyle\xrightarrow{U_{\phi^{2}\times\phi^{2},\phi^{4}_{anc}}\otimes
U_{k^{2}\times k^{2},k^{4}_{anc}}}$
$\displaystyle\left(\frac{1}{\sqrt{2k^{4}}}\sum_{i=0}^{2k^{4}-1}\ket{i+1}\right)\left(\sum_{j_{1}\dots
j_{a}\dots j_{|\Omega|}=0}^{2k-1}c_{j_{1}\dots j_{a}\dots
j_{|\Omega|}}\ket{j_{1}\dots j_{a}+1-k\dots j_{|\Omega|}}\ket{k}\right.$
$\displaystyle\qquad\left.\ket{j_{a}+1-k}\ket{k}\ket{(j_{a}+1-k)^{2}}\ket{(j_{a}+1-k)^{2}}\ket{k^{2}}\ket{k^{2}}\right)$
$\displaystyle\qquad\ket{(j_{a}+1-k)^{4}}\ket{k^{4}}\ket{scratch}$
$\displaystyle\xrightarrow{U_{\phi^{4}_{anc}+K^{4}_{anc}}}$
$\displaystyle\left(\frac{1}{\sqrt{2k^{4}}}\sum_{i=0}^{2k^{4}-1}\ket{i+1}\right)\left(\sum_{j_{1}\dots
j_{a}\dots j_{|\Omega|}=0}^{2k-1}c_{j_{1}\dots j_{a}\dots
j_{|\Omega|}}\ket{j_{1}\dots j_{a}+1-k\dots j_{|\Omega|}}\ket{k}\right.$
$\displaystyle\qquad\left.\ket{j_{a}+1-k}\ket{k}\ket{(j_{a}+1-k)^{2}}\ket{(j_{a}+1-k)^{2}}\ket{k^{2}}\ket{k^{2}}\right)$
$\displaystyle\qquad\ket{k^{4}+(j_{a}+1-k)^{4}}\ket{k^{4}}\ket{scratch}$

As before, the ancilla count for $U_{initial}$ is given by the number of
ancillae used to store values, as well as those used in the $\ket{scratch}$
register actually used to compute the values. Those used to store values are
now given by

  * •

$\log_{2}{(2k^{4})}$ (for the comparison)

  * •

$\log_{2}{(k)}$ (store $\ket{k}$)

  * •

$\log_{2}{(2k)}$ (copy $\ket{\phi}_{a}$)

  * •

$\log_{2}{(k)}$ (copy $\ket{k}$)

  * •

$2\log_{2}{(2k)}$ (product of two $\log_{2}{(2k)}$ numbers)

  * •

$2\log_{2}{(k)}$ (product of two $\log_{2}{(k)}$ numbers)

  * •

$2\log_{2}{(2k)}$ (copy $(j_{a}+1-k)^{2}$)

  * •

$2\log_{2}{(k)}$ (copy $k^{2}$)

  * •

$4\log_{2}{(2k)}$ (product of two $2\log_{2}{(2k)}$ numbers)

  * •

$4\log_{2}{(k)}$ (product of two $2\log_{2}{(k)}$ numbers)

In addition, the number of ancillae used in $\ket{scratch}$ to actually carry
out the various computations in $U_{initial}$ is given by

  * •

$\log_{2}{(2k^{2})}-1$ ($U_{P+1}$)

  * •

$\log_{2}{(2k)}-1$ ($U_{\phi_{a}+1}$)

  * •

$\log_{2}{(2k)}$ ($U_{\phi-k}$)

  * •

$\left[\log_{2}{(2k)}+1\right]\left[2\log_{2}{(2k)}-1\right]+1$
($U_{\phi\times\phi_{anc},\phi_{anc}^{2}}$)

  * •

$\left[\log_{2}{(k)}+1\right]\left[2\log_{2}{(k)}-1\right]+1$ ($U_{K\times
K_{anc},K^{2}}$)

  * •

$\left[2\log_{2}{(2k)}+1\right]\left[4\log_{2}{(2k)}-1\right]+1$
($U_{\phi^{2}\times\phi^{2},\phi_{anc}^{4}}$)

  * •

$\left[2\log_{2}{(k)}+1\right]\left[4\log_{2}{(k)}-1\right]+1$
($U_{K^{2}\times K^{2},K_{anc}^{2}}$)

  * •

$4\log_{2}{(2k)}$ ($U_{\phi^{4}_{anc}+K^{4}_{anc}}$)

With this redefinition of $U_{initial}$ and the resultant definitions using
Eq. (366), we obtain

$U_{PREP}^{\dagger}U_{SELECT}U_{PREP}\overline{\ket{0}}\ket{\phi}\ket{0}_{anc}=\left(\overline{\ket{0}}\frac{\hat{\phi}^{4}}{|\phi_{max}|^{4}}\ket{\phi}+\ket{\Phi^{\perp}}\right)\ket{0}_{anc}$
(372)

where $\left(|\overline{0}\rangle\langle\overline{0}|\otimes
I\right)|\Phi^{\perp}\rangle=0$, and we obtain the state
$\hat{\phi}^{4}|\phi\rangle$ with probability
$\frac{|\hat{\phi}^{4}|\phi\rangle|^{2}}{|\phi_{max}|^{8}}$ upon post-
selection.

Just as before, let us denote this entire sequence as $U_{initial}$. Let
$n=\log_{2}{2k}$. The two incrementers cost $(n-2)+(4n-3)$ ANDs, the
subtraction $n$, the (first round of) multiplications
$(2n^{2}-1)+(2(n-1)^{2}-1)$, the (first round of) CNOTs none, the (second
round of) multiplications $(8n^{2}-1)+(8(n-1)^{2}-1)$, and the addition $4n$
ANDs. Adding all these, the cost of $U_{initial}$ is now $20n^{2}-10n+1$ ANDs.
Since the cost of $U_{initial}^{\dagger}$ is the same, these operations cost a
total of $2|\Omega|\left(20n^{2}-10n+1\right)$ ANDs, or
$8|\Omega|\left(20n^{2}-10n+1\right)$ T gates.

Just as before, we follow this with a $\texttt{CMP}^{\prime}$ operation,
followed by a (multi)-controlled $Z$, then the $\texttt{CMP}^{\prime\dagger}$
operation. The $\texttt{CMP}^{\prime}$ operation (and its inverse) compares
two $\log_{2}{2k^{4}}$-qubit numbers and costs $\log_{2}{2k^{4}}$ many ANDs.
Thus, the comparisons require $|\Omega|\log_{2}{2k^{4}}$ many logical ANDs
across the entire lattice, contributing to a T gate count of
$4|\Omega|\log_{2}{2k^{4}}$.

In addition, each $Z$ gate must be controlled on the state of
$2+\log_{2}{|\Omega|}=\log_{2}{4|\Omega|}$ many qubits. Each of these can be
performed using $\log_{2}{4|\Omega|}-1=\log_{2}{2|\Omega|}$ many logical ANDs
(and as many uncomputations). Thus, these controlled gates contribute a total
of $|\Omega|\log_{2}{2|\Omega|}$ many logical ANDs, and therefore
$4|\Omega|\log_{2}{2|\Omega|}$ many T gates.

In all, the total T gate count for this family of terms is given by

$\displaystyle Count(T)_{\phi^{4}}$ $\displaystyle=$ $\displaystyle
2|\Omega|\left(20\log^{2}_{2}{k}+38\log_{2}{k}+2\log_{2}{|\Omega|}+15\right)$
(373)

###  C.2 Block encoding of $H_{amp}$ using binary decompositions

In this section first we describe in detail Algorithm IIIa, outlined in
Section IV.5.3, that simulates $H_{amp}$ (Eq. 11) using an LCU decomposition
of $\Phi$, obtained from the binary decomposition of integers. This helps in
expressing $\Phi$ as sum of Z operators and hence we obtain LCU decompoition
of $\Phi^{2}$ and $\Phi^{4}$ as sum of Z operators. The $\ell_{1}$ norm of the
coefficients of an LCU is referred to as the $\ell_{1}$ norm of the
decomposition or operator. We recall that
$H_{amp}=c\mathbb{I}+H_{amp}^{\prime}$, for some constant $c$. Thus it is
sufficient to implement $e^{-iH_{amp}^{\prime}\tau}$ because it is equal to
$e^{-iH_{amp}\tau}$ up to some global phase. We describe a block-encoding of
$H_{amp}^{\prime}$ by first block encoding each of its partitions and then
combining them using Theorem 13. We implement the circuits using Clifford+T
and rotation gates and apply optimization techniques (for example Theorem 14).
Thus we prove Theorem 22 in Section IV.5.3. Next, we prove a bound on the
$\ell_{1}$ norm of the Hamiltonian in Section C.2.1. Finally, we provide a
more detailed explanation about Algorithm IIIb outlined in Section IV.5.4,
where we obtain LCU decomposition of $\Phi^{2}$ and $\Phi^{4}$ from binary
representation of integers.

##### Decomposition of $\Phi$ :

We decompose $\frac{\Phi}{\Delta\Phi}$ as follows, as done in [15].

$\displaystyle\frac{\Phi}{\Delta\Phi}$ $\displaystyle=$
$\displaystyle\text{diag}(-k,\ldots,-1,0,1,\ldots,k-1)=\frac{1}{2}\text{diag}(-2k+1,\ldots,-1,1,\ldots,2k-1)-\frac{1}{2}\mathbb{I}$
(374) $\displaystyle=$
$\displaystyle-\frac{1}{2}\sum_{j=0}^{\log_{2}k}2^{j}\text{Z}_{j}-\frac{1}{2}\mathbb{I}$

Number of non-identity unitaries in the above LCU is $(\log_{2}k+1)$ and the
$\ell_{1}$ norm is $\frac{1}{2}\left[1+\sum_{j=0}^{\log_{2}k}2^{j}\right]=k$.

##### Decomposition of $\Phi^{2}$ :

From Eq. (374), we have

$\displaystyle\left(\frac{\Phi}{\Delta\Phi}\right)^{2}$ $\displaystyle=$
$\displaystyle\left(\frac{\Phi}{\Delta\Phi}+\frac{\mathbb{I}}{2}\right)^{2}-\left(\frac{\Phi}{\Delta\Phi}+\frac{\mathbb{I}}{2}\right)+\frac{\mathbb{I}}{4}$
(375) $\displaystyle=$
$\displaystyle\frac{1}{12}\left(4^{\log_{2}k+1}-1\right)\mathbb{I}+\sum_{j=0}^{\log_{2}k-1}\sum_{k>j}^{\log_{2}k}2^{j+k-1}\text{Z}_{j}\text{Z}_{k}+\frac{1}{2}\sum_{j=0}^{\log_{2}k}2^{j}\text{Z}_{j}+\frac{\mathbb{I}}{4}$
$\displaystyle=$
$\displaystyle\frac{1}{6}\left(2^{2\log_{2}k+1}+1\right)\mathbb{I}+\sum_{j=0}^{\log_{2}k-1}\sum_{k>j}^{\log_{2}k}2^{j+k-1}\text{Z}_{j}\text{Z}_{k}+\frac{1}{2}\sum_{j=0}^{\log_{2}k}2^{j}\text{Z}_{j}.$

Number of non-identity unitaries in this expansion is

$\displaystyle
1+\frac{\log_{2}k(\log_{2}k+1)}{2}+(\log_{2}k+1)=1+\frac{(\log_{2}k+1)(\log_{2}k+2)}{2}.$
(376)

If $\log_{2}k=\zeta$, then the $\ell_{1}$ norm is

$\displaystyle\frac{1}{6}\left(2^{2\zeta+1}+1\right)+\frac{1}{2}\sum_{j=0}^{\zeta}2^{j}\text{Z}_{j}+\frac{1}{2}\sum_{j=0}^{\zeta-1}2^{j}\sum_{k>j}^{\zeta}2^{k}$
(377) $\displaystyle=$
$\displaystyle\frac{1}{6}\left(2k^{2}+1\right)+\frac{1}{2}\left(2^{\zeta+1}-1\right)+\frac{1}{2}\sum_{j=0}^{\zeta-1}2^{j+j+1}\sum_{k=0}^{\zeta-(j+1)}2^{k}$
$\displaystyle=$
$\displaystyle\frac{k^{2}}{3}+\frac{1}{6}+k-\frac{1}{2}+\frac{1}{2}\sum_{j=0}^{\zeta-1}2^{2j+1}(2^{\zeta-j}-1)$
$\displaystyle=$
$\displaystyle\frac{k^{2}}{3}+k-\frac{1}{3}+\sum_{j=0}^{\zeta-1}2^{\zeta+j}-\sum_{j=0}^{\zeta-1}4^{j}$
$\displaystyle=$
$\displaystyle\frac{k^{2}}{3}+k-\frac{1}{3}+2^{\zeta}(2^{\zeta}-1)-\frac{4^{\zeta}-1}{3}$
$\displaystyle=$
$\displaystyle\frac{k^{2}}{3}+k-\frac{1}{3}+k^{2}-k-\frac{k^{2}}{3}+\frac{1}{3}=k^{2}.$

##### Decomposition of $\Phi^{4}$ :

Since
$\left(\frac{\Phi}{\Delta\Phi}\right)^{4}=\left(\left(\frac{\Phi}{\Delta\Phi}\right)^{2}\right)^{2}$,
so we can express it as sum of terms with 1, 2, 3 and up to 4 Z gates. So
number of unitaries in the decomposition can be at most

$\displaystyle
1+\binom{\zeta}{1}+\binom{\zeta}{2}+\binom{\zeta}{3}+\binom{\zeta}{4}\in$
(378) $\displaystyle=$
$\displaystyle\frac{1}{24}\left(\zeta^{4}-2\zeta^{3}+11\zeta^{2}+14\zeta+24\right)\qquad[\zeta=\log_{2}k]$
$\displaystyle\in$ $\displaystyle O(\zeta^{4})\quad\text{ or }\quad
O\left(\log_{2}^{4}k\right).$

To derive the $\ell_{1}$ norm of this decomposition we first observe that

$\displaystyle\left(\frac{\Phi}{\Delta\Phi}\right)^{4}=\left(\left(\frac{\Phi}{\Delta\Phi}\right)^{2}-\frac{2k^{2}+1}{6}\mathbb{I}\right)^{2}+2\frac{2k^{2}+1}{6}\left(\left(\frac{\Phi}{\Delta\Phi}\right)^{2}-\frac{2k^{2}+1}{6}\mathbb{I}\right)+\left(\frac{2k^{2}+1}{6}\right)^{2}\mathbb{I}.$

From Eq. 377 we know that that the $\ell_{1}$ norm of
$\left(\left(\frac{\Phi}{\Delta\Phi}\right)^{2}-\frac{2k^{2}+1}{6}\mathbb{I}\right)$
is $k^{2}-\frac{2k^{2}+1}{6}=\frac{2k^{2}}{3}-\frac{1}{6}$. Thus the
$\ell_{1}$ norm of $\left(\frac{\Phi}{\Delta\Phi}\right)^{4}$ is at most

$\displaystyle\left(\frac{2k^{2}}{3}-\frac{1}{6}\right)^{2}+2\cdot\frac{2k^{2}+1}{6}\left(\frac{2k^{2}}{3}-\frac{1}{6}\right)+\left(\frac{2k^{2}+1}{6}\right)^{2}=k^{4}.$
(379)

###### Proof of Theorem 22.

We re-collect that we have partitioned the Hamiltonian $H_{amp}^{\prime}$
(i.e. $H_{amp}$ without the $\mathbb{I}$ part) as follows.

$\displaystyle H_{1\vec{x}}$ $\displaystyle=$
$\displaystyle\sum_{j}\alpha_{j}Z_{j}+\sum_{j,k}\alpha_{jk}Z_{j}Z_{k}+\mathcal{F}\left(\sum_{j}\gamma_{j}Z_{j}+\sum_{j,k}\gamma_{jk}Z_{j}Z_{k}\right)\mathcal{F}^{\dagger}$
(380) $\displaystyle H_{2\vec{x}}$ $\displaystyle=$
$\displaystyle\sum_{j,k,l}\alpha_{jkl}Z_{j}Z_{k}Z_{l}+\sum_{j,k,l,m}\alpha_{jklm}Z_{j}Z_{k}Z_{l}Z_{m}$
(381) $\displaystyle H_{12}$ $\displaystyle=$
$\displaystyle\sum_{\vec{x}\in\Omega}H_{1\vec{x}}+H_{2\vec{x}}$ (382)
$\displaystyle H_{3\vec{x}\vec{x^{\prime}}}$ $\displaystyle=$
$\displaystyle\sum_{j,j^{\prime}}\beta_{jj^{\prime}}\left(Z_{j}\right)_{\vec{x}}\left(Z_{j^{\prime}}\right)_{\vec{x^{\prime}}}$
(383) $\displaystyle H_{3}$ $\displaystyle=$
$\displaystyle\sum_{(\vec{x},\vec{x^{\prime}})\in
E_{D}}H_{3\vec{x}\vec{x^{\prime}}}$ (384) $\displaystyle H_{amp}^{\prime}$
$\displaystyle=$ $\displaystyle H_{12}+H_{3}$ (385)

Let $L_{1}=\binom{\log_{2}k+1}{1}$, $L_{2}=\binom{\log_{2}k+1}{2}$,
$L_{3}=\binom{\log_{2}k+1}{3}$, $L_{4}=\binom{\log_{2}k+1}{4}$ and
$L_{5}=(\log_{2}k+1)^{2}$.

##### Block encoding of $H_{1\vec{x}}$ :

The ancilla preparation sub-routine is as follows. We assume a bijective map
between $j^{\prime}=(j,k)$ to some integer in $[L_{1}+1,L_{1}+L_{2}]$.

$\displaystyle\text{PREP}_{1\vec{x}}\ket{0}^{1+\log_{2}(L_{1}+L_{2})}$
$\displaystyle=$
$\displaystyle\frac{1}{\mathcal{N}_{1\vec{x}}}\left(\sum_{j=1}^{L_{1}}\sqrt{\alpha_{j}}\ket{j,0}+\sum_{j^{\prime}=L_{1}+1}^{L_{1}+L_{2}}\sqrt{\alpha_{j^{\prime}}}\ket{j^{\prime},0}+\sum_{j=1}^{L_{1}}\sqrt{\gamma_{j}}\ket{j,1}\right.$
(386)
$\displaystyle\left.+\sum_{j^{\prime}=L_{1}+1}^{L_{1}+L_{2}}\sqrt{\gamma_{j^{\prime}}}\ket{j^{\prime},0}\right)\qquad[\mathcal{N}_{1\vec{x}}\text{
is normalization constant.}]$

The last qubit is used to select the QFT. We require $1+\log_{2}(L_{1}+L_{2})$
qubits. For the state preparation we require $1+\log_{2}(L_{1}+L_{2})$ H,
$4(L_{1}+L_{2})-2$ rotation gates and
$4(L_{1}+L_{2})+3\log_{2}(L_{1}+L_{2})-4$ CNOT.

The select sub-routine does the following.

$\displaystyle\text{SELECT}_{1\vec{x}}\ket{j,0}\ket{\psi}$
$\displaystyle\rightarrow$ $\displaystyle\ket{j,0}Z_{j}\ket{\psi}$
$\displaystyle\text{SELECT}_{1\vec{x}}\ket{j,1}\ket{\psi}$
$\displaystyle\rightarrow$
$\displaystyle\ket{j,1}\mathcal{F}Z_{j}\mathcal{F}^{\dagger}\ket{\psi}$ (387)

If $j>L_{1}+1$ then we applly two Z gates depending on the mapping. The last
qubit is used to selectively apply the pairs of $(\log_{2}k+1)$-qubit QFT. We
require $L_{1}+L_{2}$ compute-uncompute pairs of $C^{\log_{2}(L_{1}+L_{2})}X$
gates, which can be synthesized efficiently using Theorem 14 [27]. If we
divide the control qubits into $M_{1}$ groups such that the $j^{th}$ group has
$\frac{1}{r_{j}}$ fraction of the qubits, then we require

$\displaystyle\sum_{i=1}^{M_{1}}(L_{1}+L_{2})^{\frac{1}{r_{i}}}C^{\frac{\log(L_{1}+L_{2})}{r_{i}}}X+(L_{1}+L_{2})\cdot
C^{M_{1}}X$

(compute-uncompute) pairs of gates. We assume equal partitioning into 2 groups
i.e. $M_{1}=2$ and $r_{1}=\frac{1}{2}$. Then, using the constructions in [75,
76] , i.e. from Eq. 91 we require

$\displaystyle
4\sqrt{L_{1}+L_{2}}\left(\log_{2}(L_{1}+L_{2})-2\right)+4(L_{1}+L_{2})$

T gates and

$\displaystyle\sqrt{L_{1}+L_{2}}\left(4\log_{2}(L_{1}+L_{2})-6\right)+5(L_{1}+L_{2})$

CNOT gates. Additionally we require
$(\log_{2}k+1)+\frac{\log_{2}k(\log_{2}k+1)}{2}=\frac{(\log_{2}k+1)(\log_{2}k+2)}{2}$
number of CZ gates and two $(\log_{2}k+1)$-qubit QFT. To implement the QFTs we
require approximately [71]

$\displaystyle
8(\log_{2}2k)\log_{2}\left(\frac{\log_{2}2k}{\epsilon}\right)+\log_{2}\left(\frac{\log_{2}2k}{\epsilon}\right)\log_{2}\left(\frac{\log_{2}\left(\frac{\log_{2}2k}{\epsilon}\right)}{\epsilon}\right)$

T gates and almost an equal number of CNOT gates.

##### Block encoding of $H_{2\vec{x}}$ :

The ancilla preparation sub-routine is as follows.

$\displaystyle\text{PREP}_{2\vec{x}}\ket{0}^{\log_{2}(L_{3}+L_{4})}=\frac{1}{\sqrt{\mathcal{N}_{2\vec{x}}}}\sum_{j=1}^{L_{3}+L_{4}}\sqrt{\alpha_{j}^{\prime\prime}}\ket{j}$
(388)

where $\alpha_{j}^{\prime\prime}$ are the weights obtained while expressing
$H_{2\vec{x}}$ as sum of Z operators (Eq. 381). For the state preparation we
require $\log_{2}(L_{3}+L_{4})$ H, $2(L_{3}+L_{4})+3\log_{2}(L_{3}+L_{4})-7$
CNOT and $2(L_{3}+L_{4})-2$ rotation gates.

The select sub-routines does the following :

$\displaystyle\text{SELECT}_{2\vec{x}}\ket{j}\ket{\psi}\rightarrow\ket{j}U_{j}\ket{\psi},$
(389)

where $U_{j}$ is the $j^{th}$ unitary in the LCU decomposition of
$H_{2\vec{x}}$ in Eq. 381. To selectively implement the unitaries we require
$L_{3}+L_{4}$ compute-uncompute pairs of $C^{\log_{2}(L_{3}+L_{4})}X$ gates.
Using Theorem 14 and assuming that the control qubits have been divided into
two equal groups, we require

$\displaystyle
2(L_{3}+L_{4})^{\frac{1}{2}}C^{\frac{\log(L_{3}+L_{4})}{2}}X+(L_{3}+L_{4})\cdot
C^{2}X$ (390)

(compute-uncompute) pairs. These in turn can be decomposed into

$\displaystyle
4\sqrt{L_{3}+L_{4}}\left(\log_{2}(L_{3}+L_{4})-2\right)+4(L_{3}+L_{4})$ (391)

T gates and

$\displaystyle\sqrt{L_{3}+L_{4}}\left(4\log_{2}(L_{3}+L_{4})-6\right)+5(L_{3}+L_{4})$
(392)

CNOT gates. Additionally, we require

$\displaystyle\binom{\log_{2}k+1}{3}+\binom{\log_{2}k+1}{4}=\binom{\log_{2}k+2}{4}$
(393)

CZ gates.

##### Block encoding of $H_{3\vec{x}\vec{x^{\prime}}}$ :

The ancilla preparation sub-routine is as follows.

$\displaystyle\text{PREP}_{3\vec{x}\vec{x^{\prime}}}\ket{0}^{\log_{2}L_{5}}=\frac{1}{\mathcal{N}_{3\vec{x}\vec{x^{\prime}}}}\sum_{j=1}^{L_{5}}\sqrt{\beta_{j}^{\prime}}\ket{j}$
(394)

where $\beta_{j}^{\prime}$ are the weights given in Eq. 383. For state
preparation we require $\log_{2}L_{5}$ H gates, $2L_{5}+3\log_{2}L_{5}-7$ CNOT
and $2L_{5}-2$ rotation gates.

The selection sub-routine is as follows.

$\displaystyle\text{SELECT}_{3\vec{x}\vec{x^{\prime}}}\ket{j}\ket{\psi}\rightarrow\ket{j}U_{j}\ket{\psi}$
(395)

where $U_{j}$ is the corresponding unitary. We require $L_{5}$ compute-
uncompute pairs of $C^{\log_{2}L_{5}}X$ gates. Again we apply Theorem 14 and
assume that the control qubits have been divided into two equal groups. Then
we require

$\displaystyle 2L_{5}^{\frac{1}{2}}C^{\frac{\log L_{5}}{2}}X+L_{5}\cdot
C^{2}X$ (396)

(compute-uncompute) pairs of gates. These can be further decomposed [75, 76]
into

$\displaystyle 4\sqrt{L_{5}}\left(\log_{2}L_{5}-2\right)+4L_{5}$ (397)

T gates and

$\displaystyle\sqrt{L_{5}}\left(4\log_{2}L_{5}-6\right)+5L_{5}$ (398)

CNOT gates. Additionally we require $\left(\log_{2}k+1\right)^{2}$ CZ gates.

##### Block encoding of $H_{12}$ :

We use the recursive block encoding Theorem 13. We can block encode
$H_{1\vec{x}}+H_{2\vec{x}}$ using ancilla preparation sub-routine that has 1 H
and 2 rotation gates. The unitary selection sub-routine adds an extra control
to each unitary. For $H_{12}$ we prepare an equal superposition of
$\log_{2}|\Omega|$ qubits, using $\log_{2}|\Omega|$ H gates and use these to
select an ancilla of each subspace. The rest of the operations are controlled
on this. Thus this adds another control. We require $|\Omega|$ number of
$C^{\log_{2}|\Omega|}X$ compute-uncompute pairs of gates. Using Theorem 14 and
assuming an equal partitioning of the control qubits into two equal groups, we
can implement the multi-controlled-X gates using

$\displaystyle|\Omega|^{\frac{1}{2}}C^{\frac{\log|\Omega|}{2}}+|\Omega|\cdot
C^{M_{4}}X$ (399)

(compute-uncompute) pairs, that can be further decomposed [75, 76] into

$\displaystyle 4\sqrt{|\Omega|}\left(\log_{2}|\Omega|-2\right)+4|\Omega|$
(400)

T gates and

$\displaystyle\sqrt{|\Omega|}\left(4\log_{2}|\Omega|-6\right)+5|\Omega|$ (401)

CNOT gates.

##### Block encoding of $H_{3}$ :

We use Theorem 13. We prepare $\log_{2}|E_{D}|$ qubits in equal superposition,
using $\log_{2}|E_{D}|$ H gates. We use these to select two sub-spaces.
Specifically, each superimposed state selects an ancilla. From this ancilla we
use two CNOTs to select an ancilla in each of the two corresponding sub-
spaces. The rest of the operations are controlled on these ancillae. So, each
unitary of $H_{3\vec{x}\vec{x^{\prime}}}$ has 1 extra control. Using Theorem
14 and assuming an equal partitioning into two groups, for the selection we
require

$\displaystyle 2|E_{D}|^{\frac{1}{2}}C^{\frac{\log|E_{D}|}{2}}X+|E_{D}|\cdot
C^{M_{5}}X$ (402)

(compute-uncompute) pairs. These, in turn can be decomposed [75, 76] into

$\displaystyle 4\sqrt{|E_{D}|}\left(\log_{2}|E_{D}|-2\right)+4|E_{D}|$ (403)

T gates and

$\displaystyle\sqrt{|E_{D}|}\left(4\log_{2}|E_{D}|-6\right)+5|E_{D}|$ (404)

CNOT gates.

##### Block encoding of $H$ :

We prepare 1 qubit in equal superposition using 1 H. The rest of the
operations are controlled on this. So it adds an extra control. Thus overall,
unitaries in $H_{1\vec{x}}$, $H_{2\vec{x}}$ have 3 extra controls and
unitaries in $H_{3\vec{x}\vec{x^{\prime}}}$ have 2 extra controls. Thus for
each unitary in $H_{1\vec{x}}$, $H_{2\vec{x}}$ we require a (compute-
uncompute) pair of $C^{3}X$, that can be implemented with $8$ T and $9$ CNOT
gates. Each unitary in $H_{3\vec{x}\vec{x^{\prime}}}$ require a (compute-
uncompute) pair of $C^{2}X$, that can be implemented with $4$ T and $5$ CNOT
gates.

Overall, we require following numbers of T gates,

$\displaystyle N_{t}$ $\displaystyle\leq$
$\displaystyle|\Omega|\left[4\sqrt{L_{1}+L_{2}}\left(\log_{2}(L_{1}+L_{2})-2\right)+12(L_{1}+L_{2})+4\sqrt{L_{3}+L_{4}}\left(\log_{2}(L_{3}+L_{4})-2\right)+12(L_{3}+L_{4})\right]$
(405)
$\displaystyle+|E_{D}|\left(4\sqrt{L_{5}}\left(\log_{2}L_{5}-2\right)+8L_{5}\right)+4\sqrt{|\Omega|}\left(\log_{2}|\Omega|-2\right)+4|\Omega|+4\sqrt{|E_{D}|}\left(\log_{2}|E_{D}|-2\right)+4|E_{D}|$
$\displaystyle+2|\Omega|\left(8(\log_{2}2k)\log_{2}\left(\frac{\log_{2}2k}{\epsilon_{QFT}}\right)+\log_{2}\left(\frac{\log_{2}2k}{\epsilon_{QFT}}\right)\log_{2}\left(\frac{\log_{2}\left(\frac{\log_{2}2k}{\epsilon_{QFT}}\right)}{\epsilon_{QFT}}\right)\right)$

following number of CNOT gates,

$\displaystyle N_{cx}$ $\displaystyle\in$
$\displaystyle|\Omega|\left[\sqrt{L_{1}+L_{2}}\left(4\log_{2}(L_{1}+L_{2})-6\right)+14(L_{1}+L_{2})+\sqrt{L_{3}+L_{4}}\left(4\log_{2}(L_{3}+L_{4})-6\right)+14(L_{3}+L_{4})\right]$
(406)
$\displaystyle+|E_{D}|\left(\sqrt{L_{5}}\left(4\log_{2}L_{5}-6\right)+10L_{5}\right)+\sqrt{|\Omega|}\left(4\log_{2}|\Omega|-6\right)+5|\Omega|+\sqrt{|E_{D}|}\left(4\log_{2}|E_{D}|-6\right)+5|E_{D}|$
$\displaystyle+2|\Omega|\left(8(\log_{2}2k)\log_{2}\left(\frac{\log_{2}2k}{\epsilon_{QFT}}\right)+\log_{2}\left(\frac{\log_{2}2k}{\epsilon_{QFT}}\right)\log_{2}\left(\frac{\log_{2}\left(\frac{\log_{2}2k}{\epsilon_{QFT}}\right)}{\epsilon_{QFT}}\right)\right)$
$\displaystyle+2(2(L_{1}+L_{2})+L_{3}+L_{4}+L_{5})+3(\log_{2}(L_{1}+L_{2})+\log_{2}(L_{3}+L_{4})+\log_{2}L_{5})-21$

following number of rotation gates,

$\displaystyle N_{r}\leq 4(L_{1}+L_{2})+2(L_{3}+L_{4})+2L_{5}-4$ (407)

following number of CZ gates

$\displaystyle
N_{cz}\leq|\Omega|\left(L_{1}+L_{2}+L_{3}+L_{4}\right)+|E_{D}|L_{5},$ (408)

and the following number of H gates,

$\displaystyle N_{h}\leq
3+\log_{2}(L_{1}+L_{2})+\log_{2}(L_{3}+L_{4})+\log_{2}L_{5}+\log_{2}|E_{D}|+\log_{2}|\Omega|,$
(409)

where $L_{1}=\log_{2}k+1$, $L_{2}=\binom{\log_{2}k+1}{2}$,
$L_{3}=\binom{\log_{2}k+1}{3}$, $L_{4}=\binom{\log_{2}k+1}{4}$ and
$L_{5}=(\log_{2}k+1)^{2}$. Hence we prove Theorem 22.

∎

####  C.2.1 $\ell_{1}$ norm of $H_{amp}^{\prime}$

In this section we prove a bound on the $\ell_{1}$ norm of the implemented
Hamiltonian i.e. $H_{amp^{\prime}}$, as decomposed in Eq 380-385.

###### Proof of Lemma 23.

We try to shave off most of the identity factors, as these contribute to a
global phase only. Let $|\Delta\Phi|:=\Delta$ and $\log_{2}k:=\zeta$.

$\displaystyle B_{1}$ $\displaystyle:=$
$\displaystyle\sum_{j=0}^{\zeta}2^{j}Z_{j}$ $\displaystyle B_{2}$
$\displaystyle:=$
$\displaystyle\sum_{j=0}^{\zeta-1}\sum_{k>j}^{\zeta}2^{j+k}Z_{j}Z_{k}$
$\displaystyle A_{1}$ $\displaystyle:=$
$\displaystyle\left(\frac{\hat{\Phi}}{\Delta}\right)^{2}-\frac{2k^{2}+1}{6}\mathbb{I}=\frac{B_{1}+B_{2}}{2}$

Each one of the above matrices is a sum of non-identity operators. Now we
express each summand as a function of the above operators and identity.

$\displaystyle\left(\frac{\hat{\Phi}}{\Delta}\right)^{2}$ $\displaystyle=$
$\displaystyle A_{1}+\frac{2k^{2}+1}{6}\mathbb{I}$ (410)
$\displaystyle\left(\frac{\hat{\Phi}}{\Delta}\right)^{4}$ $\displaystyle=$
$\displaystyle
A_{1}^{2}+\frac{2k^{2}+1}{3}A_{1}+\left(\frac{2k^{2}+1}{6}\right)^{2}\mathbb{I}+\left(\frac{2k^{2}+1}{3}\right)A_{1}$
(411) $\displaystyle\left(\frac{\Pi}{\Delta}\right)^{2}$ $\displaystyle=$
$\displaystyle\mathcal{F}\left(\frac{\hat{\Phi}}{\Delta}\right)^{2}\mathcal{F}^{\dagger}=\mathcal{F}A_{1}\mathcal{F}^{\dagger}+\frac{2k^{2}+1}{6}\mathbb{I}$
(412) $\displaystyle B_{1}^{2}$ $\displaystyle=$
$\displaystyle\left(\sum_{j=0}^{\zeta}2^{j}Z_{j}\right)^{2}=\frac{4k^{2}-1}{3}\mathbb{I}+\frac{1}{2}B_{2}$
(413) $\displaystyle A_{1}^{2}$ $\displaystyle=$
$\displaystyle\frac{1}{4}\left(B_{1}^{2}+B_{2}^{2}+2B_{1}B_{2}\right)=\frac{4k^{2}-1}{12}\mathbb{I}+\frac{1}{8}B_{2}+\frac{1}{4}B_{2}^{2}+\frac{1}{2}B_{1}B_{2}$
(414)

Now consider the following term.

$\displaystyle\sum_{\vec{x}\in\Omega}\sum_{\vec{x^{\prime}}\in\mathcal{N}_{x}}\Phi(\vec{x})\Phi(\vec{x^{\prime}})$
(415) $\displaystyle=$
$\displaystyle\left(\frac{\Delta}{2}\right)^{2}\sum_{\vec{x}}\sum_{\vec{x^{\prime}}\in\mathcal{N}_{x}}\left(\mathbb{I}+\sum_{j=0}^{\zeta}2^{j}Z_{j,x}+\sum_{j^{\prime}=0}^{\zeta}2^{j^{\prime}}Z_{j^{\prime},x^{\prime}}+\sum_{j,j^{\prime}=0}^{\zeta}2^{j+j^{\prime}}Z_{j,x}Z_{j^{\prime},x^{\prime}}\right)$
$\displaystyle=$
$\displaystyle\left(\frac{\Delta}{2}\right)^{2}\sum_{\vec{x}}\sum_{\vec{x}\in\mathcal{N}_{x}}\left(\mathbb{I}+B_{1,x}+B_{1,x^{\prime}}+\sum_{j,j^{\prime}=0}^{\zeta}2^{j+j^{\prime}}Z_{j,x}Z_{j^{\prime},x^{\prime}}\right)$
$\displaystyle:=$
$\displaystyle\left(\frac{\Delta}{2}\right)^{2}\sum_{\vec{x}}\sum_{\vec{x^{\prime}}\in\mathcal{N}_{x}}\left(\mathbb{I}+B_{1,x}+B_{1,x^{\prime}}+B_{3,x,x^{\prime}}\right)$

Plugging Eq. 410-415 in the expression for $H_{amp}$ we obtain the following.

$\displaystyle H_{amp}$ $\displaystyle=$
$\displaystyle\sum_{\vec{x}}c_{\mathbb{I}}\mathbb{I}+\sum_{\vec{x}}\left(\frac{\lambda\Delta^{4}}{24}A_{1}^{2}+\frac{\Delta^{2}}{2}\mathcal{F}A_{1}\mathcal{F}^{\dagger}+\left(\frac{(M^{2}+1)\Delta^{2}}{4}+\frac{\lambda\Delta^{4}(2k^{2}+1)}{144}\right)B_{1}\right.$
(416)
$\displaystyle\left.\left(\frac{(M^{2}+d)\Delta^{2}}{4}+\frac{\lambda\Delta^{4}(2k^{2}+1)}{144}\right)B_{2}\right)-\frac{\Delta^{2}}{2}\sum_{\vec{x}}\sum_{\vec{x^{\prime}}\in\mathcal{N}_{x}}B_{3,x,x^{\prime}}$
$\displaystyle=$
$\displaystyle\sum_{\vec{x}}c_{\mathbb{I}}^{\prime}\mathbb{I}+\sum_{\vec{x}}\frac{\Delta^{2}}{2}\mathcal{F}A_{1}\mathcal{F}^{\dagger}-\frac{\Delta^{2}}{2}\sum_{\vec{x},\vec{x^{\prime}}}B_{3,x,x^{\prime}}+\sum_{\vec{x}}\left(\frac{(M^{2}+1)\Delta^{2}}{4}+\frac{\lambda\Delta^{4}(2k^{2}+1)}{144}\right)B_{1}$
$\displaystyle+\sum_{\vec{x}}\frac{\lambda\Delta^{4}}{48}B_{1}B_{2}+\sum_{\vec{x}}\left(\frac{(M^{2}+d)\Delta^{2}}{4}+\frac{\lambda\Delta^{4}(2k^{2}+1)}{144}+\frac{\lambda\Delta^{4}}{192}\right)B_{2}+\sum_{\vec{x}}\frac{\lambda\Delta^{4}}{96}B_{2}^{2}$

Now we compute the norms of the following.

$\displaystyle\|A_{1}\|$ $\displaystyle\leq$
$\displaystyle\frac{2k^{2}}{3}-\frac{1}{6}$
$\displaystyle\|B_{3,x,x^{\prime}}\|$ $\displaystyle\leq$
$\displaystyle(2k-1)^{2}$ $\displaystyle\|B_{1}\|$ $\displaystyle\leq$
$\displaystyle 2k-1$ $\displaystyle\|B_{2}\|$ $\displaystyle\leq$
$\displaystyle 2\left(\frac{2k^{2}}{3}-k+\frac{1}{3}\right)$
$\displaystyle\|B_{2}^{2}\|$ $\displaystyle\leq$ $\displaystyle
4\left(\frac{4k^{4}}{9}-\frac{4k^{3}}{3}+\frac{13k^{2}}{9}-\frac{2k}{3}+\frac{1}{9}\right)$
$\displaystyle\|B_{1}B_{2}\|$ $\displaystyle\leq$ $\displaystyle
2\left(\frac{4k^{3}}{3}-\frac{8k^{2}}{3}+\frac{5k}{3}-\frac{1}{3}\right)$

Substituting the above inequalities in Eq. 416 we have the following, thus
proving Lemma 23.

$\displaystyle\|H_{amp}^{\prime}\|$ $\displaystyle\leq$
$\displaystyle|\Omega|\left(\frac{\lambda\Delta^{4}}{27}k^{4}+k^{2}\left(\left(\frac{M^{2}+7d+1}{3}\right)\Delta^{2}-0.048611\lambda\Delta^{4}\right)+k\left(-3d\Delta^{2}+0.03125\lambda\Delta^{4}\right)\right.$
(417)
$\displaystyle\left.+\Delta^{2}\left(\frac{-M^{2}+8d-4}{6}\right)-0.0081019\lambda\Delta^{4}\right)$

∎

####  C.2.2 Block encoding using binary decomposition for all operators

In this section we first prove Theorem 29 in detail and then we explicitly
construct some circuits for the signature matrices arising in the
decomposition of $\Phi^{2}$ and $\Phi^{4}$.

###### Proof of Theorem 29.

In this case we partition $H_{amp}$ as follows.

$\displaystyle H_{\phi^{2}\vec{x}}$ $\displaystyle=$
$\displaystyle\Pi^{2}(\vec{x})+(M^{2}+d+1)\Phi^{2}(\vec{x})$ $\displaystyle
H_{\phi^{4}\vec{x}}$ $\displaystyle=$ $\displaystyle\Phi^{4}(\vec{x})$
$\displaystyle H_{\phi\vec{x}\vec{x^{\prime}}}$ $\displaystyle=$
$\displaystyle\Phi(\vec{x})\Phi(\vec{x^{\prime}})=H_{3\vec{x}\vec{x^{\prime}}}$
$\displaystyle H_{3}$ $\displaystyle=$
$\displaystyle\sum_{\vec{x},\vec{x^{\prime}}\in
E_{D}}H_{3\vec{x}\vec{x^{\prime}}}$ $\displaystyle H_{12}^{\prime}$
$\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{\vec{x}\in\Omega}H_{\phi^{2}\vec{x}}+\frac{\Lambda}{4!}H_{\phi^{4}\vec{x}}$
$\displaystyle H_{amp}$ $\displaystyle=$ $\displaystyle H_{12}^{\prime}+H_{3}$
(418)

The recursive block encoding is done in a similar fashion as before. We give
brief descriptions with gate complexity.

##### Block encoding of $H_{\phi^{2}\vec{x}}$ :

Let $\Phi^{2}=\sum_{j=0}^{2\log_{2}k}U_{j}$, where $U_{j}$ is a signature
matrix. These can be obtained using Lemma 16, as described in Section IV.5.4.
The ancilla preparation sub-routine is,

$\displaystyle\text{PREP}_{\phi^{2}\vec{x}}=\frac{1}{\mathcal{N}_{\phi^{2}\vec{x}}}\left(\sum_{j=0}^{2\log_{2}k}\sqrt{\alpha_{j}}\ket{j,0}+\sum_{l=0}^{2\log_{2}k}\sqrt{\beta_{l}}\ket{l,1}\right),$
(419)

where the weights $\alpha_{j}$ and $\beta_{l}$ include the coefficients from
LCU decomposition of operators $\Phi^{2}$ and
$\Pi^{2}=\mathcal{F}\Phi^{2}\mathcal{F}^{\dagger}$, as well as the
coefficients of $\Phi^{2}$ and $\Pi^{2}$ in the definition of the Hamiltonian.
The last qubit is used to select the QFT. We require $1+\log_{2}(2\log_{2}k)$
qubits. For the state preparation we require $1+\log_{2}(2\log_{2}k)$ H,
$4\log_{2}(k)-2$ rotations, $4\log_{2}(k)+3\log_{2}(2\log_{2}k)-7$ CNOT gates.

The SELECT sub-routine does the following.

$\displaystyle\text{SELECT}_{\phi^{2}\vec{x}}\ket{j,0}\ket{\psi}$
$\displaystyle\mapsto\ket{j,0}U_{j}\ket{\psi}$
$\displaystyle\text{SELECT}_{\phi^{2}\vec{x}}\ket{j,1}\ket{\psi}$
$\displaystyle\mapsto\ket{j,0}\mathcal{F}U_{j}\mathcal{F}^{\dagger}\ket{\psi}$
(420)

As explained, we require $2\log_{2}k$ number of $C^{\log(2\log k)}X$ gates to
select the unitaries. Using Theorem 14, if we divide the control qubits into 2
equal groups then we require the following number of T gates to implement the
control that selects the signature matrices

$\displaystyle 4\sqrt{2\log_{2}k}(\log(2\log_{2}k)-2)+8\log_{2}k,$ (421)

and the following number of CNOT gates

$\displaystyle\sqrt{2\log_{2}k}(4\log(2\log_{2}k)-6)+10\log_{2}k.$ (422)

Additionally, assuming Conjecture 28 we require $O(\log^{2}k)$ number of
T-gates for the implementation of the signature matrices. We also requrie two
$\log_{2}k+1$-qubit QFT.

##### Block encoding of $H_{\phi^{4}\vec{x}}$ :

Let $\Phi^{4}=\sum_{j=0}^{4\log_{2}k}U_{j}$, where $U_{j}$ is a signature
matrix obtained using Lemma 16, as described in Section IV.5.4. The ancilla
preparation sub-routine is as follows.

$\displaystyle\text{PREP}_{\phi^{4}\vec{x}}=\frac{1}{\mathcal{N}_{\phi^{4}\vec{x}}}\sum_{j=0}^{4\log_{2}k}\sqrt{\alpha_{j}}\ket{j}$
(423)

where the weights $\alpha_{j}$ include the coefficients from LCU decomposition
of operators $\Phi^{4}$. We require $1+\log_{2}(4\log_{2}k)$ qubits. For the
state preparation we require $1+\log_{2}(4\log_{2}k)$ H, $8\log_{2}(k)-2$
rotations, $8\log_{2}(k)+3\log_{2}(4\log_{2}k)-7$ CNOT gates.

The SELECT sub-routine does the following.

$\displaystyle\text{SELECT}_{\phi^{4}\vec{x}}\ket{j,0}\ket{\psi}$
$\displaystyle\mapsto\ket{j}U_{j}\ket{\psi}$

As explained, we require $4\log_{2}k$ number of $C^{\log(4\log k)}X$ gates to
select the unitaries. Using Theorem 14, if we divide the control qubits into 2
equal groups then we require the following number of T gates

$\displaystyle 4\sqrt{4\log_{2}k}(\log(4\log_{2}k)-2)+16\log_{2}k,$ (425)

and the following number of CNOT gates

$\displaystyle\sqrt{4\log_{2}k}(4\log(4\log_{2}k)-6)+20\log_{2}k.$ (426)

Assuming Conjecture 28 we require $O(\log^{2}k)$ T-gates to implement the
signature matrices.

##### Block encoding of $H_{12}^{\prime}$ :

We use the recursive block encoding Theorem 13. We can block encode
$H_{\phi^{2}\vec{x}}+\frac{\Lambda}{24}H_{\phi^{4}\vec{x}}$ using ancilla
preparation sub-routine that has 1 H and 2 rotation gates. For
$H_{12}^{\prime}$ we prepare an equal superposition of $\log_{2}|\Omega|$
qubits, using $\log_{2}|\Omega|$ H gates and use these to select an ancilla of
each subspace. The rest of the operations are controlled on this. Thus this
adds another control. We require $|\Omega|$ number of $C^{\log_{2}|\Omega|}X$
compute-uncompute pairs of gates. Using Theorem 14 and assuming an equal
partitioning of the control qubits into two equal groups, we can implement the
multi-controlled-X gates using

$\displaystyle|\Omega|^{\frac{1}{2}}C^{\frac{\log|\Omega|}{2}}X+|\Omega|\cdot
C^{2}X$ (427)

(compute-uncompute) pairs, that can be further decomposed [75, 76] into

$\displaystyle 4\sqrt{|\Omega|}\left(\log_{2}|\Omega|-2\right)+4|\Omega|$
(428)

T gates and

$\displaystyle\sqrt{|\Omega|}\left(4\log_{2}|\Omega|-6\right)+5|\Omega|$ (429)

CNOT gates.

##### Block encoding of $H_{3\vec{x}\vec{x^{\prime}}}$ and $H_{3}$ :

The block encoding of
$\Phi(\vec{x})\Phi(\vec{x^{\prime}})=H_{3\vec{x}\vec{x^{\prime}}}$ is provided
earlier. For the preparation sub-routine we require
$\log_{2}|E_{D}|+\log_{2}(\log_{2}k+1)^{2}$ H, $2(\log_{2}k+1)^{2}-2$ rotation
gates, $2(\log_{2}k+1)^{2}+3\log_{2}(\log_{2}k+1)^{2}-7$ CNOT gates. For the
selection sub-routine we require

$\displaystyle|E_{D}|\left(8(\log_{2}k+1)(\log_{2}(\log_{2}k+1)-1)+4(\log_{2}k+1)^{2}\right)$
$\displaystyle+4\sqrt{|E_{D}|}(\log_{2}|E_{D}|-2)+4|E_{D}|$ (430)

T gates and

$\displaystyle|E_{D}|\left((\log_{2}k+1)(8\log_{2}(\log_{2}k+1)-6)+5(\log_{2}k+1)^{2}\right)$
$\displaystyle+\sqrt{|E_{D}|}(4\log_{2}|E_{D}|-6)+5|E_{D}|$ (431)

CNOT gates and $(\log_{2}k+1)^{2}$ CZ gates.

##### Block encoding of $H_{amp}$ :

Using Theorem 13 we can block encode $H_{amp}$ using a PREP sub-routine with 1
H and 2 rotation gates and a SELECT sub-routine that adds an extra control.
Thus under the assumptions of Conjecture 28 we require

$\displaystyle N_{t}^{\prime}$ $\displaystyle\leq$
$\displaystyle|\Omega|\left(4\sqrt{2\log_{2}k}(\log_{2}(2\log_{2}k)-2)+8\log_{2}k+4\sqrt{4\log_{2}k}(\log_{2}(4\log_{2}k)-2)+16\log_{2}k\right)$
(432)
$\displaystyle+4\sqrt{|\Omega|}\left(\log_{2}|\Omega|-2\right)+4|\Omega|+|E_{D}|\left(8(\log_{2}k+1)(\log_{2}(\log_{2}k+1)-1)+4(\log_{2}k+1)^{2}+4\right)$
$\displaystyle+4\sqrt{|E_{D}|}(\log_{2}|E_{D}|-2)$
$\displaystyle+2|\Omega|(8(\log_{2}2k)\log_{2}\left(\frac{\log_{2}2k}{\epsilon_{QFT}}\right)+\log_{2}\left(\frac{\log_{2}2k}{\epsilon_{QFT}}\right)\log_{2}\left(\frac{\log_{2}\left(\frac{\log_{2}2k}{\epsilon_{QFT}}\right)}{\epsilon_{QFT}}\right))+O\left(|\Omega|\log_{2}^{2}k\right)$

T gates,

$\displaystyle N_{cx}^{\prime}$ $\displaystyle\leq$
$\displaystyle|\Omega|\left(\sqrt{2\log_{2}k}(4\log_{2}(2\log_{2}k)-6)+10\log_{2}k+\sqrt{4\log_{2}k}(4\log_{2}(4\log_{2}k)-6)+20\log_{2}k+5\right)$
(433)
$\displaystyle+\sqrt{|\Omega|}\left(4\log_{2}|\Omega|-6\right)+|E_{D}|\left((\log_{2}k+1)(8\log_{2}(\log_{2}k+1)-6)+5(\log_{2}k+1)^{2}+5\right)+\sqrt{|E_{D}|}(4\log_{2}|E_{D}|-6)$
$\displaystyle+2|\Omega|\left(8(\log_{2}2k)\log_{2}\left(\frac{\log_{2}2k}{\epsilon_{QFT}}\right)+\log_{2}\left(\frac{\log_{2}2k}{\epsilon_{QFT}}\right)\log_{2}\left(\frac{\log_{2}\left(\frac{\log_{2}2k}{\epsilon_{QFT}}\right)}{\epsilon_{QFT}}\right)\right)$

CNOT gates,

$\displaystyle N_{r}\leq 12\log_{2}k+2(\log_{2}k+1)^{2}-3$ (434)

rotation gates. This proves Theorem 29 ∎

####  C.2.3 Quantum circuits for signature matrices in the decomposition of
$\phi^{2}$

In this section we describe the explicit constructions of signature matrices
appearing in the LCU decomposition of $\Phi^{2}$, as discussed in Section
IV.5.4. We recall that

$\displaystyle\Phi^{2}$ $\displaystyle=$
$\displaystyle\text{diag}\left((k-1)^{2},(k-2)^{2},\ldots,1,0,1,\ldots,(k-1)^{2},k^{2}\right)=+c_{0}\mathbb{I}+\sum_{\ell=1}^{\zeta^{\prime}}c_{\ell}U_{\ell},$
(435)

where $c_{0}$, $c_{\ell}$ are real coefficients and $U_{\ell}$ is a signature
matrix obtained from the $\ell^{th}$ bit in the binary decomposition of
$0,1,\ldots,k^{2}$ and then replacing the 0 with 1 and 1 with -1, as explained
earlier. $\zeta^{\prime}=1+2\log k$ is the maximum number of bits in the
binary expansion of $k^{2}$. We assume $k=2^{k^{\prime}}$ for some integer
$k^{\prime}$ since we have a unitary. As mentioned earlier, in Table 4 we have
listed all integers $n$ such that $n\leq 2^{7}=128$ and the $b_{\ell}^{th}$
($1\leq\ell\leq 15$) bit in the binary decomposition of $n^{2}$ has 1. In
Table 6 we enumerate all integers $n\leq 2^{x}$ (where $x=2,\ldots,12$) such
that $n^{2}$ has a binary decomposition with 1 at a particular bit position.

We consider the case where $k=2^{7}$. So our circuits consist of 8 qubits and
we label them as $q_{8},\ldots,q_{1}$, corresponding to the 8 bits -
$b_{8},\ldots,b_{1}$, in the binary decomposition of any number with value at
most $2^{7}$. $b_{8}$ and $b_{1}$ are the most and the least significant bits,
respectively. In Fact 26 we have mentioned that $U_{1}$ can be implemented
with a single Z gate on qubit $q_{1}$ and $U_{2}$ is an all 0 matrix.

(a)

(b)

(c)

(d)

(e)

(f)

Figure 17: Quantum circuits for (a) $U_{3}$, (b) $U_{4}$, (c) $U_{5}$, (d)
$U_{6}$, (e) $U_{7}$ and (f) $U_{14}$. Qubits not affected by gate operations
have not been shown.

$\mathbf{\ell=3}:$ From Lemma 24 we know that $-1$ occurs whenever
$n\in\\{8k+4,8k+5,8k+6,8k+7\\}$ and it can be square of an integer if it is of
the form $8k+4$ (Eq. 161). Now, $8k+4=4(2k+1)=2^{2}(2k+1)$ and so it is a
square of the form $(2(2k^{\prime\prime}+1))^{2}$, where $k^{\prime\prime}$ is
an integer. If $(2(2k^{\prime\prime}+1))^{2}=j^{2}$ then it can occur at row
$(k-1)-j$ and $k-1+j$. If we expand all integers of the form
$2(2k^{\prime\prime}+1)$ we observe that they have a trailing 10. Adding or
subtracting $k-1$ changes these two bits to 01. Thus all such integers appear
in those rows whose index has a trailing 01. This implies whenever the state
of the first qubit is 1 and second qubit is 0, a -1 phase is incurred. Thus we
can implement $U_{3}$ with a (compute-uncompute) pair of Toffoli, X, and a Z
on an extra ancilla, as shown in Fig. 17(a). To implement controlled-$U_{3}$
we add one control to Z, which does not contribute to additional T gates.

$\mathbf{\ell=4}:$ From Lemma 24 we know that $-1$ occurs whenever
$n\in\\{16k+8,16k+9,\ldots 16k+15\\}$ and it can be square of an integer if it
is of the form $16k+9$ (Equation 161). The integers whose squares are of this
form have trailing 011 or 101, for example $3^{3},5^{2},11^{2},13^{2}$, etc.
So they occur at positions with trailing 100 or 010. $U_{4}$ can be
implemented with 4 CNOT and 1 CZ, as shown in Fig. 17(b). To implement
controlled-$U_{4}$ we add an extra control to CZ, that contributes to T gates.

$\mathbf{\ell=5}:$ Integers, the binary decomposition of whose squares have 1
in the $5^{th}$ position are of the form $16n+m$, where $n$ is a non-negative
integer and $m\in\\{4,5,7,9,11,12\\}$ (Table 4) and in binary
$m\in\\{0100,0101,0111,1001,1100,1011\\}$. The trailing bits in the binary
decomposition of integers of the form $16n+m$ are in
$\\{0100,0101,0111,1001,1100,1011\\}$ and so in $U_{5}$ they appear at
positions whose binary decomposition have the following trailing bits
\- $1011,1010,1000,0110,0011,0100$. So we can implement $U_{5}$ with the
circuit shown in Fig. 17(c), consisting of 3 double-controlled-Z and 4 pairs
of CNOT. To implement controlled-$U_{5}$ we add extra controls to the CZs.

$\mathbf{\ell=6}:$ In Table 4 we have listed the integers such that the binary
decomposition of their squares have 1 in the $6^{th}$ position. These are of
the form $32n+m$ where $n$ is a non-negative integer and

$m\in S_{m}=\\{6,7,10,11,13,15,17,19,21,22,25,26\\}.$

In binary the integers in $S_{m}$ are as follows.

$S_{m}\in\\{00110,00111,01010,01011,01101,01111,10001,10011,10101,10110,11001,11010\\}$

We obtain the row positions by adding and subtracting $11\ldots 111$, which
implies that the trailing 5 bits get complemented. Thus $U_{6}$ can be
implemented with the circuit shown in Fig. 17(d), consisting of 6 (compute-
uncompute) pairs of CNOT and 3 2-qubit-controlled-Z. To implement
controlled-$U_{6}$ we need to add one control to each multi-controlled Z.

$\mathbf{\ell=7}:$ In Table 4 we have listed the integers such that the binary
decomposition of their squares have 1 in the $7^{th}$ position. These are of
the form $64n+m$ where $n$ is a non-negative integer and $m\in S_{m}$, a set
specified in Table 4. As explained, the gates in this unitary act on 6 qubits,
corresponding to the last significant 6 bits in the binary representation of
an integer. We calculate the binary representation of integers in $S_{m}$. We
obtain the row positions with $-1$ by adding and subtracting $11\ldots 111$.
We group appropriate binary strings in order to induce ”Don’t care”
conditions, in order to optimize the circuit. Thus we obtain the circuit in
Fig. 17(e), that implements $U_{7}$.

$\mathbf{\ell=14}:$ From Table 4 we observe that squares of integers from 91
(01011011) to 127 (01111111) are such that their binary expansions have 1 in
the $14^{th}$ bit position. These integers appear at rows 0-36 and 218-254.
The binary encoding of these rows range from 00000000 (0) - 00100100 (36) and
11011010 (218) - 11111110 (254). Thus when the state of the qubits are within
the stated range the circuit incurs a phase of -1. So $U_{14}$ can be
implemented with the circuit shown in Fig. 17(f). Again, we have optimized the
circuit by identifying ”Don’t care” conditions among groups of binary strings.

####  C.2.4 Quantum circuits for signature matrices in the decomposition of
$\phi^{4}$

In this section we describe the explicit constructions of signature matrices
appearing in the LCU decomposition of $\Phi^{4}$, as discussed in Section
IV.5.4. We recall that

$\displaystyle\Phi^{4}$ $\displaystyle=$
$\displaystyle\text{diag}\left((k-1)^{4},(k-2)^{4},\ldots,1,0,1,\ldots,(k-1)^{4},k^{4}\right)=+c_{0}^{\prime}\mathbb{I}+\sum_{\ell=1}^{\zeta^{\prime\prime}}c_{\ell}^{\prime}U_{\ell}^{\prime},$
(436)

where $c_{0}^{\prime}$, $c_{\ell}^{\prime}$ are real coefficients and
$U_{\ell}^{\prime}$ is a signature matrix obtained from the $\ell^{th}$ bit in
the binary decomposition of $0,1,\ldots,k^{4}$ and then replacing the 0 with 1
and 1 with -1, as explained earlier. $\zeta^{\prime\prime}=1+4\log k$ is the
maximum number of bits in the binary expansion of $k^{4}$. As mentioned
earlier, in Table 5 we have listed all integers $n$ such that $n\leq
2^{7}=128$ and the $b_{\ell}^{th}$ ($1\leq\ell\leq 29$) bit in the binary
decomposition of $n^{4}$ has 1. In Table 7 we enumerate all integers $n\leq
2^{x}$ (where $x=2,\ldots,12$) such that $n^{4}$ has a binary decomposition
with 1 at a particular bit position. As in previous section, we consider the
case where $k=2^{7}$. So our circuits consist of 8 qubits and we label them as
$q_{8},\ldots,q_{1}$, corresponding to the 8 bits - $b_{8},\ldots,b_{1}$, in
the binary decomposition of any number with value at most $2^{7}$. $b_{8}$ and
$b_{1}$ are the most and the least significant bits, respectively. In Fact 26
we have mentioned that $U_{1}$ can be implemented with a single Z gate on
qubit $q_{1}$ and $U_{2},U_{3},U_{4}$ are all 0 matrix.

(a)

(b)

(c)

(d)

(e)

Figure 18: Quantum circuits for (a) $U_{5}^{\prime}$, (b) $U_{6}^{\prime}$,
(c) $U_{7}^{\prime}$, (d) $U_{8}^{\prime}$ and (f) $U_{28}^{\prime}$. Qubits
not affected by gate operations have not been shown.

$\mathbf{\ell=5}:$ In Table 5 we have enlisted all the integers such that the
binary decomposition of their fourth power has 1 in the $5^{th}$ bit position.
These are of the form $8n+2,8n+3,8n+5,8n+6$, where $n$ is a non-negative
integer. The binary decomposition of 2, 3, 5 and 6 are 010, 011, 101 and 110,
respectively. So the trailing bits in the binary decomposition of integers of
the above form are either 010, 011, 101 or 110. These appear in rows whose
binary decomposition has any of the four trailing bits - 101, 100, 010, 001.
Therefore, $U_{5}^{\prime}$ can be implemented with the circuit shown in
Figure 18(a), consisting of 4 (compute-uncompute) pairs of CNOT and 2 CZ.
Controlled-$U_{5}^{\prime}$ can be implemented by adding extra controls to
each CZ.

$\mathbf{\ell=6}:$ Consider integers of the form $16n+m$, where $n$ is a non-
negative integer and

$m\in S_{m}=\\{5(0101),7(0111),9(1001),11(1011)\\}.$

From Table 5, we observe that the binary decomposition of the fourth power of
these integers has 1 in the $6^{th}$ bit position. In $\Phi^{4}$ these
integers appear at rows such that the binary decomposition of their index has
trailing 4 bits which are complements of those in $S_{m}$. Thus,
$U_{6}^{\prime}$ can be implemented with the circuit in Figure 18(b),
consisting of 2 (compute-uncompute) pairs of CNOTs, and 1 CZ.
Controlled-$U_{6}^{\prime}$ can be implemented by adding an extra control to
CZ.

$\mathbf{\ell=7}:$ Consider integers of the form $32n+m$, where $n$ is a non-
negative integer and

$m\in
S_{m}=\\{3(00011),5(00101),7(00111),15(01111),17(10001),25(11001),27(11011),29(11101)\\}.$

From Table 5 we can say that the binary decomposition of the fourth power of
these integers has 1 in the $7^{th}$ bit position. These integers appear at
rows whose binary decomposition has the last 5 bits that are complements of
the ones in $S_{m}$. So, $U_{7}^{\prime}$ can be implemented with the circuit
in Figure 18(c), consisting of 6 (compute-uncompute) pairs of CNOT and two
double-controlled-Z. Controlled- $U_{7}^{\prime}$ can be implemented by adding
extra control to the controlled-Z.

$\mathbf{\ell=8}:$ In Table 5 we have listed the integers such that the binary
decomposition of their fourth power have 1 in the $8^{th}$ position. These are
of the form $64n+m$ where $n$ is a non-negative integer and $m\in S_{m}$, a
set specified in Table 5. As explained, the gates in this unitary act on 6
qubits, corresponding to the last significant 6 bits in the binary
representation of an integer. We calculate the binary representation of
integers in $S_{m}$. We obtain the row positions with $-1$ by adding and
subtracting $11\ldots 111$. We group appropriate binary strings in order to
induce ”Don’t care” conditions, in order to optimize the circuit. Thus we
obtain the circuit in Fig. 18(d), that implements $U_{8}^{\prime}$.

$\mathbf{\ell=28}:$ From Table 5 we observe that the fourth power of integers
from 108 to 127 are such that their binary expansions have 1 in the $14^{th}$
bit position. These integers appear at rows 0-19 and 235-254. The binary
encoding of these rows range from 00000000 (0) - 00010011 (19) and 11101011
(218) - 11111110 (254). Thus when the state of the qubits are within the
stated range the circuit incurs a phase of -1. So $U_{28}^{\prime}$ can be
implemented with the circuit shown in Figure 18(e). Again, we have optimized
the circuit significantly by identifying appropriate ”Don’t care” conditions.

Bit |  Integers |  $\\#$Integers
---|---|---
$b_{1}$ |  $2n+1:0\leq n\leq 63$ | 64
$b_{2}$ |  $\emptyset$ | 0
$b_{3}$ |  $2(2n+1):0\leq 31$ | 32
$b_{4}$ |  $8n+3,8n+5:0\leq 15$ | 32
$b_{5}$ |  $16n+m:0\leq n\leq 7$, $m\in\\{4,5,7,9,11,12\\}$ | 48
$b_{6}$ |  $32n+m:0\leq n\leq 3$, $m\in\\{6,7,10,11,13,15,17,19,21,22,25,26\\}$ | 48
$b_{7}$ |  $64n+m:n=0,1$, $m\in\\{8,9,10,11,14,15,18,19,22,24,25,27,29,31,33,35,37,39,40,42,45,46,49,50,53,54,55,56\\}$ | 56
$b_{8}$ |  12, 13, 14, 15, 20, 21, 22, 26, 27, 30, 31, 34, 35, 38, 39, 41, 42, 44, 45, 47, 50, 52, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 76, 78, 81, 83, 84, 86, 87, 89, 90, 93, 94, 97, 98, 101, 102, 106, 107, 108, 113, 114, 115, 116 | 56
$b_{9}$ |  16, 17, 18, 19, 20, 21, 22, 28, 29, 30, 31, 36, 37, 38, 39, 43, 44, 45, 48, 49, 50, 54, 55, 58, 59, 62, 63, 66, 67, 70, 71, 74, 75, 77, 78, 80, 81, 84, 87, 90, 92, 93, 95, 98, 100, 101, 103, 105, 106, 108, 110, 112, 113, 115, 117, 119, 121, 123, 125, 127 | 60
$b_{10}$ |  23, 24, 25, 26, 27, 28, 29, 30, 31, 40, 41, 42, 43, 44, 45, 51, 52, 53, 54, 55, 60, 61, 62, 63, 68, 69, 70, 71, 76, 77, 78, 82, 83, 84, 88, 89, 90, 94, 95, 99, 100, 101, 104, 105, 106, 109, 110, 114, 115, 118, 119, 122, 123, 126, 127 | 55
$b_{11}$ |  32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 56, 57, 58, 59, 60, 61, 62, 63, 72, 73, 74, 75, 76, 77, 78, 85, 86, 87, 88, 89, 90, 96, 97, 98, 99, 100, 101, 107, 108, 109, 110, 116, 117, 118, 119, 124, 125, 126, 127 | 53
$b_{12}$ |  46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 102, 103, 104, 105, 106, 107, 108, 109, 110, 120, 121, 122, 123, 124, 125, 126, 127 | 47
$b_{13}$ |  64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 | 44
$b_{14}$ |  91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 | 37
$b_{15}$ |  128 | 1
Table 4:  The leftmost column stores bit positions, indicated by $b_{i}$. The second column stores integers such that the binary decomposition of their square has 1 in the $b_{i}^{th}$ bit position. The third column stores the number of integers whose square has 1 in the $b_{i}^{th}$ bit position. We have listed integers until 128.  Bit |  Integers |  $\\#$Integers
---|---|---
$b_{1}$ |  $2n+1:0\leq n\leq 63$ | 64
$b_{2}$ |  $\emptyset$ | 0
$b_{3}$ |  $\emptyset$ | 0
$b_{4}$ |  $\emptyset$ | 0
$b_{5}$ |  $8n+2,8n+3,8n+5,8n+6:0\leq n\leq 15$ | 64
$b_{6}$ |  $16n+m$ : $0\leq n\leq 7$, $m\in\\{5,7,9,11\\}$ | 32
$b_{7}$ |  $32n+m$ : $0\leq n\leq 3$, $m\in\\{3,5,7,15,17,25,27,29\\}$ | 32
$b_{8}$ |  $64n+m$ : $n=0,1$, $m\in\\{9,13,15,21,25,27,29,31,33,35,37,39,43,49,51,55\\}$ | 32
$b_{9}$ |  4, 6, 7, 9, 10, 11, 12, 13, 15, 19, 20, 21, 22, 23, 25, 26, 27, 28, 31, 35, 36, 38, 42, 44, 47, 52, 54, 58, 59, 60, 61, 63, 65, 67, 68, 69, 70, 74, 76, 81, 84, 86, 90, 92, 93, 97, 100, 101, 102, 103, 105, 106, 107, 108, 109, 113, 115, 116, 117, 118, 119, 121, 122, 124 | 64
$b_{10}$ |  5, 10, 13, 14, 17, 18, 21, 22, 27, 29, 31, 41, 42, 43, 45, 46, 49, 50, 51, 53, 54, 57, 63, 67, 69, 73, 74, 78, 81, 82, 86, 89, 91, 93, 95, 103, 105, 106, 109, 110, 113, 114, 117, 118, 119, 121, 125, 127 | 48
$b_{11}$ |  6, 10, 13, 14, 15, 17, 19, 21, 23, 25, 30, 31, 34, 35, 39, 41, 47, 49, 50, 53, 54, 58, 59, 61, 63, 69, 70, 74, 75, 77, 78, 79, 81, 85, 87, 89, 91, 93, 94, 95, 98, 101, 105, 107, 109, 111, 113, 114, 115, 118, 119, 122, 127 | 53
$b_{12}$ |  7, 9, 11, 13, 18, 19, 26, 27, 29, 30, 33, 37, 39, 41, 42, 43, 50, 51, 54, 58, 62, 63, 66, 67, 69, 70, 74, 75, 78, 83, 86, 87, 89, 91, 93, 97, 98, 102, 107, 110, 121, 123, 125, 127 | 44
$b_{13}$ |  8, 9, 11, 12, 14, 18, 19, 20, 21, 22, 24, 25, 26, 27, 30, 31, 33, 37, 38, 40, 41, 42, 44, 45, 46, 47, 49, 50, 51, 52, 54, 56, 57, 62, 63, 67, 69, 70, 72, 73, 76, 79, 81, 84, 88, 89, 91, 94, 95, 97, 101, 104, 105, 107, 108, 116, 117, 118, 120, 121, 122, 126, 127 | 63
$b_{14}$ |  10, 11, 13, 19, 20, 21, 25, 26, 28, 34, 35, 36, 42, 43, 44, 47, 49, 51, 53, 54, 55, 58, 59, 62, 65, 67, 77, 82, 83, 84, 86, 87, 90, 92, 93, 98, 100, 102, 103, 105, 106, 108, 109, 111, 113, 114, 119, 126, 127 | 49
$b_{15}$ |  12, 13, 15, 17, 19, 20, 21, 23, 25, 26, 28, 29, 30, 34, 35, 38, 39, 42, 46, 47, 49, 50, 53, 59, 60, 61, 62, 63, 65, 67, 68, 69, 70, 71, 73, 75, 77, 78, 79, 81, 82, 89, 91, 93, 94, 95, 97, 98, 99, 100, 101, 103, 106, 108, 109, 111, 113, 115, 116, 117, 118, 119, 121, 122, 125, 126, 127 | 67
$b_{16}$ |  14, 15, 18, 19, 21, 22, 25, 26, 29, 35, 36, 37, 38, 45, 49, 52, 54, 55, 58, 59, 60, 66, 69, 71, 74, 75, 78, 81, 82, 84, 85, 86, 95, 97, 99, 100, 101, 102, 105, 108, 109, 113, 115, 116, 119, 121, 123, 124, 126 | 49
$b_{17}$ |  16, 17, 18, 19, 22, 24, 25, 28, 36, 38, 39, 40, 41, 42, 44, 48, 49, 50, 51, 52, 54, 55, 57, 60, 61, 62, 66, 67, 69, 71, 73, 74, 76, 80, 82, 84, 88, 89, 90, 92, 93, 94, 98, 99, 100, 101, 102, 103, 104, 108, 109, 112, 113, 114, 117, 119, 124, 125, 126, 127 | 60
$b_{18}$ |  20, 21, 22, 26, 29, 31, 33, 35, 38, 39, 40, 41, 42, 45, 47, 49, 50, 51, 52, 55, 56, 61, 67, 68, 70, 71, 72, 75, 79, 84, 86, 87, 88, 91, 94, 95, 97, 98, 101, 102, 105, 106, 108, 110, 113, 116, 117, 118, 119, 121, 124 | 51
$b_{19}$ |  23, 24, 25, 26, 30, 31, 34, 35, 37, 38, 40, 42, 43, 45, 46, 49, 50, 51, 52, 56, 58, 60, 68, 70, 76, 78, 83, 84, 85, 89, 91, 92, 93, 94, 97, 98, 100, 103, 105, 106, 111, 113, 115, 118, 120, 121, 122, 123, 124, 125, 126 | 51
$b_{20}$ |  27, 28, 29, 30, 31, 36, 37, 38, 41, 42, 44, 45, 47, 50, 52, 53, 55, 58, 59, 69, 70, 72, 74, 76, 77, 85, 87, 89, 90, 95, 98, 99, 104, 105, 108, 109, 110, 111, 115, 116, 117, 118, 120, 125 | 44
$b_{21}$ |  32, 33, 34, 35, 36, 37, 38, 43, 44, 45, 48, 49, 50, 53, 56, 59, 61, 63, 65, 67, 69, 72, 73, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 88, 89, 91, 93, 95, 96, 98, 99, 100, 101, 102, 103, 104, 105, 107, 108, 110, 113, 114, 119, 120, 122, 124 | 56
$b_{22}$ |  39, 40, 41, 42, 43, 44, 45, 51, 52, 53, 57, 58, 59, 62, 63, 66, 67, 70, 73, 75, 76, 78, 80, 82, 84, 87, 89, 90, 93, 94, 98, 99, 100, 101, 102, 103, 104, 105, 109, 110, 112, 113, 115, 117, 119, 122, 123 | 47
$b_{23}$ |  46, 47, 48, 49, 50, 51, 52, 53, 60, 61, 62, 63, 68, 69, 70, 74, 75, 76, 79, 80, 83, 84, 86, 87, 90, 92, 93, 95, 97, 98, 100, 102, 104, 107, 109, 112, 115, 116, 119, 120, 121 | 41
$b_{24}$ |  54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 71, 72, 73, 74, 75, 76, 81, 82, 83, 84, 88, 89, 90, 94, 95, 99, 100, 103, 104, 106, 107, 110, 113, 116, 118, 119, 121, 123, 125, 127 | 40
$b_{25}$ |  64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 85, 86, 87, 88, 89, 90, 96, 97, 98, 99, 100, 105, 106, 107, 111, 112, 113, 117, 118, 119, 122, 123, 126, 127 | 37
$b_{26}$ |  77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 101, 102, 103, 104, 105, 106, 107, 114, 115, 116, 117, 118, 119, 124, 125, 126, 127 | 31
$b_{27}$ |  91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 120, 121, 122, 123, 124, 125, 126, 127 | 25
$b_{28}$ |  108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127 | 20
$b_{29}$ |  128 | 1
Table 5:  The leftmost column stores bit positions, indicated by $b_{i}$. The second column stores integers such that the binary decomposition of their fourth power has 1 in the $b_{i}^{th}$ bit position. The third column stores the number of integers whose fourth power has 1 in the $b_{i}^{th}$ bit position. We have listed integers until 128.  | $\mathbf{2^{2}}$ | $\mathbf{2^{3}}$ | $\mathbf{2^{4}}$ | $\mathbf{2^{5}}$ | $\mathbf{2^{6}}$ | $\mathbf{2^{7}}$ | $\mathbf{2^{8}}$ | $\mathbf{2^{9}}$ | $\mathbf{2^{10}}$ | $\mathbf{2^{11}}$ | $\mathbf{2^{12}}$
---|---|---|---|---|---|---|---|---|---|---|---
$\mathbf{b_{1}}$ | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048
$\mathbf{b_{2}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
$\mathbf{b_{3}}$ | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024
$\mathbf{b_{4}}$ | 1 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024
$\mathbf{b_{5}}$ | 1 | 3 | 6 | 12 | 24 | 48 | 96 | 192 | 384 | 768 | 1536
$\mathbf{b_{6}}$ | 0 | 2 | 6 | 12 | 24 | 48 | 96 | 192 | 384 | 768 | 1536
$\mathbf{b_{7}}$ | 0 | 1 | 6 | 14 | 28 | 56 | 112 | 224 | 448 | 896 | 1792
$\mathbf{b_{8}}$ | 0 | 0 | 4 | 11 | 28 | 56 | 112 | 224 | 448 | 896 | 1792
$\mathbf{b_{9}}$ | 0 | 0 | 1 | 11 | 27 | 60 | 120 | 240 | 480 | 960 | 1920
$\mathbf{b_{10}}$ | 0 | 0 | 0 | 9 | 24 | 55 | 120 | 240 | 480 | 960 | 1920
$\mathbf{b_{11}}$ | 0 | 0 | 0 | 1 | 22 | 53 | 121 | 248 | 496 | 992 | 1984
$\mathbf{b_{12}}$ | 0 | 0 | 0 | 0 | 18 | 47 | 108 | 233 | 496 | 992 | 1984
$\mathbf{b_{13}}$ | 0 | 0 | 0 | 0 | 1 | 44 | 106 | 236 | 493 | 1008 | 2016
$\mathbf{b_{14}}$ | 0 | 0 | 0 | 0 | 0 | 37 | 97 | 221 | 478 | 995 | 2016
$\mathbf{b_{15}}$ | 0 | 0 | 0 | 0 | 0 | 1 | 88 | 212 | 469 | 983 | 2017
$\mathbf{b_{16}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 74 | 195 | 446 | 957 | 1990
$\mathbf{b_{17}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 175 | 422 | 932 | 1952
$\mathbf{b_{18}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 149 | 389 | 891 | 1915
$\mathbf{b_{19}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 350 | 847 | 1864
$\mathbf{b_{20}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 299 | 779 | 1786
$\mathbf{b_{21}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 699 | 1692
$\mathbf{b_{22}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 599 | 1560
$\mathbf{b_{23}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1397
$\mathbf{b_{24}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1199
$\mathbf{b_{25}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1
Table 6:  Number of integers less than $2^{x}$, $x=2,3,\ldots,12$, such that the binary decomposition of their square has 1 at a certain bit position. That is, the cell at the intersection of row labeled by bit $b_{i}$ and column labeled by integer $2^{x}$ stores the number of integers $n\leq 2^{x}$ such that the binary decomposition of $n^{2}$ has 1 at bit position $b_{i}$.  | $\mathbf{2^{2}}$ | $\mathbf{2^{3}}$ | $\mathbf{2^{4}}$ | $\mathbf{2^{5}}$ | $\mathbf{2^{6}}$ | $\mathbf{2^{7}}$ | $\mathbf{2^{8}}$ | $\mathbf{2^{9}}$ | $\mathbf{2^{10}}$ | $\mathbf{2^{11}}$ | $\mathbf{2^{12}}$
---|---|---|---|---|---|---|---|---|---|---|---
$\mathbf{b_{1}}$ | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048
$\mathbf{b_{2}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
$\mathbf{b_{3}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
$\mathbf{b_{4}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
$\mathbf{b_{5}}$ | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048
$\mathbf{b_{6}}$ | 0 | 2 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024
$\mathbf{b_{7}}$ | 1 | 3 | 4 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024
$\mathbf{b_{8}}$ | 0 | 0 | 3 | 8 | 16 | 32 | 64 | 128 | 256 | 512 | 1024
$\mathbf{b_{9}}$ | 1 | 3 | 9 | 19 | 32 | 64 | 128 | 256 | 512 | 1024 | 2048
$\mathbf{b_{10}}$ | 0 | 1 | 4 | 11 | 23 | 48 | 96 | 192 | 384 | 768 | 1536
$\mathbf{b_{11}}$ | 0 | 1 | 5 | 12 | 25 | 53 | 96 | 192 | 384 | 768 | 1536
$\mathbf{b_{12}}$ | 0 | 1 | 4 | 10 | 22 | 44 | 91 | 192 | 384 | 768 | 1536
$\mathbf{b_{13}}$ | 0 | 1 | 5 | 16 | 35 | 63 | 135 | 263 | 512 | 1024 | 2048
$\mathbf{b_{14}}$ | 0 | 0 | 3 | 9 | 24 | 49 | 102 | 213 | 439 | 896 | 1792
$\mathbf{b_{15}}$ | 0 | 0 | 3 | 13 | 28 | 67 | 122 | 226 | 451 | 905 | 1792
$\mathbf{b_{16}}$ | 0 | 0 | 2 | 9 | 21 | 49 | 102 | 217 | 447 | 886 | 1763
$\mathbf{b_{17}}$ | 0 | 0 | 1 | 8 | 26 | 60 | 116 | 261 | 507 | 1029 | 2073
$\mathbf{b_{18}}$ | 0 | 0 | 0 | 6 | 22 | 51 | 106 | 216 | 458 | 935 | 1915
$\mathbf{b_{19}}$ | 0 | 0 | 0 | 6 | 22 | 51 | 123 | 248 | 487 | 987 | 1970
$\mathbf{b_{20}}$ | 0 | 0 | 0 | 5 | 19 | 44 | 105 | 222 | 465 | 935 | 1876
$\mathbf{b_{21}}$ | 0 | 0 | 0 | 1 | 18 | 56 | 118 | 235 | 503 | 1023 | 2080
$\mathbf{b_{22}}$ | 0 | 0 | 0 | 0 | 15 | 47 | 108 | 226 | 458 | 961 | 1941
$\mathbf{b_{23}}$ | 0 | 0 | 0 | 0 | 12 | 41 | 103 | 241 | 494 | 995 | 2026
$\mathbf{b_{24}}$ | 0 | 0 | 0 | 0 | 10 | 40 | 96 | 225 | 465 | 958 | 1928
$\mathbf{b_{25}}$ | 0 | 0 | 0 | 0 | 1 | 37 | 104 | 231 | 478 | 1019 | 2038
$\mathbf{b_{26}}$ | 0 | 0 | 0 | 0 | 0 | 31 | 93 | 208 | 447 | 927 | 1936
$\mathbf{b_{27}}$ | 0 | 0 | 0 | 0 | 0 | 25 | 89 | 211 | 475 | 990 | 2020
$\mathbf{b_{28}}$ | 0 | 0 | 0 | 0 | 0 | 20 | 83 | 202 | 448 | 963 | 1965
$\mathbf{b_{29}}$ | 0 | 0 | 0 | 0 | 0 | 1 | 73 | 194 | 448 | 943 | 1993
$\mathbf{b_{30}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 63 | 190 | 440 | 942 | 1926
$\mathbf{b_{31}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 51 | 178 | 435 | 952 | 2008
$\mathbf{b_{32}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 40 | 162 | 411 | 918 | 1911
$\mathbf{b_{33}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 146 | 393 | 904 | 1922
$\mathbf{b_{34}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 125 | 377 | 878 | 1870
$\mathbf{b_{35}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 103 | 352 | 856 | 1854
$\mathbf{b_{36}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 81 | 323 | 828 | 1875
$\mathbf{b_{37}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 291 | 793 | 1821
$\mathbf{b_{38}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 251 | 756 | 1755
$\mathbf{b_{39}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 208 | 707 | 1737
$\mathbf{b_{40}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 162 | 645 | 1665
$\mathbf{b_{41}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 579 | 1592
$\mathbf{b_{42}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 503 | 1515
$\mathbf{b_{43}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 416 | 1412
$\mathbf{b_{44}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 325 | 1294
$\mathbf{b_{45}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1159
$\mathbf{b_{46}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1004
$\mathbf{b_{47}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 832
$\mathbf{b_{48}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 651
$\mathbf{b_{49}}$ | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1
Table 7:  Number of integers less than $2^{x}$, $x=2,3,\ldots,12$, such that
the binary decomposition of their fourth power has 1 at a certain bit
position. That is, the cell at the intersection of row labeled by bit $b_{i}$
and column labeled by integer $2^{x}$ stores the number of integers $n\leq
2^{x}$ such that the binary decomposition of $n^{4}$ has 1 at bit position
$b_{i}$.

## References

  * [1] Seth Lloyd.  Universal quantum simulators.  Science, 273(5278):1073–1078, 1996.
  * [2] Dominic W Berry, Graeme Ahokas, Richard Cleve, and Barry C Sanders.  Efficient quantum algorithms for simulating sparse Hamiltonians.  Communications in Mathematical Physics, 270:359–371, 2007.
  * [3] Andrew M Childs and Nathan Wiebe.  Hamiltonian simulation using linear combinations of unitary operations.  Quantum Information and Computation, 12(11&12):901–924, 2012.
  * [4] Andrew M Childs, Robin Kothari, and Rolando D Somma.  Quantum algorithm for systems of linear equations with exponentially improved dependence on precision.  SIAM Journal on Computing, 46(6):1920–1950, 2017.
  * [5] Guang Hao Low and Isaac L. Chuang.  Hamiltonian Simulation by Qubitization.  Quantum, 3:163, July 2019.
  * [6] Yuan Su, Dominic W Berry, Nathan Wiebe, Nicholas Rubin, and Ryan Babbush.  Fault-tolerant quantum simulations of chemistry in first quantization.  PRX Quantum, 2(4):040332, 2021.
  * [7] Christian W. Bauer, Zohreh Davoudi, A. Baha Balantekin, Tanmoy Bhattacharya, Marcela Carena, Wibe A. de Jong, Patrick Draper, Aida El-Khadra, Nate Gemelke, Masanori Hanada, Dmitri Kharzeev, Henry Lamm, Ying-Ying Li, Junyu Liu, Mikhail Lukin, Yannick Meurice, Christopher Monroe, Benjamin Nachman, Guido Pagano, John Preskill, Enrico Rinaldi, Alessandro Roggero, David I. Santiago, Martin J. Savage, Irfan Siddiqi, George Siopsis, David Van Zanten, Nathan Wiebe, Yukari Yamauchi, Kübra Yeter-Aydeniz, and Silvia Zorzetti.  Quantum Simulation for High Energy Physics.  arXiv, April 2022.
  * [8] John Kogut and Leonard Susskind.  Hamiltonian formulation of Wilson’s lattice gauge theories.  Phys. Rev. D, 11:395–408, Jan 1975.
  * [9] Sidney D. Drell, Helen R. Quinn, Benjamin Svetitsky, and Marvin Weinstein.  Quantum electrodynamics on a lattice: A Hamiltonian variational approach to the physics of the weak-coupling region.  Phys. Rev. D, 19:619–638, Jan 1979.
  * [10] Stephen P. Jordan, Hari Krovi, Keith S. M. Lee, and John Preskill.  BQP-completeness of scattering in scalar quantum field theory.  Quantum, 2:44, January 2018.
  * [11] Natalie Klco and Martin J. Savage.  Digitization of scalar fields for quantum computing.  Physical Review A, 99(5):052335, May 2019.
  * [12] Yuri Alexeev, Dave Bacon, Kenneth R Brown, Robert Calderbank, Lincoln D Carr, Frederic T Chong, Brian DeMarco, Dirk Englund, Edward Farhi, Bill Fefferman, et al.  Quantum computer systems for scientific discovery.  PRX quantum, 2(1):017001, 2021.
  * [13] Christian W Bauer, Zohreh Davoudi, A Baha Balantekin, Tanmoy Bhattacharya, Marcela Carena, Wibe A De Jong, Patrick Draper, Aida El-Khadra, Nate Gemelke, Masanori Hanada, et al.  Quantum simulation for high-energy physics.  PRX quantum, 4(2):027001, 2023.
  * [14] Nhung H Nguyen, Minh C Tran, Yingyue Zhu, Alaina M Green, C Huerta Alderete, Zohreh Davoudi, and Norbert M Linke.  Digital quantum simulation of the Schwinger model and symmetry protection with trapped ions.  PRX Quantum, 3(2):020324, 2022.
  * [15] Alexander F Shaw, Pavel Lougovski, Jesse R Stryker, and Nathan Wiebe.  Quantum algorithms for simulating the lattice Schwinger model.  Quantum, 4:306, 2020.
  * [16] Stephen P. Jordan, Keith S. M. Lee, and John Preskill.  Quantum algorithms for quantum field theories.  Science, 336(6085):1130–1133, 2012.
  * [17] Stephen P. Jordan, Keith S. M. Lee, and John Preskill.  Quantum Algorithms for Fermionic Quantum Field Theories.  arXiv:1404.7115 [hep-th, physics:quant-ph], April 2014.
  * [18] Panayotis G. Kevrekidis and Jesús Cuevas-Maraver.  A dynamical perspective on the $\Phi^{4}$ model: Past, present and future.  Springer, 2019.
  * [19] Richard P. Feynman.  Photon-hadron Interactions.  Taylor and Francis, 5 2019.
  * [20] J. D. Bjorken and Emmanuel A. Paschos.  Inelastic Electron Proton and gamma Proton Scattering, and the Structure of the Nucleon.  Phys. Rev., 185:1975–1982, 1969.
  * [21] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe.  Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics.  In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 193–204, 2019.
  * [22] João Barata, Niklas Mueller, Andrey Tarasov, and Raju Venugopalan.  Single-particle digitization strategy for quantum computation of a $\phi^{4}$ scalar field theory.  Physical Review A, 103(4):042410, 2021.
  * [23] Zohreh Davoudi, Alexander F. Shaw, and Jesse R. Stryker.  General quantum algorithms for Hamiltonian simulation with applications to a non-Abelian lattice gauge theory.  Quantum, 7:1213, December 2023.
  * [24] Mason Rhodes, Michael Kreshchuk, and Shivesh Pathak.  Exponential improvements in the simulation of lattice gauge theories using near-optimal techniques, 2024.
  * [25] Siddharth Hariprakash, Neel S. Modi, Michael Kreshchuk, Christopher F. Kane, and Christian W Bauer.  Strategies for simulating time evolution of Hamiltonian lattice field theories.  arXiv, 2024.
  * [26] Priyanka Mukhopadhyay, Nathan Wiebe, and Hong Tao Zhang.  Synthesizing efficient circuits for Hamiltonian simulation.  npj Quantum Information, 9(31), 2023.
  * [27] Priyanka Mukhopadhyay, Torin F Stetina, and Nathan Wiebe.  Quantum simulation of the first-quantized Pauli-Fierz Hamiltonian.  PRX Quantum, 5:010345, 2024.
  * [28] 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.
  * [29] Ryan Babbush, Nathan Wiebe, Jarrod McClean, James McClain, Hartmut Neven, and Garnet Kin-Lic Chan.  Low-depth quantum simulation of materials.  Physical Review X, 8(1):011044, 2018.
  * [30] Andrew M Childs, Dmitri Maslov, Yunseong Nam, Neil J Ross, and Yuan Su.  Toward the first quantum simulation with quantum speedup.  Proceedings of the National Academy of Sciences, 115(38):9456–9461, 2018.
  * [31] Brett Giles and Peter Selinger.  Exact synthesis of multiqubit Clifford+T circuits.  Physical Review A—Atomic, Molecular, and Optical Physics, 87(3):032332, 2013.
  * [32] 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.
  * [33] Neil J Ross and Peter Selinger.  Optimal ancilla-free Clifford+T approximation of Z-rotations.  Quantum Inf. Comput., 16(11&12):901–953, 2016.
  * [34] Michele Mosca and Priyanka Mukhopadhyay.  A polynomial time and space heuristic algorithm for T-count.  Quantum Science and Technology, 7(1):015003, 2021.
  * [35] Vlad Gheorghiu, Michele Mosca, and Priyanka Mukhopadhyay.  A (quasi-) polynomial time heuristic algorithm for synthesizing T-depth optimal circuits.  npj Quantum Information, 8(1):110, 2022.
  * [36] Vlad Gheorghiu, Michele Mosca, and Priyanka Mukhopadhyay.  T-count and T-depth of any multi-qubit unitary.  npj Quantum Information, 8(1):1–10, 2022.
  * [37] Priyanka Mukhopadhyay.  Synthesis of V-count-optimal quantum circuits for multiqubit unitaries.  Physical Review A, 109(5):052619, 2024.
  * [38] Priyanka Mukhopadhyay.  CS-count-optimal quantum circuits for arbitrary multi-qubit unitaries.  Scientific Reports, 14(1):13916, 2024.
  * [39] Priyanka Mukhopadhyay.  Synthesizing Toffoli-optimal quantum circuits for arbitrary multi-qubit unitaries.  arXiv preprint arXiv:2401.08950, 2024.
  * [40] Austin G. Fowler, Matteo Mariantoni, John M. Martinis, and Andrew N. Cleland.  Surface codes: Towards practical large-scale quantum computation.  Phys. Rev. A, 86:032324, Sep 2012.
  * [41] Austin G. Fowler and Craig Gidney.  Low overhead quantum computation using lattice surgery, 2019.
  * [42] Daniel Litinski.  Magic State Distillation: Not as Costly as You Think.  Quantum, 3:205, December 2019.
  * [43] Meijian Li, Tuomas Lappi, and Xingbo Zhao.  Scattering and gluon emission in a color field: A light-front Hamiltonian approach.  Phys. Rev. D, 104(5):056014, 2021.
  * [44] Niklas Mueller, Andrey Tarasov, and Raju Venugopalan.  Deeply inelastic scattering structure functions on a hybrid quantum computer.  Phys. Rev. D, 102(1):016007, 2020.
  * [45] Michael Kreshchuk, William M. Kirby, Gary Goldstein, Hugo Beauchemin, and Peter J. Love.  Quantum simulation of quantum field theory in the light-front formulation.  Phys. Rev. A, 105(3):032418, 2022.
  * [46] Heinz J. Rothe.  Lattice Gauge Theories.  World Scientific Publishing Company, 2012.
  * [47] Zoltan Bajnok and Marton Lajer.  Truncated Hilbert space approach to the 2d $\phi^{4}$ theory.  Journal of High Energy Physics, 2016(10), October 2016.
  * [48] Barak Gabai and Xi Yin.  On the S-matrix of Ising field theory in two dimensions.  Journal of High Energy Physics, 2022(10), October 2022.
  * [49] Martin Lüscher.  Two-particle states on a torus and their relation to the scattering matrix.  Nuclear Physics B, 354(2):531–578, 1991.
  * [50] Raúl A. Briceño, Jozef J. Dudek, and Ross D. Young.  Scattering processes and resonances from lattice QCD.  Rev. Mod. Phys., 90:025001, Apr 2018.
  * [51] Maxwell T. Hansen and Stephen R. Sharpe.  Lattice QCD and three-particle decays of resonances.  Annual Review of Nuclear and Particle Science, 69(Volume 69, 2019):65–107, 2019.
  * [52] Akaki Rusetsky.  Three particles on the lattice, 2019.
  * [53] Maxim Mai, Michael Döring, and Akaki Rusetsky.  Multi-particle systems on the lattice and chiral extrapolations: a brief review.  The European Physical Journal Special Topics, 230(6):1623–1643, June 2021.
  * [54] Fernando Romero-López.  Multi-hadron interactions from lattice QCD, 2023.
  * [55] Richard D Mattuck and Börje Johansson.  Quantum field theory of phase transitions in Fermi systems.  Advances in Physics, 17(68):509–562, 1968.
  * [56] JR Espinosa, M Quiros, and Fabio Zwirner.  On the phase transition in the scalar theory.  Physics Letters B, 291(1-2):115–124, 1992.
  * [57] Matthew Hagan and Nathan Wiebe.  Composite quantum simulations.  Quantum, 7:1181, 2023.
  * [58] Abhishek Rajput, Alessandro Roggero, and Nathan Wiebe.  Hybridized methods for quantum simulation in the interaction picture.  Quantum, 6:780, 2022.
  * [59] Rolando D. Somma.  Quantum simulations of one dimensional quantum systems.  arXiv, August 2016.
  * [60] Alexandru Macridin, Panagiotis Spentzouris, James Amundson, and Roni Harnik.  Digital quantum computation of fermion-boson interacting systems.  Physical Review A, 98(4):042312, October 2018.
  * [61] Alexandru Macridin, Panagiotis Spentzouris, James Amundson, and Roni Harnik.  Electron-Phonon Systems on a Universal Quantum Computer.  Physical Review Letters, 121(11):110504, September 2018.
  * [62] Enrico Rinaldi, Xizhi Han, Mohammad Hassan, Yuan Feng, Franco Nori, Michael McGuigan, and Masanori Hanada.  Matrix Model simulations using Quantum Computing, Deep Learning, and Lattice Monte Carlo.  PRX Quantum, 3(1):010324, February 2022.
  * [63] Masanori Hanada, Junyu Liu, Enrico Rinaldi, and Masaki Tezuka.  Estimating truncation effects of quantum bosonic systems using sampling algorithms.  arXiv, March 2023.
  * [64] Jacky Huyghebaert and Hans De Raedt.  Product formula methods for time-dependent Schrodinger problems.  Journal of Physics A: Mathematical and General, 23(24):5777, 1990\.
  * [65] Nathan Wiebe, Dominic Berry, Peter Høyer, and Barry C Sanders.  Higher order decompositions of ordered operator exponentials.  Journal of Physics A: Mathematical and Theoretical, 43(6):065203, 2010.
  * [66] Dave Wecker, Matthew B Hastings, Nathan Wiebe, Bryan K Clark, Chetan Nayak, and Matthias Troyer.  Solving strongly correlated electron models on a quantum computer.  Physical Review A, 92(6):062318, 2015.
  * [67] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu.  Theory of Trotter error with commutator scaling.  Phys. Rev. X, 11:011020, Feb 2021.
  * [68] Masuo Suzuki.  General theory of fractal path integrals with applications to many-body theories and statistical physics.  Journal of Mathematical Physics, 32(2):400–407, 1991.
  * [69] Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su.  Toward the first quantum simulation with quantum speedup.  Proceedings of the National Academy of Sciences, 115(38):9456–9461, 2018.
  * [70] 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.
  * [71] Yunseong Nam, Yuan Su, and Dmitri Maslov.  Approximate quantum Fourier transform with ${O}(n\log(n))$T gates.  npj Quantum Information, 6(1):1–6, 2020.
  * [72] Guang Hao Low and Isaac L Chuang.  Optimal Hamiltonian simulation by quantum signal processing.  Physical Review Letters, 118(1):010501, 2017.
  * [73] Guang Hao Low and Isaac L Chuang.  Hamiltonian simulation by qubitization.  Quantum, 3:163, 2019.
  * [74] Andrew M Childs and Nathan Wiebe.  Hamiltonian simulation using linear combinations of unitary operations.  arXiv preprint arXiv:1202.5822, 2012.
  * [75] Yong He, Ming-Xing Luo, E Zhang, Hong-Ke Wang, and Xiao-Feng Wang.  Decompositions of n-qubit Toffoli gates with linear circuit complexity.  International Journal of Theoretical Physics, 56(7):2350–2361, 2017\.
  * [76] Craig Gidney.  Halving the cost of quantum addition.  Quantum, 2:74, 2018.
  * [77] Farrokh Vatan and Colin Williams.  Optimal quantum circuits for general two-qubit gates.  Phys. Rev. A, 69:032315, Mar 2004.
  * [78] Alex Bocharov, Martin Roetteler, and Krysta M. Svore.  Efficient synthesis of universal repeat-until-success quantum circuits.  Phys. Rev. Lett., 114:080502, Feb 2015.
  * [79] Peter Selinger.  Efficient Clifford+T approximation of single-qubit operators, 2014.
  * [80] Adriano Barenco, Charles H Bennett, Richard Cleve, David P DiVincenzo, Norman Margolus, Peter Shor, Tycho Sleator, John A Smolin, and Harald Weinfurter.  Elementary gates for quantum computation.  Physical review A, 52(5):3457, 1995.
  * [81] Matthew Amy, Parsiad Azimzadeh, and Michele Mosca.  On the controlled-not complexity of controlled-not–phase circuits.  Quantum Science and Technology, 4(1):015002, 2018.
  * [82] Vlad Gheorghiu, Jiaxin Huang, Sarah Meng Li, Michele Mosca, and Priyanka Mukhopadhyay.  Reducing the CNOT count for Clifford+T circuits on NISQ architectures.  IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2022.
  * [83] Alexei Kitaev and William A. Webb.  Wavefunction preparation and resampling using a quantum computer, 2009\.
  * [84] Dominic W Berry, Andrew M Childs, and Robin Kothari.  Hamiltonian simulation with nearly optimal dependence on all parameters.  In 2015 IEEE 56th annual symposium on foundations of computer science, pages 792–809. IEEE, 2015.
  * [85] Yutaro Akahoshi, Kazunori Maruyama, Hirotaka Oshima, Shintaro Sato, and Keisuke Fujii.  Partially fault-tolerant quantum computing architecture with error-corrected Clifford gates and space-time efficient analog rotations.  PRX Quantum, 5(1):010337, 2024.
  * [86] Earl T. Campbell, Barbara M. Terhal, and Christophe Vuillot.  Roads towards fault-tolerant universal quantum computation.  Nature, 549(7671):172–179, September 2017.
  * [87] Austin G Fowler, Matteo Mariantoni, John M Martinis, and Andrew N Cleland.  Surface codes: Towards practical large-scale quantum computation.  Physical Review A—Atomic, Molecular, and Optical Physics, 86(3):032324, 2012.
  * [88] Dave Wecker, Bela Bauer, Bryan K Clark, Matthew B Hastings, and Matthias Troyer.  Gate-count estimates for performing quantum chemistry on small quantum computers.  Physical Review A, 90(2):022305, 2014.
  * [89] Ryan Babbush, Jarrod McClean, Dave Wecker, Alán Aspuru-Guzik, and Nathan Wiebe.  Chemical basis of Trotter-Suzuki errors in quantum chemistry simulation.  Physical Review A, 91(2):022311, 2015.
  * [90] João Barata, Xiaojian Du, Meijian Li, Wenyang Qian, and Carlos A. Salgado.  Quantum simulation of in-medium QCD jets: Momentum broadening, gluon production, and entropy growth.  Phys. Rev. D, 108(5):056023, 2023.
  * [91] The cost of incrementing 1 to an $n$-bit number is $n-2$ ANDs.
  * [92] The cost of multiplying 2 $n$-bit numbers is $2n^{2}-1$ many logical ANDs.