$\displaystyle\lvert\psi_{\eta}\rangle$
$\displaystyle=\frac{\lvert\overbrace{0\underbrace{1\cdots 1}_{\eta-1}0\cdots
0}^{\frac{n}{2}}10\cdots 0\rangle+i\lvert\overbrace{1\underbrace{1\cdots
1}_{\eta-1}0\cdots 0}^{\frac{n}{2}}00\cdots 0\rangle}{\sqrt{2}},$ (149)
$\displaystyle\lvert\phi_{\eta}\rangle$
$\displaystyle=\frac{\lvert\overbrace{0\underbrace{1\cdots 1}_{\eta-1}0\cdots
0}^{\frac{n}{2}}10\cdots 0\rangle+\lvert\overbrace{1\underbrace{1\cdots
1}_{\eta-1}0\cdots 0}^{\frac{n}{2}}00\cdots 0\rangle}{\sqrt{2}}.$

Similar to the previous subsection, we may assume that $n$ is even. We have
the following proposition showing that the fermionic seminorm of nested
commutators is nearly attained.

######  Proposition 14.

Define ${T}$, ${V}$ as in (139) and $\lvert{\psi}_{\eta}\rangle$,
$\lvert{\phi}_{\eta}\rangle$ as in (149). Then,

$\begin{rcases*}\big{|}\langle{\psi}_{\eta}\rvert\overbrace{\big{[}{V},\ldots\big{[}{V}}^{p},{T}\big{]}\big{]}\lvert{\psi}_{\eta}\rangle\big{|},&p\text{
odd}\\\
\big{|}\langle{\phi}_{\eta}\rvert\underbrace{\big{[}{V},\ldots\big{[}{V}}_{p},{T}\big{]}\big{]}\lvert{\phi}_{\eta}\rangle\big{|},&p\text{
even}\end{rcases*}=2^{p}\eta^{p}+\mathcal{O}\left(\eta^{p-1}\right).$ (150)

A proof of this proposition is given in Appendix D. By rescaling the
Hamiltonian constructed in (141), we can demonstrate the tightness of our
bound as follows. For any $s,w>0$, we define the rescaled Hamiltonian as in
(144). Comparing with the definition of the interacting-electronic model (1),
we see that $\left\lVert\tau\right\rVert=s$ and
$\left\lVert\nu\right\rVert_{\max}=w$. The above proposition then shows that

$\Big{\|}\underbrace{\big{[}{V},\ldots\big{[}{V}}_{p},{T}\big{]}\big{]}\Big{\|}_{\eta}=\Omega\left((w\eta)^{p}s/n\right).$
(151)

This establishes the second claimed bound in (5) of Theorem 2.

Note that a similar example can be constructed to demonstrate the tightness of
our bound for simulating sparse electronic Hamiltonians. Specifically, for
$u,w>0$ and integer $2\leq d\leq\eta\leq\frac{n}{2}$,141414Similar to above,
the special case $d=1$ can be handled using
$T=uA_{0}^{\dagger}A_{1}+uA_{1}^{\dagger}A_{0}$ and $V=wN_{0}$. we define the
electronic Hamiltonian as in (146). Comparing with the definition of the
interacting-electronic model (1), we see that
$\left\lVert\tau\right\rVert_{\max}=u$ and
$\left\lVert\nu\right\rVert_{\max}=w$. A similar calculation then shows that

$\Big{\|}\underbrace{\big{[}{V},\ldots\big{[}{V}}_{p},{T}\big{]}\big{]}\Big{\|}_{\eta}=\Omega\left((wd)^{p}u\right).$
(152)

This proves the second claimed bound in (6) of Theorem 2.

##  6 Applications

The class of interacting-electronic Hamiltonians (1) encompasses various
quantum systems arising in physics and chemistry, for which the performance of
digital quantum simulation can be improved using our result. As for
illustration, we consider improving quantum simulation of the plane-wave-basis
electronic structure in Section 6.1 and the Fermi-Hubbard model in Section
6.2.

###  6.1 Plane-wave-basis electronic structure

Simulating the electronic-structure Hamiltonians is one of the most promising
applications of digital quantum computers. Recall that in the second-quantized
plane-wave basis, such a Hamiltonian takes the form

$\displaystyle H$
$\displaystyle=\frac{1}{2n}\sum_{j,k,\mu}\kappa_{\mu}^{2}\cos[\kappa_{\mu}\cdot
r_{k-j}]A_{j}^{\dagger}A_{k}$ (153)
$\displaystyle\quad-\frac{4\pi}{\omega}\sum_{j,\iota,\mu\neq
0}\frac{\zeta_{\iota}\cos[\kappa_{\mu}\cdot(\widetilde{r}_{\iota}-r_{j})]}{\kappa_{\mu}^{2}}N_{j}+\frac{2\pi}{\omega}\sum_{\begin{subarray}{c}j\neq
k\\\ \mu\neq 0\end{subarray}}\frac{\cos[\kappa_{\mu}\cdot
r_{j-k}]}{\kappa_{\mu}^{2}}N_{j}N_{k},$

where $\omega$ is the volume of the computational cell,
$\kappa_{\mu}=2\pi\mu/\omega^{1/3}$ are $n$ vectors of plane-wave frequencies,
$\mu$ are three-dimensional vectors of integers with elements in the interval
$[-n^{1/3},n^{1/3}]$, $r_{j}$ are the positions of electrons, $\zeta_{\iota}$
are nuclear charges, and $\widetilde{r}_{\iota}$ are the nuclear coordinates.
We further rewrite the second term as

$\displaystyle-\frac{4\pi}{\omega}\sum_{j,\iota,\mu\neq
0}\frac{\zeta_{\iota}\cos[\kappa_{\mu}\cdot(\widetilde{r}_{\iota}-r_{j})]}{\kappa_{\mu}^{2}}N_{j}=-\frac{4\pi}{\omega\eta}\sum_{j,k,\iota,\mu\neq
0}\frac{\zeta_{\iota}\cos[\kappa_{\mu}\cdot(\widetilde{r}_{\iota}-r_{j})]}{\kappa_{\mu}^{2}}N_{j}N_{k},$
(154)

which is valid since we estimate the simulation error within the
$\eta$-electron manifold. Comparing with the definition of interacting-
electronic model (1), we see that

$\displaystyle\tau_{j,k}$
$\displaystyle=\frac{1}{2n}\sum_{\mu}\kappa_{\mu}^{2}\cos[\kappa_{\mu}\cdot
r_{k-j}],$ (155) $\displaystyle\nu_{l,m}$
$\displaystyle=-\frac{4\pi}{\omega\eta}\sum_{\iota,\mu\neq
0}\frac{\zeta_{\iota}\cos[\kappa_{\mu}\cdot(\widetilde{r}_{\iota}-r_{l})]}{\kappa_{\mu}^{2}}+\frac{2\pi}{\omega}\sum_{\mu\neq
0}\frac{\cos[\kappa_{\mu}\cdot
r_{l-m}]}{\kappa_{\mu}^{2}}\left(1-\delta_{l,m}\right).$

To proceed, we need to bound the spectral norm $\left\lVert\tau\right\rVert$
and the max-norm $\left\lVert\nu\right\rVert_{\max}$ of the coefficient
matrices. We have

$\left\lVert\tau\right\rVert=\mathcal{O}\left(\frac{n^{2/3}}{\omega^{2/3}}\right),\qquad\left\lVert\tau\right\rVert_{\max}=\mathcal{O}\left(\frac{1}{n^{1/3}\omega^{2/3}}\right),\qquad\left\lVert\nu\right\rVert_{\max}=\mathcal{O}\left(\frac{n^{1/3}}{\omega^{1/3}}\right),$
(156)

where the first equality follows from [6, Eq. (F10)], the second equality
follows from [6, Eq. (F11)–(F13)] and the third equality follows from [6, Eq.
(F7) and (F9)]. We also consider a constant system density
$\eta=\mathcal{O}\left(\omega\right)$ following the setting of [6]. Applying
Theorem 1, we find that a $p$th-order formula $\mathscr{S}_{p}(t)$ can
approximate the evolution of electronic-structure Hamiltonian with Trotter
error

$\displaystyle\left\lVert\mathscr{S}_{p}(t)-e^{-itH}\right\rVert_{\eta}$
$\displaystyle=\mathcal{O}\left(\left(\left\lVert\tau\right\rVert+\left\lVert\nu\right\rVert_{\max}\eta\right)^{p-1}\left\lVert\tau\right\rVert\left\lVert\nu\right\rVert_{\max}\eta^{2}t^{p+1}\right)$
(157)
$\displaystyle=\mathcal{O}\left(\left(\frac{n^{2/3}}{\eta^{2/3}}+n^{1/3}\eta^{2/3}\right)^{p}n^{1/3}\eta^{2/3}t^{p+1}\right).$

This approximation is accurate for sufficiently small $t$. To evolve for a
longer time, we divide the evolution into $r$ steps and use
$\mathscr{S}_{p}(t/r)$ within each step, which gives an approximation with
error

$\displaystyle\left\lVert\mathscr{S}_{p}^{r}(t/r)-e^{-itH}\right\rVert_{\eta}\leq
r\left\lVert\mathscr{S}_{p}(t/r)-e^{-i\frac{t}{r}H}\right\rVert_{\eta}=\mathcal{O}\left(\left(\frac{n^{2/3}}{\eta^{2/3}}+n^{1/3}\eta^{2/3}\right)^{p}n^{1/3}\eta^{2/3}\frac{t^{p+1}}{r^{p}}\right).$
(158)

To simulate with accuracy $\epsilon$, it suffices to choose

$r=\mathcal{O}\left(\left(\frac{n^{2/3}}{\eta^{2/3}}+n^{1/3}\eta^{2/3}\right)n^{1/3p}\eta^{2/3p}\frac{t^{1+1/p}}{\epsilon^{1/p}}\right).$
(159)

Note that this can also be achieved using the weaker bound (9) from path
counting, since both $\left\lVert\tau\right\rVert$ and
$n\left\lVert\tau\right\rVert_{\max}$ have the same asymptotic scaling.

To simplify our discussion, we consider digital quantum simulation with
constant time and accuracy, obtaining

$r=\mathcal{O}\left(\left(\frac{n^{2/3}}{\eta^{2/3}}+n^{1/3}\eta^{2/3}\right)n^{1/p}\right).$
(160)

We further implement each Trotter step using the approach of [54, Sect. 5],
and obtain a quantum circuit with gate complexity

$g=\mathcal{O}\left(\left(\frac{n^{5/3}}{\eta^{2/3}}+n^{4/3}\eta^{2/3}\right)n^{1/p}\mathrm{polylog}(n)\right).$
(161)

which implies

$g=\left(\frac{n^{5/3}}{\eta^{2/3}}+n^{4/3}\eta^{2/3}\right)n^{o(1)}$ (162)

by choosing the order $p$ sufficiently large.

Up to a negligible factor $n^{o(1)}$, this gate complexity improves the best
previous result of the electronic-structure simulation in the second-quantized
plane-wave basis. This is because our approach improves the performance of
digital quantum simulation by simultaneously exploiting commutativity of the
Hamiltonian and prior knowledge of the initial state, whereas previous results
were only able to employ at most one of these information. Indeed, previous
work [6, Appendix G] gave a Trotterization with error bound

$\left\lVert\mathscr{S}_{p}(t)-e^{-itH}\right\rVert_{\eta}=\mathcal{O}\left(\left(\left\lVert\tau\right\rVert+\left\lVert\nu\right\rVert_{\max}\eta\right)^{p-1}\left\lVert\tau\right\rVert\left\lVert\nu\right\rVert_{\max}\eta^{p+2}t^{p+1}\right).$
(163)

Their approach used the initial-state information by computing the Trotter
error within the $\eta$-electron manifold, but the commutativity of the
Hamiltonian was ignored, giving a simulation with gate count
$\left(n^{5/3}\eta^{1/3}+n^{4/3}\eta^{5/3}\right)n^{o(1)}$ worse than our
result. On the other hand, the work [27, Proposition F.4] used commutativity
of the Hamiltonian to show

$\left\lVert\mathscr{S}_{p}(t)-e^{-itH}\right\rVert_{\eta}=\mathcal{O}\left(\left(\left\lVert\tau\right\rVert_{\max}+\left\lVert\nu\right\rVert_{\max}\right)^{p-1}\left\lVert\tau\right\rVert_{\max}\left\lVert\nu\right\rVert_{\max}n^{p+2}t^{p+1}\right).$
(164)

and gave a simulation with complexity $\frac{n^{7/3}}{\eta^{1/3}}n^{o(1)}$,
whereas Ref. [54] gave an interaction-picture approach with cost
$\mathcal{O}\left(\frac{n^{8/3}}{\eta^{2/3}}\mathrm{polylog}(n)\right)$. Our
new result matches these when $\eta$ and $n$ are comparable to each other, but
can be much more efficient in the regime where $\eta$ is much smaller than
$n$.

Interestingly, our asymptotic result remains conditionally advantageous even
when compared with the first-quantized simulations. There, the best previous
approach is the interaction-picture approach [7] with gate complexity
$\mathcal{O}\left(n^{1/3}\eta^{8/3}\mathrm{polylog}(n)\right)$, larger than
our new complexity when
$n=\mathcal{O}\left(\eta^{2-2/(p+1)}\mathrm{polylog}(n)\right)$. A related
approach was described in [7] based on qubitization, which has a similar
performance comparison with our result.151515It is a subject for future work
to compare the concrete resources required by our approach and those required
by the first-quantized approach of [75]. See Table 1 for details.

We mention however that there is one caveat when ignoring the factor
$n^{o(1)}$ in our above discussion. This is achieved by choosing the order $p$
of Trotterization sufficiently large, which can result in a gate complexity
with an unrealistically large prefactor depending on the definition of higher-
order formulas.161616For the $p$th-order Suzuki formula, we have a factor of
$5^{p}$ in the gate complexity, although this may be different for different
formulas. Nevertheless, recent work suggests that Trotterization remains
advantageous for simulating the plane-wave-basis electronic structure even
with a low-order formula [42], to which our paper provides new theoretical
insights.

###  6.2 Fermi-Hubbard model

We also consider applications of our result to simulations of the Fermi-
Hubbard Hamiltonian, which models many important properties of interacting
electrons. This Hamiltonian is defined as

$H=-s\sum_{\langle
j,k\rangle,\sigma}\left(A_{j,\sigma}^{\dagger}A_{k,\sigma}+A_{k,\sigma}^{\dagger}A_{j,\sigma}\right)+v\sum_{j}N_{j,0}N_{j,1},$
(165)

where $\langle j,k\rangle$ denotes a summation over nearest-neighbor lattice
sites and $\sigma\in\\{0,1\\}$.

We note that this Hamiltonian can be represented in terms of a sparse
interacted Hamiltonian. Indeed, in the one-dimensional case, we have

$H=-s\sum_{j,\sigma}\left(A_{j,\sigma}^{\dagger}A_{j+1,\sigma}+A_{j+1,\sigma}^{\dagger}A_{j,\sigma}\right)+v\sum_{j}N_{j,0}N_{j,1},$
(166)

where $j=0,1,\ldots,n-1$ and $\sigma=0,1$. Comparing with the definition of
interacting-electronic model (1), we see that

$\tau=-s\sum_{j}\left(\lvert j\rangle\langle j+1\rvert+\lvert
j+1\rangle\langle j\rvert\right)\otimes(\lvert 0\rangle\langle 0\rvert+\lvert
1\rangle\langle 1\rvert),\qquad\nu=\frac{v}{2}\sum_{j}\lvert j\rangle\langle
j\rvert\otimes\left(\lvert 0\rangle\langle 1\rvert+\lvert 1\rangle\langle
0\rvert\right),$ (167)

so the coefficient matrices $\tau$ and $\nu$ are $2$-sparse. Similar analysis
holds for the higher-dimensional Fermi-Hubbard model, with the sparsity
$d=2^{m}$ where $m$ is the dimensionality of the lattice.

We can therefore apply Theorem 1 to conclude that a $p$th-order formula
$\mathscr{S}_{p}(t)$ approximates the evolution of Fermi-Hubbard Hamiltonian
with Trotter error

$\left\lVert\mathscr{S}_{p}(t)-e^{-itH}\right\rVert_{\eta}=\mathcal{O}\left((s+v)^{p-1}sv2^{m(p+1)}\eta
t^{p+1}\right)=\mathcal{O}\left(\eta t^{p+1}\right),$ (168)

assuming $s$, $v$, and $m$ are constant. For $r$ steps of Trotterization, we
apply the triangle inequality to get

$\left\lVert\mathscr{S}_{p}^{r}(t/r)-e^{-itH}\right\rVert_{\eta}\leq
r\left\lVert\mathscr{S}_{p}(t/r)-e^{-i\frac{t}{r}H}\right\rVert_{\eta}=\mathcal{O}\left(\eta\frac{t^{p+1}}{r^{p}}\right).$
(169)

To simulate with constant time and accuracy, it thus suffices to choose

$r=\mathcal{O}\left(\eta^{1/p}\right),$ (170)

giving gate complexity171717By exploiting locality, we can perform $e^{-itV}$
with $O\left(n\right)$ gates. An additional logarithmic factor will be
introduced if we implement $e^{-itT}$ using the fermionic Fourier transform.
However, this can be avoided by further decomposing
$T=T_{\text{odd}}+T_{\text{even}}$ as in [22], so that
$H=T_{\text{odd}}+T_{\text{even}}+V$. The analysis of Trotter error proceeds
in a similar way as in Section 4, which establishes the claimed gate
complexity of $\mathcal{O}\left(n\eta^{1/p}\right)$.

$g=\mathcal{O}\left(n\eta^{1/p}\right).$ (171)

The Fermi-Hubbard model only contains nearest-neighbor interactions and,
according to [22], can be near optimally simulated with
$\mathcal{O}\left(n^{1+1/p}\right)$ gates. On the other hand, recent work [28]
shows that Trotterization algorithm has gate complexity
$\mathcal{O}\left(n\eta^{1+1/p}\right)$ when restricted to the $\eta$-electron
manifold. Our result improves over those previous work by combining the
sparsity of interactions, commutativity of the Hamiltonian and information
about the initial state.

##  7 Discussion

We have given improved quantum simulations of a class of interacting electrons
using Trotterization, by simultaneously exploiting commutativity of the
Hamiltonian, sparsity of interactions, and prior knowledge of the initial
state. We identified applications to simulating the plane-wave-basis
electronic structure, improving the best previous result in second
quantization up to a negligible factor while conditionally outperforming the
first-quantized simulation. We obtained further speedups when the electronic
Hamiltonian has $d$-sparse interactions, which gave faster Trotterization of
the Fermi-Hubbard model. We constructed concrete electronic systems for which
our bounds are almost saturated, providing a provable guarantee on the
tightness of our analysis.

Our focus has been on the asymptotic performance of digital quantum simulation
throughout this paper. However, we believe that the techniques we have
developed can also be used to give quantum simulations with low constant-
prefactor overhead, for instance, through a more careful application of our
Proposition 9, Proposition 10, Proposition 11 and Proposition 12. Such
improvements would especially benefit the simulation of plane-wave-basis
electronic structure, where many pairs of Hamiltonian terms commute and the
number of electrons can be significantly smaller than the spin-orbital number.
Existing numerical studies almost exclusively used the second-order Suzuki
formula [42, 84, 5, 65, 19] and their results did not fully leverage the
commutativity of the Hamiltonian and the initial-state knowledge, which may
then be improved by the techniques presented here using general Trotterization
schemes.

Our analysis is applicable to a class of electronic Hamiltonians of the form
$H=\sum_{j,k}\tau_{j,k}A_{j}^{\dagger}A_{k}+\sum_{l,m}\nu_{l,m}N_{l}N_{m}$. By
imposing further constraints on the coefficients, we may somewhat sacrifice
this generality but instead get further improvement on the simulation
performance. One possibility is to consider the subclass of systems that are
translation-invariant, i.e., $\tau_{j,k}=\tau_{j+q,k+q}$ and
$\nu_{l,m}=\nu_{l+q,m+q}$. This translational invariance is used in the
circuit implementations for both our applications (electronic-structure
Hamiltonians and Fermi-Hubbard model), but is nevertheless ignored in the
proof of our upper bounds (Theorem 1) and tightness result (Theorem 2). By
incorporating additional features of the Hamiltonian such as translational
invariance, it is plausible that our current complexity estimate can be
further improved.

A natural problem that has yet to be addressed here is the simulation of
electronic-structure Hamiltonians in a more compact molecular basis. Such
Hamiltonians typically take the form
$H=\sum_{j,k}h_{j,k}A_{j}^{\dagger}A_{k}+\sum_{j,k,l,m}h_{j,k,l,m}A_{j}^{\dagger}A_{k}A_{l}^{\dagger}A_{m}$,
more complex than the electronic model (1) considered here. In this case, the
exponentials of the two-body terms
$\sum_{j,k,l,m}h_{j,k,l,m}A_{j}^{\dagger}A_{k}A_{l}^{\dagger}A_{m}$ do not
have a convenient circuit implementation and our current approach is not
directly applicable. This motivates further developments of _hybrid quantum
simulation_ , in which Trotterization is combined with more advanced quantum
algorithms to speed up digital quantum simulation. We leave a detailed study
of such problems as a subject for future work.

More generally, we could consider digital quantum simulations of other types
of physical systems, such as bosonic systems [70] or fermion-boson interacting
systems [72]. We hope our techniques could offer insights to such problems and
find further applications in digital quantum simulation beyond what have been
discussed here.

## Acknowledgements

We thank Fernando Brandão for inspiring discussions during the initial stages
of this work, and Géza Giedke and anonymous referees for their comments on an
earlier draft. YS thanks Nathan Wiebe, Guang Hao Low, Ryan Babbush, Minh Cong
Tran, Kunal Sharma, John Preskill, and Andrew Childs for helpful discussions.
He is supported by the National Science Foundation RAISE-TAQS 1839204 and
Amazon Web Services, AWS Quantum Program. HH is supported by the J. Yang &
Family Foundation. The Institute for Quantum Information and Matter is an NSF
Physics Frontiers Center PHY-1733907.

##  Appendix A Analysis of single-layer commutator

In this appendix, we complete the proof of Proposition 8 that bounds the terms
arising in the commutator analysis of first-order formula.

For the third statement of Proposition 8, we let
$X=\sum_{j,k,l}\tau_{j,k}\nu_{l,k}A_{j}^{\dagger}N_{l}A_{k}$ and compute

$\displaystyle X^{\dagger}X$
$\displaystyle=\sum_{j_{1},k_{1},l_{1},j_{2},k_{2},l_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{l_{1},k_{1}}\tau_{j_{2},k_{2}}\nu_{l_{2},k_{2}}A_{k_{1}}^{\dagger}N_{l_{1}}A_{j_{1}}A_{j_{2}}^{\dagger}N_{l_{2}}A_{k_{2}}$
(172)
$\displaystyle=\sum_{j_{1},k_{1},l_{1},k_{2},l_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{l_{1},k_{1}}\tau_{j_{1},k_{2}}\nu_{l_{2},k_{2}}A_{k_{1}}^{\dagger}N_{l_{1}}N_{l_{2}}A_{k_{2}}$
$\displaystyle\quad-\sum_{j_{1},k_{1},l_{1},j_{2},k_{2},l_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{l_{1},k_{1}}\tau_{j_{2},k_{2}}\nu_{l_{2},k_{2}}A_{k_{1}}^{\dagger}N_{l_{1}}A_{j_{2}}^{\dagger}A_{j_{1}}N_{l_{2}}A_{k_{2}}.$

Applying the operator Cauchy-Schwarz inequality (Lemma 1) similarly as in
(63),

$\displaystyle X^{\dagger}X$
$\displaystyle\leq\sum_{j_{1},k_{1},l_{1},k_{2},l_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{l_{1},k_{1}}\tau_{j_{1},k_{2}}\nu_{l_{2},k_{2}}A_{k_{1}}^{\dagger}N_{l_{1}}N_{l_{2}}A_{k_{2}}$
(173)
$\displaystyle\quad+\sum_{j_{1},k_{1},l_{1},j_{2},k_{2},l_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{l_{1},k_{1}}\tau_{j_{1},k_{2}}\nu_{l_{2},k_{2}}A_{k_{1}}^{\dagger}N_{l_{1}}A_{j_{2}}^{\dagger}A_{j_{2}}N_{l_{2}}A_{k_{2}}$
$\displaystyle=\sum_{j_{1},k_{1},l_{1},k_{2},l_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{l_{1},k_{1}}\tau_{j_{1},k_{2}}\nu_{l_{2},k_{2}}A_{k_{1}}^{\dagger}N_{l_{1}}N_{l_{2}}A_{k_{2}}N.$

We now perform diagonalization using Lemma 2, obtaining

$X^{\dagger}X\leq\left\lVert\tau\right\rVert^{2}\sum_{k_{1},l_{1},l_{2}}\bar{\nu}_{l_{1},k_{1}}\nu_{l_{2},k_{1}}A_{k_{1}}^{\dagger}N_{l_{1}}N_{l_{2}}A_{k_{1}}N.$
(174)

Using the Hölder-type inequality for the expectation value (Lemma 3), we have

$\displaystyle\left\lVert X^{\dagger}X\right\rVert_{\eta}$
$\displaystyle\leq\left\lVert\left\lVert\tau\right\rVert^{2}\sum_{k_{1},l_{1},l_{2}}\bar{\nu}_{l_{1},k_{1}}\nu_{l_{2},k_{1}}A_{k_{1}}^{\dagger}N_{l_{1}}N_{l_{2}}A_{k_{1}}N\right\rVert_{\eta}=\left\lVert\tau\right\rVert^{2}\eta\left\lVert\sum_{k_{1},l_{1},l_{2}}\bar{\nu}_{l_{1},k_{1}}\nu_{l_{2},k_{1}}A_{k_{1}}^{\dagger}N_{l_{1}}N_{l_{2}}A_{k_{1}}\right\rVert_{\eta}$
(175)
$\displaystyle\leq\left\lVert\tau\right\rVert^{2}\eta\left\lVert\sum_{k_{1}}A_{k_{1}}^{\dagger}A_{k_{1}}\right\rVert_{\eta}\max_{k_{1}}\left\lVert\sum_{l_{1},l_{2}}\bar{\nu}_{l_{1},k_{1}}\nu_{l_{2},k_{1}}N_{l_{1}}N_{l_{2}}\right\rVert_{\eta-1},$

where
$\left\lVert\sum_{k_{1}}A_{k_{1}}^{\dagger}A_{k_{1}}\right\rVert_{\eta}=\eta$
and
$\left\lVert\sum_{l_{1},l_{2}}\bar{\nu}_{l_{1},k_{1}}\nu_{l_{2},k_{1}}N_{l_{1}}N_{l_{2}}\right\rVert_{\eta-1}\leq\left\lVert\nu\right\rVert_{\max}^{2}\eta^{2}$.
This completes the proof of the third statement of Proposition 8.

For the fourth statement, we let
$X=\sum_{j,k,m}\tau_{j,k}\nu_{j,m}A_{j}^{\dagger}N_{m}A_{k}$ and compute

$\displaystyle X^{\dagger}X$
$\displaystyle=\sum_{j_{1},k_{1},m_{1},j_{2},k_{2},m_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{j_{1},m_{1}}\tau_{j_{2},k_{2}}\nu_{j_{2},m_{2}}A_{k_{1}}^{\dagger}N_{m_{1}}A_{j_{1}}A_{j_{2}}^{\dagger}N_{m_{2}}A_{k_{2}}$
(176)
$\displaystyle=\sum_{j_{1},k_{1},m_{1},k_{2},m_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{j_{1},m_{1}}\tau_{j_{1},k_{2}}\nu_{j_{1},m_{2}}A_{k_{1}}^{\dagger}N_{m_{1}}N_{m_{2}}A_{k_{2}}$
$\displaystyle\quad-\sum_{j_{1},k_{1},m_{1},j_{2},k_{2},m_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{j_{1},m_{1}}\tau_{j_{2},k_{2}}\nu_{j_{2},m_{2}}A_{k_{1}}^{\dagger}N_{m_{1}}A_{j_{2}}^{\dagger}A_{j_{1}}N_{m_{2}}A_{k_{2}}.$

Applying the operator Cauchy-Schwarz inequality (Lemma 1),

$\displaystyle X^{\dagger}X$
$\displaystyle\leq\sum_{j_{1},k_{1},m_{1},k_{2},m_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{j_{1},m_{1}}\tau_{j_{1},k_{2}}\nu_{j_{1},m_{2}}A_{k_{1}}^{\dagger}N_{m_{1}}N_{m_{2}}A_{k_{2}}$
(177)
$\displaystyle\quad+\sum_{j_{1},k_{1},m_{1},j_{2},k_{2},m_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{j_{1},m_{1}}\tau_{j_{1},k_{2}}\nu_{j_{1},m_{2}}A_{k_{1}}^{\dagger}N_{m_{1}}A_{j_{2}}^{\dagger}A_{j_{2}}N_{m_{2}}A_{k_{2}}$
$\displaystyle=\sum_{j_{1},k_{1},m_{1},k_{2},m_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{j_{1},m_{1}}\tau_{j_{1},k_{2}}\nu_{j_{1},m_{2}}A_{k_{1}}^{\dagger}N_{m_{1}}N_{m_{2}}A_{k_{2}}N.$

We now use the Hölder-type inequality for the expectation value (Lemma 3) to
get

$\displaystyle\left\lVert X^{\dagger}X\right\rVert_{\eta}$
$\displaystyle\leq\left\lVert\sum_{j_{1},k_{1},m_{1},k_{2},m_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{j_{1},m_{1}}\tau_{j_{1},k_{2}}\nu_{j_{1},m_{2}}A_{k_{1}}^{\dagger}N_{m_{1}}N_{m_{2}}A_{k_{2}}N\right\rVert_{\eta}$
(178)
$\displaystyle\leq\eta\left\lVert\sum_{j_{1},k_{1},k_{2}}\bar{\tau}_{j_{1},k_{1}}\tau_{j_{1},k_{2}}A_{k_{1}}^{\dagger}A_{k_{2}}\right\rVert_{\eta}\max_{j_{1}}\left\lVert\sum_{m_{1},m_{2}}\bar{\nu}_{j_{1},m_{1}}\nu_{j_{1},m_{2}}N_{m_{1}}N_{m_{2}}\right\rVert_{\eta-1}.$

The second fermionic seminorm can be directly bounded as
$\left\lVert\sum_{m_{1},m_{2}}\bar{\nu}_{j_{1},m_{1}}\nu_{j_{1},m_{2}}N_{m_{1}}N_{m_{2}}\right\rVert_{\eta-1}\leq\left\lVert\nu\right\rVert_{\max}^{2}\eta^{2}$,
whereas the first seminorm can be bounded using diagonalization (Lemma 2)

$\left\lVert\sum_{j_{1},k_{1},k_{2}}\bar{\tau}_{j_{1},k_{1}}\tau_{j_{1},k_{2}}A_{k_{1}}^{\dagger}A_{k_{2}}\right\rVert_{\eta}\leq\left\lVert\sum_{k_{1}}\left\lVert\tau^{\dagger}\tau\right\rVert
A_{k_{1}}^{\dagger}A_{k_{1}}\right\rVert_{\eta}\leq\left\lVert\tau^{\dagger}\tau\right\rVert\eta.$
(179)

This completes the proof of the fourth statement of Proposition 8.

For the fifth statement, we let
$X=\sum_{j,k}\tau_{j,k}\nu_{j,j}A_{j}^{\dagger}A_{k}$ and compute

$\displaystyle X^{\dagger}X$
$\displaystyle=\sum_{j_{1},k_{1},j_{2},k_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{j_{1},j_{1}}\tau_{j_{2},k_{2}}\nu_{j_{2},j_{2}}A_{k_{1}}^{\dagger}A_{j_{1}}A_{j_{2}}^{\dagger}A_{k_{2}}$
(180)
$\displaystyle=\sum_{j_{1},k_{1},k_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{j_{1},j_{1}}\tau_{j_{1},k_{2}}\nu_{j_{1},j_{1}}A_{k_{1}}^{\dagger}A_{k_{2}}-\sum_{j_{1},k_{1},j_{2},k_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{j_{1},j_{1}}\tau_{j_{2},k_{2}}\nu_{j_{2},j_{2}}A_{k_{1}}^{\dagger}A_{j_{2}}^{\dagger}A_{j_{1}}A_{k_{2}}.$

Applying the operator Cauchy-Schwarz inequality (Lemma 1),

$\displaystyle X^{\dagger}X$
$\displaystyle\leq\sum_{j_{1},k_{1},k_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{j_{1},j_{1}}\tau_{j_{1},k_{2}}\nu_{j_{1},j_{1}}A_{k_{1}}^{\dagger}A_{k_{2}}+\sum_{j_{1},k_{1},j_{2},k_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{j_{1},j_{1}}\tau_{j_{1},k_{2}}\nu_{j_{1},j_{2}}A_{k_{1}}^{\dagger}A_{j_{2}}^{\dagger}A_{j_{2}}A_{k_{2}}$
(181)
$\displaystyle=\sum_{j_{1},k_{1},k_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{j_{1},j_{1}}\tau_{j_{1},k_{2}}\nu_{j_{1},j_{1}}A_{k_{1}}^{\dagger}A_{k_{2}}N.$

We now use the Hölder-type inequality for the expectation value (Lemma 3) to
get

$\displaystyle\left\lVert X^{\dagger}X\right\rVert_{\eta}$
$\displaystyle\leq\left\lVert\sum_{j_{1},k_{1},k_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{j_{1},j_{1}}\tau_{j_{1},k_{2}}\nu_{j_{1},j_{1}}A_{k_{1}}^{\dagger}A_{k_{2}}N\right\rVert_{\eta}$
(182)
$\displaystyle=\eta\left\lVert\sum_{j_{1},k_{1},k_{2}}\bar{\tau}_{j_{1},k_{1}}\tau_{j_{1},k_{2}}A_{k_{1}}^{\dagger}A_{k_{2}}\right\rVert_{\eta}\max_{j_{1}}\left\lVert\bar{\nu}_{j_{1},j_{1}}\nu_{j_{1},j_{1}}I\right\rVert_{\eta-1}.$

The second fermionic seminorm can be directly bounded by
$\left\lVert\nu\right\rVert_{\max}^{2}$, whereas we perform diagonalization to
the first seminorm (Lemma 2):

$\left\lVert\sum_{j_{1},k_{1},k_{2}}\bar{\tau}_{j_{1},k_{1}}\tau_{j_{1},k_{2}}A_{k_{1}}^{\dagger}A_{k_{2}}\right\rVert_{\eta}\leq\left\lVert\tau^{\dagger}\tau\right\rVert\left\lVert\sum_{k_{1}}A_{k_{1}}^{\dagger}A_{k_{1}}\right\rVert_{\eta}=\left\lVert\tau^{\dagger}\tau\right\rVert\eta.$
(183)

This completes the proof of the fifth statement of Proposition 8.

For the sixth statement, we let
$X=\sum_{j,k,l}\tau_{j,k}\nu_{l,j}A_{j}^{\dagger}N_{l}A_{k}$ and compute

$\displaystyle X^{\dagger}X$
$\displaystyle=\sum_{j_{1},k_{1},l_{1},j_{2},k_{2},l_{2}}\tau_{j_{1},k_{1}}\nu_{l_{1},j_{1}}\tau_{j_{2},k_{2}}\nu_{l_{2},j_{2}}A_{k_{1}}^{\dagger}N_{l_{1}}A_{j_{1}}A_{j_{2}}^{\dagger}N_{l_{2}}A_{k_{2}}$
(184)
$\displaystyle=\sum_{j_{1},k_{1},l_{1},k_{2},l_{2}}\tau_{j_{1},k_{1}}\nu_{l_{1},j_{1}}\tau_{j_{1},k_{2}}\nu_{l_{2},j_{1}}A_{k_{1}}^{\dagger}N_{l_{1}}N_{l_{2}}A_{k_{2}}$
$\displaystyle\quad-\sum_{j_{1},k_{1},l_{1},j_{2},k_{2},l_{2}}\tau_{j_{1},k_{1}}\nu_{l_{1},j_{1}}\tau_{j_{2},k_{2}}\nu_{l_{2},j_{2}}A_{k_{1}}^{\dagger}N_{l_{1}}A_{j_{2}}^{\dagger}A_{j_{1}}N_{l_{2}}A_{k_{2}}.$

Applying the operator Cauchy-Schwarz inequality (Lemma 1),

$\displaystyle X^{\dagger}X$
$\displaystyle\leq\sum_{j_{1},k_{1},l_{1},k_{2},l_{2}}\tau_{j_{1},k_{1}}\nu_{l_{1},j_{1}}\tau_{j_{1},k_{2}}\nu_{l_{2},j_{1}}A_{k_{1}}^{\dagger}N_{l_{1}}N_{l_{2}}A_{k_{2}}$
(185)
$\displaystyle\quad+\sum_{j_{1},k_{1},l_{1},j_{2},k_{2},l_{2}}\tau_{j_{1},k_{1}}\nu_{l_{1},j_{1}}\tau_{j_{1},k_{2}}\nu_{l_{2},j_{1}}A_{k_{1}}^{\dagger}N_{l_{1}}A_{j_{2}}^{\dagger}A_{j_{2}}N_{l_{2}}A_{k_{2}}$
$\displaystyle=\sum_{j_{1},k_{1},l_{1},k_{2},l_{2}}\tau_{j_{1},k_{1}}\nu_{l_{1},j_{1}}\tau_{j_{1},k_{2}}\nu_{l_{2},j_{1}}A_{k_{1}}^{\dagger}N_{l_{1}}N_{l_{2}}A_{k_{2}}N.$

We now use the Hölder-type inequality for the expectation value (Lemma 3) to
get

$\displaystyle\left\lVert X^{\dagger}X\right\rVert_{\eta}$
$\displaystyle\leq\left\lVert\sum_{j_{1},k_{1},l_{1},k_{2},l_{2}}\tau_{j_{1},k_{1}}\nu_{l_{1},j_{1}}\tau_{j_{1},k_{2}}\nu_{l_{2},j_{1}}A_{k_{1}}^{\dagger}N_{l_{1}}N_{l_{2}}A_{k_{2}}N\right\rVert_{\eta}$
(186)
$\displaystyle=\eta\left\lVert\sum_{j_{1},k_{1},k_{2}}\tau_{j_{1},k_{1}}\tau_{j_{1},k_{2}}A_{k_{1}}^{\dagger}A_{k_{2}}\right\rVert_{\eta}\max_{j_{1}}\left\lVert\sum_{l_{1},l_{2}}\nu_{l_{1},j_{1}}\nu_{l_{2},j_{1}}N_{l_{1}}N_{l_{2}}\right\rVert_{\eta-1}.$

The second fermionic seminorm can be directly bounded by
$\left\lVert\nu\right\rVert_{\max}^{2}\eta^{2}$, whereas we perform
diagonalization to the first seminorm (Lemma 2):

$\left\lVert\sum_{j_{1},k_{1},k_{2}}\tau_{j_{1},k_{1}}\tau_{j_{1},k_{2}}A_{k_{1}}^{\dagger}A_{k_{2}}\right\rVert_{\eta}\leq\left\lVert\tau^{\dagger}\tau\right\rVert\left\lVert\sum_{k_{1}}A_{k_{1}}^{\dagger}A_{k_{2}}\right\rVert_{\eta}=\left\lVert\tau^{\dagger}\tau\right\rVert\eta.$
(187)

This completes the proof of the sixth statement of Proposition 8.

##  Appendix B Counting fermionic paths for non-sparse interactions

In this appendix, we use the path-counting technique to prove (9) for non-
sparse interacting electrons. We will make use of the following commutation
relations

$\displaystyle\left[A_{j}^{\dagger}A_{k},A_{j_{x}}^{\dagger}\right]$
$\displaystyle=\delta_{k,j_{x}}A_{j}^{\dagger},\quad\left[A_{j}^{\dagger}A_{k},A_{k_{y}}\right]=-\delta_{k_{y},j}A_{k},\quad\left[A_{j}^{\dagger}A_{k},N_{l_{z}}\right]=\delta_{k,l_{z}}A_{j}^{\dagger}A_{k}-\delta_{j,l_{z}}A_{j}^{\dagger}A_{k},$
(188) $\displaystyle\left[N_{l}N_{m},A_{j_{x}}^{\dagger}\right]$
$\displaystyle=\delta_{m,j_{x}}N_{l}A_{j_{x}}^{\dagger}+\delta_{l,j_{x}}N_{m}A_{j_{x}}^{\dagger}-\delta_{l,k_{x}}\delta_{m,k_{x}}A^{\dagger}_{j_{x}},$
(189) $\displaystyle\left[N_{l}N_{m},A_{k_{x}}\right]$
$\displaystyle=-\delta_{m,k_{x}}A_{k_{x}}N_{l}-\delta_{l,k_{x}}A_{k_{x}}N_{m}+\delta_{l,k_{x}}\delta_{m,k_{x}}A_{k_{x}},$
(190)

which are slightly different from the ones used before. These relations can be
derived in a similar way as in Equation (77) and (78).

Our analysis of the non-sparse interactions mirrors that of the sparse case in
Section 4.2.

######  Proposition 15 (Non-sparse path-counting bound).

Under the same assumption as in Proposition 11, we have

$\displaystyle\sum_{\langle j_{p+1},k_{p+1}\rangle}\ldots\sum_{\langle
j_{1},k_{1}\rangle}\sum_{P\rhd\left(H^{\gamma_{p+1}}_{j_{p+1}k_{p+1}},\ldots,H^{\gamma_{1}}_{j_{1}k_{1}}\right)}\left\lVert
P\lvert\boldsymbol{c}_{\eta}\rangle\right\rVert$
$\displaystyle=\mathcal{O}\left(n^{\left\lvert\boldsymbol{\gamma}\right\rvert}\eta^{p+2-\left\lvert\boldsymbol{\gamma}\right\rvert}\right),$
(191) $\displaystyle\sum_{\langle j_{p+1},k_{p+1}\rangle}\ldots\sum_{\langle
j_{1},k_{1}\rangle}\sum_{P^{\dagger}\rhd\left(H^{\gamma_{p+1}}_{j_{p+1}k_{p+1}},\ldots,H^{\gamma_{1}}_{j_{1}k_{1}}\right)}\left\lVert
P^{\dagger}\lvert\boldsymbol{c}_{\eta}\rangle\right\rVert$
$\displaystyle=\mathcal{O}\left(n^{\left\lvert\boldsymbol{\gamma}\right\rvert}\eta^{p+2-\left\lvert\boldsymbol{\gamma}\right\rvert}\right).$
(192)

###### Proof.

We will prove the following claims by induction on $q=2,\ldots,p+1$.

  * •

All fermionic paths $P$ are products of $A^{\dagger}_{i}A_{j}$ and $N_{k}$.

  * •

All fermionic paths $P$ have at most $q+1$ elementary fermionic operators.

  * •

The number of fermionic paths $P$ that start with a fermionic operator acting
on a specific site $i$ is at most
$3^{q-1}q!n^{\sum_{q^{\prime}=1}^{q}\gamma_{q^{\prime}}}\eta^{\sum_{q^{\prime}=1}^{q}(1-\gamma_{q^{\prime}})}$.

The base case $q=2$ can be easily verified by noting that we only need to
consider $[T,V]$ or $[V,T]$. For every site $i$, there are at most $6n\eta$
fermionic paths starting with this site, all of which are products of
$A^{\dagger}_{i}A_{j}$ and $N_{k}$. This is because there are at most three
summation indices. The rightmost index must be equal to $i$ and the indices
for $N_{k}$, $A_{j}$ have at most $\eta$ choices, while the remaining index
has $n$ possible choices, giving a total of $n\eta$ choices. The additional
factor of $6$ comes from the number of different expansion terms in Equation
(188), (189), (190). Furthermore, every fermionic path consists of at most $3$
fermionic operators. These established the claims for the base case $q=2$.

For every $q>2$, we now use the induction hypothesis for $q-1$ to prove the
claims for $q$. If $\gamma_{q}=1$, then we take another commutator with
$T=\sum_{j_{q},k_{q}}\tau_{j_{q},k_{q}}A^{\dagger}_{j_{q}}A_{k_{q}}$. We can
see that all fermionic paths
$P\rhd\left(H^{\gamma_{q}}_{j_{q}k_{q}},\ldots,H^{\gamma_{1}}_{j_{1}k_{1}}\right)$
come from the expansion of

$[A^{\dagger}_{j_{q}}A_{k_{q}},P^{\prime}],\ \forall\langle
j_{q},k_{q}\rangle,\ \forall
P^{\prime}\rhd\left(H^{\gamma_{q-1}}_{j_{q-1}k_{q-1}},\ldots,H^{\gamma_{1}}_{j_{1}k_{1}}\right).$
(193)

Using the commutation rule $[X,Y_{1}\ldots
Y_{\kappa}]=\sum_{k=1}^{\kappa}Y_{1}\ldots Y_{k-1}[X,Y_{k}]Y_{k+1}\ldots
Y_{\kappa}$, we show that the claims hold for $q$ as follows. When we take the
commutation of $A^{\dagger}_{j_{q}}A_{k_{q}}$ with $A_{j}^{\dagger}$ or
$A_{k}$, we know from (189) that one free index will be introduced, resulting
in an additional factor of $n$. When we take the commutation of
$A^{\dagger}_{j_{q}}A_{k_{q}}$ with $N_{l}$, we will remove the fermionic
operator $N_{l}$ and replace it with $A^{\dagger}_{j_{q}}A_{k_{q}}$, which
removes a factor of $\eta$ and adds an additional factor of $n\eta$.
Additionally, there are at most $(q-1)+1$ fermionic operators in $P^{\prime}$.
Hence the number of fermionic paths $P$ that start with a fermionic operator
acting on site $i$ is at most

$(2q)3^{q-2}(q-1)!nn^{\sum_{q^{\prime}=1}^{q-1}\gamma_{q^{\prime}}}\eta^{\sum_{q^{\prime}=1}^{q-1}(1-\gamma_{q^{\prime}})}\leq
3^{q-1}q!n^{\sum_{q^{\prime}=1}^{q}\gamma_{q^{\prime}}}\eta^{\sum_{q^{\prime}=1}^{q}(1-\gamma_{q^{\prime}})}.$
(194)

Furthermore, in both cases, we add at most one additional fermionic operator.
Therefore, all fermionic paths will have at most $(q-1)+1+1=q+1$ fermionic
operators. And $[A^{\dagger}_{j_{q}}A_{k_{q}},P^{\prime}]$ remains a product
of $A^{\dagger}_{i}A_{j}$ and $N_{k}$.

The inductive step for $\gamma_{q}=0$ follows from a similar argument. The
first two claims can be directly verified. For the last claim, we proceed in a
slightly different way as follows. When we take the commutator of
$N^{\dagger}_{j_{q}}N_{k_{q}}$ with $A_{j}^{\dagger}$ or $A_{k}$, we will add
$N_{j_{q}}$ or $N_{k_{q}}$ to the fermionic path, which results in an
additional factor of $\eta$. When we take the commutator of
$N^{\dagger}_{j_{q}}N_{k_{q}}$ with $N_{k}$, the commutator is equal to zero.
Hence the number of fermionic paths that start with a fermionic operator
acting on site $i$ is at most

$(3q)3^{q-2}(q-1)!\eta
n^{\sum_{q^{\prime}=1}^{q-1}\gamma_{q^{\prime}}}\eta^{\sum_{q^{\prime}=1}^{q-1}(1-\gamma_{q^{\prime}})}\leq
3^{q-1}q!n^{\sum_{q^{\prime}=1}^{q}\gamma_{q^{\prime}}}\eta^{\sum_{q^{\prime}=1}^{q}(1-\gamma_{q^{\prime}})}.$
(195)

We have thus shown that the claims hold for $q$.

Performing the induction on $q$ from $2$ to $p+1$ shows that the number of
fermionic paths starting with site $i$ is at most

$3^{p}(p+1)!n^{\sum_{q=1}^{p+1}\gamma_{q}}\eta^{\sum_{q=1}^{p+1}(1-\gamma_{q})}=\mathcal{O}\left(n^{\sum_{q=1}^{p+1}\gamma_{q}}\eta^{\sum_{q=1}^{p+1}(1-\gamma_{q})}\right).$
(196)

Because each fermionic path $P$ is a product of $A^{\dagger}_{i}A_{j}$ and
$N_{k}$, $\left\lVert P\lvert\boldsymbol{c}_{\eta}\rangle\right\rVert$ would
be nonzero only if the rightmost fermionic operator acts on one of the $\eta$
occupied sites in the configuration $\boldsymbol{c}_{\eta}$. Hence there are
at most
$\eta\mathcal{O}(n^{\sum_{q=1}^{p+1}\gamma_{q}}\eta^{\sum_{q=1}^{p+1}(1-\gamma_{q})})$
fermionic paths with non-zero $\left\lVert
P\lvert\boldsymbol{c}_{\eta}\rangle\right\rVert$. Finally, recall from Lemma 4
that $\left\lVert P\lvert\boldsymbol{c}_{\eta}\rangle\right\rVert$ is either
$0$ or $1$. Therefore, we have

$\sum_{\langle j_{p+1},k_{p+1}\rangle}\ldots\sum_{\langle
j_{1},k_{1}\rangle}\sum_{P\rhd\left(H^{\gamma_{p+1}}_{j_{p+1}k_{p+1}},\ldots,H^{\gamma_{1}}_{j_{1}k_{1}}\right)}\left\lVert
P\lvert\boldsymbol{c}_{\eta}\rangle\right\rVert=\mathcal{O}\left(n^{\sum_{q=1}^{p+1}\gamma_{q}}\eta^{1+\sum_{q=1}^{p+1}(1-\gamma_{q})}\right).$
(197)

The other bound

$\sum_{\langle j_{p+1},k_{p+1}\rangle}\ldots\sum_{\langle
j_{1},k_{1}\rangle}\sum_{P^{\dagger}\rhd\left(H^{\gamma_{p+1}}_{j_{p+1}k_{p+1}},\ldots,H^{\gamma_{1}}_{j_{1}k_{1}}\right)}\left\lVert
P^{\dagger}\lvert\boldsymbol{c}_{\eta}\rangle\right\rVert=\mathcal{O}\left(n^{\left\lvert\boldsymbol{\gamma}\right\rvert}\eta^{p+2-\left\lvert\boldsymbol{\gamma}\right\rvert}\right)$
(198)

can be similarly proved using the fact that the leftmost fermionic operator of
$P^{\dagger}$ must act on one of the $\eta$ occupied sites in any fixed
configuration. ∎

We can combine the above proposition with the path-counting bound (Proposition
11) to obtain

$\displaystyle\left\lVert\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]\right\rVert_{\eta}$
$\displaystyle=\mathcal{O}\left((n\left\lVert\tau\right\rVert_{\max})^{\left\lvert\boldsymbol{\gamma}\right\rvert}(\eta\left\lVert\nu\right\rVert_{\max})^{p+1-\left\lvert\boldsymbol{\gamma}\right\rvert}\eta\right).$
(199)

Finally, we use the Trotter error bound (43) to obtain

$\left\lVert\mathscr{S}_{p}(t)-e^{-itH}\right\rVert_{\eta}=\mathcal{O}\left(\left(n\left\lVert\tau\right\rVert_{\max}+\eta\left\lVert\nu\right\rVert_{\max}\right)^{p-1}\left\lVert\tau\right\rVert_{\max}\left\lVert\nu\right\rVert_{\max}n\eta^{2}t^{p+1}\right),$
(200)

completing the proof of (9).

Note that this bound is slightly worse than Eq. (2) of Theorem 1, as the norm
inequality $\left\lVert\tau\right\rVert\leq
n\left\lVert\tau\right\rVert_{\max}$ always holds but not necessarily
saturates. However, in the electronic-structure application, it indeed holds
that $\left\lVert\tau\right\rVert$ and $n\left\lVert\tau\right\rVert_{\max}$
have the same asymptotic scaling, so (2) and (9) give digital quantum
simulations with the same asymptotic gate complexity. See Section 6.1 for
further discussions.

##  Appendix C Lower-bounding $\left\lVert[T,\ldots[T,V]]\right\rVert_{\eta}$

In this appendix, we prove Proposition 13 that lower-bounds
$\left\lVert[T,\ldots[T,V]]\right\rVert_{\eta}$ for the electronic Hamiltonian
(139). After the fermionic Fourier transform (140), we have

$\displaystyle\widetilde{T}$ $\displaystyle=\mathrm{FFFT}^{\dagger}\cdot
T\cdot\mathrm{FFFT}=nN_{0},$ (201) $\displaystyle\widetilde{V}$
$\displaystyle=\mathrm{FFFT}^{\dagger}\cdot
V\cdot\mathrm{FFFT}=\frac{1}{n^{2}}\sum_{j,k,l,m}\left(\sum_{x=0}^{\frac{n}{2}-1}e^{\frac{2\pi
ix(k-j)}{n}}\right)\left(\sum_{y=0}^{\frac{n}{2}-1}e^{\frac{2\pi
iy(m-l)}{n}}\right)A_{j}^{\dagger}A_{k}A_{l}^{\dagger}A_{m},$

which gives the commutator

$\left[\widetilde{T},\widetilde{V}\right]=\frac{1}{n}\sum_{k,l,m}H_{0klm}-\frac{1}{n}\sum_{j,l,m}H_{j0lm}+\frac{1}{n}\sum_{j,k,m}H_{jk0m}-\frac{1}{n}\sum_{j,k,l}H_{jkl0}$
(202)

with

$H_{jklm}=\tau_{jklm}A_{j}^{\dagger}A_{k}A_{l}^{\dagger}A_{m},\qquad\tau_{jklm}=\left(\sum_{x=0}^{\frac{n}{2}-1}e^{\frac{2\pi
ix(k-j)}{n}}\right)\left(\sum_{y=0}^{\frac{n}{2}-1}e^{\frac{2\pi
iy(m-l)}{n}}\right).$ (203)

For $\eta\leq\frac{n}{2}$, we will choose the initial state from the two-
dimensional subspace spanned by

$\lvert\widetilde{\psi}_{0}\rangle=\lvert 010\cdots 0\overbrace{1\cdots
1}^{\eta-1}\rangle,\qquad\lvert\widetilde{\psi}_{1}\rangle=\lvert 100\cdots
0\overbrace{1\cdots 1}^{\eta-1}\rangle.$ (204)

Denoting the projection to this subspace as
$\widetilde{\Pi}=\lvert\widetilde{\psi}_{0}\rangle\langle\widetilde{\psi}_{0}\rvert+\lvert\widetilde{\psi}_{1}\rangle\langle\widetilde{\psi}_{1}\rvert$,
we have that $\widetilde{\Pi}$ commutes with $\widetilde{T}=nN_{0}$, which
means
$\widetilde{\Pi}[\widetilde{T},\ldots[\widetilde{T},\widetilde{V}]]\widetilde{\Pi}=[\widetilde{T},\ldots\widetilde{\Pi}[\widetilde{T},\widetilde{V}]\widetilde{\Pi}]$.
We simplify the effective commutator
$\widetilde{\Pi}[\widetilde{T},\widetilde{V}]\widetilde{\Pi}$ based on the
following observations:

  1. 1.

$A_{0}^{\dagger}A_{k}A_{l}^{\dagger}A_{m}$: This will always nullify
$\lvert\widetilde{\psi}_{0}\rangle$ from left. For
$\langle\widetilde{\psi}_{1}\rvert
A_{0}^{\dagger}A_{k}A_{l}^{\dagger}A_{m}\lvert\widetilde{\psi}_{1}\rangle$ to
be nonzero, we must let one of $\\{k,m\\}$ be $0$, while the other is equal to
$l$. For $\langle\widetilde{\psi}_{1}\rvert
A_{0}^{\dagger}A_{k}A_{l}^{\dagger}A_{m}\lvert\widetilde{\psi}_{0}\rangle$ to
be nonzero, we must let one of $\\{k,m\\}$ be $1$, while the other is equal to
$l$.

  2. 2.

$A_{j}^{\dagger}A_{0}A_{l}^{\dagger}A_{m}$: For
$\langle\widetilde{\psi}_{0}\rvert
A_{j}^{\dagger}A_{0}A_{l}^{\dagger}A_{m}\lvert\widetilde{\psi}_{0}\rangle$ to
be nonzero, we must let $l=0$ and $j=m$. For
$\langle\widetilde{\psi}_{0}\rvert
A_{j}^{\dagger}A_{0}A_{l}^{\dagger}A_{m}\lvert\widetilde{\psi}_{1}\rangle$ to
be nonzero, we must let one of $\\{j,l\\}$ be $1$, while the other is equal to
$m$. For $\langle\widetilde{\psi}_{1}\rvert
A_{j}^{\dagger}A_{0}A_{l}^{\dagger}A_{m}\lvert\widetilde{\psi}_{1}\rangle$ to
be nonzero, we must let $j=0$ and $l=m$. For
$\langle\widetilde{\psi}_{1}\rvert
A_{j}^{\dagger}A_{0}A_{l}^{\dagger}A_{m}\lvert\widetilde{\psi}_{0}\rangle$ to
be nonzero, we must let $j=0$, $l=0$ and $m=1$.

  3. 3.

$A_{j}^{\dagger}A_{k}A_{0}^{\dagger}A_{m}$: For
$\langle\widetilde{\psi}_{0}\rvert
A_{j}^{\dagger}A_{k}A_{0}^{\dagger}A_{m}\lvert\widetilde{\psi}_{0}\rangle$ to
be nonzero, we must let $k=0$ and $j=m$. For
$\langle\widetilde{\psi}_{1}\rvert
A_{j}^{\dagger}A_{k}A_{0}^{\dagger}A_{m}\lvert\widetilde{\psi}_{0}\rangle$ to
be nonzero, we must let one of $\\{k,m\\}$ be $1$, while the other is equal to
$j$. For $\langle\widetilde{\psi}_{1}\rvert
A_{j}^{\dagger}A_{k}A_{0}^{\dagger}A_{m}\lvert\widetilde{\psi}_{1}\rangle$ to
be nonzero, we must let $m=0$ and $j=k$. For
$\langle\widetilde{\psi}_{0}\rvert
A_{j}^{\dagger}A_{k}A_{0}^{\dagger}A_{m}\lvert\widetilde{\psi}_{1}\rangle$ to
be nonzero, we must let $m=0$, $k=0$ and $j=1$.

  4. 4.

$A_{j}^{\dagger}A_{k}A_{l}^{\dagger}A_{0}$: This will always nullify
$\lvert\widetilde{\psi}_{0}\rangle$ from right. For
$\langle\widetilde{\psi}_{1}\rvert
A_{j}^{\dagger}A_{k}A_{l}^{\dagger}A_{0}\lvert\widetilde{\psi}_{1}\rangle$ to
be nonzero, we must let one of $\\{j,l\\}$ be $0$, while the other is equal to
$k$. For $\langle\widetilde{\psi}_{0}\rvert
A_{j}^{\dagger}A_{k}A_{l}^{\dagger}A_{0}\lvert\widetilde{\psi}_{1}\rangle$ to
be nonzero, we must let one of $\\{j,l\\}$ be $1$, while the other is equal to
$k$.

After removing double-counting and canceling redundant terms, we obtain

$\displaystyle\widetilde{\Pi}\left[\widetilde{T},\widetilde{V}\right]\widetilde{\Pi}$
$\displaystyle=\cancel{\frac{1}{n}\sum_{l}H_{00ll}}+\frac{1}{n}\sum_{l}H_{01ll}\cancel{+\frac{1}{n}\sum_{k}H_{0kk0}}+\frac{1}{n}\sum_{k}H_{0kk1}$
(205) $\displaystyle\quad\cancel{-\frac{1}{n}H_{0000}}-\frac{1}{n}H_{0111}$
$\displaystyle\quad\cancel{-\frac{1}{n}\sum_{j}H_{j00j}}-\frac{1}{n}\sum_{l}H_{10ll}-\frac{1}{n}\sum_{j}H_{j01j}\cancel{-\frac{1}{n}\sum_{l}H_{00ll}}-\frac{1}{n}H_{0001}$
$\displaystyle\quad\cancel{+\frac{1}{n}H_{0000}}\underbrace{+\frac{1}{n}H_{1011}}_{0}$
$\displaystyle\quad\cancel{+\frac{1}{n}\sum_{j}H_{j00j}}+\frac{1}{n}\sum_{j}H_{jj01}+\frac{1}{n}\sum_{j}H_{j10j}\cancel{+\frac{1}{n}\sum_{j}H_{jj00}}+\frac{1}{n}H_{1000}$
$\displaystyle\quad\cancel{-\frac{1}{n}H_{0000}}\underbrace{-\frac{1}{n}H_{1101}}_{0}$
$\displaystyle\quad\cancel{-\frac{1}{n}\sum_{j}H_{jj00}}-\frac{1}{n}\sum_{j}H_{jj10}\cancel{-\frac{1}{n}\sum_{k}H_{0kk0}}-\frac{1}{n}\sum_{k}H_{1kk0}$
$\displaystyle\quad\cancel{+\frac{1}{n}H_{0000}}+\frac{1}{n}H_{1110}.$

We merge the remaining twelve terms into four groups:

  1. 1.

The first group contains terms

$\displaystyle\
\frac{1}{n}\sum_{l}H_{01ll}-\frac{1}{n}\sum_{l}H_{10ll}+\frac{1}{n}\sum_{j}H_{jj01}-\frac{1}{n}\sum_{j}H_{jj10}$
(206) $\displaystyle=$ $\displaystyle\
\frac{1}{n}\sum_{l}\tau_{01ll}A_{0}^{\dagger}A_{1}A_{l}^{\dagger}A_{l}-\frac{1}{n}\sum_{l}\tau_{10ll}A_{1}^{\dagger}A_{0}A_{l}^{\dagger}A_{l}+\frac{1}{n}\sum_{j}\tau_{jj01}A_{j}^{\dagger}A_{j}A_{0}^{\dagger}A_{1}-\frac{1}{n}\sum_{j}\tau_{jj10}A_{j}^{\dagger}A_{j}A_{1}^{\dagger}A_{0}$
$\displaystyle=$ $\displaystyle\
N\left(\sum_{x=0}^{\frac{n}{2}-1}e^{\frac{2\pi
ix}{n}}\right)A_{0}^{\dagger}A_{1}-N\left(\sum_{x=0}^{\frac{n}{2}-1}e^{-\frac{2\pi
ix}{n}}\right)A_{1}^{\dagger}A_{0}.$

We will see that this is the dominant contribution to the effective commutator
that is at least $\Omega\left(n\eta\right)$.

  2. 2.

The second group contains terms

$\displaystyle-\frac{1}{n}H_{0111}-\frac{1}{n}H_{0001}+\frac{1}{n}H_{1000}+\frac{1}{n}H_{1110}$
(207) $\displaystyle=$
$\displaystyle-\frac{1}{n}\tau_{0111}A_{0}^{\dagger}A_{1}A_{1}^{\dagger}A_{1}-\frac{1}{n}\tau_{0001}A_{0}^{\dagger}A_{0}A_{0}^{\dagger}A_{1}+\frac{1}{n}\tau_{1000}A_{1}^{\dagger}A_{0}A_{0}^{\dagger}A_{0}+\frac{1}{n}\tau_{1110}A_{1}^{\dagger}A_{1}A_{1}^{\dagger}A_{0}$
$\displaystyle=$ $\displaystyle-\left(\sum_{x=0}^{\frac{n}{2}-1}e^{\frac{2\pi
ix}{n}}\right)A_{0}^{\dagger}A_{1}+\left(\sum_{x=0}^{\frac{n}{2}-1}e^{-\frac{2\pi
ix}{n}}\right)A_{1}^{\dagger}A_{0}=\mathcal{O}\left(n\right),$

which does not dominate the result scaling.

  3. 3.

The third group contains terms

$\displaystyle\frac{1}{n}\sum_{k}H_{0kk1}-\frac{1}{n}\sum_{k}H_{1kk0}$
$\displaystyle=\frac{1}{n}\sum_{k}\tau_{0kk1}A_{0}^{\dagger}A_{k}A_{k}^{\dagger}A_{1}-\frac{1}{n}\sum_{k}\tau_{1kk0}A_{1}^{\dagger}A_{k}A_{k}^{\dagger}A_{0}$
(208)
$\displaystyle=\frac{1}{n}\tau_{0001}A_{0}^{\dagger}A_{1}+\frac{1}{n}\sum_{k}\tau_{0kk1}A_{k}A_{k}^{\dagger}A_{0}^{\dagger}A_{1}$
$\displaystyle\quad-\frac{1}{n}\tau_{1110}A_{1}^{\dagger}A_{0}-\frac{1}{n}\sum_{k}\tau_{1kk0}A_{k}A_{k}^{\dagger}A_{1}^{\dagger}A_{0}$
$\displaystyle=\frac{1}{n}\tau_{0001}A_{0}^{\dagger}A_{1}+\frac{1}{n}\sum_{k}\tau_{0kk1}A_{0}^{\dagger}A_{1}-\frac{1}{n}\sum_{k}\tau_{0kk1}A_{k}^{\dagger}A_{k}A_{0}^{\dagger}A_{1}$
$\displaystyle\quad-\frac{1}{n}\tau_{1110}A_{1}^{\dagger}A_{0}-\frac{1}{n}\sum_{k}\tau_{1kk0}A_{1}^{\dagger}A_{0}+\frac{1}{n}\sum_{k}\tau_{1kk0}A_{k}^{\dagger}A_{k}A_{1}^{\dagger}A_{0},$

where

$\displaystyle\frac{1}{n}\tau_{0001}A_{0}^{\dagger}A_{1}-\frac{1}{n}\tau_{1110}A_{1}^{\dagger}A_{0}=\frac{1}{2}\left(\sum_{x=0}^{\frac{n}{2}-1}e^{\frac{2\pi
ix}{n}}\right)A_{0}^{\dagger}A_{1}-\frac{1}{2}\left(\sum_{x=0}^{\frac{n}{2}-1}e^{-\frac{2\pi
ix}{n}}\right)A_{1}^{\dagger}A_{0}=\mathcal{O}\left(n\right),$ (209)

and

$\displaystyle\
\frac{1}{n}\sum_{k}\tau_{0kk1}A_{0}^{\dagger}A_{1}-\frac{1}{n}\sum_{k}\tau_{1kk0}A_{1}^{\dagger}A_{0}$
(210) $\displaystyle=$ $\displaystyle\
\frac{1}{n}\sum_{k}\left(\sum_{x=0}^{\frac{n}{2}-1}e^{\frac{2\pi
ixk}{n}}\sum_{y=0}^{\frac{n}{2}-1}e^{\frac{2\pi
iy(1-k)}{n}}\right)A_{0}^{\dagger}A_{1}-\frac{1}{n}\sum_{k}\left(\sum_{x=0}^{\frac{n}{2}-1}e^{\frac{2\pi
ix(k-1)}{n}}\sum_{y=0}^{\frac{n}{2}-1}e^{-\frac{2\pi
iyk}{n}}\right)A_{1}^{\dagger}A_{0}$ $\displaystyle=$ $\displaystyle\
\left(\sum_{x=0}^{\frac{n}{2}-1}e^{\frac{2\pi
ix}{n}}\right)A_{0}^{\dagger}A_{1}-\left(\sum_{x=0}^{\frac{n}{2}-1}e^{-\frac{2\pi
ix}{n}}\right)A_{1}^{\dagger}A_{0}=\mathcal{O}\left(n\right).$

We rewrite the remaining terms as

$\displaystyle-\frac{1}{n}\sum_{k}\tau_{0kk1}A_{k}^{\dagger}A_{k}A_{0}^{\dagger}A_{1}+\frac{1}{n}\sum_{k}\tau_{1kk0}A_{k}^{\dagger}A_{k}A_{1}^{\dagger}A_{0}$
(211) $\displaystyle=$
$\displaystyle-\frac{1}{n}\sum_{k}\left(\sum_{x=0}^{\frac{n}{2}-1}e^{\frac{2\pi
ixk}{n}}\sum_{y=0}^{\frac{n}{2}-1}e^{\frac{2\pi
iy(1-k)}{n}}\right)A_{k}^{\dagger}A_{k}A_{0}^{\dagger}A_{1}$ $\displaystyle\
+\frac{1}{n}\sum_{k}\left(\sum_{x=0}^{\frac{n}{2}-1}e^{\frac{2\pi
ix(k-1)}{n}}\sum_{y=0}^{\frac{n}{2}-1}e^{-\frac{2\pi
iyk}{n}}\right)A_{k}^{\dagger}A_{k}A_{1}^{\dagger}A_{0}.$

  4. 4.

The fourth group contains terms

$\displaystyle-\frac{1}{n}\sum_{j}H_{j01j}+\frac{1}{n}\sum_{j}H_{j10j}$ (212)
$\displaystyle=$
$\displaystyle-\frac{1}{n}\sum_{j}\tau_{j01j}A_{j}^{\dagger}A_{0}A_{1}^{\dagger}A_{j}+\frac{1}{n}\sum_{j}\tau_{j10j}A_{j}^{\dagger}A_{1}A_{0}^{\dagger}A_{j}$
$\displaystyle=$
$\displaystyle-\frac{1}{n}\tau_{1011}A_{1}^{\dagger}A_{0}+\frac{1}{n}\sum_{j}\tau_{j01j}A_{j}^{\dagger}A_{j}A_{1}^{\dagger}A_{0}+\frac{1}{n}\tau_{0100}A_{0}^{\dagger}A_{1}-\frac{1}{n}\sum_{j}\tau_{j10j}A_{j}^{\dagger}A_{j}A_{0}^{\dagger}A_{1}.$

Similar to the previous case, we have

$-\frac{1}{n}\tau_{1011}A_{1}^{\dagger}A_{0}+\frac{1}{n}\tau_{0100}A_{0}^{\dagger}A_{1}=\mathcal{O}\left(n\right),$
(213)

whereas the remaining terms can be rewritten as

$\displaystyle\
\frac{1}{n}\sum_{j}\tau_{j01j}A_{j}^{\dagger}A_{j}A_{1}^{\dagger}A_{0}-\frac{1}{n}\sum_{j}\tau_{j10j}A_{j}^{\dagger}A_{j}A_{0}^{\dagger}A_{1}$
(214) $\displaystyle=$ $\displaystyle\
\frac{1}{n}\sum_{j}\left(\sum_{x=0}^{\frac{n}{2}-1}e^{-\frac{2\pi
ixj}{n}}\sum_{y=0}^{\frac{n}{2}-1}e^{\frac{2\pi
iy(j-1)}{n}}\right)A_{j}^{\dagger}A_{j}A_{1}^{\dagger}A_{0}$ $\displaystyle\
-\frac{1}{n}\sum_{j}\left(\sum_{x=0}^{\frac{n}{2}-1}e^{\frac{2\pi
ix(1-j)}{n}}\sum_{y=0}^{\frac{n}{2}-1}e^{\frac{2\pi
iyj}{n}}\right)A_{j}^{\dagger}A_{j}A_{0}^{\dagger}A_{1}.$

To summarize, the effective commutator
$\widetilde{\Pi}\left[\widetilde{T},\widetilde{V}\right]\widetilde{\Pi}$ has
action

$\displaystyle\widetilde{\Pi}\left[\widetilde{T},\widetilde{V}\right]\widetilde{\Pi}=$
$\displaystyle\ N\left(\sum_{x=0}^{\frac{n}{2}-1}e^{\frac{2\pi
ix}{n}}\right)A_{0}^{\dagger}A_{1}-N\left(\sum_{x=0}^{\frac{n}{2}-1}e^{-\frac{2\pi
ix}{n}}\right)A_{1}^{\dagger}A_{0}$ (215) $\displaystyle\
-\frac{2}{n}\sum_{k}\left(\sum_{x=0}^{\frac{n}{2}-1}e^{\frac{2\pi
ixk}{n}}\sum_{y=0}^{\frac{n}{2}-1}e^{\frac{2\pi
iy(1-k)}{n}}\right)A_{k}^{\dagger}A_{k}A_{0}^{\dagger}A_{1}$ $\displaystyle\
+\frac{2}{n}\sum_{k}\left(\sum_{x=0}^{\frac{n}{2}-1}e^{\frac{2\pi
ix(k-1)}{n}}\sum_{y=0}^{\frac{n}{2}-1}e^{-\frac{2\pi
iyk}{n}}\right)A_{k}^{\dagger}A_{k}A_{1}^{\dagger}A_{0}+\mathcal{O}\left(n\right).$

We now take the expectation of this operator with respect to the state

$\lvert\widetilde{\psi}_{\eta}\rangle=\frac{\lvert 010\cdots
0\overbrace{1\cdots 1}^{\eta-1}\rangle+\lvert 100\cdots 0\overbrace{1\cdots
1}^{\eta-1}\rangle}{\sqrt{2}}.$ (216)

Using the limit

$\lim\limits_{z\rightarrow 0}\left(\frac{2}{1-e^{2\pi iz}}+\frac{1}{\pi
iz}\right)=1=\lim\limits_{z\rightarrow 0}\left(-\frac{2}{1-e^{-2\pi
iz}}+\frac{1}{\pi iz}\right),$ (217)

we have

$\displaystyle\
\langle\widetilde{\psi}_{\eta}\rvert\left(N\left(\sum_{x=0}^{\frac{n}{2}-1}e^{\frac{2\pi
ix}{n}}\right)A_{0}^{\dagger}A_{1}-N\left(\sum_{x=0}^{\frac{n}{2}-1}e^{-\frac{2\pi
ix}{n}}\right)A_{1}^{\dagger}A_{0}\right)\lvert\widetilde{\psi}_{\eta}\rangle$
(218) $\displaystyle=$ $\displaystyle\
\eta\langle\widetilde{\psi}_{\eta}\rvert\left(\frac{2}{1-e^{\frac{2\pi
i}{n}}}A_{0}^{\dagger}A_{1}-\frac{2}{1-e^{-\frac{2\pi
i}{n}}}A_{1}^{\dagger}A_{0}\right)\lvert\widetilde{\psi}_{\eta}\rangle$
$\displaystyle=$ $\displaystyle-\frac{n\eta}{\pi
i}\langle\widetilde{\psi}_{\eta}\rvert\left(A_{0}^{\dagger}A_{1}+A_{1}^{\dagger}A_{0}\right)\lvert\widetilde{\psi}_{\eta}\rangle+\mathcal{O}\left(\eta\right)=-\frac{n\eta}{\pi
i}+\mathcal{O}\left(\eta\right).$

On the other hand,

$\displaystyle\frac{1}{n}\langle\widetilde{\psi}_{\eta}\rvert\left(-\sum_{k}\left(\sum_{x=0}^{\frac{n}{2}-1}e^{\frac{2\pi
ixk}{n}}\sum_{y=0}^{\frac{n}{2}-1}e^{\frac{2\pi
iy(1-k)}{n}}\right)A_{k}^{\dagger}A_{k}A_{0}^{\dagger}A_{1}+\sum_{k}\left(\sum_{x=0}^{\frac{n}{2}-1}e^{\frac{2\pi
ix(k-1)}{n}}\sum_{y=0}^{\frac{n}{2}-1}e^{-\frac{2\pi
iyk}{n}}\right)A_{k}^{\dagger}A_{k}A_{1}^{\dagger}A_{0}\right)\lvert\widetilde{\psi}_{\eta}\rangle$
(219) $\displaystyle=$
$\displaystyle\frac{1}{n}\langle\widetilde{\psi}_{\eta}\rvert\left(-\sum_{k=n-\eta+1}^{n-1}\frac{1-e^{\pi
ik}}{1-e^{\frac{2\pi ik}{n}}}\frac{1-e^{\pi i(1-k)}}{1-e^{\frac{2\pi
i(1-k)}{n}}}A_{0}^{\dagger}A_{1}+\sum_{k=n-\eta+1}^{n-1}\frac{1-e^{\pi
i(k-1)}}{1-e^{\frac{2\pi i(k-1)}{n}}}\frac{1-e^{-\pi ik}}{1-e^{-\frac{2\pi
ik}{n}}}A_{1}^{\dagger}A_{0}\right)\lvert\widetilde{\psi}_{\eta}\rangle+\mathcal{O}\left(n\right)=\mathcal{O}\left(n\right),$

where the last equality holds since for integer $k$ exactly one of $k$ and
$k-1$ is even. We have thus proved

$\langle\widetilde{\psi}_{\eta}\rvert\left[\widetilde{T},\widetilde{V}\right]\lvert\widetilde{\psi}_{\eta}\rangle=-\frac{n\eta}{\pi
i}+\mathcal{O}\left(n\right).$ (220)

The above argument can be extended to analyze multilayer nested commutators.
Indeed, for initial state

$\lvert\widetilde{\phi}_{\eta}\rangle=\frac{\lvert 010\cdots
0\overbrace{1\cdots 1}^{\eta-1}\rangle+i\lvert 100\cdots 0\overbrace{1\cdots
1}^{\eta-1}\rangle}{\sqrt{2}},$ (221)

we have

$\displaystyle\langle\widetilde{\phi}_{\eta}\rvert\left[\widetilde{T},\left[\widetilde{T},\widetilde{V}\right]\right]\lvert\widetilde{\phi}_{\eta}\rangle$
$\displaystyle=-\frac{n^{2}\eta}{\pi
i}\langle\widetilde{\phi}_{\eta}\rvert\left(A_{0}^{\dagger}A_{1}-A_{1}^{\dagger}A_{0}\right)\lvert\widetilde{\phi}_{\eta}\rangle+\mathcal{O}\left(n^{2}+n\eta\right)$
(222) $\displaystyle=\frac{n^{2}\eta}{\pi}+\mathcal{O}\left(n^{2}\right),$

and similar results hold for general nested commutators
$[\widetilde{T},\ldots[\widetilde{T},\widetilde{V}]]$. This completes the
proof of Proposition 13.

For sparse interactions, we have $u,w>0$, positive integer $2\leq
d\leq\eta\leq\frac{n}{2}$ and consider the electronic Hamiltonian (146).
Similar to the above analysis, we compute the commutators by performing the
fermionic Fourier transform, but only to the first $d$ spin orbitals,
obtaining

$\displaystyle\widetilde{T}$ $\displaystyle=\mathrm{FFFT}_{d}^{\dagger}\cdot
T\cdot\mathrm{FFFT}_{d}=udN_{0},$ (223) $\displaystyle\widetilde{V}$
$\displaystyle=\mathrm{FFFT}_{d}^{\dagger}\cdot
V\cdot\mathrm{FFFT}_{d}=\frac{w}{d^{2}}\sum_{j,k,l,m=0}^{d-1}\left(\sum_{x=0}^{\frac{d}{2}-1}e^{\frac{2\pi
ix(k-j)}{d}}\right)\left(\sum_{y=0}^{\frac{d}{2}-1}e^{\frac{2\pi
iy(m-l)}{d}}\right)A_{j}^{\dagger}A_{k}A_{l}^{\dagger}A_{m}.$

We choose the initial state from the two-dimensional subspace spanned by

$\lvert\widetilde{\psi}_{0,d}\rangle=\lvert\overbrace{011\cdots 1}^{d}0\cdots
0\overbrace{1\cdots
1}^{\eta-d+1}\rangle,\qquad\lvert\widetilde{\psi}_{1,d}\rangle=\lvert\overbrace{101\cdots
1}^{d}0\cdots 0\overbrace{1\cdots 1}^{\eta-d+1}\rangle$ (224)

and denote the projection to this subspace as
$\widetilde{\Pi}_{d}=\lvert\widetilde{\psi}_{0,d}\rangle\langle\widetilde{\psi}_{0,d}\rvert+\lvert\widetilde{\psi}_{1,d}\rangle\langle\widetilde{\psi}_{1,d}\rvert$.
Then, the effective commutator
$\widetilde{\Pi}_{d}\left[\widetilde{T},\widetilde{V}\right]\widetilde{\Pi}_{d}$
has action

$\displaystyle\widetilde{\Pi}_{d}\left[\widetilde{T},\widetilde{V}\right]\widetilde{\Pi}_{d}=$
$\displaystyle\
uw\sum_{j=0}^{d-1}N_{j}\left(\sum_{x=0}^{\frac{d}{2}-1}e^{\frac{2\pi
ix}{d}}\right)A_{0}^{\dagger}A_{1}-\sum_{j=0}^{d-1}N_{j}\left(\sum_{x=0}^{\frac{d}{2}-1}e^{-\frac{2\pi
ix}{d}}\right)A_{1}^{\dagger}A_{0}$ (225) $\displaystyle\
-\frac{2uw}{d}\sum_{k=0}^{d-1}\left(\sum_{x=0}^{\frac{d}{2}-1}e^{\frac{2\pi
ixk}{d}}\sum_{y=0}^{\frac{d}{2}-1}e^{\frac{2\pi
iy(1-k)}{d}}\right)A_{k}^{\dagger}A_{k}A_{0}^{\dagger}A_{1}$ $\displaystyle\
+\frac{2uw}{d}\sum_{k=0}^{d-1}\left(\sum_{x=0}^{\frac{d}{2}-1}e^{\frac{2\pi
ix(k-1)}{d}}\sum_{y=0}^{\frac{d}{2}-1}e^{-\frac{2\pi
iyk}{d}}\right)A_{k}^{\dagger}A_{k}A_{1}^{\dagger}A_{0}+\mathcal{O}\left(uwd\right).$

We then define the state

$\lvert\widetilde{\psi}_{\eta,d}\rangle=\frac{\lvert\overbrace{011\cdots
1}^{d}0\cdots 0\overbrace{1\cdots
1}^{\eta-d+1}\rangle+\lvert\overbrace{101\cdots 1}^{d}0\cdots
0\overbrace{1\cdots 1}^{\eta-d+1}\rangle}{\sqrt{2}},$ (226)

so that

$\langle\widetilde{\psi}_{\eta,d}\rvert\left[\widetilde{T},\widetilde{V}\right]\lvert\widetilde{\psi}_{\eta,d}\rangle=-\frac{uwd^{2}}{\pi
i}+\mathcal{O}\left(uwd\right).$ (227)

The calculation can be extended to multilayer nested commutators, using either
$\lvert\widetilde{\psi}_{\eta,d}\rangle$ or

$\lvert\widetilde{\phi}_{\eta,d}\rangle=\frac{\lvert\overbrace{011\cdots
1}^{d}0\cdots 0\overbrace{1\cdots
1}^{\eta-d+1}\rangle+i\lvert\overbrace{101\cdots 1}^{d}0\cdots
0\overbrace{1\cdots 1}^{\eta-d+1}\rangle}{\sqrt{2}}$ (228)

as the initial state.

##  Appendix D Lower-bounding $\left\lVert[V,\ldots[V,T]]\right\rVert_{\eta}$

In this appendix, we prove Proposition 14 that lower-bounds
$\left\lVert[V,\ldots[V,T]]\right\rVert_{\eta}$ for the electronic Hamiltonian
(139). Recall that we have $H=T+V$ with

$T=\sum_{j,k=0}^{n-1}A_{j}^{\dagger}A_{k},\qquad
V=\sum_{x,y=0}^{\frac{n}{2}-1}N_{x}N_{y},$ (229)

which implies the commutator

$[V,T]=\sum_{x=0}^{\frac{n}{2}-1}N_{x}\bigg{(}\sum_{\begin{subarray}{c}0\leq
j\leq\frac{n}{2}-1\\\ \frac{n}{2}\leq k\leq
n-1\end{subarray}}-\sum_{\begin{subarray}{c}\frac{n}{2}\leq j\leq n-1\\\ 0\leq
k\leq\frac{n}{2}-1\end{subarray}}\bigg{)}A_{j}^{\dagger}A_{k}+\bigg{(}\sum_{\begin{subarray}{c}0\leq
j\leq\frac{n}{2}-1\\\ \frac{n}{2}\leq k\leq
n-1\end{subarray}}-\sum_{\begin{subarray}{c}\frac{n}{2}\leq j\leq n-1\\\ 0\leq
k\leq\frac{n}{2}-1\end{subarray}}\bigg{)}A_{j}^{\dagger}A_{k}\sum_{y=0}^{\frac{n}{2}-1}N_{y}.$
(230)

For $\eta\leq\frac{n}{2}$, we will choose the initial state from the two-
dimensional subspace spanned by

$\lvert{\psi}_{0}\rangle=\lvert\overbrace{0\underbrace{1\cdots
1}_{\eta-1}0\cdots 0}^{\frac{n}{2}}10\cdots
0\rangle,\qquad\lvert{\psi}_{1}\rangle=\lvert\overbrace{1\underbrace{1\cdots
1}_{\eta-1}0\cdots 0}^{\frac{n}{2}}00\cdots 0\rangle.$ (231)

Denoting the projection to this subspace as
${\Pi}=\lvert{\psi}_{0}\rangle\langle{\psi}_{0}\rvert+\lvert{\psi}_{1}\rangle\langle{\psi}_{1}\rvert$,
we have that ${\Pi}$ commutes with $\sum_{0\leq x\leq\frac{n}{2}-1}N_{x}$.
Meanwhile,

$\Pi\bigg{(}\sum_{\begin{subarray}{c}0\leq j\leq\frac{n}{2}-1\\\
\frac{n}{2}\leq k\leq
n-1\end{subarray}}-\sum_{\begin{subarray}{c}\frac{n}{2}\leq j\leq n-1\\\ 0\leq
k\leq\frac{n}{2}-1\end{subarray}}\bigg{)}A_{j}^{\dagger}A_{k}\Pi=A_{0}^{\dagger}A_{\frac{n}{2}}-A_{\frac{n}{2}}^{\dagger}A_{0}.$
(232)

This shows that the effective commutator $\Pi[V,T]\Pi$ has the action

$\Pi[V,T]\Pi=\sum_{x=0}^{\frac{n}{2}-1}N_{x}\left(A_{0}^{\dagger}A_{\frac{n}{2}}-A_{\frac{n}{2}}^{\dagger}A_{0}\right)+\left(A_{0}^{\dagger}A_{\frac{n}{2}}-A_{\frac{n}{2}}^{\dagger}A_{0}\right)\sum_{y=0}^{\frac{n}{2}-1}N_{y}.$
(233)

We now take the expectation of this operator with respect to the state

$\lvert\psi_{\eta}\rangle=\frac{\lvert\overbrace{0\underbrace{1\cdots
1}_{\eta-1}0\cdots 0}^{\frac{n}{2}}10\cdots
0\rangle+i\lvert\overbrace{1\underbrace{1\cdots 1}_{\eta-1}0\cdots
0}^{\frac{n}{2}}00\cdots 0\rangle}{\sqrt{2}},$ (234)

which gives

$\displaystyle\langle\psi_{\eta}\rvert[V,T]\lvert\psi_{\eta}\rangle$
$\displaystyle=\langle\psi_{\eta}\rvert\left(\sum_{x=0}^{\frac{n}{2}-1}N_{x}\left(A_{0}^{\dagger}A_{\frac{n}{2}}-A_{\frac{n}{2}}^{\dagger}A_{0}\right)+\left(A_{0}^{\dagger}A_{\frac{n}{2}}-A_{\frac{n}{2}}^{\dagger}A_{0}\right)\sum_{y=0}^{\frac{n}{2}-1}N_{y}\right)\lvert\psi_{\eta}\rangle$
(235)
$\displaystyle=2\eta\langle\psi_{\eta}\rvert\left(A_{0}^{\dagger}A_{\frac{n}{2}}-A_{\frac{n}{2}}^{\dagger}A_{0}\right)\lvert\psi_{\eta}\rangle+\mathcal{O}\left(1\right)=(-1)^{\eta}2i\eta+\mathcal{O}\left(1\right).$

This proves the desired scaling for the single-layer commutator. This argument
can be extended to analyze multilayer nested commutators. Indeed, for initial
state

$\lvert\phi_{\eta}\rangle=\frac{\lvert\overbrace{0\underbrace{1\cdots
1}_{\eta-1}0\cdots 0}^{\frac{n}{2}}10\cdots
0\rangle+\lvert\overbrace{1\underbrace{1\cdots 1}_{\eta-1}0\cdots
0}^{\frac{n}{2}}00\cdots 0\rangle}{\sqrt{2}},$ (236)

we have

$\displaystyle\langle\phi_{\eta}\rvert[V,[V,T]]\lvert\phi_{\eta}\rangle$
$\displaystyle=\langle\phi_{\eta}\rvert\left(\sum_{x=0}^{\frac{n}{2}-1}N_{x}\right)^{2}\left(A_{0}^{\dagger}A_{\frac{n}{2}}+A_{\frac{n}{2}}^{\dagger}A_{0}\right)\lvert\phi_{\eta}\rangle$
(237)
$\displaystyle\quad+2\langle\phi_{\eta}\rvert\left(\sum_{x=0}^{\frac{n}{2}-1}N_{x}\right)\left(A_{0}^{\dagger}A_{\frac{n}{2}}+A_{\frac{n}{2}}^{\dagger}A_{0}\right)\left(\sum_{y=0}^{\frac{n}{2}-1}N_{y}\right)\lvert\phi_{\eta}\rangle$
$\displaystyle\quad+\langle\phi_{\eta}\rvert\left(A_{0}^{\dagger}A_{\frac{n}{2}}+A_{\frac{n}{2}}^{\dagger}A_{0}\right)\left(\sum_{y=0}^{\frac{n}{2}-1}N_{y}\right)^{2}\lvert\phi_{\eta}\rangle=(-1)^{\eta-1}4\eta^{2}+\mathcal{O}\left(\eta\right),$

and similar results hold for general nested commutators
$[{V},\ldots[{V},{T}]]$. This completes the proof of Proposition 14.

For sparse interactions, we have $u,w>0$, positive integer $2\leq
d\leq\eta\leq\frac{n}{2}$ and consider the electronic Hamiltonian (146).
Similar to above, we have the commutator

$[V,T]=uw\sum_{x=0}^{\frac{d}{2}-1}N_{x}\bigg{(}\sum_{\begin{subarray}{c}0\leq
j\leq\frac{d}{2}-1\\\ \frac{d}{2}\leq k\leq
d-1\end{subarray}}-\sum_{\begin{subarray}{c}\frac{d}{2}\leq j\leq d-1\\\ 0\leq
k\leq\frac{d}{2}-1\end{subarray}}\bigg{)}A_{j}^{\dagger}A_{k}+uw\bigg{(}\sum_{\begin{subarray}{c}0\leq
j\leq\frac{d}{2}-1\\\ \frac{d}{2}\leq k\leq
d-1\end{subarray}}-\sum_{\begin{subarray}{c}\frac{d}{2}\leq j\leq d-1\\\ 0\leq
k\leq\frac{d}{2}-1\end{subarray}}\bigg{)}A_{j}^{\dagger}A_{k}\sum_{y=0}^{\frac{d}{2}-1}N_{y}.$
(238)

We choose the initial state from the two-dimensional subspace spanned by

$\lvert{\psi}_{0,d}\rangle=\lvert\overbrace{\underbrace{01\cdots
1}_{\frac{d}{2}}10\cdots 0}^{d}0\cdots 0\overbrace{1\cdots
1}^{\eta-\frac{d}{2}}\rangle,\qquad\lvert{\psi}_{1,d}\rangle=\lvert\overbrace{\underbrace{11\cdots
1}_{\frac{d}{2}}00\cdots 0}^{d}0\cdots 0\overbrace{1\cdots
1}^{\eta-\frac{d}{2}}\rangle$ (239)

and denote the projection to this subspace as
${\Pi}_{d}=\lvert{\psi}_{0,d}\rangle\langle{\psi}_{0,d}\rvert+\lvert{\psi}_{1,d}\rangle\langle{\psi}_{1,d}\rvert$.
Then, the effective commutator $\Pi_{d}[V,T]\Pi_{d}$ has the action

$\Pi_{d}[V,T]\Pi_{d}=uw\sum_{x=0}^{\frac{d}{2}-1}N_{x}\left(A_{0}^{\dagger}A_{\frac{d}{2}}-A_{\frac{d}{2}}^{\dagger}A_{0}\right)+uw\left(A_{0}^{\dagger}A_{\frac{d}{2}}-A_{\frac{d}{2}}^{\dagger}A_{0}\right)\sum_{y=0}^{\frac{d}{2}-1}N_{y}.$
(240)

Choosing the initial state

$\lvert\psi_{\eta,d}\rangle=\frac{\lvert\overbrace{\underbrace{01\cdots
1}_{\frac{d}{2}}10\cdots 0}^{d}0\cdots 0\overbrace{1\cdots
1}^{\eta-\frac{d}{2}}\rangle+i\lvert\overbrace{\underbrace{11\cdots
1}_{\frac{d}{2}}00\cdots 0}^{d}0\cdots 0\overbrace{1\cdots
1}^{\eta-\frac{d}{2}}\rangle}{\sqrt{2}},$ (241)

we have

$\langle\psi_{\eta,d}\rvert[V,T]\lvert\psi_{\eta,d}\rangle=(-1)^{\frac{d}{2}}iuwd+\mathcal{O}\left(uw\right).$
(242)

The calculation can be extended to multilayer nested commutators, using either
$\lvert\psi_{\eta,d}\rangle$ or

$\lvert\phi_{\eta,d}\rangle=\frac{\lvert\overbrace{\underbrace{01\cdots
1}_{\frac{d}{2}}10\cdots 0}^{d}0\cdots 0\overbrace{1\cdots
1}^{\eta-\frac{d}{2}}\rangle+\lvert\overbrace{\underbrace{11\cdots
1}_{\frac{d}{2}}00\cdots 0}^{d}0\cdots 0\overbrace{1\cdots
1}^{\eta-\frac{d}{2}}\rangle}{\sqrt{2}},$ (243)

as the initial state.

## References

  * Aharonov and Ta-Shma [2003] Dorit Aharonov and Amnon Ta-Shma.  Adiabatic quantum state generation and statistical zero knowledge.  In _Proceedings of the 35th ACM Symposium on Theory of Computing_ , pages 20–29, 2003.  doi: 10.1145/780542.780546.  arXiv:quant-ph/0301023.
  * An and Lin [2019] Dong An and Lin Lin.  Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm, 2019.  arXiv:1909.05500.
  * An et al. [2021] Dong An, Di Fang, and Lin Lin.  Time-dependent unbounded Hamiltonian simulation with vector norm scaling.  _Quantum_ , 5:459, May 2021.  ISSN 2521-327X.  doi: 10.22331/q-2021-05-26-459.  arXiv:2012.13105.
  * Aspuru-Guzik et al. [2005] Alán Aspuru-Guzik, Anthony D. Dutoi, Peter J. Love, and Martin Head-Gordon.  Simulated quantum computation of molecular energies.  _Science_ , 309(5741):1704–1707, 2005.  doi: 10.1126/science.1113479.  arXiv:quant-ph/0604193.
  * Babbush et al. [2015] 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.  doi: 10.1103/PhysRevA.91.022311.  arXiv:1410.8159.
  * Babbush et al. [2018] 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:011044, Mar 2018.  doi: 10.1103/PhysRevX.8.011044.  arXiv:1706.00023.
  * Babbush et al. [2019] Ryan Babbush, Dominic W. Berry, Jarrod R. McClean, and Hartmut Neven.  Quantum simulation of chemistry with sublinear scaling in basis size.  _npj Quantum Information_ , 5(1):92, Nov 2019\.  ISSN 2056-6387.  doi: 10.1038/s41534-019-0199-y.  arXiv:1807.09802.
  * Bauer et al. [2020] Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet Kin Chan.  Quantum algorithms for quantum chemistry and quantum materials science.  _Chemical Reviews_ , 120(22):12685–12717, 2020\.  doi: 10.1021/acs.chemrev.9b00829.  arXiv:2001.03685.
  * Berry [2014] Dominic W. Berry.  High-order quantum algorithm for solving linear differential equations.  _Journal of Physics A: Mathematical and Theoretical_ , 47(10):105301, feb 2014.  doi: 10.1088/1751-8113/47/10/105301.  arXiv:1010.2745.
  * Berry et al. [2007] Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders.  Efficient quantum algorithms for simulating sparse Hamiltonians.  _Communications in Mathematical Physics_ , 270(2):359–371, 2007.  doi: 10.1007/s00220-006-0150-x.  arXiv:quant-ph/0508139.
  * Berry et al. [2014] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma.  Exponential improvement in precision for simulating sparse Hamiltonians.  In _Proceedings of the 46th Annual ACM Symposium on Theory of Computing_ , pages 283–292, 2014.  doi: 10.1145/2591796.2591854.  arXiv:1312.1414.
  * Berry et al. [2015a] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D. Somma.  Simulating Hamiltonian dynamics with a truncated Taylor series.  _Physical Review Letters_ , 114(9):090502, 2015a.  doi: 10.1103/PhysRevLett.114.090502.  arXiv:1412.4687.
  * Berry et al. [2015b] Dominic W. Berry, Andrew M. Childs, and Robin Kothari.  Hamiltonian simulation with nearly optimal dependence on all parameters.  In _Proceedings of the 56th IEEE Symposium on Foundations of Computer Science_ , pages 792–809, 2015b.  doi: 10.1109/FOCS.2015.54.  arXiv:1501.01715.
  * 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.  arXiv:1902.02134.
  * Brandao and Svore [2017] Fernando G. S. L. Brandao and Krysta M. Svore.  Quantum speed-ups for solving semidefinite programs.  In _Proceedings of the 58th IEEE Symposium on Foundations of Computer Science_ , pages 415–426, 2017.  doi: 10.1109/FOCS.2017.45.  arXiv:1609.05537.
  * Cade et al. [2020] Chris Cade, Lana Mineh, Ashley Montanaro, and Stasja Stanisic.  Strategies for solving the Fermi-Hubbard model on near-term quantum computers.  _Physical Review B_ , 102:235122, Dec 2020.  doi: 10.1103/PhysRevB.102.235122.  arXiv:1912.06007.
  * Cai [2020] Zhenyu Cai.  Resource estimation for quantum variational simulations of the Hubbard model.  _Physical Review Applied_ , 14:014059, Jul 2020.  doi: 10.1103/PhysRevApplied.14.014059.  arXiv:1910.02719.
  * Campbell [2019] Earl Campbell.  Random compiler for fast Hamiltonian simulation.  _Physical Review Letters_ , 123:070503, Aug 2019.  doi: 10.1103/PhysRevLett.123.070503.  arXiv:1811.08017.
  * Campbell [2020] Earl T. Campbell.  Early fault-tolerant simulations of the Hubbard model, 2020.  arXiv:2012.09238.
  * 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.  _Chemical Reviews_ , 119(19):10856–10915, 2019\.  doi: 10.1021/acs.chemrev.8b00803.  arXiv:1812.09976.
  * Chen et al. [2020] Chi-Fang Chen, Hsin-Yuan Huang, Richard Kueng, and Joel A. Tropp.  Quantum simulation via randomized product formulas: Low gate complexity with accuracy guarantees, 2020.  arXiv:2008.11751.
  * Childs and Su [2019] Andrew M. Childs and Yuan Su.  Nearly optimal lattice simulation by product formulas.  _Physical Review Letters_ , 123:050503, Aug 2019.  doi: 10.1103/PhysRevLett.123.050503.  arXiv:1901.00564.
  * Childs et al. [2003] Andrew M. Childs, Richard Cleve, Enrico Deotto, Edward Farhi, Sam Gutmann, and Daniel A. Spielman.  Exponential algorithmic speedup by quantum walk.  In _Proceedings of the 35th ACM Symposium on Theory of Computing_ , pages 59–68, 2003.  doi: 10.1145/780542.780552.  arXiv:quant-ph/0209131.
  * Childs et al. [2018] 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.  doi: 10.1073/pnas.1801723115.  arXiv:0905.0887.
  * Childs et al. [2019a] Andrew M. Childs, Aaron Ostrander, and Yuan Su.  Faster quantum simulation by randomization.  _Quantum_ , 3:182, September 2019a.  ISSN 2521-327X.  doi: 10.22331/q-2019-09-02-182.  arXiv:1805.08385.
  * Childs et al. [2019b] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu.  A theory of Trotter error, 2019b.  arXiv:1912.08854.
  * Childs et al. [2021] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu.  Theory of Trotter error with commutator scaling.  _Physical Review X_ , 11:011020, Feb 2021.  doi: 10.1103/PhysRevX.11.011020.
  * Clinton et al. [2020] Laura Clinton, Johannes Bausch, and Toby Cubitt.  Hamiltonian simulation algorithms for near-term quantum hardware, 2020\.  arXiv:2003.06886.
  * Ferris [2014] Andrew J. Ferris.  Fourier transform for fermionic systems and the spectral tensor network.  _Physical Review Letters_ , 113:010401, Jul 2014.  doi: 10.1103/PhysRevLett.113.010401.  arXiv:1310.7605.
  * Feynman [1982] Richard P. Feynman.  Simulating physics with computers.  _International Journal of Theoretical Physics_ , 21(6-7):467–488, 1982.  doi: 10.1007/BF02650179.
  * Gharibyan et al. [2020] Hrant Gharibyan, Masanori Hanada, Masazumi Honda, and Junyu Liu.  Toward simulating superstring/M-theory on a quantum computer, 2020.  arXiv:2011.06573.
  * Gilyén et al. [2019] 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.  ISBN 978-1-4503-6705-9.  doi: 10.1145/3313276.3316366.  arXiv:1806.01838.
  * Haah et al. [2018] Jeongwan Haah, Matthew B. Hastings, Robin Kothari, and Guang Hao Low.  Quantum algorithm for simulating real time evolution of lattice Hamiltonians.  In _Proceedings of the 59th IEEE Symposium on Foundations of Computer Science_ , pages 350–360, 2018.  doi: 10.1109/FOCS.2018.00041.  arXiv:1801.03922.
  * Hadfield and Papageorgiou [2018] Stuart Hadfield and Anargyros Papageorgiou.  Divide and conquer approach to quantum Hamiltonian simulation.  _New Journal of Physics_ , 20(4):043003, 2018\.  doi: 10.1088/1367-2630/aab1ef.
  * Halimeh et al. [2020] Jad C. Halimeh, Haifeng Lang, Julius Mildenberger, Zhang Jiang, and Philipp Hauke.  Gauge-symmetry protection using single-body terms, 2020.  arXiv:2007.00668.
  * Harrow et al. [2009] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd.  Quantum algorithm for linear systems of equations.  _Physical Review Letters_ , 103(15):150502, 2009\.  doi: 10.1103/PhysRevLett.103.150502.  arXiv:0811.3171.
  * Helgaker et al. [2013] Trygve Helgaker, Poul Jørgensen, and Jeppe Olsen.  _Molecular electronic-structure theory_.  John Wiley & Sons, 2013.  doi: 10.1002/9781119019572.
  * Horn and Johnson [2012] Roger A. Horn and Charles R. Johnson.  _Matrix analysis_.  Cambridge university press, 2012.  doi: 10.1017/CBO9781139020411.
  * Jordan et al. [2012] Stephen P. Jordan, Keith S. M. Lee, and John Preskill.  Quantum algorithms for quantum field theories.  _Science_ , 336(6085):1130–1133, 2012.  doi: 10.1126/science.1217069.  arXiv:1111.3633.
  * Jordan et al. [2014] Stephen P. Jordan, Keith S. M. Lee, and John Preskill.  Quantum algorithms for fermionic quantum field theories, 2014.  arXiv:1404.7115.
  * Kivlichan et al. [2018] Ian D. Kivlichan, Jarrod McClean, Nathan Wiebe, Craig Gidney, Alán Aspuru-Guzik, Garnet Kin-Lic Chan, and Ryan Babbush.  Quantum simulation of electronic structure with linear depth and connectivity.  _Physical Review Letters_ , 120(11):110501, 2018\.  doi: 10.1103/PhysRevLett.120.110501.  arXiv:1711.04789.
  * Kivlichan et al. [2020] Ian D. Kivlichan, Craig Gidney, Dominic W. Berry, Nathan Wiebe, Jarrod McClean, Wei Sun, Zhang Jiang, Nicholas Rubin, Austin Fowler, Alán Aspuru-Guzik, Hartmut Neven, and Ryan Babbush.  Improved fault-tolerant quantum simulation of condensed-phase correlated electrons via Trotterization.  _Quantum_ , 4:296, 2020.  doi: 10.22331/q-2020-07-16-296.  arXiv:1902.10673.
  * Kuwahara et al. [2021] Tomotaka Kuwahara, Álvaro M. Alhambra, and Anurag Anshu.  Improved thermal area law and quasilinear time algorithm for quantum Gibbs states.  _Physical Review X_ , 11:011047, Mar 2021.  doi: 10.1103/PhysRevX.11.011047.  arXiv:2007.11174.
  * LeBlanc et al. [2015] J. P. F. LeBlanc, Andrey E. Antipov, Federico Becca, Ireneusz W. Bulik, Garnet Kin-Lic Chan, Chia-Min Chung, Youjin Deng, Michel Ferrero, Thomas M. Henderson, Carlos A. Jiménez-Hoyos, E. Kozik, Xuan-Wen Liu, Andrew J. Millis, N. V. Prokof’ev, Mingpu Qin, Gustavo E. Scuseria, Hao Shi, B. V. Svistunov, Luca F. Tocchio, I. S. Tupitsyn, Steven R. White, Shiwei Zhang, Bo-Xiao Zheng, Zhenyue Zhu, and Emanuel Gull.  Solutions of the two-dimensional hubbard model: Benchmarks and results from a wide range of numerical algorithms.  _Physical Review X_ , 5:041041, Dec 2015.  doi: 10.1103/PhysRevX.5.041041.  arXiv:1505.02290.
  * Lee et al. [2020] 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, 2020.  arXiv:2011.03494.
  * Lin and Tong [2020a] Lin Lin and Yu Tong.  Near-optimal ground state preparation.  _Quantum_ , 4:372, December 2020a.  ISSN 2521-327X.  doi: 10.22331/q-2020-12-14-372.  arXiv:2002.12508.
  * Lin and Tong [2020b] Lin Lin and Yu Tong.  Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems.  _Quantum_ , 4:361, November 2020b.  ISSN 2521-327X.  doi: 10.22331/q-2020-11-11-361.  arXiv:1910.14596.
  * Linke et al. [2018] Norbert M. Linke, Sonika Johri, Caroline Figgatt, Kevin A. Landsman, Anne Y. Matsuura, and Christopher Monroe.  Measuring the Rényi entropy of a two-site Fermi-Hubbard model on a trapped ion quantum computer.  _Physical Review A_ , 98:052334, Nov 2018.  doi: 10.1103/PhysRevA.98.052334.  arXiv:1712.08581.
  * Liu et al. [2020] Yi-Xiang Liu, Jordan Hines, Zhi Li, Ashok Ajoy, and Paola Cappellaro.  High-fidelity trotter formulas for digital quantum simulation.  _Physical Review A_ , 102:010601, Jul 2020.  doi: 10.1103/PhysRevA.102.010601.  arXiv:1903.01654.
  * Lloyd [1996] Seth Lloyd.  Universal quantum simulators.  _Science_ , pages 1073–1078, 1996.  doi: 10.1126/science.273.5278.1073.
  * Low and Chuang [2017a] Guang Hao Low and Isaac L. Chuang.  Hamiltonian simulation by uniform spectral amplification, 2017a.  arXiv:1707.05391.
  * Low and Chuang [2017b] Guang Hao Low and Isaac L. Chuang.  Optimal Hamiltonian simulation by quantum signal processing.  _Physical Review Letters_ , 118:010501, 2017b.  doi: 10.1103/PhysRevLett.118.010501.  arXiv:1606.02685.
  * Low and Chuang [2019] Guang Hao Low and Isaac L. Chuang.  Hamiltonian simulation by qubitization.  _Quantum_ , 3:163, July 2019.  doi: 10.22331/q-2019-07-12-163.  arXiv:1610.06546.
  * Low and Wiebe [2018] Guang Hao Low and Nathan Wiebe.  Hamiltonian simulation in the interaction picture, 2018.  arXiv:1805.00675.
  * Low et al. [2019] Guang Hao Low, Vadym Kliuchnikov, and Nathan Wiebe.  Well-conditioned multiproduct Hamiltonian simulation, 2019.  arXiv:1907.11679.
  * McArdle et al. [2020] Sam McArdle, Suguru Endo, Alán Aspuru-Guzik, Simon C. Benjamin, and Xiao Yuan.  Quantum computational chemistry.  _Reviews of Modern Physics_ , 92(1):015003, 2020\.  doi: 10.1103/RevModPhys.92.015003.  arXiv:1808.10402.
  * McClean et al. [2014] Jarrod R. McClean, Ryan Babbush, Peter J. Love, and Alán Aspuru-Guzik.  Exploiting locality in quantum computation for quantum chemistry.  _The Journal of Physical Chemistry Letters_ , 5(24):4368–4380, 2014.  doi: 10.1021/jz501649m.  arXiv:1407.7863.
  * Meister et al. [2020] Richard Meister, Simon C. Benjamin, and Earl T. Campbell.  Tailoring term truncations for electronic structure calculations using a linear combination of unitaries, 2020.  arXiv:2007.11624.
  * Motta et al. [2021] Mario Motta, Erika Ye, Jarrod R. McClean, Zhendong Li, Austin J. Minnich, Ryan Babbush, and Garnet Kin-Lic Chan.  Low rank representations for quantum simulation of electronic structure.  _npj Quantum Information_ , 7(1):83, May 2021\.  ISSN 2056-6387.  doi: 10.1038/s41534-021-00416-z.  arXiv:1312.2579.
  * Ortiz et al. [2001] G. Ortiz, J. E. Gubernatis, E. Knill, and R. Laflamme.  Quantum algorithms for fermionic simulations.  _Physical Review A_ , 64:022319, Jul 2001.  doi: 10.1103/PhysRevA.64.022319.  arXiv:cond-mat/0012334.
  * Otte [2010] Peter Otte.  Boundedness properties of fermionic operators.  _Journal of Mathematical Physics_ , 51(8):083503, 2010.  doi: 10.1063/1.3464264.  arXiv:0911.4438.
  * Ouyang et al. [2020] Yingkai Ouyang, David R. White, and Earl T. Campbell.  Compilation by stochastic Hamiltonian sparsification.  _Quantum_ , 4:235, 2020.  doi: 10.22331/q-2020-02-27-235.  arXiv:1910.06255.
  * Peng et al. [2020] Tianyi Peng, Aram W. Harrow, Maris Ozols, and Xiaodi Wu.  Simulating large quantum circuits on a small quantum computer.  _Physical Review Letters_ , 125:150504, Oct 2020.  doi: 10.1103/PhysRevLett.125.150504.  arXiv:1904.00102.
  * Peskin and Schroeder [2018] Michael E. Peskin and Daniel V. Schroeder.  _An introduction to quantum field theory_.  CRC press, 2018.  doi: 10.1201/9780429503559.
  * Poulin et al. [2015] David Poulin, Matthew B. Hastings, Dave Wecker, Nathan Wiebe, Andrew C. Doherty, and Matthias Troyer.  The Trotter step size required for accurate quantum simulation of quantum chemistry.  _Quantum Information and Computation_ , 15(5-6):361–384, 2015.  arXiv:1406.4920.
  * Quantum and collaborators [2020] Google AI Quantum and collaborators.  Observation of separated dynamics of charge and spin in the Fermi-Hubbard model, 2020.  arXiv:2010.07965.
  * Rall [2021] Patrick Rall.  Faster coherent quantum algorithms for phase, energy, and amplitude estimation, 2021.  arXiv:2103.09717.
  * 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.  arXiv:1605.03590.
  * Şahinoğlu and Somma [2020] Burak Şahinoğlu and Rolando D. Somma.  Hamiltonian simulation in the low energy subspace, 2020.  arXiv:2006.02660.
  * Sawaya et al. [2020] Nicolas P. D. Sawaya, Tim Menke, Thi Ha Kyaw, Sonika Johri, Alán Aspuru-Guzik, and Gian Giacomo Guerreschi.  Resource-efficient digital quantum simulation of $d$-level systems for photonic, vibrational, and spin-$s$ Hamiltonians.  _npj Quantum Information_ , 6(1):49, Jun 2020\.  ISSN 2056-6387.  doi: 10.1038/s41534-020-0278-0.  arXiv:1909.12847.
  * Seeley et al. [2012] Jacob T. Seeley, Martin J. Richard, and Peter J. Love.  The Bravyi-Kitaev transformation for quantum computation of electronic structure.  _The Journal of Chemical Physics_ , 137(22):224109, 2012.  doi: 10.1063/1.4768229.  arXiv:1208.5986.
  * Shaw et al. [2020] Alexander F. Shaw, Pavel Lougovski, Jesse R. Stryker, and Nathan Wiebe.  Quantum algorithms for simulating the lattice Schwinger model.  _Quantum_ , 4:306, August 2020.  ISSN 2521-327X.  doi: 10.22331/q-2020-08-10-306.  arXiv:2002.11146.
  * Somma [2015] Rolando D. Somma.  Quantum simulations of one dimensional quantum systems, 2015.  arXiv:1503.06319.
  * Somma [2016] Rolando D. Somma.  A Trotter-Suzuki approximation for Lie groups with applications to Hamiltonian simulation.  _Journal of Mathematical Physics_ , 57:062202, 2016.  doi: 10.1063/1.4952761.  arXiv:1512.03416.
  * Su et al. [2021] Yuan Su, Dominic W. Berry, Nathan Wiebe, Nicholas Rubin, and Ryan Babbush.  Fault-tolerant quantum simulations of chemistry in first quantization, 2021.  arXiv:2105.12767.
  * Suzuki [1985] Masuo Suzuki.  Decomposition formulas of exponential operators and Lie exponentials with some applications to quantum mechanics and statistical physics.  _Journal of Mathematical Physics_ , 26(4):601–612, 1985.  doi: 10.1063/1.526596.
  * Suzuki [1990] Masuo Suzuki.  Fractal decomposition of exponential operators with applications to many-body theories and Monte Carlo simulations.  _Physics Letters A_ , 146(6):319–323, 1990.  doi: 10.1016/0375-9601(90)90962-N.
  * Toloui and Love [2013] Borzu Toloui and Peter J. Love.  Quantum algorithms for quantum chemistry based on the sparsity of the CI-matrix, 2013.  arXiv:1312.2579.
  * Tran et al. [2019] Minh C. Tran, Andrew Y. Guo, Yuan Su, James R. Garrison, Zachary Eldredge, Michael Foss-Feig, Andrew M. Childs, and Alexey V. Gorshkov.  Locality and digital quantum simulation of power-law interactions.  _Physical Review X_ , 9:031006, Jul 2019.  doi: 10.1103/PhysRevX.9.031006.  arXiv:1808.05225.
  * Tran et al. [2021] Minh C. Tran, Yuan Su, Daniel Carney, and Jacob M. Taylor.  Faster digital quantum simulation by symmetry protection.  _PRX Quantum_ , 2:010323, Feb 2021.  doi: 10.1103/PRXQuantum.2.010323.  arXiv:2006.16248.
  * von Burg et al. [2020] Vera von Burg, Guang Hao Low, Thomas Häner, Damian S. Steiger, Markus Reiher, Martin Roetteler, and Matthias Troyer.  Quantum computing enhanced computational catalysis, 2020.  arXiv:2007.14460.
  * Wan and Kim [2020] Kianna Wan and Isaac Kim.  Fast digital methods for adiabatic state preparation, 2020.  arXiv:2004.04164.
  * Wecker et al. [2014] 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:022305, Aug 2014.  doi: 10.1103/PhysRevA.90.022305.  arXiv:1312.1695.
  * Wecker et al. [2015] 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.  doi: 10.1103/PhysRevA.92.062318.  arXiv:1506.05135.
  * Whitfield et al. [2011] James D. Whitfield, Jacob Biamonte, and Alán Aspuru-Guzik.  Simulation of electronic structure hamiltonians using quantum computers.  _Molecular Physics_ , 109(5):735–750, 2011.  doi: 10.1080/00268976.2011.552441.  arXiv:1001.3855.
  * Wick [1950] Gian Carlo Wick.  The evaluation of the collision matrix.  _Physical Review_ , 80:268–272, Oct 1950.  doi: 10.1103/PhysRev.80.268.
  * Xu et al. [2020] Shenglong Xu, Leonard Susskind, Yuan Su, and Brian Swingle.  A sparse model of quantum holography, 2020.  arXiv:2008.02303.
  * Zheng et al. [2017] Bo-Xiao Zheng, Chia-Min Chung, Philippe Corboz, Georg Ehlers, Ming-Pu Qin, Reinhard M Noack, Hao Shi, Steven R White, Shiwei Zhang, and Garnet Kin-Lic Chan.  Stripe order in the underdoped region of the two-dimensional Hubbard model.  _Science_ , 358(6367):1155–1160, 2017.  doi: 10.1126/science.aam7127.  arXiv:1701.00054.