aff1]Institute for Quantum Information and Matter, Caltech, Pasadena, CA
91125, USA aff2]Google Research, Venice, CA 90291, USA aff3]Department of
Computing and Mathematical Sciences, Caltech, Pasadena, CA 91125, USA aff4]AWS
Center for Quantum Computing, Pasadena, CA 91125, USA

# Nearly tight Trotterization of interacting electrons

Yuan Su  Hsin-Yuan Huang  Earl T. Campbell  [  [  [  [

###### Abstract

We consider simulating quantum systems on digital quantum computers. We show
that the performance of quantum simulation can be improved by simultaneously
exploiting commutativity of the target Hamiltonian, sparsity of interactions,
and prior knowledge of the initial state. We achieve this using Trotterization
for a class of interacting electrons that encompasses various physical
systems, including the plane-wave-basis electronic structure and the Fermi-
Hubbard model. We estimate the simulation error by taking the transition
amplitude of nested commutators of the Hamiltonian terms within the
$\eta$-electron manifold. We develop multiple techniques for bounding the
transition amplitude and expectation of general fermionic operators, which may
be of independent interest. We show that it suffices to use
$\left(\frac{n^{5/3}}{\eta^{2/3}}+n^{4/3}\eta^{2/3}\right)n^{o(1)}$ gates to
simulate electronic structure in the plane-wave basis with $n$ spin orbitals
and $\eta$ electrons, improving the best previous result in second
quantization up to a negligible factor while outperforming the first-quantized
simulation when $n=\eta^{2-o(1)}$. We also obtain an improvement for
simulating the Fermi-Hubbard model. We construct concrete examples for which
our bounds are almost saturated, giving a nearly tight Trotterization of
interacting electrons.

###### Contents

  1. 1 Introduction
    1. 1.1 Combining interaction sparsity, commutativity, and initial-state knowledge
    2. 1.2 Simulating interacting electrons
    3. 1.3 Main techniques
    4. 1.4 Applications
  2. 2 Preliminaries
    1. 2.1 Trotterization and Trotter error
    2. 2.2 Second-quantization representation
    3. 2.3 Fermionic seminorm
  3. 3 Recursive bound on the expectation of fermionic operators
    1. 3.1 Main techniques
    2. 3.2 Single-layer commutator
    3. 3.3 Multilayer nested commutators
  4. 4 Path-counting bound on the expectation of fermionic operators
    1. 4.1 Path-counting bound
    2. 4.2 Counting fermionic paths for $d$-sparse interactions
  5. 5 Tightness
    1. 5.1 Lower-bounding $\left\lVert[T,\ldots[T,V]]\right\rVert_{\eta}$
    2. 5.2 Lower-bounding $\left\lVert[V,\ldots[V,T]]\right\rVert_{\eta}$
  6. 6 Applications
    1. 6.1 Plane-wave-basis electronic structure
    2. 6.2 Fermi-Hubbard model
  7. 7 Discussion
  8. A Analysis of single-layer commutator
  9. B Counting fermionic paths for non-sparse interactions
  10. C Lower-bounding $\left\lVert[T,\ldots[T,V]]\right\rVert_{\eta}$
  11. D Lower-bounding $\left\lVert[V,\ldots[V,T]]\right\rVert_{\eta}$

##  1 Introduction

Simulating quantum systems to model their dynamics and energy spectra is one
of the most promising applications of digital quantum computers. Indeed, the
difficulty of performing such simulations on classical computers led Feynman
[30] and others to propose the idea of quantum computation. In 1996, Lloyd
proposed the first explicit quantum algorithm for simulating local
Hamiltonians [50]. Since then, various quantum simulation algorithms have been
developed [10, 11, 12, 13, 52, 53, 54, 33, 25, 18, 62, 55], with potential
applications in studying condensed matter physics [24], quantum chemistry [20,
56], quantum field theories [39, 40], superstring/M-theory [31], as well as in
designing other classical [43] and quantum algorithms [9, 15, 23, 36, 2, 46,
82, 32, 47, 67].

Lloyd’s original work considered the simulation of $k$-local Hamiltonians.
This was subsequently extended to the study of $d$-sparse Hamiltonians [1,
10], which provides a framework that abstracts the design of quantum
algorithms from the underlying physical settings. However, despite their
theoretical value, algorithms for sparse Hamiltonian simulation do not always
provide the fastest approach for simulating concrete physical systems.
Hamiltonians arising in practice often have additional features beyond
sparseness, such as locality [33, 79], commutativity [22, 27, 74], and
symmetry [80, 35], that can be used to improve the performance of simulation.
Besides, prior knowledge of the initial state [73, 69, 6, 28] and the norm
distribution of Hamiltonian terms [18, 34, 21, 58, 49] have also been proven
useful for digital quantum simulation.

We show that a number of these features, in particular the sparsity,
commutativity, and initial-state information, can be combined to give an even
faster simulation. We achieve this improvement for a class of interacting-
electronic Hamiltonians, which includes many physically relevant systems such
as the plane-wave-basis electronic-structure Hamiltonian and the Fermi-Hubbard
model. Our approach uses Trotterization—a method widely applied in digital
quantum simulation.

Our analysis proceeds by computing the transition amplitude of simulation
error within the $\eta$-electron manifold. To this end, we develop multiple
techniques for bounding the transition amplitude/expectation of a general
fermionic operator, which may be of independent interest. For an $n$-spin-
orbital electronic-structure problem in the plane-wave basis, our result
improves the best previous result in second quantization [54, 6, 27] up to a
negligible factor while outperforming the first-quantized result [7] when
$n=\eta^{2-o(1)}$. We also obtain an improvement for simulating the Fermi-
Hubbard model. We construct concrete examples for which our bounds are almost
saturated, giving a nearly tight Trotterization of interacting electrons.

###  1.1 Combining interaction sparsity, commutativity, and initial-state
knowledge

Sparsity can be used to improve digital quantum simulation in multiple ways. A
common notion of $d$-sparsity concerns the target Hamiltonian itself, where
each row and column of the Hamiltonian contains $d$ nonzero elements accessed
by querying quantum oracles. As aforementioned, this provides an abstract
framework for designing efficient simulation algorithms and is versatile for
establishing lower bounds [10], although it sometimes ignores other important
properties of the target system, such as locality, commutativity, and
symmetry. Another notion of sparsity, closely related to our paper, considers
the interactions between the underlying qubits or modes [14, 87, 63, 57]. The
sparsity of interactions does not in general imply the underlying Hamiltonian
is sparse, but it provides a tighter bound on the number of terms in the
Hamiltonian and may thus be favorable to digital quantum simulation.

Trotterization (and its alternative variants [27, 25, 62, 34, 55]) provides a
simple approach to digital quantum simulation and is so far the only known
approach that can exploit the commutativity of the Hamiltonian. Indeed, in the
extreme case where all the terms in the Hamiltonian commute, we can
simultaneously diagonalize them and apply the first-order Lie-Trotter formula
$\mathscr{S}_{1}(t)$ without error. Previous studies have also established
commutator error bounds for certain low-order formulas [76] and specific
systems [22, 74]. An analysis of a general formula $\mathscr{S}_{p}(t)$ is,
however, considerably more difficult and has remained elusive until the recent
proof of the commutator scaling of Trotter error [27].

A different direction to speeding up digital quantum simulation is to exploit
information about the initial state. The error of digital quantum simulation
is commonly quantified in previous work by the spectral-norm distance, which
considers all possible states in the underlying Hilbert space. But if the
state is known to be within some subspace throughout the simulation, then in
principle this knowledge could be used to improve the algorithm. For instance,
digital quantum simulation in practice often starts with an initial state in
the low-energy subspace of the Hamiltonian, so a worst-case spectral-norm
analysis will inevitably overestimate the error. To address this, recent
studies have considered a low-energy projection on the simulation error and
provided improved approaches, using either Trotterization [73, 69, 6, 28] or
more advanced quantum algorithms [51], that can be advantageous when the
energy of the initial state is sufficiently small.

Ideally, the sparsity of interactions, commutativity of the Hamiltonian, and
prior knowledge about the initial state can all be combined to yield an even
faster digital quantum simulation. This combination, however, appears to be
technically challenging to achieve. Indeed, the state-of-the-art analysis of
Trotterization represents the simulation error in terms of nested commutators
of Hamiltonian terms with exponential conjugations [27, Theorem 5]. This
representation is versatile for computing the commutator scaling of Trotter
error, but it yields little information about the energy of the initial state.
To the best of our knowledge, the only previous attempt to address this
problem was made by Somma for simulating bosonic Hamiltonians [73], whose
solution seems to have a divergence issue.111Recent work [3] developed a
tighter analysis of Trotter error for time-dependent Hamiltonian simulation
that exploits both commutativity of the target Hamiltonian and knowledge about
the initial state. Instead, we combine the sparsity, the commutativity and the
initial-state information to give an improved simulation of a class of
interacting electrons.

###  1.2 Simulating interacting electrons

Simulating interacting electrons has emerged as one of the most important
applications of digital quantum simulation [8]. Following pioneering work such
as [4, 60], recent developments of efficient quantum algorithms for electronic
structure simulation have dramatically reduced the simulation cost through
various techniques [56, 20, 45, 81, 85, 71, 78, 14, 59, 6, 68].

Here, we consider simulating the following class of interacting electrons by
Trotterization:

$H=T+V:=\sum_{j,k}\tau_{j,k}A_{j}^{\dagger}A_{k}+\sum_{l,m}\nu_{l,m}N_{l}N_{m},$
(1)

where $A_{j}^{\dagger}$, $A_{k}$ are the fermionic _creation_ and
_annihilation operators_ , $N_{l}$ are the _occupation-number operators_ ,
$\tau$, $\nu$ are coefficient matrices, and the summation is over $n$ spin
orbitals. The specific definitions of these fermionic operators are given in
Section 2.2. We say the interactions are _$d$ -sparse_ if there are at most
$d$ nonzero elements within each row/column of $\tau$ and $\nu$. This model
represents various systems arising in physics and chemistry, including the
electronic-structure Hamiltonians in the plane-wave basis [6] and the Fermi-
Hubbard model [28, 42].

To apply Trotterization, we need to express the Hamiltonian as a sum of
elementary terms, each of which can be directly exponentiated on a quantum
computer; see Section 2.1 for a review of this algorithm. For the electronic
Hamiltonian (1), it suffices to consider the two-term decomposition $H=T+V$,
as the exponentials of $T$ and $V$ can be directly implemented using various
quantum circuits. For instance, all the terms in $V$ commute with each other
so $e^{-itV}=\prod_{l,m}e^{-it\nu_{l,m}N_{l}N_{m}}$, where each
$e^{-it\nu_{l,m}N_{l}N_{m}}$ corresponds to a two-qubit operation under the
Jordan-Wigner transformation. On the other hand, the exponential $e^{-itT}$
can be implemented by diagonalization, i.e.,
$e^{-itT}=Ue^{-i\sum\lambda_{\ell}N_{\ell}}U^{\dagger}$, where $U$ can be
efficiently implemented using Givens rotations [65, 41]. In cases where $\tau$
and $\nu$ are translationally invariant $\tau_{j,k}=\tau_{j+q,k+q}$,
$\nu_{l,m}=\nu_{l+q,m+q}$, we can implement $e^{-itT}$ using the fast
fermionic Fourier transform [6] and a related circuit implementation exists
for $e^{-itV}$ [54].

We now apply a $p$th-order Trotterization $\mathscr{S}_{p}(t)$ to approximate
the evolution of the electronic Hamiltonian (1) for time $t$. We prove the
following bound on the error of this approximation.

######  Theorem 1 (Fermionic seminorm of Trotter error).

Let
$H=T+V=\sum_{j,k}\tau_{j,k}A_{j}^{\dagger}A_{k}+\sum_{l,m}\nu_{l,m}N_{l}N_{m}$
be an interacting-electronic Hamiltonian (1) with $n$ spin orbitals, which we
simulate using a $p$th-order formula $\mathscr{S}_{p}(t)$. Then,

$\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^{2}t^{p+1}\right).$
(2)

Furthermore, if the interactions are $d$-sparse,

$\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}d^{p+1}\eta
t^{p+1}\right).$ (3)

Here, $\left\lVert\cdot\right\rVert$ is the _spectral norm_ ,
$\left\lVert\cdot\right\rVert_{\max}$ is the _max-norm_ denoting the largest
matrix element in absolute value, and

$\left\lVert
X\right\rVert_{\eta}:=\max_{\lvert\psi_{\eta}\rangle,\lvert\phi_{\eta}\rangle}\left\lvert\langle\phi_{\eta}\rvert
X\lvert\psi_{\eta}\rangle\right\rvert$ (4)

is the _fermionic $\eta$-seminorm_ for _number-preserving operator_ $X$, where
$\lvert\psi_{\eta}\rangle$, $\lvert\phi_{\eta}\rangle$ are quantum states with
$\eta$ electrons.

This theorem follows from an inductive estimate of the fermionic seminorm of
nested commutators of Hamiltonian terms, and will be formally proved in
Section 3 and Section 4. Note that in order to use the prior knowledge of the
initial state, we have considered the fermionic seminorm
$\left\lVert\cdot\right\rVert_{\eta}$ of Trotter error with respect to the
$\eta$-electron manifold. This seminorm is closely related to other metrics
used to quantify the impact of initial-state information to digital quantum
simulation [73, 69, 6, 28]; see Section 2.3 for a detailed discussion. The
resulting bound depends on the number of electrons $\eta$, as well as the
spectral norm $\left\lVert\tau\right\rVert$, the max-norm
$\left\lVert\tau\right\rVert_{\max},\left\lVert\nu\right\rVert_{\max}$, and
the sparsity of interactions $d$, but there is no dependence on the total
number of spin orbitals $n$. This improves over previous work [27, Theorem
F.5] where an explicit $n$-scaling seems unavoidable. Meanwhile, other prior
estimates of the fermionic seminorm [6, Appendix G] [28, Theorem 13] did not
exploit commutativity of the Hamiltonian and would introduce an additional
factor of $\eta^{p}$ in the Trotter error bound. Our result thus improves the
performance of digital quantum simulation by combining the initial-state
information, the interaction sparsity, and commutativity of the Hamiltonian.

A common issue with the Trotterization algorithm is that existing analyses can
be very loose for simulating certain physical systems. However, we address
this with the following theorem, which shows that the asymptotic scaling of
our bound is nearly tight.

######  Theorem 2 (Tightness).

For $s,w>0$ and positive integer $\eta\leq\frac{n}{2}$, there exists an
interacting-electronic Hamiltonian
$H=T+V=\sum_{j,k}\tau_{j,k}A_{j}^{\dagger}A_{k}+\sum_{l,m}\nu_{l,m}N_{l}N_{m}$
as in (1) with $n$ spin orbitals such that $\left\lVert\tau\right\rVert=s$,
$\left\lVert\nu\right\rVert_{\max}=w$,

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

In addition, for $u,w>0$ and positive integer $d\leq\eta\leq\frac{n}{2}$,
there exists a $d$-sparse interacting-electronic Hamiltonian (1) with $n$ spin
orbitals such that $\left\lVert\tau\right\rVert_{\max}=u$,
$\left\lVert\nu\right\rVert_{\max}=w$,

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

We prove the above theorem by choosing
$T=\sum_{j,k=0}^{n-1}A_{j}^{\dagger}A_{k}$ and
$V=\sum_{l,m=0}^{n/2-1}N_{l}N_{m}$ and computing their rescaled nested
commutators, both in the original basis and the Fourier basis; see Section 5
for the proof. Note that both commutators $[T,\ldots[T,V]]$ and
$[V,\ldots,[V,T]]$ contribute to the Trotter error, as well as other types of
nested commutators which do not dominate the error scaling (Proposition 1).
Modulo an application of the triangle inequality, Theorem 2 then shows that
our bound (2) overestimates the Trotter error by a factor of $n\eta$ in the
worst case, whereas (3) overestimates a factor of at most $\eta$. For $p$
sufficiently large, this only contributes $n^{o(1)}$ and $\eta^{o(1)}$ to the
gate complexity, respectively. In this sense, we have given a nearly tight
Trotterization of interacting-electronic Hamiltonians (1).222For specific
molecules, our complexity estimates may be further improved by using
additional features of the Hamiltonians; see Section 7 for a further
discussion of this point.

###  1.3 Main techniques

The proof of Theorem 1 relies on multiple approaches we develop for bounding
the fermionic seminorm, which may be of independent interest. Recall from (4)
that the fermionic seminorm $\left\lVert X\right\rVert_{\eta}$ of a number-
preserving operator $X$ is the maximum transition amplitude of $X$ within the
$\eta$-electron manifold.

Our first approach is based on the observation that the fermionic seminorm of
$X$ can be alternatively represented using the expectation of $X^{\dagger}X$,
i.e.,

$\left\lVert
X\right\rVert_{\eta}=\max_{\lvert\psi_{\eta}\rangle,\lvert\phi_{\eta}\rangle}\left\lvert\langle\phi_{\eta}\rvert
X\lvert\psi_{\eta}\rangle\right\rvert=\max_{\lvert\psi_{\eta}\rangle}\sqrt{\langle\psi_{\eta}\rvert
X^{\dagger}X\lvert\psi_{\eta}\rangle}.$ (7)

We then upper bound $X^{\dagger}X$ in terms of the _particle-number operator_
$N=\sum_{j}N_{j}$, so that the expectation scales with the number of electrons
$\eta=\langle\psi_{\eta}\rvert N\lvert\psi_{\eta}\rangle$ instead of the total
number of spin orbitals. Assuming $X$ is a sum of product of fermionic
operators, we contract the summation indices in $X^{\dagger}X$ by using either
diagonalization (Lemma 2) or an operator Cauchy-Schwarz inequality (Lemma 1)
[61]. To extend this argument to general fermionic operators, we prove a
Hölder-type inequality (Lemma 3) and apply it recursively to bound
$X^{\dagger}X$. We detail this recursive approach in Section 3 and use it to
prove (2).

Our second approach starts by bounding the fermionic seminorm

$\left\lVert
X\right\rVert_{\eta}=\max_{\lvert\psi_{\eta}\rangle,\lvert\phi_{\eta}\rangle}\left\lvert\langle\phi_{\eta}\rvert
X\lvert\psi_{\eta}\rangle\right\rvert$ (8)

in terms of the maximum expectation value
$\max_{\lvert\psi_{\eta}\rangle}\left\lvert\langle\psi_{\eta}\rvert
X\lvert\psi_{\eta}\rangle\right\rvert$. We then expand $X$ and
$\lvert\psi_{\eta}\rangle$ and give a combinatorial argument to count the
number of “paths” which have nonzero contribution to the expectation
(Proposition 11). We discuss this path-counting approach in more detail in
Section 4 and use it to prove (3). It is worth mentioning that the path-
counting technique can also be used to prove the following alternative bound
for the $p$th-order Trotterization

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

This is slightly weaker than (2) since $\left\lVert\tau\right\rVert\leq
n\left\lVert\tau\right\rVert_{\max}$ always holds but not necessarily
saturates, but in our application it yields the same gate complexity for the
electronic-structure simulation in the second-quantized plane-wave basis. We
discuss this further in Appendix B.

Note that the expectation of fermionic operators, when taken with respect to
the computational-basis states, can be exactly computed using the so-called
Wick’s theorem [86, 64]. However, this approach would introduce unnecessary
term reordering which actually complicates our proof. In contrast, the
underlying idea of path counting is conceptually simpler and may have
potential applications in other contexts beyond the analysis of Trotter error.

###  1.4 Applications

The nearly tight Trotterization of electronic Hamiltonian (1) gives improved
simulations of many systems arising in condensed matter physics and quantum
chemistry, including the plane-wave-basis electronic-structure Hamiltonian and
the Fermi-Hubbard model.

The electronic-structure problem considers electrons interacting with each
other and some fixed nuclei. An efficient simulation of such systems could
help understand chemical reactions, and provide insight into material
properties. Here, we consider representing the electronic-structure
Hamiltonian in the plane-wave basis [6]:

$\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}$ (10)
$\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 can represent this Hamiltonian in the form (1) with

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

Assuming a constant system density $\eta=\mathcal{O}\left(\omega\right)$,
Theorem 1 then implies that

$\left\lVert\mathscr{S}_{p}(t)-e^{-itH}\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}t^{p+1}\right).$
(12)

This approximation is accurate for a short-time evolution. To simulate for a
longer time, we divide the evolution into $r$ steps and apply
$\mathscr{S}_{p}(t/r)$ within each step, obtaining

$\displaystyle\left\lVert\mathscr{S}_{p}^{r}(t/r)-e^{-itH}\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).$
(13)

Therefore,

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

steps suffices to simulate for a constant time and accuracy with a $p$th-order
Trotterization. Implementing each step using the approach of [54, Sect. 5] and
choosing $p$ sufficiently large, we obtain the gate complexity

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

Up to the negligible factor $n^{o(1)}$, this improves the best previous result
in second quantization while outperforming the first-quantized simulation when
$n=\eta^{2-o(1)}$. See Table 1 for a gate-count comparison. We discuss this in
detail in Section 6.1.

Simulation Algorithm | $n,\eta$ | $\eta=\Theta(n)$
---|---|---
Interaction-picture (Ref. [7], first quantization) | $\widetilde{\mathcal{O}}\left(n^{1/3}\eta^{8/3}\right)$ | $\widetilde{\mathcal{O}}\left(n^{3}\right)$
Qubitization (Ref. [7], first quantization) | $\widetilde{\mathcal{O}}\left(n^{2/3}\eta^{4/3}+n^{1/3}\eta^{8/3}\right)$ | $\widetilde{\mathcal{O}}\left(n^{3}\right)$
Interaction-picture (Ref. [54], second quantization) | $\widetilde{\mathcal{O}}\left(\frac{n^{8/3}}{\eta^{2/3}}\right)$ | $\widetilde{\mathcal{O}}\left(n^{2}\right)$
Trotterization (Ref. [6], second quantization) | $\left(n^{5/3}\eta^{1/3}+n^{4/3}\eta^{5/3}\right)n^{o(1)}$ | $n^{3+o(1)}$
Trotterization (Ref. [27], second quantization) | $\left(\frac{n^{7/3}}{\eta^{1/3}}\right)n^{o(1)}$ | $n^{2+o(1)}$
Trotterization (Theorem 1, second quantization) | $\left(\frac{n^{5/3}}{\eta^{2/3}}+n^{4/3}\eta^{2/3}\right)n^{o(1)}$ | $n^{2+o(1)}$
Table 1: Comparison of our result and previous results for simulating the
plane-wave-basis electronic structure with $n$ spin orbitals and $\eta$
electrons. We use $\widetilde{\mathcal{O}}\left(\cdot\right)$ to suppress
polylogarithmic factors in the gate complexity scaling.

We also consider applications to the Fermi-Hubbard model, which is believed to
capture the physics of some high temperature superconductors. This model is
classically challenging to simulate [88, 44], but is a potential candidate for
near-term quantum simulation [17, 16, 48, 66]. We have

$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},$
(16)

where $\langle j,k\rangle$ denotes a summation over nearest-neighbor lattice
sites and $\sigma\in\\{0,1\\}$ labels the spin degree of freedom. The Fermi-
Hubbard model represents a lattice system with nearest-neighbor interactions
and, according to [22], can be simulated with
$\mathcal{O}\left(n^{1+1/p}\right)$ gates using a $p$th-order Trotterization
for a constant time and accuracy. On the other hand, recent work [28] shows
that the Trotterization algorithm has gate complexity
$\mathcal{O}\left(n\eta^{1+1/p}\right)$ when restricted to the $\eta$-electron
manifold. By simultaneously using the sparsity of interactions, commutativity
of the Hamiltonian and information about the initial state, we show in Section
6.2 that $\mathcal{O}\left(n\eta^{1/p}\right)$ gates suffices, improving both
results for the Fermi-Hubbard model.333Note however that this does not
significantly improve the approach based on Lieb-Robinson bounds [33], since
that approach has gate complexity $\widetilde{\mathcal{O}}\left(n\right)$ when
using a high-precision quantum simulation algorithm as a subroutine.

We conclude the paper in Section 7 with a discussion of the results and some
open questions.

##  2 Preliminaries

In this section, we summarize preliminaries of this paper, including a
discussion of the Trotterization algorithm and its error analysis in Section
2.1, a brief summary of the second-quantization representation in Section 2.2,
and an introduction to the fermionic seminorm and its properties in Section
2.3.

###  2.1 Trotterization and Trotter error

The Trotterization algorithm approximates the evolution of a sum of
Hamiltonian terms using exponentials of the individual terms. For the
interacting-electronic Hamiltonian (1), it suffices to consider a two-term
decomposition $H=T+V$, as the exponentials of $T$ and $V$ can be directly
implemented on a quantum computer. Then, the ideal evolution under $H$ for
time $t$ is given by $e^{-itH}=e^{-it(T+V)}$, which can be approximated by a
$p$th-order product formula $\mathscr{S}_{p}(t)$, such as the first-order Lie-
Trotter formula

$\mathscr{S}_{1}(t):=e^{-itT}e^{-itV}$ (17)

and ($2k$)th-order Suzuki formulas [77]

$\displaystyle\mathscr{S}_{2}(t)$
$\displaystyle:=e^{-i\frac{t}{2}V}e^{-itT}e^{-i\frac{t}{2}V},$ (18)
$\displaystyle\mathscr{S}_{2k}(t)$
$\displaystyle:=\mathscr{S}_{2k-2}(u_{k}t)^{2}\,\mathscr{S}_{2k-2}((1-4u_{k})t)\,\mathscr{S}_{2k-2}(u_{k}t)^{2},$

where $u_{k}:=1/(4-4^{1/(2k-1)})$. This approximation is accurate when $t$ is
small. To simulate for a longer time, we divide the evolution into $r$
_Trotter steps_ and apply $\mathscr{S}_{p}(t/r)$ with _Trotter error_ at most
$\epsilon/r$. We choose $r$ sufficiently large so that the simulation error,
as quantified by the spectral norm
$\left\lVert\mathscr{S}_{p}^{r}(t/r)-e^{-itH}\right\rVert$, is at most
$\epsilon$.

Trotterization (and its alternative variants) provides a simple approach to
digital quantum simulation and is so far the only known approach that can
exploit commutativity of the Hamiltonian. Indeed, in the extreme case where
all the Hamiltonian terms commute, Trotterization can implement the exact
evolution without error. Previous studies have also established commutator
analysis of Trotter error for systems with geometrical locality [22] and Lie-
algebraic structures [74], as well as certain low-order formulas [76],
including the first-order Lie-Trotter formula

$\mathscr{S}_{1}(t)-e^{-itH}=\int_{0}^{t}\mathrm{d}\tau_{1}\int_{0}^{\tau_{1}}\mathrm{d}\tau_{2}\
e^{-i(t-\tau_{1})H}e^{-i\tau_{1}T}e^{i\tau_{2}T}\left[iT,iV\right]e^{-i\tau_{2}T}e^{-i\tau_{1}V}$
(19)

and the second-order Suzuki formula

$\displaystyle\mathscr{S}_{2}(t)-e^{-itH}$
$\displaystyle=\int_{0}^{t}\mathrm{d}\tau_{1}\int_{0}^{\tau_{1}}\mathrm{d}\tau_{2}\int_{0}^{\tau_{2}}\mathrm{d}\tau_{3}\
e^{-i(t-\tau_{1})H}e^{-i\frac{\tau_{1}}{2}V}$ (20)
$\displaystyle\quad\cdot\left(e^{-i\tau_{3}T}\left[-iT,\left[-iT,-i\frac{V}{2}\right]\right]e^{i\tau_{3}T}+e^{i\frac{\tau_{3}}{2}V}\left[i\frac{V}{2},\left[i\frac{V}{2},iT\right]\right]e^{-i\frac{\tau_{3}}{2}V}\right)e^{-i\tau_{1}T}e^{-i\frac{\tau_{1}}{2}V}.$

An analysis of the general case is, however, considerably more difficult and
has remained elusive until the recent proof of commutator scaling of Trotter
error [27]. Here, we introduce a stronger version of that result which can be
proved as in [26, Appendix C] by combining Theorem 3, 4, and 5 of [27] without
invoking the triangle inequality.444It is essential to invoke a representation
of the Trotter error where nested commutators have at most a constant number
of layers [27]. If such a representation were not used, Trotterization would
have a worse asymptotic complexity [83, Appendix B].

######  Proposition 1 (Commutator representation of Trotter error).

Let $H=T+V$ be a two-term Hamiltonian and $\mathscr{S}_{p}(t)$ be a $p$th-
order formula. Define $H_{0}=V$ and $H_{1}=T$. Then,

$\displaystyle\mathscr{S}_{p}(t)-e^{-itH}$
$\displaystyle=\int_{0}^{t}\mathrm{d}\tau_{1}\int_{0}^{\tau_{1}}\mathrm{d}\tau_{2}\sum_{\boldsymbol{\gamma},j}a_{\boldsymbol{\gamma},j}(\tau_{1},\tau_{2})e^{-i(t-\tau_{1})H}$
(21)
$\displaystyle\qquad\qquad\qquad\qquad\quad\cdot\mathscr{U}_{\boldsymbol{\gamma},j}(\tau_{1},\tau_{2})\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]\mathscr{W}_{\boldsymbol{\gamma},j}(\tau_{1},\tau_{2}),$

where $\boldsymbol{\gamma}\in\\{0,1\\}^{p+1}$ are binary vectors555We use bold
symbols to represent vectors throughout this paper. and $j$ goes through a
constant range of numbers (depending on the order $p$). Here,
$\mathscr{U}_{\boldsymbol{\gamma},j}(\tau_{1},\tau_{2})$ and
$\mathscr{W}_{\boldsymbol{\gamma},j}(\tau_{1},\tau_{2})$ are products of
evolutions of $T$ and $V$ with time variables $\tau_{1}$ and $\tau_{2}$ and
$a_{\boldsymbol{\gamma}}(\tau_{1},\tau_{2})$ are coefficients such that

$\int_{0}^{t}\mathrm{d}\tau_{1}\int_{0}^{\tau_{1}}\mathrm{d}\tau_{2}\
\left\lvert
a_{\boldsymbol{\gamma},j}(\tau_{1},\tau_{2})\right\rvert=\mathcal{O}\left(t^{p+1}\right).$
(22)

As an immediate application, we find that the spectral norm of the Trotter
error scales with nested commutators of the Hamiltonian terms, i.e.,

$\left\lVert\mathscr{S}_{p}(t)-e^{-itH}\right\rVert=\mathcal{O}\left(\max_{\boldsymbol{\gamma}}\left\lVert\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]\right\rVert
t^{p+1}\right).$ (23)

Note that the use of $\max_{\boldsymbol{\gamma}}$ in place of
$\sum_{\boldsymbol{\gamma}}$ does not change the scaling as
$\boldsymbol{\gamma}$ only ranges over a constant number of binary vectors. We
then divide the evolution into $r$ steps and apply the triangle inequality to
obtain

$\left\lVert\mathscr{S}_{p}^{r}(t/r)-e^{-itH}\right\rVert\leq
r\left\lVert\mathscr{S}_{p}(t/r)-e^{-i\frac{t}{r}H}\right\rVert=\mathcal{O}\left(\max_{\boldsymbol{\gamma}}\left\lVert\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]\right\rVert\frac{t^{p+1}}{r^{p}}\right).$
(24)

It thus suffices to choose

$r=\mathcal{O}\left(\frac{\left(\max_{\boldsymbol{\gamma}}\left\lVert\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]\right\rVert\right)^{1/p}t^{1+1/p}}{\epsilon^{1/p}}\right)$
(25)

to ensure that the error of simulation is no more than $\epsilon$.

The above analysis is versatile for computing the commutator dependence of
Trotter error. Unfortunately, the resulting bound does not use prior knowledge
of the initial state and will in particular be loose if the initial state lies
within a low-energy subspace. On the other hand, recent work of Şahinoğlu and
Somma proposed a Trotterization approach for simulating low-energy initial
states but the commutativity of the Hamiltonian was ignored in their analysis
[69]. Here, we address this by simultaneously using commutativity of the
Hamiltonian and prior knowledge of the initial state to improve the simulation
of a class of interacting electrons. We obtain further improvement when the
electronic Hamiltonian has sparse interactions. In the following, we introduce
preliminaries about the second-quantization representation (Section 2.2) and
the notion of fermionic seminorm (Section 2.3), on which our analysis will be
based.

###  2.2 Second-quantization representation

In this section, we review several facts about the second-quantization
representation that are relevant to our analysis. We refer the reader to the
book of Helgaker, Jørgensen, and Olsen [37] for a detailed discussion of this
topic.

We use the abstract Fock space to represent electronic Hamiltonians.
Specifically, for a system of $n$ spin orbitals, we construct a
$2^{n}$-dimensional space $\operatorname{span}\\{\lvert
c_{0},c_{1},\ldots,c_{n-1}\rangle\\}$ spanned by the basis vectors $\lvert
c_{0},c_{1},\ldots,c_{n-1}\rangle$, where $c_{j}=1$ represents that mode $j$
is occupied and $c_{j}=0$ otherwise. General vectors in the Fock space,
denoted by $\lvert\psi\rangle$ or $\lvert\phi\rangle$, are then given by
linear combinations of these orthonormal basis vectors. We define the _$\eta$
-electron subspace_ $\operatorname{span}\\{\lvert
c_{0},c_{1},\ldots,c_{n-1}\rangle,\sum_{j}c_{j}=\eta\\}$. By considering all
$0\leq\eta\leq n$, we obtain the decomposition

$\operatorname{span}\left\\{\lvert
c_{0},c_{1},\ldots,c_{n-1}\rangle\right\\}={}_{\eta=0}^{n}\operatorname{span}\Big{\\{}\lvert
c_{0},c_{1},\ldots,c_{n-1}\rangle,\sum_{j}c_{j}=\eta\Big{\\}},$ (26)

where denotes the orthogonal direct sum. Using bold symbol $\boldsymbol{c}$ to
represent an arbitrary _fermionic configuration_ and
$\left\lvert\boldsymbol{c}\right\rvert=\sum_{j}c_{j}$ to denote the _Hamming
weight_ , we have

$\operatorname{span}\left\\{\lvert\boldsymbol{c}\rangle\right\\}={}_{\eta=0}^{n}\operatorname{span}\Big{\\{}\lvert\boldsymbol{c}\rangle,\left\lvert\boldsymbol{c}\right\rvert=\eta\Big{\\}}.$
(27)

We say that normalized vectors in the $\eta$-electron subspace form the
_$\eta$ -electron manifold_ and denote an arbitrary such vector by
$\lvert\psi_{\eta}\rangle$ or $\lvert\phi_{\eta}\rangle$.

The $n$ elementary fermionic _creation operators_ are defined through the
relations

$\displaystyle A_{j}^{\dagger}\lvert
c_{0},c_{1},\ldots,0_{j},\ldots,c_{n-1}\rangle$
$\displaystyle=(-1)^{\sum_{k=0}^{j-1}c_{k}}\lvert
c_{0},c_{1},\ldots,1_{j},\ldots,c_{n-1}\rangle,$ (28) $\displaystyle
A_{j}^{\dagger}\lvert c_{0},c_{1},\ldots,1_{j},\ldots,c_{n-1}\rangle$
$\displaystyle=0,$

whereas the fermionic _annihilation operators_ are defined by

$\displaystyle A_{j}\lvert c_{0},c_{1},\ldots,0_{j},\ldots,c_{n-1}\rangle$
$\displaystyle=0,$ (29) $\displaystyle A_{j}\lvert
c_{0},c_{1},\ldots,1_{j},\ldots,c_{n-1}\rangle$
$\displaystyle=(-1)^{\sum_{k=0}^{j-1}c_{k}}\lvert
c_{0},c_{1},\ldots,0_{j},\ldots,c_{n-1}\rangle.$

The use of $\dagger$ is justified by the fact that $A_{j}^{\dagger}$ is indeed
the Hermitian adjoint of $A_{j}$ with respect to the inner product in the Fock
space. We also introduce the _occupation-number operators_
$N_{j}=A_{j}^{\dagger}A_{j}$ and add them together to get the _particle-number
operator_ $N=\sum_{j=0}^{n-1}N_{j}$.

Fermionic creation and annihilation operators satisfy the canonical
anticommutation relations

$A_{j}^{\dagger}A_{k}^{\dagger}+A_{k}^{\dagger}A_{j}^{\dagger}=A_{j}A_{k}+A_{k}A_{j}=0,\qquad
A_{j}^{\dagger}A_{k}+A_{k}A_{j}^{\dagger}=\delta_{j,k}I,$ (30)

where the Kronecker-delta function $\delta_{j,k}$ is one if $j=k$ and zero
otherwise. Applying these, we obtain the following commutation relations of
second-quantized fermionic operators.

######  Proposition 2 (Commutation relations of fermionic operators).

The following commutation relations hold for second-quantized fermionic
operators:

  1. 1.

$\left[A_{l}^{\dagger}A_{m},A_{j}^{\dagger}\right]=\delta_{j,m}A_{l}^{\dagger}$,
$\left[A_{l}^{\dagger}A_{m},A_{k}\right]=-\delta_{k,l}A_{m}$;

  2. 2.

$\left[N_{l},A_{j}^{\dagger}\right]=\delta_{l,j}A_{j}^{\dagger}$,
$\left[N_{l},A_{k}\right]=-\delta_{l,k}A_{k}$;

  3. 3.

$\left[N,A_{j}^{\dagger}\right]=A_{j}^{\dagger}$,
$\left[N,A_{k}\right]=-A_{k}$;

  4. 4.

$\left[N_{l},N_{m}\right]=0$.

We say a fermionic operator is _number-preserving_ if every $\eta$-electron
subspace is invariant under the action of this operator. Equivalently,
operator $X$ is number-preserving if and only if it commutes with the
particle-number operator, i.e., $\left[N,X\right]=0$. Yet another equivalent
definition is based on the notion of _$\eta$ -electron projections_: letting
$\Pi_{\eta}$ be orthogonal projections onto the $\eta$-electron subspaces,
then $X$ is number-preserving if and only if it commutes with every
$\Pi_{\eta}$, namely, $\left[\Pi_{\eta},X\right]=0$. In the matrix
representation, $X$ is block-diagonalized by the set of $\eta$-electron
projections $\\{\Pi_{\eta}\\}$.

A special example of number-preserving operator is the particle-number
operator $N$, which acts as a scalar multiplication by $\eta$ within the
$\eta$-electron subspace. Other examples include _excitation operators_
$A_{j}^{\dagger}A_{k}$, occupation-number operators $N_{l}$, and elementary
exponentials in the Trotterization algorithm
$e^{-it\sum_{j,k}\tau_{j,k}A_{j}^{\dagger}A_{k}}$ and
$e^{-it\sum_{l,m}\nu_{l,m}N_{l}N_{m}}$. The fermionic Fourier transform [29]
as given below is also number-preserving:666This can alternatively be proved
using the fact that the fermionic Fourier transform is generated by the
fermionic swap and Hadamard gate [6, Appendix I], both of which are number-
preserving.

$\mathrm{FFFT}^{\dagger}\cdot
A_{j}^{\dagger}\cdot\mathrm{FFFT}=\frac{1}{\sqrt{n}}\sum_{l=0}^{n-1}e^{-\frac{2\pi
ijl}{n}}A_{l}^{\dagger},\qquad\mathrm{FFFT}^{\dagger}\cdot
A_{k}\cdot\mathrm{FFFT}=\frac{1}{\sqrt{n}}\sum_{m=0}^{n-1}e^{\frac{2\pi
ikm}{n}}A_{m},$ (31)

since

$\displaystyle\mathrm{FFFT}^{\dagger}\cdot N\cdot\mathrm{FFFT}$
$\displaystyle=\sum_{j=0}^{n-1}\mathrm{FFFT}^{\dagger}\cdot
A_{j}^{\dagger}\cdot\mathrm{FFFT}\cdot\mathrm{FFFT}^{\dagger}\cdot
A_{j}\cdot\mathrm{FFFT}$ (32)
$\displaystyle=\frac{1}{n}\sum_{l,m=0}^{n-1}\left(\sum_{j=0}^{n-1}e^{\frac{2\pi
ij(m-l)}{n}}\right)A_{l}^{\dagger}A_{m}=\sum_{l=0}^{n-1}A_{l}^{\dagger}A_{l}=N.$

In fact, the set of number-preserving operators contains identity and is
closed under linear combination, multiplication, Hermitian conjugation, and
taking limit.

######  Proposition 3 (Number-preserving operators as a closed unital
$\dagger$-subalgebra).

The following operators are respectively number-preserving:

  1. 1.

the identity operator $I$;

  2. 2.

$\lambda X+\mu Y$, if $X$ and $Y$ are number-preserving, and $\lambda$ and
$\mu$ are complex numbers;

  3. 3.

$XY$, if $X$ and $Y$ are number-preserving;

  4. 4.

$X^{\dagger}$, if $X$ is number-preserving;

  5. 5.

$\lim\limits_{i\rightarrow\infty}X_{i}$, if $X_{i}$ are number-preserving and
the limit exists.

###  2.3 Fermionic seminorm

We now introduce the notion of fermionic seminorm, which we use to quantify
the error of the Trotterization algorithm that takes the prior knowledge of
the initial state into consideration.

For any number-preserving operator $X$ and $0\leq\eta\leq n$, we define the
_fermionic $\eta$-seminorm_ as the maximum transition amplitude within the
$\eta$-electron manifold:

$\left\lVert
X\right\rVert_{\eta}:=\max_{\lvert\psi_{\eta}\rangle,\lvert\phi_{\eta}\rangle}\left\lvert\langle\phi_{\eta}\rvert
X\lvert\psi_{\eta}\rangle\right\rvert,$ (33)

where $\lvert\psi_{\eta}\rangle,\lvert\phi_{\eta}\rangle$ are quantum states
containing $\eta$ electrons.777Note that it is possible to extend this to
define $\left\lVert\cdot\right\rVert_{\eta\rightarrow\xi}$ for operators that
map the $\eta$-electron subspace to $\xi$-electron subspace, although this is
not needed in our analysis and will not be further pursued here. When there is
no ambiguity, we drop the dependence on $\eta$ and call $\left\lVert
X\right\rVert_{\eta}$ the fermionic seminorm of $X$. As the name suggests and
the following proposition confirms, the fermionic seminorm is indeed a
seminorm defined on the closed unital $\dagger$-subalgebra of number-
preserving operators.

######  Proposition 4 (Seminorm properties).

The following properties hold for the fermionic seminorm:

  1. 1.

$\left\lVert\lambda
X\right\rVert_{\eta}=\left\lvert\lambda\right\rvert\left\lVert
X\right\rVert_{\eta}$, if $X$ is number-preserving and $\lambda$ is a complex
number;

  2. 2.

$\left\lVert X+Y\right\rVert_{\eta}\leq\left\lVert
X\right\rVert_{\eta}+\left\lVert Y\right\rVert_{\eta}$, if $X$ and $Y$ are
number-preserving;

  3. 3.

$\left\lVert XY\right\rVert_{\eta}\leq\left\lVert
X\right\rVert_{\eta}\left\lVert Y\right\rVert_{\eta}$, if $X$ and $Y$ are
number-preserving;

  4. 4.

$\left\lVert I\right\rVert_{\eta}=1$;

  5. 5.

$\left\lVert UXW\right\rVert_{\eta}=\left\lVert X\right\rVert_{\eta}$, if
$U,X,W$ are number-preserving and $U,W$ are unitary;

  6. 6.

$\left\lVert X^{\dagger}\right\rVert_{\eta}=\left\lVert X\right\rVert_{\eta}$,
if $X$ is number-preserving.

###### Proof.

We will only prove the third statement, as the remaining follow directly from
the definition of the fermionic seminorm. We consider

$\displaystyle\left\lVert XY\right\rVert_{\eta}$
$\displaystyle=\max_{\lvert\psi_{\eta}\rangle,\lvert\phi_{\eta}\rangle}\left\lvert\langle\phi_{\eta}\rvert
XY\lvert\psi_{\eta}\rangle\right\rvert$ (34)
$\displaystyle=\max_{\lvert\psi_{\eta}\rangle,\lvert\phi_{\eta}\rangle}\left\lvert\langle\phi_{\eta}\rvert
X\Pi_{\eta}\Pi_{\eta}Y\lvert\psi_{\eta}\rangle\right\rvert$
$\displaystyle\leq\max_{\lvert\phi_{\eta}\rangle}\left\lVert\Pi_{\eta}X^{\dagger}\lvert\phi_{\eta}\rangle\right\rVert\max_{\lvert\psi_{\eta}\rangle}\left\lVert\Pi_{\eta}Y\lvert\psi_{\eta}\rangle\right\rVert,$

where $\Pi_{\eta}$ is the orthogonal projection onto the $\eta$-electron
subspace and the last step follows from the Cauchy-Schwarz inequality. To
proceed, we optimize over an arbitrary state $\lvert\varphi\rangle$ to get

$\displaystyle\left\lVert\Pi_{\eta}X^{\dagger}\lvert\phi_{\eta}\rangle\right\rVert$
$\displaystyle=\max_{\lvert\varphi\rangle}\left\lvert\langle\varphi\rvert\Pi_{\eta}X^{\dagger}\lvert\phi_{\eta}\rangle\right\rvert$
(35)
$\displaystyle=\max_{\lvert\varphi\rangle}\left\lVert\Pi_{\eta}\lvert\varphi\rangle\right\rVert\left\lvert\frac{\langle\varphi\rvert\Pi_{\eta}}{\left\lVert\Pi_{\eta}\lvert\varphi\rangle\right\rVert}X^{\dagger}\lvert\phi_{\eta}\rangle\right\rvert$
$\displaystyle\leq\left\lVert X^{\dagger}\right\rVert_{\eta}=\left\lVert
X\right\rVert_{\eta}$

assuming $\Pi_{\eta}\lvert\varphi\rangle\neq 0$, as the case
$\Pi_{\eta}\lvert\varphi\rangle=0$ never leads to maximality. But on the other
hand,

$\displaystyle\left\lVert X\right\rVert_{\eta}$ $\displaystyle=\left\lVert
X^{\dagger}\right\rVert_{\eta}=\max_{\lvert\phi_{\eta}\rangle,\lvert\varphi_{\eta}\rangle}\left\lvert\langle\varphi_{\eta}\rvert
X^{\dagger}\lvert\psi_{\eta}\rangle\right\rvert$ (36)
$\displaystyle=\max_{\lvert\phi_{\eta}\rangle,\lvert\varphi_{\eta}\rangle}\left\lvert\langle\varphi_{\eta}\rvert\Pi_{\eta}X^{\dagger}\lvert\psi_{\eta}\rangle\right\rvert$
$\displaystyle\leq\max_{\lvert\phi_{\eta}\rangle,\lvert\varphi\rangle}\left\lvert\langle\varphi\rvert\Pi_{\eta}X^{\dagger}\lvert\psi_{\eta}\rangle\right\rvert=\max_{\lvert\phi_{\eta}\rangle}\left\lVert\Pi_{\eta}X^{\dagger}\lvert\phi_{\eta}\rangle\right\rVert,$

implying
$\max_{\lvert\phi_{\eta}\rangle}\left\lVert\Pi_{\eta}X^{\dagger}\lvert\phi_{\eta}\rangle\right\rVert=\left\lVert
X\right\rVert_{\eta}$. Similarly, we have
$\max_{\lvert\psi_{\eta}\rangle}\left\lVert\Pi_{\eta}Y\lvert\psi_{\eta}\rangle\right\rVert=\left\lVert
Y\right\rVert_{\eta}$. This completes the proof of the third statement. ∎

The fermionic seminorm, as defined in (33) by the maximum transition amplitude
within the $\eta$-electron manifold, provides a reasonable metric for
quantifying the error of digital quantum simulation with initial-state
constraints. Indeed, a seminorm similar to our definition was used by Somma
[73] for analyzing quantum simulation of bosonic Hamiltonians. However, we
point out that this is not the only error metric that takes the prior
knowledge of the initial state into account. Recent work [69] analyzed the
low-energy simulation of $k$-local frustration-free Hamiltonians by computing
the spectral norm of Trotter error projected on the low-energy subspace.
However, the following proposition shows that these two error metrics are the
same for fermionic systems.

######  Proposition 5 (Fermionic seminorm as a projected spectral norm).

For any number-preserving operator $X$, it holds that

$\left\lVert
X\right\rVert_{\eta}=\max_{\lvert\psi_{\eta}\rangle,\lvert\phi_{\eta}\rangle}\left\lvert\langle\phi_{\eta}\rvert
X\lvert\psi_{\eta}\rangle\right\rvert=\left\lVert X\Pi_{\eta}\right\rVert.$
(37)

###### Proof.

The underlying idea behind this proposition is already hinted in the proof of
Proposition 4. We have

$\displaystyle\max_{\lvert\psi_{\eta}\rangle,\lvert\phi_{\eta}\rangle}\left\lvert\langle\phi_{\eta}\rvert
X\lvert\psi_{\eta}\rangle\right\rvert$
$\displaystyle=\max_{\lvert\psi_{\eta}\rangle,\lvert\phi_{\eta}\rangle}\left\lvert\langle\phi_{\eta}\rvert\Pi_{\eta}X\Pi_{\eta}\lvert\psi_{\eta}\rangle\right\rvert$
(38)
$\displaystyle\leq\max_{\lvert\psi\rangle,\lvert\phi\rangle}\left\lvert\langle\phi\rvert\Pi_{\eta}X\Pi_{\eta}\lvert\psi\rangle\right\rvert=\left\lVert\Pi_{\eta}X\Pi_{\eta}\right\rVert.$

But on the other hand,

$\displaystyle\left\lVert\Pi_{\eta}X\Pi_{\eta}\right\rVert$
$\displaystyle=\max_{\lvert\psi\rangle,\lvert\phi\rangle}\left\lvert\langle\phi\rvert\Pi_{\eta}X\Pi_{\eta}\lvert\psi\rangle\right\rvert$
(39)
$\displaystyle=\max_{\lvert\psi\rangle,\lvert\phi\rangle}\left\lVert\Pi_{\eta}\lvert\phi\rangle\right\rVert\left\lVert\Pi_{\eta}\lvert\psi\rangle\right\rVert\left\lvert\frac{\langle\phi\rvert\Pi_{\eta}}{\left\lVert\Pi_{\eta}\lvert\phi\rangle\right\rVert}X\frac{\Pi_{\eta}\lvert\psi\rangle}{\left\lVert\Pi_{\eta}\lvert\psi\rangle\right\rVert}\right\rvert$
$\displaystyle\leq\max_{\lvert\psi_{\eta}\rangle,\lvert\phi_{\eta}\rangle}\left\lvert\langle\phi_{\eta}\rvert
X\lvert\psi_{\eta}\rangle\right\rvert$

assuming $\Pi_{\eta}\lvert\phi\rangle\neq 0$ and
$\Pi_{\eta}\lvert\psi\rangle\neq 0$, as the zero vector will not lead to
maximality. The proposition then follows since number-preserving operator $X$
commutes with the $\eta$-electron projection $\Pi_{\eta}$. ∎

Another common approach to quantify the error of digital quantum simulation is
to take the maximum expectation
$\max_{\lvert\psi_{\eta}\rangle}\left\lvert\langle\psi_{\eta}\rvert\cdot\lvert\psi_{\eta}\rangle\right\rvert$
within the $\eta$-electron manifold. This approach is used by previous work
[6, 65, 28] and appears to give a natural metric when digital quantum
simulation is used as a subroutine in phase estimation. We show that this only
differs from our definition (33) by at most a constant factor, reaffirming the
fermionic seminorm as a proper error metric for simulating fermionic systems.

######  Proposition 6 (Transition amplitude and expectation).

For any number-preserving operator $X$, the following statements hold:

  1. 1.

$\max_{\lvert\psi_{\eta}\rangle,\lvert\phi_{\eta}\rangle}\left\lvert\langle\phi_{\eta}\rvert
X\lvert\psi_{\eta}\rangle\right\rvert=\max_{\lvert\psi_{\eta}\rangle}\left\lvert\langle\psi_{\eta}\rvert
X\lvert\psi_{\eta}\rangle\right\rvert$, if $X$ is Hermitian;

  2. 2.

$\max_{\lvert\psi_{\eta}\rangle,\lvert\phi_{\eta}\rangle}\left\lvert\langle\phi_{\eta}\rvert
X\lvert\psi_{\eta}\rangle\right\rvert=\max_{\lvert\psi_{\eta}\rangle}\sqrt{\langle\psi_{\eta}\rvert
X^{\dagger}X\lvert\psi_{\eta}\rangle}$ (equivalently, $\left\lVert
X^{\dagger}X\right\rVert_{\eta}=\left\lVert X\right\rVert_{\eta}^{2}$);

  3. 3.

$\max_{\lvert\psi_{\eta}\rangle}\left\lvert\langle\psi_{\eta}\rvert
X\lvert\psi_{\eta}\rangle\right\rvert\leq\max_{\lvert\psi_{\eta}\rangle,\lvert\phi_{\eta}\rangle}\left\lvert\langle\phi_{\eta}\rvert
X\lvert\psi_{\eta}\rangle\right\rvert\leq
2\max_{\lvert\psi_{\eta}\rangle}\left\lvert\langle\psi_{\eta}\rvert
X\lvert\psi_{\eta}\rangle\right\rvert$.888Note that the second inequality is
tight by considering $X=A_{0}^{\dagger}A_{1}$ on a fermionic system with two
spin orbitals and one electron.

###### Proof.

The first statement follows from the fact that $\Pi_{\eta}X\Pi_{\eta}$ is
Hermitian and that the spectral norm of a Hermitian operator is its largest
eigenvalue in absolute value. For the second statement,

$\max_{\lvert\psi_{\eta}\rangle,\lvert\phi_{\eta}\rangle}\left\lvert\langle\phi_{\eta}\rvert
X\lvert\psi_{\eta}\rangle\right\rvert=\left\lVert
X\right\rVert_{\eta}=\left\lVert
X\Pi_{\eta}\right\rVert=\sqrt{\left\lVert\Pi_{\eta}X^{\dagger}X\Pi_{\eta}\right\rVert}=\max_{\lvert\psi_{\eta}\rangle}\sqrt{\langle\psi_{\eta}\rvert
X^{\dagger}X\lvert\psi_{\eta}\rangle}.$ (40)

The first inequality of Statement 3 is trivial. For the second inequality, we
apply the polarization identity

$\displaystyle\langle\phi_{\eta}\rvert X\lvert\psi_{\eta}\rangle$
$\displaystyle=\frac{1}{4}\Big{(}\left(\langle\phi_{\eta}\rvert+\langle\psi_{\eta}\rvert\right)X\left(\lvert\phi_{\eta}\rangle+\lvert\psi_{\eta}\rangle\right)-\left(\langle\phi_{\eta}\rvert-\langle\psi_{\eta}\rvert\right)X\left(\lvert\phi_{\eta}\rangle-\lvert\psi_{\eta}\rangle\right)$
(41)
$\displaystyle\qquad\quad-i\left(\langle\phi_{\eta}\rvert-i\langle\psi_{\eta}\rvert\right)X\left(\lvert\phi_{\eta}\rangle+i\lvert\psi_{\eta}\rangle\right)+i\left(\langle\phi_{\eta}\rvert+i\langle\psi_{\eta}\rvert\right)X\left(\lvert\phi_{\eta}\rangle-i\lvert\psi_{\eta}\rangle\right)\Big{)}$

to obtain

$\displaystyle\left\lvert\langle\phi_{\eta}\rvert
X\lvert\psi_{\eta}\rangle\right\rvert$ (42)
$\displaystyle\leq\frac{\max_{\lvert\varphi_{\eta}\rangle}\left\lvert\langle\varphi_{\eta}\rvert
X\lvert\varphi_{\eta}\rangle\right\rvert}{4}\left(\left\lVert\lvert\phi_{\eta}\rangle+\lvert\psi_{\eta}\rangle\right\rVert^{2}+\left\lVert\lvert\phi_{\eta}\rangle-\lvert\psi_{\eta}\rangle\right\rVert^{2}+\left\lVert\lvert\phi_{\eta}\rangle+i\lvert\psi_{\eta}\rangle\right\rVert^{2}+\left\lVert\lvert\phi_{\eta}\rangle-i\lvert\psi_{\eta}\rangle\right\rVert^{2}\right)$
$\displaystyle=2\max_{\lvert\varphi_{\eta}\rangle}\left\lvert\langle\varphi_{\eta}\rvert
X\lvert\varphi_{\eta}\rangle\right\rvert,$

from which the claimed inequality follows by maximizing over states
$\lvert\psi_{\eta}\rangle$ and $\lvert\phi_{\eta}\rangle$. ∎

We now apply Proposition 1 to compute the fermionic seminorm of Trotter error,
obtaining

$\left\lVert\mathscr{S}_{p}(t)-e^{-itH}\right\rVert_{\eta}=\mathcal{O}\left(\max_{\boldsymbol{\gamma}}\left\lVert\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]\right\rVert_{\eta}t^{p+1}\right).$
(43)

We find that the resulting error bound depends on the fermionic seminorm of
nested commutators, and the performance of digital quantum simulation can thus
be potentially improved by simultaneously exploiting commutativity of the
Hamiltonian and prior knowledge of the initial state. However, the main
difficulty here is to give a tight estimate of
$\left\lVert\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]\right\rVert_{\eta}$,
which seems technically challenging to address. To this end, we develop two
approaches for bounding the expectation/transition amplitude of general
fermionic operators in Section 3 and Section 4 and prove our main result
Theorem 1, establish the tightness of our bound in Section 5, and discuss
applications and further implications of our result in Section 6 and Section
7.

##  3 Recursive bound on the expectation of fermionic operators

In this section, we present our first approach for bounding the expectation of
fermionic operators, and thereby bounding the fermionic seminorm of Trotter
error. We introduce in Section 3.1 the main techniques used in our approach,
including an operator Cauchy-Schwarz inequality, a diagonalization procedure,
and a Hölder-type inequality for the expectation value. We then describe our
approach in detail and apply it to prove Eq. (2) of our main result Theorem 1.
The proof is based on induction: we analyze the base case in Section 3.2 and
the inductive step in Section 3.3, respectively.

###  3.1 Main techniques

Recall that the main technical challenge to estimate the simulation error of
the electronic Hamiltonian (1) is to bound the fermionic seminorm
$\left\lVert\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]\right\rVert_{\eta}$,
where $\gamma_{j}=0,1$, $H_{0}=V$ and $H_{1}=T$. Applying the commutation
relations in Proposition 2, we see that we need to analyze a general fermionic
operator of the form

$X=\sum_{\boldsymbol{j},\boldsymbol{k},\boldsymbol{l}}w_{\boldsymbol{j},\boldsymbol{k},\boldsymbol{l}}\
\cdots A_{j_{x}}^{\dagger}\cdots N_{l_{z}}\cdots A_{k_{y}}\cdots$ (44)

Our first approach starts by reexpressing the fermionic seminorm of $X$ using
the expectation of $X^{\dagger}X$:

$\left\lVert
X\right\rVert_{\eta}=\max_{\lvert\psi_{\eta}\rangle}\sqrt{\langle\psi_{\eta}\rvert
X^{\dagger}X\lvert\psi_{\eta}\rangle}.$ (45)

We note that $X^{\dagger}X$ is a positive semidefinite operator, and an upper
bound of it with respect to the partial ordering of positive semidefiniteness
will therefore give a bound on the expectation value. We achieve this by
contracting the corresponding indices in $X$ and $X^{\dagger}$, using either
an operator Cauchy-Schwarz inequality (Lemma 1) or diagonalization (Lemma 2).

######  Lemma 1 (Operator Cauchy-Schwarz inequality [61, Proposition 3.4]).

For any finite lists of operators $\\{B_{j}\\}$ and $\\{C_{j}\\}$ with the
same cardinality, we have

$-\sum_{j,k}B_{j}^{\dagger}C_{k}^{\dagger}C_{k}B_{j}\leq\sum_{j,k}B_{j}^{\dagger}C_{k}^{\dagger}C_{j}B_{k}\leq\sum_{j,k}B_{j}^{\dagger}C_{k}^{\dagger}C_{k}B_{j},$
(46)

where Hermitian operators are partially ordered according to the positive
semidefiniteness.

###### Proof.

We have

$\displaystyle 0$ $\displaystyle\leq\sum_{j,k}\left(C_{k}B_{j}\mp
C_{j}B_{k}\right)^{\dagger}\left(C_{k}B_{j}\mp C_{j}B_{k}\right)$ (47)
$\displaystyle=\sum_{j,k}\left(B_{j}^{\dagger}C_{k}^{\dagger}C_{k}B_{j}\mp
B_{k}^{\dagger}C_{j}^{\dagger}C_{k}B_{j}\mp
B_{j}^{\dagger}C_{k}^{\dagger}C_{j}B_{k}+B_{k}^{\dagger}C_{j}^{\dagger}C_{j}B_{k}\right)$
$\displaystyle=2\sum_{j,k}B_{j}^{\dagger}C_{k}^{\dagger}C_{k}B_{j}\mp
2\sum_{j,k}B_{j}^{\dagger}C_{k}^{\dagger}C_{j}B_{k}.$

This implies

$\pm\sum_{j,k}B_{j}^{\dagger}C_{k}^{\dagger}C_{j}B_{k}\leq\sum_{jk}B_{j}^{\dagger}C_{k}^{\dagger}C_{k}B_{j},$
(48)

from which the claimed inequality follows. ∎

######  Lemma 2 (Diagonalization).

For any finite list of operators $\\{B_{j}\\}$ and Hermitian coefficient
matrix $\mu$, we have

$-\left\lVert\mu\right\rVert\sum_{j}B_{j}^{\dagger}B_{j}\leq\sum_{j,k}\mu_{j,k}B_{j}^{\dagger}B_{k}\leq\left\lVert\mu\right\rVert\sum_{j}B_{j}^{\dagger}B_{j},$
(49)

where Hermitian operators are partially ordered according to the positive
semidefiniteness.

###### Proof.

Since $\mu$ is Hermitian, we may diagonalize it to $\widetilde{\mu}$ by
unitary transformation $w$ as

$\mu=w^{\dagger}\widetilde{\mu}w,$ (50)

where $\widetilde{\mu}$ is a diagonal matrix with all eigenvalues of $\mu$ as
the diagonal elements. We then define
$\widetilde{B}_{l}:=\sum_{k}w_{l,k}B_{k}$ so that

$\sum_{j,k}\mu_{j,k}B_{j}^{\dagger}B_{k}=\sum_{l}\widetilde{\mu}_{l}\widetilde{B}_{l}^{\dagger}\widetilde{B}_{l},$
(51)

which implies

$-\left\lVert\mu\right\rVert\sum_{l}\widetilde{B}_{l}^{\dagger}\widetilde{B}_{l}\leq\sum_{j,k}\mu_{j,k}B_{j}^{\dagger}B_{k}\leq\left\lVert\mu\right\rVert\sum_{l}\widetilde{B}_{l}^{\dagger}\widetilde{B}_{l}.$
(52)

But $\sum_{l}\widetilde{B}_{l}^{\dagger}\widetilde{B}_{l}$ has identity as the
coefficient matrix which is invariant under a change of basis:

$\sum_{l}\widetilde{B}_{l}^{\dagger}\widetilde{B}_{l}=\sum_{j}B_{j}^{\dagger}B_{j}.$
(53)

This completes the proof. ∎

By applying Lemma 1 or Lemma 2, we can get a bound of $X^{\dagger}X$ with
respect to the partial ordering of positive semidefiniteness, with one pair of
the corresponding indices in $X$ and $X^{\dagger}$ contracted. Indeed, these
techniques were used by Otte to establish the boundedness of quadratic
fermionic operators in infinite-dimensional Hilbert spaces [61]. However, the
difficulty here is that we need to handle more complex products of fermionic
operators in the Trotter error estimate. To this end, we prove a Hölder-type
inequality for the expectation value, which allows us to apply Lemma 1 and
Lemma 2 recursively to get a desired bound.

######  Lemma 3 (Hölder-type inequality for expectation).

For any finite lists of fermionic operators $\\{B_{j}\\}$ and $\\{C_{k}\\}$
with the same cardinality,

$\max_{\lvert\psi_{\eta}\rangle}\langle\psi_{\eta}\rvert\sum_{j}B_{j}^{\dagger}C_{j}^{\dagger}C_{j}B_{j}\lvert\psi_{\eta}\rangle\leq\max_{\lvert\psi_{\eta}\rangle}\langle\psi_{\eta}\rvert\sum_{j}B_{j}^{\dagger}B_{j}\lvert\psi_{\eta}\rangle\max_{k,\lvert\phi_{\xi}\rangle}\langle\phi_{\xi}\rvert
C_{k}^{\dagger}C_{k}\lvert\phi_{\xi}\rangle,$ (54)

where we assume $B_{j}$ map the $\eta$-electron subspace to the $\xi$-electron
subspace and $C_{j}$ are number-preserving. In terms of the fermionic
seminorm, we have

$\Big{\|}\sum_{j}B_{j}^{\dagger}C_{j}^{\dagger}C_{j}B_{j}\Big{\|}_{\eta}\leq\Big{\|}\sum_{j}B_{j}^{\dagger}B_{j}\Big{\|}_{\eta}\max_{k}\left\lVert
C_{k}^{\dagger}C_{k}\right\rVert_{\xi}.$ (55)

###### Proof.

The claimed inequality follows from

$\displaystyle\Big{\|}\sum_{j}B_{j}^{\dagger}C_{j}^{\dagger}C_{j}B_{j}\Big{\|}_{\eta}$
$\displaystyle=\Big{\|}\sum_{j}B_{j}^{\dagger}\Pi_{\xi}C_{j}^{\dagger}C_{j}\Pi_{\xi}B_{j}\Big{\|}_{\eta}$
(56)
$\displaystyle\leq\bigg{\|}\sum_{j}\left\lVert\Pi_{\xi}C_{j}^{\dagger}C_{j}\Pi_{\xi}\right\rVert
B_{j}^{\dagger}B_{j}\bigg{\|}_{\eta}$
$\displaystyle\leq\Big{\|}\sum_{j}B_{j}^{\dagger}B_{j}\Big{\|}_{\eta}\max_{k}\left\lVert\Pi_{\xi}C_{k}^{\dagger}C_{k}\Pi_{\xi}\right\rVert$
$\displaystyle=\Big{\|}\sum_{j}B_{j}^{\dagger}B_{j}\Big{\|}_{\eta}\max_{k}\left\lVert
C_{k}^{\dagger}C_{k}\right\rVert_{\xi}.$

∎

Using the above lemmas, we can now prove Eq. (2) of our main result Theorem 1
by induction. We analyze the base case in Section 3.2 and the inductive step
in Section 3.3.

###  3.2 Single-layer commutator

We now prove Eq. (2) of our main result Theorem 1 by induction. In the base
case, we consider simulating the interacting-electronic Hamiltonian (1) using
the first-order formula $\mathscr{S}_{1}(t)$. We know from (19) that

$\left\lVert\mathscr{S}_{1}(t)-e^{-itH}\right\rVert_{\eta}\leq\frac{t^{2}}{2}\left\lVert\left[T,V\right]\right\rVert_{\eta},$
(57)

where $T=\sum_{j,k}\tau_{j,k}A_{j}^{\dagger}A_{k}$ and
$V=\sum_{l,m}\nu_{l,m}N_{l}N_{m}$. Our goal is to show that

$\left\lVert\left[T,V\right]\right\rVert_{\eta}=\mathcal{O}\left(\left\lVert\tau\right\rVert\left\lVert\nu\right\rVert_{\max}\eta^{2}\right).$
(58)

To this end, we apply Proposition 2 to expand the single-layer commutator
$\left[T,V\right]$ into linear combinations of fermionic creation,
annihilation, and occupation-number operators. We have

$\displaystyle\left[T,V\right]$
$\displaystyle=\sum_{j,k,l,m}\tau_{j,k}\nu_{l,m}\left[A_{j}^{\dagger}A_{k},N_{l}N_{m}\right]$
(59)
$\displaystyle=\sum_{j,k,l,m}\tau_{j,k}\nu_{l,m}A_{j}^{\dagger}\left[A_{k},N_{l}N_{m}\right]+\sum_{j,k,l,m}\tau_{j,k}\nu_{l,m}\left[A_{j}^{\dagger},N_{l}N_{m}\right]A_{k}$
$\displaystyle=\sum_{j,k,m}\tau_{j,k}\nu_{k,m}A_{j}^{\dagger}A_{k}N_{m}+\sum_{j,k,l}\tau_{j,k}\nu_{l,k}A_{j}^{\dagger}N_{l}A_{k}$
$\displaystyle\quad-\sum_{j,k,m}\tau_{j,k}\nu_{j,m}A_{j}^{\dagger}N_{m}A_{k}-\sum_{j,k,l}\tau_{j,k}\nu_{l,j}N_{l}A_{j}^{\dagger}A_{k}.$

At this stage, it is possible to directly bound the terms in the last equality
using Lemma 1, Lemma 2, and Lemma 3 from the previous subsection. However, we
will further commute the occupation-number operator in between the creation
and annihilation operators, obtaining

$\displaystyle\left[T,V\right]$
$\displaystyle=\sum_{j,k,m}\tau_{j,k}\nu_{k,m}A_{j}^{\dagger}N_{m}A_{k}+\sum_{j,k}\tau_{j,k}\nu_{k,k}A_{j}^{\dagger}A_{k}+\sum_{j,k,l}\tau_{j,k}\nu_{l,k}A_{j}^{\dagger}N_{l}A_{k}$
(60)
$\displaystyle\quad-\sum_{j,k,m}\tau_{j,k}\nu_{j,m}A_{j}^{\dagger}N_{m}A_{k}-\sum_{j,k}\tau_{j,k}\nu_{j,j}A_{j}^{\dagger}A_{k}-\sum_{j,k,l}\tau_{j,k}\nu_{l,j}A_{j}^{\dagger}N_{l}A_{k}.$

This additional commutation leads to an error bound with the same asymptotic
scaling but a slightly larger prefactor. The benefit is that the analysis can
be directly extended to handle the inductive step in the next subsection.

######  Proposition 7 (Structure of single-layer commutator).

Let
$H=T+V=\sum_{j,k}\tau_{j,k}A_{j}^{\dagger}A_{k}+\sum_{l,m}\nu_{l,m}N_{l}N_{m}$
be an interacting-electronic Hamiltonian (1). Then, the commutator $[T,V]$ has
the expansion

$\displaystyle\left[T,V\right]$
$\displaystyle=\sum_{j,k,m}\tau_{j,k}\nu_{k,m}A_{j}^{\dagger}N_{m}A_{k}+\sum_{j,k}\tau_{j,k}\nu_{k,k}A_{j}^{\dagger}A_{k}+\sum_{j,k,l}\tau_{j,k}\nu_{l,k}A_{j}^{\dagger}N_{l}A_{k}$
(61)
$\displaystyle\quad-\sum_{j,k,m}\tau_{j,k}\nu_{j,m}A_{j}^{\dagger}N_{m}A_{k}-\sum_{j,k}\tau_{j,k}\nu_{j,j}A_{j}^{\dagger}A_{k}-\sum_{j,k,l}\tau_{j,k}\nu_{l,j}A_{j}^{\dagger}N_{l}A_{k}.$

It is worth noting that the above six terms from the expansion of $[T,V]$
share a similar structure. Specifically, they all consist of creation operator
$A_{j}^{\dagger}$, annihilation operator $A_{k}$, and (possibly) occupation-
number operator $N_{l}$, with one coefficient matrix $\tau$ and one matrix
$\nu$. The main difference between these terms is that the coefficient matrix
$\nu$ is acting on different indices. See Figure 1 for a graph illustration of
this structure.

$j$$k$$m$$\tau$$\nu$ (a)
$\sum_{j,k,m}\tau_{j,k}\nu_{k,m}A_{j}^{\dagger}N_{m}A_{k}$

$j$$k$$\tau$$\nu$ (b) $\sum_{j,k}\tau_{j,k}\nu_{k,k}A_{j}^{\dagger}A_{k}$

$j$$k$$l$$\tau$$\nu$ (c)
$\sum_{j,k,l}\tau_{j,k}\nu_{l,k}A_{j}^{\dagger}N_{l}A_{k}$

$j$$k$$m$$\tau$$\nu$ (d)
$\sum_{j,k,m}\tau_{j,k}\nu_{j,m}A_{j}^{\dagger}N_{m}A_{k}$

$j$$k$$\tau$$\nu$ (e) $\sum_{j,k}\tau_{j,k}\nu_{j,j}A_{j}^{\dagger}A_{k}$

$j$$k$$l$$\tau$$\nu$ (f)
$\sum_{j,k,l}\tau_{j,k}\nu_{l,j}A_{j}^{\dagger}N_{l}A_{k}$

Figure 1: Graph illustration of the expansion terms from the single-layer
commutator $[T,V]$. Here, vertices in the graph denote the indices in the
summation and edges represent the coefficients. Note that the graphs can be
made directional so that they are one-to-one corresponding to fermionic
operators, although this is not needed in our analysis and will not be further
pursued here.

We now bound the asymptotic scaling of the fermionic seminorm for each of the
six terms in the commutator expansion.

######  Proposition 8 (Fermionic seminorm of single-layer commutator).

Let
$H=T+V=\sum_{j,k}\tau_{j,k}A_{j}^{\dagger}A_{k}+\sum_{l,m}\nu_{l,m}N_{l}N_{m}$
be an interacting-electronic Hamiltonian (1). Then,

  1. 1.

$\left\lVert\sum_{j,k,m}\tau_{j,k}\nu_{k,m}A_{j}^{\dagger}N_{m}A_{k}\right\rVert_{\eta}\leq\left\lVert\tau\right\rVert\left\lVert\nu\right\rVert_{\max}\eta^{2}$;

  2. 2.

$\left\lVert\sum_{j,k}\tau_{j,k}\nu_{k,k}A_{j}^{\dagger}A_{k}\right\rVert_{\eta}\leq\left\lVert\tau\right\rVert\left\lVert\nu\right\rVert_{\max}\eta$;

  3. 3.

$\left\lVert\sum_{j,k,l}\tau_{j,k}\nu_{l,k}A_{j}^{\dagger}N_{l}A_{k}\right\rVert_{\eta}\leq\left\lVert\tau\right\rVert\left\lVert\nu\right\rVert_{\max}\eta^{2}$;

  4. 4.

$\left\lVert\sum_{j,k,m}\tau_{j,k}\nu_{j,m}A_{j}^{\dagger}N_{m}A_{k}\right\rVert_{\eta}\leq\left\lVert\tau\right\rVert\left\lVert\nu\right\rVert_{\max}\eta^{2}$;

  5. 5.

$\left\lVert\sum_{j,k}\tau_{j,k}\nu_{j,j}A_{j}^{\dagger}A_{k}\right\rVert_{\eta}\leq\left\lVert\tau\right\rVert\left\lVert\nu\right\rVert_{\max}\eta$;

  6. 6.

$\left\lVert\sum_{j,k,l}\tau_{j,k}\nu_{l,j}A_{j}^{\dagger}N_{l}A_{k}\right\rVert_{\eta}\leq\left\lVert\tau\right\rVert\left\lVert\nu\right\rVert_{\max}\eta^{2}$.

###### Proof.

We present the proof of the first two statements here. The remaining
justifications proceed in a similar way and are left to Appendix A.

Letting $X=\sum_{j,k,m}\tau_{j,k}\nu_{k,m}A_{j}^{\dagger}N_{m}A_{k}$, we have
$\left\lVert X\right\rVert_{\eta}=\sqrt{\left\lVert
X^{\dagger}X\right\rVert_{\eta}}$. Now,

$\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}_{k_{1},m_{1}}\tau_{j_{2},k_{2}}\nu_{k_{2},m_{2}}A_{k_{1}}^{\dagger}N_{m_{1}}A_{j_{1}}A_{j_{2}}^{\dagger}N_{m_{2}}A_{k_{2}}$
(62)
$\displaystyle=\sum_{j_{1},k_{1},m_{1},k_{2},m_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{k_{1},m_{1}}\tau_{j_{1},k_{2}}\nu_{k_{2},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}_{k_{1},m_{1}}\tau_{j_{2},k_{2}}\nu_{k_{2},m_{2}}A_{k_{1}}^{\dagger}N_{m_{1}}A_{j_{2}}^{\dagger}A_{j_{1}}N_{m_{2}}A_{k_{2}},$

where $\bar{\tau}_{j_{1},k_{1}}$ is the complex conjugate of
$\tau_{j_{1},k_{1}}$ and we have used the anti-commutation relation
$A_{j_{1}}A_{j_{2}}^{\dagger}+A_{j_{2}}^{\dagger}A_{j_{1}}=\delta_{j_{1},j_{2}}I$.
For the second term, we let
$B_{j_{1}}^{\dagger}=\sum_{k_{1},m_{1}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{k_{1},m_{1}}A_{k_{1}}^{\dagger}N_{m_{1}}$
and apply the operator Cauchy-Schwarz inequality (Lemma 1):

$\displaystyle-\sum_{j_{1},k_{1},m_{1},j_{2},k_{2},m_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{k_{1},m_{1}}\tau_{j_{2},k_{2}}\nu_{k_{2},m_{2}}A_{k_{1}}^{\dagger}N_{m_{1}}A_{j_{2}}^{\dagger}A_{j_{1}}N_{m_{2}}A_{k_{2}}$
(63) $\displaystyle=$
$\displaystyle-\sum_{j_{1},j_{2}}B_{j_{1}}^{\dagger}A_{j_{2}}^{\dagger}A_{j_{1}}B_{j_{2}}\leq\sum_{j_{1},j_{2}}B_{j_{1}}^{\dagger}A_{j_{2}}^{\dagger}A_{j_{2}}B_{j_{1}}=\sum_{j_{1}}B_{j_{1}}^{\dagger}NB_{j_{1}}$
$\displaystyle=$
$\displaystyle\sum_{j_{1}}\sum_{k_{1},m_{1},k_{2},m_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{k_{1},m_{1}}\tau_{j_{1},k_{2}}\nu_{k_{2},m_{2}}A_{k_{1}}^{\dagger}N_{m_{1}}NN_{m_{2}}A_{k_{2}}$
$\displaystyle=$
$\displaystyle\sum_{j_{1}}\sum_{k_{1},m_{1},k_{2},m_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{k_{1},m_{1}}\tau_{j_{1},k_{2}}\nu_{k_{2},m_{2}}A_{k_{1}}^{\dagger}N_{m_{1}}N_{m_{2}}A_{k_{2}}N$
$\displaystyle-\sum_{j_{1}}\sum_{k_{1},m_{1},k_{2},m_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{k_{1},m_{1}}\tau_{j_{1},k_{2}}\nu_{k_{2},m_{2}}A_{k_{1}}^{\dagger}N_{m_{1}}N_{m_{2}}A_{k_{2}}.$

This implies

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

Note that $\sum_{j_{1}}\bar{\tau}_{j_{1},k_{1}}\tau_{j_{1},k_{2}}$ gives the
$(k_{1},k_{2})$ matrix element of $\tau^{\dagger}\tau$. Then, we define
$C_{k_{1}}^{\dagger}=\sum_{m_{1}}\bar{\nu}_{k_{1},m_{1}}A_{k_{1}}^{\dagger}N_{m_{1}}$
and perform diagonalization (Lemma 2):

$\displaystyle\sum_{k_{1},k_{2}}\left(\sum_{j_{1}}\bar{\tau}_{j_{1},k_{1}}\tau_{j_{1},k_{2}}\right)\left(\sum_{m_{1}}\bar{\nu}_{k_{1},m_{1}}A_{k_{1}}^{\dagger}N_{m_{1}}\right)\left(\sum_{m_{2}}\nu_{k_{2},m_{2}}N_{m_{2}}A_{k_{2}}\right)$
(65) $\displaystyle=$
$\displaystyle\sum_{k_{1},k_{2}}\left(\tau^{\dagger}\tau\right)_{k_{1},k_{2}}C_{k_{1}}^{\dagger}C_{k_{2}}\leq\left\lVert\tau^{\dagger}\tau\right\rVert\sum_{k_{1}}C_{k_{1}}^{\dagger}C_{k_{1}}$
$\displaystyle=$
$\displaystyle\left\lVert\tau^{\dagger}\tau\right\rVert\sum_{k_{1}}\sum_{m_{1},m_{2}}\bar{\nu}_{k_{1},m_{1}}\nu_{k_{1},m_{2}}A_{k_{1}}^{\dagger}N_{m_{1}}N_{m_{2}}A_{k_{1}}.$

Now that the indices $k_{1}$ and $k_{2}$ are contracted, we can apply the
Hölder-type inequality for the expectation value (Lemma 3). To this end, we
let $D_{k_{1}}^{\dagger}=\sum_{m_{1}}\bar{\nu}_{k_{1},m_{1}}N_{m_{1}}$ and
compute

$\displaystyle\left\lVert\sum_{k_{1}}\sum_{m_{1},m_{2}}\bar{\nu}_{k_{1},m_{1}}\nu_{k_{1},m_{2}}A_{k_{1}}^{\dagger}N_{m_{1}}N_{m_{2}}A_{k_{1}}\right\rVert_{\eta}$
$\displaystyle=\left\lVert\sum_{k_{1}}A_{k_{1}}^{\dagger}D_{k_{1}}^{\dagger}D_{k_{1}}A_{k_{1}}\right\rVert_{\eta}$
(66)
$\displaystyle\leq\left\lVert\sum_{k_{1}}A_{k_{1}}^{\dagger}A_{k_{1}}\right\rVert_{\eta}\max_{k_{1}}\left\lVert
D_{k_{1}}^{\dagger}D_{k_{1}}\right\rVert_{\eta-1}.$

The first factor can be directly bounded as

$\left\lVert\sum_{k_{1}}A_{k_{1}}^{\dagger}A_{k_{1}}\right\rVert_{\eta}=\left\lVert
N\right\rVert_{\eta}=\eta.$ (67)

For the second factor, we have

$\displaystyle D_{k_{1}}^{\dagger}D_{k_{1}}$
$\displaystyle=\sum_{m_{1},m_{2}}\bar{\nu}_{k_{1},m_{1}}\nu_{k_{1},m_{2}}N_{m_{1}}N_{m_{2}}=\sum_{m_{1},m_{2}}\bar{\nu}_{k_{1},m_{1}}\nu_{k_{1},m_{2}}N_{m_{1}}N_{m_{2}}N_{m_{1}}$
(68)
$\displaystyle\leq\left\lVert\nu\right\rVert_{\max}^{2}\sum_{m_{1},m_{2}}N_{m_{1}}N_{m_{2}}N_{m_{1}}=\left\lVert\nu\right\rVert_{\max}^{2}N^{2},$

which implies

$\left\lVert
D_{k_{1}}^{\dagger}D_{k_{1}}\right\rVert_{\eta-1}\leq\left\lVert\nu\right\rVert_{\max}^{2}\eta^{2}.$
(69)

Combining (64), (65), (66), (67), and (69) establishes the first statement.

For the second statement, we let
$X=\sum_{j,k}\tau_{j,k}\nu_{k,k}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}_{k_{1},k_{1}}\tau_{j_{2},k_{2}}\nu_{k_{2},k_{2}}A_{k_{1}}^{\dagger}A_{j_{1}}A_{j_{2}}^{\dagger}A_{k_{2}}$
(70)
$\displaystyle=\sum_{j_{1},k_{1},k_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{k_{1},k_{1}}\tau_{j_{1},k_{2}}\nu_{k_{2},k_{2}}A_{k_{1}}^{\dagger}A_{k_{2}}-\sum_{j_{1},k_{1},j_{2},k_{2}}\bar{\tau}_{j_{1},k_{1}}\bar{\nu}_{k_{1},k_{1}}\tau_{j_{2},k_{2}}\nu_{k_{2},k_{2}}A_{k_{1}}^{\dagger}A_{j_{2}}^{\dagger}A_{j_{1}}A_{k_{2}}.$

Applying Lemma 1,

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

Performing diagonalization using Lemma 2, we have

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

Note that we could directly bound the above operators as
$\left\lVert\tau\right\rVert^{2}\left\lVert\nu\right\rVert_{\max}^{2}N^{2}$
and thereby complete the proof. But we choose to instead apply Lemma 3 so that
the analysis can then be directly extended to analyze multilayer nested
commutators. We have

$\displaystyle\left\lVert X^{\dagger}X\right\rVert_{\eta}$
$\displaystyle\leq\left\lVert\left\lVert\tau\right\rVert^{2}\sum_{k_{1}}\bar{\nu}_{k_{1},k_{1}}\nu_{k_{1},k_{1}}A_{k_{1}}^{\dagger}A_{k_{1}}N\right\rVert_{\eta}=\left\lVert\tau\right\rVert^{2}\eta\left\lVert\sum_{k_{1}}\bar{\nu}_{k_{1},k_{1}}\nu_{k_{1},k_{1}}A_{k_{1}}^{\dagger}A_{k_{1}}\right\rVert_{\eta}$
(73)
$\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\bar{\nu}_{k_{1},k_{1}}\nu_{k_{1},k_{1}}I\right\rVert_{\eta-1}\leq\left\lVert\tau\right\rVert^{2}\left\lVert\nu\right\rVert_{\max}^{2}\eta^{2}.$

The proof of the second statement is now completed. See Appendix A for the
proof of the remaining statements. ∎

###  3.3 Multilayer nested commutators

We now analyze the error of simulating the interacting-electronic Hamiltonian
(1) using a general $p$th-order formula $\mathscr{S}_{p}(t)$. We know from
(43) that

$\left\lVert\mathscr{S}_{p}(t)-e^{-itH}\right\rVert_{\eta}=\mathcal{O}\left(\max_{\boldsymbol{\gamma}}\left\lVert\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]\right\rVert_{\eta}t^{p+1}\right),$
(74)

where $H_{0}=V=\sum_{l,m}\nu_{l,m}N_{l}N_{m}$ and
$H_{1}=T=\sum_{j,k}\tau_{j,k}A_{j}^{\dagger}A_{k}$. Our goal is to show that

$\left\lVert\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]\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^{2}\right)$
(75)

for each multilayer nested commutator
$\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]$.

To this end, we assume that
$\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]$
is expressed as a fermionic operator of the form

$\sum_{\boldsymbol{j},\boldsymbol{k},\boldsymbol{l}}w_{\boldsymbol{j},\boldsymbol{k},\boldsymbol{l}}\
\cdots A_{j_{x}}^{\dagger}\cdots N_{l_{z}}\cdots A_{k_{y}}\cdots$ (76)

and analyze its commutator with either $T$ or $V$. For the commutator with
$T$, we have from Proposition 2

$\left[A_{j}^{\dagger}A_{k},A_{j_{x}}^{\dagger}\right]=\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}.$
(77)

To develop some intuitions about these commutations, we introduce the notion
of _fermionic chain_ , which refers to a product of fermionic operators that
has a creation operator on the left and an annihilation operator on the right.
Then, the above commutations either extend an existing fermionic chain (in the
case where commutator is taken with $A_{j_{x}}^{\dagger}$ or $A_{k_{y}}$), or
create a new chain (in the case where commutator is taken with $N_{l_{z}}$).
On the other hand, we also apply Proposition 2 to compute the commutator with
$V$:

$\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}}A_{j_{x}}^{\dagger}N_{m}=\delta_{m,j_{x}}A_{j_{x}}^{\dagger}N_{l}+\delta_{l,j_{x}}A_{j_{x}}^{\dagger}N_{m}+\delta_{m,j_{x}}\delta_{l,j_{x}}A_{j_{x}}^{\dagger},$
(78) $\displaystyle\left[N_{l}N_{m},A_{k_{x}}\right]$
$\displaystyle=-\delta_{m,k_{x}}N_{l}A_{k_{x}}-\delta_{l,k_{x}}A_{k_{x}}N_{m}=-\delta_{m,k_{x}}N_{l}A_{k_{x}}-\delta_{l,k_{x}}N_{m}A_{k_{x}}-\delta_{m,k_{x}}\delta_{l,k_{x}}A_{k_{x}}.$

Unlike the commutator with $T$, these commutations do not extend an existing
chain or create a new chain. Rather, their effect is to append occupation-
number operators to an existing chain.

We now apply (77) and (78) iteratively to expand a general multilayer nested
commutator
$\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]$.
We summarize the structure of the resulting operator in the following
proposition.

$j_{2}$$k_{2}$$j_{1}$$k_{1}$${j}_{2}^{\prime}$${k}_{2}^{\prime}$${j}_{1}^{\prime}$${k}_{1}^{\prime}$${l}^{\prime}$${m}^{\prime}$$\tau$$\delta$$\tau$$\nu$$\nu$$\tau$$\delta$$\tau$$\nu$$\nu$
Figure 2: Graph illustration of the fermionic chain
$X=\sum_{\boldsymbol{j},\boldsymbol{k}}\tau_{j_{2},k_{2}}\delta_{k_{2},j_{1}}\tau_{j_{1},k_{1}}A_{j_{2}}^{\dagger}C_{2,1}B_{1,1}A_{k_{1}}$
with $C_{2,1}=\nu_{k_{2},k_{2}}$. Here,
$B_{1,1}=\sum_{{\boldsymbol{j}}^{\prime},{\boldsymbol{k}}^{\prime}}\beta_{1,2}\tau_{{j}_{2}^{\prime},{k}_{2}^{\prime}}\delta_{{k}_{2}^{\prime},{j}_{1}^{\prime}}\tau_{{j}_{1}^{\prime},{k}_{1}^{\prime}}A_{{j}_{2}^{\prime}}^{\dagger}{B}_{2,1}^{\prime}{C}_{2,1}^{\prime}A_{{k}_{1}^{\prime}}$
is a fermionic subchain with $\beta_{1,2}=\nu_{{j}_{2}^{\prime},j_{1}}$,
${B}_{2,1}^{\prime}=\sum_{l^{\prime}}\nu_{{l}^{\prime},{j}_{2}^{\prime}}N_{{l}^{\prime}}$
and
${C}_{2,1}^{\prime}=\sum_{{m}^{\prime}}\nu_{{k}_{2}^{\prime},{m}^{\prime}}N_{{m}^{\prime}}$.
Vertices in the graph denote the indices in the summation, whereas edges
represent the coefficients. We color a vertex if there is no fermionic
operator corresponding to this index (due to taking nested commutators).

######  Proposition 9 (Structure of multilayer nested commutators).

Let
$H=T+V=\sum_{j,k}\tau_{j,k}A_{j}^{\dagger}A_{k}+\sum_{l,m}\nu_{l,m}N_{l}N_{m}$
be an interacting-electronic Hamiltonian as in (1). Then, each nested
commutator
$\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]$
where $H_{0}=V$ and $H_{1}=T$ is a linear combination of _fermionic chains_ :

$X=\sum_{\boldsymbol{j},\boldsymbol{k}}\prod_{x=1}^{q}\tau_{j_{x},k_{x}}\prod_{x=1}^{q-1}\delta_{k_{x+1},j_{x}}\cdot
A_{j_{q}}^{\dagger}\prod_{x=1}^{q}\left(\prod_{y}B_{x,y}\prod_{z}C_{x,z}\right)A_{k_{1}}$
(79)

for some integer $q\leq p$. Here, we have
$B_{x,y}=\sum_{l}\nu_{l,j_{x}}N_{l}$, $\sum_{m}\nu_{j_{x},m}N_{m}$,
$\nu_{j_{x},j_{x}}I$ and $C_{x,z}=\sum_{l}\nu_{l,k_{x}}N_{l}$,
$\sum_{m}\nu_{k_{x},m}N_{m}$, $\nu_{k_{x},k_{x}}I$, or they define _fermionic
subchains_ :

$\displaystyle B_{x,y}$
$\displaystyle=\sum_{{\boldsymbol{j}}^{\prime},{\boldsymbol{k}}^{\prime}}\beta_{x,{x}_{0}^{\prime}}\prod_{{x}^{\prime}=1}^{{q}^{\prime}}\tau_{{j}_{{x}^{\prime}}^{\prime},{k}_{{x}^{\prime}}^{\prime}}\prod_{{x}^{\prime}=1}^{{q}^{\prime}-1}\delta_{{k}_{{x}^{\prime}+1}^{\prime},{j}_{{x}^{\prime}}^{\prime}}\cdot
A_{{j}_{{q}^{\prime}}^{\prime}}^{\dagger}\prod_{{x}^{\prime}=1}^{{q}^{\prime}}\left(\prod_{{y}^{\prime}}{B}_{{x}^{\prime},{y}^{\prime}}^{\prime}\prod_{{z}^{\prime}}{C}_{{x}^{\prime},{z}^{\prime}}^{\prime}\right)A_{{k}_{1}^{\prime}},$
(80) $\displaystyle C_{x,z}$
$\displaystyle=\sum_{{\boldsymbol{j}^{\prime\prime}},{\boldsymbol{k}^{\prime\prime}}}\chi_{x,{x}_{0}^{\prime\prime}}\prod_{{x}^{\prime\prime}=1}^{{q}^{\prime\prime}}\tau_{{j}_{{x}^{\prime\prime}}^{\prime\prime},{k}_{{x}^{\prime\prime}}^{\prime\prime}}\prod_{{x}^{\prime\prime}=1}^{{q}^{\prime\prime}-1}\delta_{{k}^{\prime\prime}_{{x}^{\prime\prime}+1},{j}_{{x}^{\prime\prime}}^{\prime\prime}}\cdot
A_{{j}_{{q}^{\prime\prime}}^{\prime\prime}}^{\dagger}\prod_{{x}^{\prime\prime}=1}^{{q}^{\prime\prime}}\left(\prod_{{y}^{\prime\prime}}{B}_{{x}^{\prime\prime},{y}^{\prime\prime}}^{\prime\prime}\prod_{{z}^{\prime\prime}}{C}_{{x}^{\prime\prime},{z}^{\prime\prime}}^{\prime\prime}\right)A_{{k}_{1}^{\prime\prime}}.$

The definition of fermionic subchain is similar to that of the fermionic
chain, except we have
$\beta_{x,{x}_{0}^{\prime}}=\nu_{{j}_{{x}_{0}^{\prime}}^{\prime},j_{x}}$,
$\nu_{j_{x},{j}_{{x}_{0}^{\prime}}^{\prime}}$,
$\nu_{{k}_{{x}_{0}^{\prime}}^{\prime},j_{x}}$,
$\nu_{j_{x},{k}_{{x}_{0}^{\prime}}^{\prime}}$ for some
${x}_{0}^{\prime}\leq{q}^{\prime}$ and
$\chi_{x,{x}_{0}^{\prime\prime}}=\nu_{{j}_{{x}_{0}^{\prime\prime}}^{\prime\prime},k_{x}}$,
$\nu_{k_{x},{j}_{{x}_{0}^{\prime\prime}}^{\prime\prime}}$,
$\nu_{{k}_{{x}_{0}^{\prime\prime}}^{\prime\prime},k_{x}}$,
$\nu_{k_{x},{k}_{{x}_{0}^{\prime\prime}}^{\prime\prime}}$ for some
${x}_{0}^{\prime\prime}\leq{q}^{\prime\prime}$.999For readability, we have
omitted the dependence of
$\boldsymbol{j},\boldsymbol{k},{\boldsymbol{j}}^{\prime},{\boldsymbol{k}}^{\prime},{\boldsymbol{j}}^{\prime\prime},{\boldsymbol{k}}^{\prime\prime}$
in the definition of fermionic chain and subchain. When written in full,
operator $B_{x,y}=B_{x,y}(\boldsymbol{j},\boldsymbol{k})$ will depend on
$\boldsymbol{j},\boldsymbol{k}$ and similar modifications apply to other
operators. See Figure 2 for a graph illustration of this structure.

Furthermore, there are at most $6^{p}p!$ fermionic chains in each
$\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]$.101010The
exact number of fermionic chains does not matter as long as it only depends on
$p$. Within each chain, coefficient $\tau$ appears
$\left\lvert\boldsymbol{\gamma}\right\rvert$ times and $\nu$ appears
$p+1-\left\lvert\boldsymbol{\gamma}\right\rvert$ times, where
$\left\lvert\boldsymbol{\gamma}\right\rvert:=\sum_{s=1}^{p+1}\gamma_{s}$. All
$B_{x,y}$, $C_{x,z}$ and hence the entire chain are number-preserving.

###### Proof.

We will analyze the structure of multilayer nested commutators by induction.
In the base case where $p=1$, we have
$\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]=[T,V]$. This commutator has the
expansion (61) with six terms, each of which is indeed a fermionic chain and
number-preserving, containing coefficient $\tau$ and $\nu$ each once. This
completes the proof of the base case.

Assuming the claim holds for the nested commutator
$\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]$,
we now consider the structure of
$\left[H_{\gamma_{p+2}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]$.
By induction, this nested commutator is a linear combination of

$\displaystyle\sum_{\boldsymbol{j},\boldsymbol{k}}\prod_{x=1}^{q}\tau_{j_{x},k_{x}}\prod_{x=1}^{q-1}\delta_{k_{x+1},j_{x}}\cdot\left[T,A_{j_{q}}^{\dagger}\right]\prod_{x=1}^{q}\left(\prod_{y}B_{x,y}\prod_{z}C_{x,z}\right)A_{k_{1}},$
(81)
$\displaystyle\sum_{\boldsymbol{j},\boldsymbol{k}}\prod_{x=1}^{q}\tau_{j_{x},k_{x}}\prod_{x=1}^{q-1}\delta_{k_{x+1},j_{x}}\cdot
A_{j_{q}}^{\dagger}\prod_{x=1}^{q}\left(\prod_{y}\left[T,B_{x,y}\right]\prod_{z}C_{x,z}\right)A_{k_{1}},$
$\displaystyle\sum_{\boldsymbol{j},\boldsymbol{k}}\prod_{x=1}^{q}\tau_{j_{x},k_{x}}\prod_{x=1}^{q-1}\delta_{k_{x+1},j_{x}}\cdot
A_{j_{q}}^{\dagger}\prod_{x=1}^{q}\left(\prod_{y}B_{x,y}\prod_{z}\left[T,C_{x,z}\right]\right)A_{k_{1}},$
$\displaystyle\sum_{\boldsymbol{j},\boldsymbol{k}}\prod_{x=1}^{q}\tau_{j_{x},k_{x}}\prod_{x=1}^{q-1}\delta_{k_{x+1},j_{x}}\cdot
A_{j_{q}}^{\dagger}\prod_{x=1}^{q}\left(\prod_{y}B_{x,y}\prod_{z}C_{x,z}\right)\left[T,A_{k_{1}}\right],$

and

$\displaystyle\sum_{\boldsymbol{j},\boldsymbol{k}}\prod_{x=1}^{q}\tau_{j_{x},k_{x}}\prod_{x=1}^{q-1}\delta_{k_{x+1},j_{x}}\cdot\left[V,A_{j_{q}}^{\dagger}\right]\prod_{x=1}^{q}\left(\prod_{y}B_{x,y}\prod_{z}C_{x,z}\right)A_{k_{1}},$
(82)
$\displaystyle\sum_{\boldsymbol{j},\boldsymbol{k}}\prod_{x=1}^{q}\tau_{j_{x},k_{x}}\prod_{x=1}^{q-1}\delta_{k_{x+1},j_{x}}\cdot
A_{j_{q}}^{\dagger}\prod_{x=1}^{q}\left(\prod_{y}\left[V,B_{x,y}\right]\prod_{z}C_{x,z}\right)A_{k_{1}},$
$\displaystyle\sum_{\boldsymbol{j},\boldsymbol{k}}\prod_{x=1}^{q}\tau_{j_{x},k_{x}}\prod_{x=1}^{q-1}\delta_{k_{x+1},j_{x}}\cdot
A_{j_{q}}^{\dagger}\prod_{x=1}^{q}\left(\prod_{y}B_{x,y}\prod_{z}\left[V,C_{x,z}\right]\right)A_{k_{1}},$
$\displaystyle\sum_{\boldsymbol{j},\boldsymbol{k}}\prod_{x=1}^{q}\tau_{j_{x},k_{x}}\prod_{x=1}^{q-1}\delta_{k_{x+1},j_{x}}\cdot
A_{j_{q}}^{\dagger}\prod_{x=1}^{q}\left(\prod_{y}B_{x,y}\prod_{z}C_{x,z}\right)\left[V,A_{k_{1}}\right].$

In each case, we see from (77) and (78) that the result is again a fermionic
chain. Specifically, commutators $\left[T,A_{j_{q}}^{\dagger}\right]$ and
$\left[T,A_{k_{1}}\right]$ increase the “length” of the current fermionic
chain from $q$ to $q+1$; commutators $\left[T,B_{x,y}\right]$ and
$\left[T,C_{x,z}\right]$ either create a fermionic subchain or give the zero
operator, or they can be computed recursively when $B_{x,y}$ and $C_{x,z}$ are
fermionic subchains; commutators $\left[V,A_{j_{q}}^{\dagger}\right]$ and
$\left[V,A_{k_{1}}\right]$ do not increase the length $q$ of the current
fermionic chain, but they increase the number of $B_{x,y}$ and $C_{x,z}$ by
one; commutators $\left[V,B_{x,y}\right]$ and $\left[V,C_{x,z}\right]$ either
give the zero operator, or they can be computed recursively if $B_{x,y}$ and
$C_{x,z}$ are fermionic subchains.

Each application of commutation rules (77) and (78) increases the number of
terms by a factor of at most $3$. The nested commutator
$\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]$
contains products of at most $2(p+1)$ elementary fermionic operators, giving
at most $6^{p+1}(p+1)!$ terms in total. Meanwhile, the number of $\tau$ or
$\nu$ increases by one depending on whether $H_{\gamma_{p+2}}=T$ or
$H_{\gamma_{p+2}}=V$. The claim about the number preservation can be verified
directly. This completes the inductive step. ∎

######  Proposition 10 (Fermionic seminorm of fermionic chain and subchain).

Let
$H=T+V=\sum_{j,k}\tau_{j,k}A_{j}^{\dagger}A_{k}+\sum_{l,m}\nu_{l,m}N_{l}N_{m}$
be an interacting-electronic Hamiltonian (1). Then, we can bound the fermionic
seminorm of the fermionic chain $X$ in (79) as

$\left\lVert
X\right\rVert_{\eta}\leq\left\lVert\tau\right\rVert^{q}\eta\prod_{x=1}^{q}\left(\prod_{y}\max_{j_{x}}\left\lVert
B_{x,y}\right\rVert_{\eta-1}\prod_{z}\max_{k_{x}}\left\lVert
C_{x,z}\right\rVert_{\eta-1}\right),$ (83)

whereas fermionic subchains $B_{x,y}$, $C_{x,z}$ in (80) can be similarly
bounded as

$\displaystyle\left\lVert B_{x,y}\right\rVert_{\eta}$
$\displaystyle\leq\left\lVert\tau\right\rVert^{{q}^{\prime}}\left\lVert\nu\right\rVert_{\max}\eta\prod_{{x}^{\prime}=1}^{{q}^{\prime}}\left(\prod_{{y}^{\prime}}\max_{{j}_{{x}^{\prime}}^{\prime}}\left\lVert
B_{{x}^{\prime},{y}^{\prime}}\right\rVert_{\eta-1}\prod_{{z}^{\prime}}\max_{{k}_{{x}^{\prime}}^{\prime}}\left\lVert
C_{{x}^{\prime},{z}^{\prime}}\right\rVert_{\eta-1}\right),$ (84)
$\displaystyle\left\lVert C_{x,y}\right\rVert_{\eta}$
$\displaystyle\leq\left\lVert\tau\right\rVert^{{q}^{\prime\prime}}\left\lVert\nu\right\rVert_{\max}\eta\prod_{{x}^{\prime\prime}=1}^{{q}^{\prime\prime}}\left(\prod_{{y}^{\prime\prime}}\max_{{j}_{{x}^{\prime\prime}}^{\prime\prime}}\left\lVert
B_{{x}^{\prime\prime},{y}^{\prime\prime}}\right\rVert_{\eta-1}\prod_{{z}^{\prime\prime}}\max_{{k}_{{x}^{\prime\prime}}^{\prime\prime}}\left\lVert
C_{{x}^{\prime\prime},{z}^{\prime\prime}}\right\rVert_{\eta-1}\right).$

###### Proof.

We will prove this bound using Lemma 1, Lemma 2, and Lemma 3 in a similar way
as in Proposition 8. Specifically, we write
$X=\sum_{j_{q}}A_{j_{q}}^{\dagger}D_{j_{q}}$, where

$D_{j_{q}}=\sum_{\begin{subarray}{c}j_{1},\ldots,\\\
j_{q-1},\boldsymbol{k}\end{subarray}}\prod_{x=1}^{q}\tau_{j_{x},k_{x}}\prod_{x=1}^{q-1}\delta_{k_{x+1},j_{x}}\cdot\prod_{x=1}^{q}\left(\prod_{y}B_{x,y}\prod_{z}C_{x,z}\right)A_{k_{1}}.$
(85)

Then,

$X^{\dagger}X=\sum_{j_{q_{1}},j_{q_{2}}}D_{j_{q_{1}}}^{\dagger}A_{j_{q_{1}}}A_{j_{q_{2}}}^{\dagger}D_{j_{q_{2}}}=\sum_{j_{q_{1}}}D_{j_{q_{1}}}^{\dagger}D_{j_{q_{1}}}-\sum_{j_{q_{1}},j_{q_{2}}}D_{j_{q_{1}}}^{\dagger}A_{j_{q_{2}}}^{\dagger}A_{j_{q_{1}}}D_{j_{q_{2}}}.$
(86)

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

$X^{\dagger}X\leq\sum_{j_{q_{1}}}D_{j_{q_{1}}}^{\dagger}D_{j_{q_{1}}}+\sum_{j_{q_{1}},j_{q_{2}}}D_{j_{q_{1}}}^{\dagger}A_{j_{q_{2}}}^{\dagger}A_{j_{q_{2}}}D_{j_{q_{1}}}=\sum_{j_{q_{1}}}D_{j_{q_{1}}}^{\dagger}D_{j_{q_{1}}}N.$
(87)

Next, we write $D_{j_{q}}=\prod_{y}B_{q,y}E_{j_{q}}$, where

$E_{j_{q}}=\sum_{\begin{subarray}{c}j_{1},\ldots,\\\
j_{q-1},\boldsymbol{k}\end{subarray}}\prod_{x=1}^{q}\tau_{j_{x},k_{x}}\prod_{x=1}^{q-1}\delta_{k_{x+1},j_{x}}\cdot\prod_{z}C_{q,z}\prod_{x=1}^{q-1}\left(\prod_{y}B_{x,y}\prod_{z}C_{x,z}\right)A_{k_{1}}.$
(88)

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

$\left\lVert X\right\rVert_{\eta}=\sqrt{\left\lVert
X^{\dagger}X\right\rVert_{\eta}}\leq\eta^{1/2}\sqrt{\Big{\|}\sum_{j_{q_{1}}}D_{j_{q_{1}}}^{\dagger}D_{j_{q_{1}}}\Big{\|}_{\eta}}\leq\eta^{1/2}\sqrt{\Big{\|}\sum_{j_{q_{1}}}E_{j_{q_{1}}}^{\dagger}E_{j_{q_{1}}}\Big{\|}_{\eta}}\prod_{y}\max_{j_{q}}\left\lVert
B_{q,y}\right\rVert_{\eta-1}.$ (89)

We now write $E_{j_{q}}=\sum_{k_{q}}\tau_{j_{q},k_{q}}F_{k_{q}}$, where

$F_{k_{q}}=\sum_{\begin{subarray}{c}j_{1},\ldots,j_{q-1},\\\
k_{1},\ldots,k_{q-1}\end{subarray}}\prod_{x=1}^{q-1}\tau_{j_{x},k_{x}}\prod_{x=1}^{q-1}\delta_{k_{x+1},j_{x}}\cdot\prod_{z}C_{q,z}\prod_{x=1}^{q-1}\left(\prod_{y}B_{x,y}\prod_{z}C_{x,z}\right)A_{k_{1}}.$
(90)

Then,

$\sum_{j_{q_{1}}}E_{j_{q_{1}}}^{\dagger}E_{j_{q_{1}}}=\sum_{k_{q_{1}},k_{q_{2}}}\left(\sum_{j_{q_{1}}}\bar{\tau}_{j_{q_{1}},k_{q_{1}}}\tau_{j_{q_{1}},k_{q_{2}}}\right)F_{k_{q_{1}}}^{\dagger}F_{k_{q_{2}}}.$
(91)

We perform diagonalization using Lemma 2, obtaining

$\sum_{j_{q_{1}}}E_{j_{q_{1}}}^{\dagger}E_{j_{q_{1}}}\leq\left\lVert\tau^{\dagger}\tau\right\rVert\sum_{k_{q_{1}}}F_{k_{q_{1}}}^{\dagger}F_{k_{q_{1}}}.$
(92)

Next, we write $F_{k_{q}}=\prod_{z}C_{q,z}G_{k_{q}}$, where

$G_{k_{q}}=\sum_{\begin{subarray}{c}j_{1},\ldots,j_{q-1},\\\
k_{1},\ldots,k_{q-1}\end{subarray}}\prod_{x=1}^{q-1}\tau_{j_{x},k_{x}}\prod_{x=1}^{q-1}\delta_{k_{x+1},j_{x}}\cdot\prod_{x=1}^{q-1}\left(\prod_{y}B_{x,y}\prod_{z}C_{x,z}\right)A_{k_{1}}.$
(93)

Invoking again the Hölder-type inequality for the expectation value (Lemma 3),
we get

$\left\lVert
X\right\rVert_{\eta}\leq\left\lVert\tau\right\rVert\eta^{1/2}\sqrt{\Big{\|}\sum_{k_{q_{1}}}G_{k_{q_{1}}}^{\dagger}G_{k_{q_{1}}}\Big{\|}_{\eta}}\prod_{y}\max_{j_{q}}\left\lVert
B_{q,y}\right\rVert_{\eta-1}\prod_{z}\max_{k_{q}}\left\lVert
C_{q,z}\right\rVert_{\eta-1}.$ (94)

Note that we can write
$G_{k_{q}}=\sum_{j_{q-1}}\delta_{k_{q},j_{q-1}}H_{j_{q-1}}$ with

$H_{j_{q-1}}=\sum_{\begin{subarray}{c}j_{1},\ldots,j_{q-2},\\\
k_{1},\ldots,k_{q-1}\end{subarray}}\prod_{x=1}^{q-1}\tau_{j_{x},k_{x}}\prod_{x=1}^{q-2}\delta_{k_{x+1},j_{x}}\cdot\prod_{x=1}^{q-1}\left(\prod_{y}B_{x,y}\prod_{z}C_{x,z}\right)A_{k_{1}},$
(95)

which implies

$\sum_{k_{q}}G_{k_{q}}^{\dagger}G_{k_{q}}=\sum_{j_{q-1}}H_{j_{q-1}}^{\dagger}H_{j_{q-1}}.$
(96)

We can now iterate this procedure $q$ times to get

$\displaystyle\left\lVert X\right\rVert_{\eta}$
$\displaystyle\leq\left\lVert\tau\right\rVert^{q}\eta^{1/2}\sqrt{\Big{\|}\sum_{k_{1}}A_{k_{1}}^{\dagger}A_{k_{1}}\Big{\|}_{\eta}}\prod_{x=1}^{q}\left(\prod_{y}\max_{j_{x}}\left\lVert
B_{x,y}\right\rVert_{\eta-1}\prod_{z}\max_{k_{x}}\left\lVert
C_{x,z}\right\rVert_{\eta-1}\right)$ (97)
$\displaystyle=\left\lVert\tau\right\rVert^{q}\eta\prod_{x=1}^{q}\left(\prod_{y}\max_{j_{x}}\left\lVert
B_{x,y}\right\rVert_{\eta-1}\prod_{z}\max_{k_{x}}\left\lVert
C_{x,z}\right\rVert_{\eta-1}\right).$

This completes the proof of (83).

Essentially the same argument can be applied to bound the fermionic seminorm
of fermionic subchains. The only difference is that we have additional
coefficients $\beta_{x,{x}_{0}^{\prime}}$ in $B_{x,y}$ and respectively
$\chi_{x,{x}_{0}^{\prime\prime}}$ in $C_{x,z}$. But their indices will be
contracted in the ${x}_{0}^{\prime}$th and ${x}_{0}^{\prime\prime}$th
iteraction of the above analysis and the coefficients can then be bounded by
$\left\lVert\nu\right\rVert_{\max}$, which completes the proof of (84). ∎

We now apply Proposition 9 to expand each nested commutator
$\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]$
into fermionic chains and use Proposition 10 to bound their fermionic
seminorm. The $\tau$ factors are already bounded by their spectral-norm
$\left\lVert\tau\right\rVert$ in Proposition 10. To proceed, we need to
further bound each $\left\lVert B_{x,y}\right\rVert_{\eta-1}$ and $\left\lVert
C_{x,z}\right\rVert_{\eta-1}$ separately. We have111111Note that one could
also diagonalize the coefficient matrix $\nu^{\dagger}\nu$ and get a bound in
terms of $\left\lVert\nu\right\rVert$. However, such a bound will be loose for
the electronic-structure simulation and will not be further considered here.

$\displaystyle\Big{\|}\sum_{l}\nu_{l,j_{x}}N_{l}\Big{\|}_{\eta-1}$
$\displaystyle=\sqrt{\Big{\|}\sum_{l_{1},l_{2}}\bar{\nu}_{l_{1},j_{x_{1}}}\nu_{l_{2},j_{x_{2}}}N_{l_{1}}N_{l_{2}}\Big{\|}_{\eta-1}}\leq\left\lVert\nu\right\rVert_{\max}\eta,$
(98) $\displaystyle\Big{\|}\sum_{m}\nu_{j_{x},m}N_{m}\Big{\|}_{\eta-1}$
$\displaystyle=\sqrt{\Big{\|}\sum_{m_{1},m_{2}}\bar{\nu}_{j_{x_{1}},m_{1}}\nu_{j_{x_{2}},m_{2}}N_{m_{1}}N_{m_{2}}\Big{\|}_{\eta-1}}\leq\left\lVert\nu\right\rVert_{\max}\eta,$
$\displaystyle\left\lVert\nu_{j_{x},j_{x}}I\right\rVert_{\eta-1}$
$\displaystyle\leq\left\lVert\nu\right\rVert_{\max}$

for $B_{x,y}$ and similar estimates hold for $C_{x,z}$. In the case where
$B_{x,y}$ or $C_{x,z}$ creates a fermionic subchain, we can estimate
recursively using Proposition 10. In particular, we will introduce a factor of
$\left\lVert\nu\right\rVert_{\max}\eta$ each time a subchain is created.

We know from Proposition 9 that the number of $\tau$ factors in each chain
agrees with the number of $H_{1}=T$ in the nested commutator, whereas the
number of $\nu$ factors coincides with the number of $H_{0}=V$. Since the
number of fermionic chains is at most $6^{p}p!$, we obtain the bound

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

Here, we have $1\leq\left\lvert\boldsymbol{\gamma}\right\rvert\leq p$ as
$[T,T]=[V,V]=0$. This completes the proof of Eq. (2) of our main result
Theorem 1.

##  4 Path-counting bound on the expectation of fermionic operators

We now present the second strategy for bounding the expectation of fermionic
operators, and apply it to estimate the fermionic seminorm of Trotter error.
Recall from (43) that

$\left\lVert\mathscr{S}_{p}(t)-e^{-itH}\right\rVert_{\eta}=\mathcal{O}\left(\max_{\boldsymbol{\gamma}}\left\lVert\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]\right\rVert_{\eta}t^{p+1}\right),$
(100)

where $H_{0}=V=\sum_{l,m}\nu_{l,m}N_{l}N_{m}$,
$H_{1}=T=\sum_{j,k}\tau_{j,k}A_{j}^{\dagger}A_{k}$ and
$\gamma_{j}\in\\{0,1\\}$. Hence to analyze the Trotter error, it suffices to
bound the fermionic seminorm
$\left\lVert\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]\right\rVert_{\eta}$.
We develop a general bound on this quantity in Section 4.1 based on a path-
counting technique. We then use it to analyze the simulation of $d$-sparse
interacting electrons in Section 4.2, proving Eq. (3) of our main result
Theorem 1.

It is worth noting that our approach can also be adapted to establish (9), a
bound slightly weaker than our main result (2) but sufficient for our
applications. See Appendix B for details.

###  4.1 Path-counting bound

We start by bounding the transition amplitude between any two states in terms
of the expectation value. Since
$\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]$
is antihermitian, we have

$\left\lVert\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]\right\rVert_{\eta}=\max_{\lvert\psi_{\eta}\rangle}\left\lvert\langle\psi_{\eta}\rvert\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]\lvert\psi_{\eta}\rangle\right\rvert.$
(101)

We now aim to bound the expectation

$\left\lvert\langle
X\rangle\right\rvert=\left\lvert\langle\psi_{\eta}\rvert\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]\lvert\psi_{\eta}\rangle\right\rvert$
(102)

for any $\lvert\psi_{\eta}\rangle$. To this end, we first expand
$\lvert\psi_{\eta}\rangle$ as:

$\lvert\psi_{\eta}\rangle=\sum_{\boldsymbol{c}\in\\{0,1\\}^{n},|\boldsymbol{c}|=\eta}\alpha_{\boldsymbol{c}}\lvert\boldsymbol{c}\rangle,$
(103)

where $\boldsymbol{c}$ is a configuration with $\eta$ electrons, and the
number of ones in $\boldsymbol{c}$ is given by the Hamming weight
$\left\lvert\boldsymbol{c}\right\rvert=\sum_{j=0}^{n-1}c_{j}$. Using the
notation

$\mu^{0}=\nu,\quad\mu^{1}=\tau,\quad H^{0}_{jk}=N_{j}N_{k},\quad
H^{1}_{jk}=A^{\dagger}_{j}A_{k},$ (104)

we expand everything to get

$\displaystyle\left\lvert\langle X\rangle\right\rvert$
$\displaystyle=\bigg{|}\sum_{j_{p+1},k_{p+1}}\ldots\sum_{j_{1},k_{1}}\sum_{\boldsymbol{c}_{1}}\sum_{\boldsymbol{c}_{2}}\bar{\alpha}_{\boldsymbol{c}_{1}}\alpha_{\boldsymbol{c}_{2}}\mu^{\gamma_{p+1}}_{j_{p+1}k_{p+1}}\ldots\mu^{\gamma_{1}}_{j_{1}k_{1}}\langle\boldsymbol{c}_{1}\rvert\left[H^{\gamma_{p+1}}_{j_{p+1}k_{p+1}},\ldots\left[H^{\gamma_{2}}_{j_{2}k_{2}},H^{\gamma_{1}}_{j_{1}k_{1}}\right]\right]\lvert\boldsymbol{c}_{2}\rangle\bigg{|}$
(105)
$\displaystyle\leq\left\lVert\tau\right\rVert_{\max}^{\left\lvert\boldsymbol{\gamma}\right\rvert}\left\lVert\nu\right\rVert_{\max}^{p+1-\left\lvert\boldsymbol{\gamma}\right\rvert}\sum_{\boldsymbol{c}_{1}}\sum_{\boldsymbol{c}_{2}}\left|\alpha_{\boldsymbol{c}_{1}}\right|\left|\alpha_{\boldsymbol{c}_{2}}\right|\times$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\quad\sum_{\langle
j_{p+1},k_{p+1}\rangle}\ldots\sum_{\langle
j_{1},k_{1}\rangle}\left|\langle\boldsymbol{c}_{1}\rvert\left[H^{\gamma_{p+1}}_{j_{p+1}k_{p+1}},\ldots\left[H^{\gamma_{2}}_{j_{2}k_{2}},H^{\gamma_{1}}_{j_{1}k_{1}}\right]\right]\lvert\boldsymbol{c}_{2}\rangle\right|,$
(106)

where $\boldsymbol{c}_{1},\boldsymbol{c}_{2}$ are configurations with $\eta$
electrons, and $\langle j,k\rangle$ only sum over indices such that the
corresponding $\mu_{j,k}^{\gamma}\neq 0$ (either $\tau$ or $\nu$ depending on
$\gamma$).

Using the commutation relations in Equation (77) and (78), we know that the
nested commutator
$\left[H^{\gamma_{p+1}}_{j_{p+1}k_{p+1}},\ldots\left[H^{\gamma_{2}}_{j_{2}k_{2}},H^{\gamma_{1}}_{j_{1}k_{1}}\right]\right]$
can be written as a sum of

$(-1)^{a}\ldots A^{\dagger}_{j}\ldots N_{l}\ldots A_{k}\ldots,$ (107)

for some $a\in\\{0,1\\}$ and a sequence of elementary fermionic operators. We
call each term $P$ a _fermionic path_ and write
$P\rhd\left(H^{\gamma_{p+1}}_{j_{p+1}k_{p+1}},\ldots,H^{\gamma_{1}}_{j_{1}k_{1}}\right)$
to mean $P$ is one of the terms in the expansion of the nested commutator. If
the nested commutator evaluates to zero, then we consider the set

$\left\\{P\mbox{ such that
}P\rhd\left(H^{\gamma_{p+1}}_{j_{p+1}k_{p+1}},\ldots,H^{\gamma_{1}}_{j_{1}k_{1}}\right)\right\\}$
(108)

to be an empty set. One possible expansion of the nested commutator is
presented in Proposition 9. This allows us to make a further expansion to
yield

$\left\lvert\langle X\rangle\right\rvert\leq
c_{\tau\nu}\sum_{\boldsymbol{c}_{1}}\sum_{\boldsymbol{c}_{2}}\left|\alpha_{\boldsymbol{c}_{1}}\right|\left|\alpha_{\boldsymbol{c}_{2}}\right|\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|\langle\boldsymbol{c}_{1}\rvert
P\lvert\boldsymbol{c}_{2}\rangle\right|,$ (109)

where
$c_{\tau\nu}=\left\lVert\tau\right\rVert_{\max}^{\left\lvert\boldsymbol{\gamma}\right\rvert}\left\lVert\nu\right\rVert_{\max}^{p+1-\left\lvert\boldsymbol{\gamma}\right\rvert}$.
We use the following proposition to characterize
$\left|\langle\boldsymbol{c}_{1}\rvert
P\lvert\boldsymbol{c}_{2}\rangle\right|$.

######  Lemma 4.

For any computational basis state $\lvert\boldsymbol{c}\rangle$ where
$\boldsymbol{c}$ is a fermionic configuration, and fermionic path

$P=(-1)^{a}\ldots A^{\dagger}_{j}\ldots N_{l}\ldots A_{k}\ldots,$ (110)

we have either $P\lvert\boldsymbol{c}\rangle$ is a computational basis state
with some phase $\pm 1$ or $P\lvert\boldsymbol{c}\rangle=0$.

###### Proof.

The proof follows from a simple induction. For the base case, we have
$P=(-1)^{a}$ without any fermionic operator, so $P\lvert\boldsymbol{c}\rangle$
is a computational basis state with some phase $\pm 1$. Now we consider the
three cases: $P=N_{l}P^{\prime}$, $P=A_{k}P^{\prime}$, or
$P=A^{\dagger}_{j}P^{\prime}$. By induction, we have
$P^{\prime}\lvert\boldsymbol{c}\rangle$ is a computational basis state
$\lvert\boldsymbol{c}^{\prime}\rangle$ with some phase $\pm 1$ or
$P^{\prime}\lvert\boldsymbol{c}\rangle=0$. The latter is trivial. For the
former case, we go through the following three cases.

  * •

If $N_{l}$ is applied on $\lvert\boldsymbol{c}^{\prime}\rangle$, we check if
site-$l$ has an electron in configuration $\boldsymbol{c}^{\prime}$. If
site-$l$ has an electron, then
$N_{l}\lvert\boldsymbol{c}^{\prime}\rangle=\lvert\boldsymbol{c}^{\prime}\rangle$;
otherwise, $N_{l}\lvert\boldsymbol{c}^{\prime}\rangle=0$.

  * •

If $A_{k}$ is applied on $\lvert\boldsymbol{c}^{\prime}\rangle$, we check if
site-$k$ has an electron in configuration $\boldsymbol{c}^{\prime}$. If
site-$k$ has an electron, then $A_{k}\lvert\boldsymbol{c}^{\prime}\rangle$
will remove the site-$k$ electron and add some phase according to the rule in
Equation (29); otherwise, $A_{k}\lvert\boldsymbol{c}^{\prime}\rangle=0$.

  * •

If $A^{\dagger}_{j}$ is applied on $\lvert\boldsymbol{c}^{\prime}\rangle$, we
check if site-$j$ has an electron in configuration $\boldsymbol{c}^{\prime}$.
If site-$j$ does not have an electron, then
$A^{\dagger}_{j}\lvert\boldsymbol{c}^{\prime}\rangle$ will create an electron
at site-$j$ and add some phase according to the rule in Equation (28);
otherwise, $A^{\dagger}_{j}\lvert\boldsymbol{c}^{\prime}\rangle=0$.

Therefore, $P\lvert\boldsymbol{c}\rangle$ is either a computational basis
state with some phase $\pm 1$ or $P\lvert\boldsymbol{c}\rangle=0$. ∎

######  Corollary 1.

We have that $\left|\langle\boldsymbol{c}_{1}\rvert
P\lvert\boldsymbol{c}_{2}\rangle\right|$ is either $0$ or $1$. Furthermore,
$\sum_{\boldsymbol{c}_{1}\in\mathcal{S}}\left|\langle\boldsymbol{c}_{1}\rvert
P\lvert\boldsymbol{c}_{2}\rangle\right|\leq\left\lVert
P\lvert\boldsymbol{c}_{2}\rangle\right\rVert$ for any set $\mathcal{S}$ of
configurations.

Next, we define a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ where the
vertices $\mathcal{V}$ are the second-quantized configurations with $\eta$
electrons, and the weighted adjacency matrix for the edges $\mathcal{E}$ is
defined as

$w_{\boldsymbol{c}_{1},\boldsymbol{c}_{2}}=\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|\langle\boldsymbol{c}_{1}\rvert
P\lvert\boldsymbol{c}_{2}\rangle\right|.$ (111)

The weight $w_{\boldsymbol{c}_{1},\boldsymbol{c}_{2}}$ counts the number of
fermionic paths that can take $\lvert\boldsymbol{c}_{2}\rangle$ to
$\lvert\boldsymbol{c}_{1}\rangle$. Note that this graph may contain self-loops
(equivalent to $w_{\boldsymbol{c}_{1},\boldsymbol{c}_{1}}>0$) as there are
fermionic paths that leave $\lvert\boldsymbol{c}_{1}\rangle$ unchanged or
simply add a phase of $-1$. We now define the _degree_ of $\boldsymbol{c}_{2}$
as

$\displaystyle\mathrm{deg}(\boldsymbol{c}_{2})$
$\displaystyle=\sum_{\boldsymbol{c}_{1}}\frac{w_{\boldsymbol{c}_{1},\boldsymbol{c}_{2}}+w_{\boldsymbol{c}_{2},\boldsymbol{c}_{1}}}{2}$
(112) $\displaystyle=\sum_{\boldsymbol{c}_{1}}\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)}\frac{\left|\langle\boldsymbol{c}_{1}\rvert
P\lvert\boldsymbol{c}_{2}\rangle\right|+\left|\langle\boldsymbol{c}_{2}\rvert
P\lvert\boldsymbol{c}_{1}\rangle\right|}{2}$ (113)
$\displaystyle=\sum_{\boldsymbol{c}_{1}}\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)}\frac{\left|\langle\boldsymbol{c}_{1}\rvert
P\lvert\boldsymbol{c}_{2}\rangle\right|+\left|\langle\boldsymbol{c}_{1}\rvert
P^{\dagger}\lvert\boldsymbol{c}_{2}\rangle\right|}{2}$ (114)
$\displaystyle\leq\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)}\frac{\left\lVert
P\lvert\boldsymbol{c}_{2}\rangle\right\rVert+\left\lVert
P^{\dagger}\lvert\boldsymbol{c}_{2}\rangle\right\rVert}{2},$ (115)

which is equivalent to counting the number of fermionic paths that evaluate
nonzero on the initial state $\lvert\boldsymbol{c}_{2}\rangle$. The last
inequality follows from Corollary 1. We now introduce the following lemma
which relates the maximum degree and the quadratic form (109) we wish to
bound.

######  Lemma 5.

For any real symmetric matrix $w\in\mathbb{R}^{k\times k}$ with nonnegative
entries and normalized real vectors $v\in\mathbb{R}^{k}$ with $\left\lVert
v\right\rVert=1$, we have121212Note that this can alternatively be proved by
analyzing the Geršgorin discs; see for example [38, Corollary 6.1.5]. Had we
not taken the expectation in (101) and symmetrized the weighted adjacency
matrix in (112), we would have needed a stronger bound here [38, 5.6.P21].

$\sum_{i,j}w_{i,j}v_{i}v_{j}\leq\max_{i}\sum_{j}w_{i,j},$ (116)

###### Proof.

Let $u_{1}$ be an eigenvector corresponding to the largest eigenvalue
$\lambda_{1}$ of $w$ with $\left\lVert u_{1}\right\rVert=1$. By the Rayleigh
quotient theorem [38, Theorem 4.2.2],

$v^{T}wv\leq u_{1}^{T}wu_{1}=\lambda_{1}$ (117)

for any $v\in\mathbb{R}^{k}$ with $\left\lVert v\right\rVert=1$, where $v^{T}$
denotes the vector transpose of $v$. Consider
$i^{*}=\operatorname*{argmax}_{j}(u_{1})_{j}$. We assume $(u_{1})_{i^{*}}>0$
without loss of generality, for otherwise we multiply $u_{1}$ by $-1$. Then,
we have

$u_{1}^{T}wu_{1}=\lambda_{1}=\frac{(wu_{1})_{i^{*}}}{(u_{1})_{i^{*}}}=\frac{\sum_{j}w_{i^{*},j}(u_{1})_{j}}{(u_{1})_{i^{*}}}\leq\sum_{j}w_{i^{*},j}\leq\max_{i}\sum_{j}w_{i,j}.$
(118)

This concludes the proof. ∎

Using Lemma 5, we obtain an upper bound of $\left\lvert\langle
X\rangle\right\rvert$

$\displaystyle\left\lvert\langle X\rangle\right\rvert$ $\displaystyle\leq
c_{\tau\nu}\sum_{\boldsymbol{c}_{1}}\sum_{\boldsymbol{c}_{2}}\left|\alpha_{\boldsymbol{c}_{1}}\right|\left|\alpha_{\boldsymbol{c}_{2}}\right|\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|\langle\boldsymbol{c}_{1}\rvert
P\lvert\boldsymbol{c}_{2}\rangle\right|$ (119)
$\displaystyle=c_{\tau\nu}\sum_{\boldsymbol{c}_{1}}\sum_{\boldsymbol{c}_{2}}w_{\boldsymbol{c}_{1},\boldsymbol{c}_{2}}\left|\alpha_{\boldsymbol{c}_{1}}\right|\left|\alpha_{\boldsymbol{c}_{2}}\right|=c_{\tau\nu}\sum_{\boldsymbol{c}_{1}}\sum_{\boldsymbol{c}_{2}}\frac{w_{\boldsymbol{c}_{1},\boldsymbol{c}_{2}}+w_{\boldsymbol{c}_{2},\boldsymbol{c}_{1}}}{2}\left|\alpha_{\boldsymbol{c}_{1}}\right|\left|\alpha_{\boldsymbol{c}_{2}}\right|$
(120) $\displaystyle\leq
c_{\tau\nu}\max_{\boldsymbol{c}_{2}}\sum_{\boldsymbol{c}_{1}}\frac{w_{\boldsymbol{c}_{1},\boldsymbol{c}_{2}}+w_{\boldsymbol{c}_{2},\boldsymbol{c}_{1}}}{2}=c_{\tau\nu}\max_{\boldsymbol{c}}\mathrm{deg}\left(\boldsymbol{c}\right)$
(121)

in terms of the maximum degree of the graph $\mathcal{G}$. Finally, we arrive
at the following proposition by combining the above bound with Equation (115).

######  Proposition 11 (Path-counting bound of fermionic seminorm).

Let
$H=T+V=\sum_{j,k}\tau_{j,k}A_{j}^{\dagger}A_{k}+\sum_{l,m}\nu_{l,m}N_{l}N_{m}$
be an interacting-electronic Hamiltonian as in (1). Then, each nested
commutator
$\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]$,
where $H_{0}=V$ and $H_{1}=T$, can be bounded as

$\displaystyle\left\lVert\left[H_{\gamma_{p+1}},\cdots\left[H_{\gamma_{2}},H_{\gamma_{1}}\right]\right]\right\rVert_{\eta}\leq\left\lVert\tau\right\rVert_{\max}^{\left\lvert\boldsymbol{\gamma}\right\rvert}\left\lVert\nu\right\rVert_{\max}^{p+1-\left\lvert\boldsymbol{\gamma}\right\rvert}\max_{\boldsymbol{c}_{\eta}}\mathrm{deg}\left(\boldsymbol{c}_{\eta}\right),$
(122)

where $\left\lvert\boldsymbol{\gamma}\right\rvert=\sum_{q=0}^{p+1}\gamma_{q}$
and $\boldsymbol{c}_{\eta}$ is a fermionic configuration with $\eta$
electrons. Here, the degree of configuration $\boldsymbol{c}_{\eta}$ is
defined as

$\mathrm{deg}\left(\boldsymbol{c}_{\eta}\right)=\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)}\frac{1}{2}\left(\left\lVert
P\lvert\boldsymbol{c}_{\eta}\rangle\right\rVert+\|P^{\dagger}\lvert\boldsymbol{c}_{\eta}\rangle\|\right),$
(123)

where for $q=1,\ldots,p+1$, $\langle j_{q},k_{q}\rangle$ sum over indices
$j_{q},k_{q}$ such that $\mu_{j_{q},k_{q}}^{\nu_{q}}\neq 0$, fermionic path
$P\rhd\left(H^{\gamma_{p+1}}_{j_{p+1}k_{p+1}},\ldots,H^{\gamma_{1}}_{j_{1}k_{1}}\right)$
goes over all the terms $P=(-1)^{a}\ldots A^{\dagger}_{j}\ldots N_{l}\ldots
A_{k}\ldots$ in the expansion of
$\left[H^{\gamma_{p+1}}_{j_{p+1}k_{p+1}},\ldots\left[H^{\gamma_{2}}_{j_{2}k_{2}},H^{\gamma_{1}}_{j_{1}k_{1}}\right]\right]$,
and $\mu^{0}=\nu,\ \mu^{1}=\tau,\ H^{0}_{jk}=N_{j}N_{k},\
H^{1}_{jk}=A^{\dagger}_{j}A_{k}$.

###  4.2 Counting fermionic paths for $d$-sparse interactions

As an illustrative example, let us consider an upper bound of
$\max_{\boldsymbol{c}}\mathrm{deg}(\boldsymbol{c})$ for electronic
Hamiltonians with $d$-sparse interactions. We will use the commutation
relations in Equation (77) and (78), restated below

$\left[A_{j}^{\dagger}A_{k},A_{j_{x}}^{\dagger}\right]=\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}.$
(124)
$\left[N_{l}N_{m},A_{j_{x}}^{\dagger}\right]=\delta_{m,j_{x}}N_{l}A_{j_{x}}^{\dagger}+\delta_{l,j_{x}}A_{j_{x}}^{\dagger}N_{m},\quad\left[N_{l}N_{m},A_{k_{x}}\right]=-\delta_{m,k_{x}}N_{l}A_{k_{x}}-\delta_{l,k_{x}}A_{k_{x}}N_{m}.$
(125)

We start with an intuitive argument. For every $q=2,\ldots,p+1$, we have

$\left[H^{\gamma_{q}}_{j_{q}k_{q}},\ldots\left[H^{\gamma_{2}}_{j_{2}k_{2}},H^{\gamma_{1}}_{j_{1}k_{1}}\right]\right]=\sum_{P\rhd\left(H^{\gamma_{q-1}}_{j_{q-1}k_{q-1}},\ldots,H^{\gamma_{1}}_{j_{1}k_{1}}\right)}\left[H^{\gamma_{q}}_{j_{q}k_{q}},P\right],$
(126)

where $P$ only contains fermionic operator acting on sites
$j_{1},k_{1},\ldots,j_{q-1},k_{q-1}$. From the commutation relations (124) and
(125), we see that at least one of $j_{q},k_{q}$ must match one of the indices
$j_{1},k_{1},\ldots,j_{q-1},k_{q-1}$. Furthermore, for every $j_{q}$, there
are at most $d$ $k_{q}$’s that have non-zero coefficient in
$\tau_{j_{q},k_{q}}$ (for $\gamma_{q}=1$) or $\nu_{j_{q},k_{q}}$ (for
$\gamma_{q}=0$). Hence, we have the following bound

$\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)}1=\mathcal{O}(nd^{p+1}).$
(127)

The $n$ factor follows from the fact that only one index can be freely choosen
between $0,\ldots,n-1$. And for any pair of indices $\langle
j_{q},k_{q}\rangle$, one of them has to match the previous indices, while the
other one can only choose from the $d$ indices under the sparsity constraint.
Hence we have the $d^{p}$ factor in the asymptotic bound.

However, this analysis can be further improved using certain properties of
$P$. Specifically, we will show that the rightmost fermionic operator in $P$
can be either an annihilation operator $A$ or an occupation-number operator
$N$. This means that, for $\left\lVert
P\lvert\boldsymbol{c}_{\eta}\rangle\right\rVert$ to be nonzero, the rightmost
fermionic operator of $P$ must act on the $\eta$ occupied sites in the
configuration $\boldsymbol{c}_{\eta}$. Therefore, we have the bound

$\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}(\eta d^{p+1}).$
(128)

Similarly, we have

$\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)}\|P^{\dagger}\lvert\boldsymbol{c}_{\eta}\rangle\|=\mathcal{O}(\eta
d^{p+1}).$ (129)

Combining with the Trotter error bound (43) and the path-counting bound (122),
we obtain

$\left\lVert\mathscr{S}_{p}(t)-e^{-itH}\right\rVert_{\eta}=\mathcal{O}\left(\left\lVert\tau\right\rVert_{\max}^{\left\lvert\boldsymbol{\gamma}\right\rvert}\left\lVert\nu\right\rVert_{\max}^{p+1-\left\lvert\boldsymbol{\gamma}\right\rvert}d^{p+1}\eta
t^{p+1}\right).$ (130)

Finally, since
$1\leq\left\lvert\boldsymbol{\gamma}\right\rvert=\sum_{q=1}^{p+1}\gamma_{q}\leq
p$, we have

$\left\lVert\tau\right\rVert_{\max}^{\left\lvert\boldsymbol{\gamma}\right\rvert}\left\lVert\nu\right\rVert_{\max}^{p+1-\left\lvert\boldsymbol{\gamma}\right\rvert}\leq(\left\lVert\tau\right\rVert_{\max}+\left\lVert\nu\right\rVert_{\max})^{p}\left\lVert\tau\right\rVert_{\max}\left\lVert\nu\right\rVert_{\max}.$
(131)

This sketches the proof of the scaling in Eq. (3) of Theorem 1. A rigorous
proof using induction is given in Proposition 12.

######  Proposition 12 (Sparse path-counting bound).

Under the same assumption as in Proposition 11, if each column and row of
coefficient matrices $\tau,\nu$ has at most $d$ nonzero elements,

$\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}(\eta d^{p+1}),$ (132) $\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}(\eta d^{p+1}).$ (133)

###### Proof.

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

  * •

All fermionic paths $P$ start with either $N$ or $A$, but not $A^{\dagger}$
(we refer to the rightmost operator as the starting point).

  * •

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 $(2d)^{q}q!/2$.

The base case $q=2$ can be easily verified by noting that we only need to
consider $[T,V]$ or $[V,T]$. Using the commutation relations given in Eq.
(124) and (125), we can see in both cases that the fermionic paths all start
with either $N$ or $A$. For every site $i$, there are at most $4d^{2}$
fermionic paths starting with site $i$. Furthermore, every fermionic path
consists of $3$ elementary fermionic operators. These results establish all
the bullet points for the base case of $q=2$.

For every $q>2$, we use the induction hypothesis for $q-1$ to prove the
desired result. If $\gamma_{q}=1$, then we will 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).$
(134)

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 can show that all the claims hold for $q$ as follows. First,
if all the fermionic paths
$P^{\prime}\rhd\left(H^{\gamma_{q-1}}_{j_{q-1}k_{q-1}},\ldots,H^{\gamma_{1}}_{j_{1}k_{1}}\right)$
start with either $N$ or $A$, then all the paths
$P\rhd\left(H^{\gamma_{q}}_{j_{q}k_{q}},\ldots,H^{\gamma_{1}}_{j_{1}k_{1}}\right)$
will start with either $N$ or $A$. This follows from the commutation
relations: $[A^{\dagger}_{j}A_{k},A_{k_{q}}]=-\delta_{k_{y},j}A_{k}$ and
$\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}$.
Furthermore, since $P^{\prime}$ has at most $(q-1)+1=q$ elementary fermionic
operators, the expansion of $[A^{\dagger}_{j_{q}}A_{k_{q}},P^{\prime}]$ will
have at most $q+1$ elementary fermionic operators.

We now prove an upper bound for the number of fermionic paths starting from a
specific site $i$. If we take the commutator of $A^{\dagger}_{j_{q}}A_{k_{q}}$
with a fermionic operator that is not the starting operator in $P$, then the
starting operator is not affected. Because of the sparsity constraint and the
$\delta$ function created by the commutation relation in Eq. (124), we have
created at most $2d(q-1)\times$ more fermionic paths starting with site $i$.
Now if we take the commutator of $A^{\dagger}_{j_{q}}A_{k_{q}}$ with the
starting operator $A_{k_{y}}$ (for some index $k_{y}$) in the fermionic path
$P^{\prime}$, then the starting operator becomes $A_{k_{q}}$ and we have an
additional $\delta_{k_{y},j_{q}}$. In this case, $k_{q}$ can start from any
site, but there will be at most $d$ choices of $j_{q}$, hence $d$ choices of
$k_{y}$. This means we have created at most $2d\times$ more fermionic paths
starting with each site. The case where $N_{l_{z}}$ is the starting operator
can be analyzed in a similar way. Together, we have created at most
$2dq\times$ more fermionic paths starting with each site. This leads to an
upper bound of

$2dq(2d)^{q-1}(q-1)!/2=(2d)^{q}q!/2$ (135)

fermionic paths for each fixed starting site. The analysis for $\gamma_{q}=0$
proceeds in a similar way using Eq. (125). This completes the inductive step
for $q$.

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

$(2d)^{p+1}(p+1)!/2=\mathcal{O}(d^{p+1}).$ (136)

Because $P$ starts with either $A$ or $N$, $\left\lVert
P\lvert\boldsymbol{c}_{\eta}\rangle\right\rVert$ would be nonzero only if the
starting fermionic operator acts on one of the $\eta$ occupied sites in the
configuration $\boldsymbol{c}_{\eta}$. Hence there are at most
$\eta\mathcal{O}(d^{p+1})$ 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,

$\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}(\eta d^{p+1}).$
(137)

A similar argument can be used to prove the other claimed 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}(\eta
d^{p+1}).$ (138)

The argument uses the property that all fermionic paths $P$ end with either
$N$ or $A^{\dagger}$ but not $A$, which again follows from the commutation
relations (124) and (125). The proof is now completed. ∎

It is worth mentioning that the path-counting approach can also be used to
analyze the simulation of non-sparse electronic Hamiltonians. The resulting
bound, as given by (9), is slightly weaker than Eq. (2) of Theorem 1, but
suffices for our applications to be discussed in Section 6.1. See Appendix B
for details and proofs.

##  5 Tightness

We have already established multiple bounds in Theorem 1 on the fermionic
seminorm of the Trotter error. However, a common issue with the Trotterization
algorithm is that its error estimate can be very loose for simulating specific
systems. Here, we prove Theorem 2 that demonstrates the tightness of our
analysis for the interacting-electronic Hamiltonian (1).

Specifically, we construct concrete examples of interacting-electronic
Hamiltonian $H=T+V$ and lower-bound the fermionic seminorm of nested
commutators: $\left\lVert[T,\ldots[T,V]]\right\rVert_{\eta}$ in Section 5.1
and $\left\lVert[V,\ldots[V,T]]\right\rVert_{\eta}$ in Section 5.2. We show
that the results almost match the upper bounds in Theorem 1. Since Trotter
error depends on these nested commutators, this shows that our result is
nearly tight modulo an application of the triangle inequality.

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

We construct the electronic Hamiltonian $H=T+V$, where

$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}.$ (139)

Note that we may without loss of generality assume that $n$ is even, for
otherwise we restrict to the first $n-1$ spin orbitals. Comparing with the
definition of the interacting-electronic model (1), we see that the
coefficient matrix $\tau$ is an all-ones matrix with spectral norm
$\left\lVert\tau\right\rVert=n$, whereas $\nu$ contains an all-ones submatrix
on the top left corner with max-norm $\left\lVert\nu\right\rVert_{\max}=1$.
Our goal is to lower-bound the fermionic seminorm
$\left\lVert[T,\ldots[T,V]]\right\rVert_{\eta}$.

Due to the complicated commutation relations between $T$ and $V$, a direct
computation of $[T,\ldots[T,V]]$ seems technically challenging. Instead, we
perform a change of basis by applying the fermionic Fourier transform

$\mathrm{FFFT}^{\dagger}\cdot
A_{j}^{\dagger}\cdot\mathrm{FFFT}=\frac{1}{\sqrt{n}}\sum_{l=0}^{n-1}e^{-\frac{2\pi
ijl}{n}}A_{l}^{\dagger},\qquad\mathrm{FFFT}^{\dagger}\cdot
A_{k}\cdot\mathrm{FFFT}=\frac{1}{\sqrt{n}}\sum_{m=0}^{n-1}e^{\frac{2\pi
ikm}{n}}A_{m}.$ (140)

This gives

$\displaystyle\widetilde{T}$ $\displaystyle=\mathrm{FFFT}^{\dagger}\cdot
T\cdot\mathrm{FFFT}=nN_{0},$ (141) $\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}.$

We also define the $\eta$-electron states for $\eta\leq\frac{n}{2}$:

$\displaystyle\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}},\quad\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}}.$ (142)

The following proposition shows that the above choice of operators and states
almost saturates the fermionic seminorm of nested commutators.

######  Proposition 13.

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

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

A proof of this proposition is given in Appendix C. 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

$T=\frac{s}{n}\sum_{j,k=0}^{n-1}A_{j}^{\dagger}A_{k},\qquad
V=w\sum_{x,y=0}^{\frac{n}{2}-1}N_{x}N_{y}.$ (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{[}{T},\ldots\big{[}{T}}_{p},{V}\big{]}\big{]}\Big{\|}_{\eta}=\Big{\|}\underbrace{\big{[}\widetilde{T},\ldots\big{[}\widetilde{T}}_{p},\widetilde{V}\big{]}\big{]}\Big{\|}_{\eta}=\Omega\left(s^{p}w\eta\right),$
(145)

where we have used the unitary invariance of the fermionic seminorm in the
first equality. This establishes the first 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, suppose
we have $u,w>0$ and positive integer $2\leq
d\leq\eta\leq\frac{n}{2}$.131313The special case $d=1$ can be handled
separately by choosing $T=uA_{0}^{\dagger}A_{1}+uA_{1}^{\dagger}A_{0}$ and
$V=wN_{0}$. We may assume without loss of generality that $d$ is even, for
otherwise we use $d-1$. We then define

$T=u\sum_{j,k=0}^{d-1}A_{j}^{\dagger}A_{k},\qquad
V=w\sum_{x,y=0}^{\frac{d}{2}-1}N_{x}N_{y}.$ (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$. We also perform a fermionic Fourier
transform to define $\widetilde{T}$ and $\widetilde{V}$, but only to the first
$d$ spin orbitals

$\displaystyle\mathrm{FFFT}_{d}^{\dagger}\cdot
A_{j}^{\dagger}\cdot\mathrm{FFFT}_{d}$
$\displaystyle=\begin{cases}\frac{1}{\sqrt{d}}\sum_{l=0}^{d-1}e^{-\frac{2\pi
ijl}{d}}A_{l}^{\dagger},&0\leq j\leq d-1,\\\ A_{j}^{\dagger},&j\geq
d.\end{cases}$ (147) $\displaystyle\mathrm{FFFT}_{d}^{\dagger}\cdot
A_{k}\cdot\mathrm{FFFT}_{d}$
$\displaystyle=\begin{cases}\frac{1}{\sqrt{d}}\sum_{m=0}^{d-1}e^{\frac{2\pi
ikm}{d}}A_{m},&0\leq k\leq d-1,\\\ A_{k},&k\geq d.\end{cases}$

Then, a similar calculation shows that

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

This establishes the first claimed bound in (6) of Theorem 2.

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

Recall from the previous section that we have constructed the electronic
Hamiltonian (139) to prove the tightness of our bound. Comparing to the
definition of the interacting-electronic model (1), we see that the
coefficient matrix $\tau$ has spectral norm $\left\lVert\tau\right\rVert=n$,
whereas coefficient matrix $\nu$ has max-norm
$\left\lVert\nu\right\rVert_{\max}=1$. Our goal in this subsection is to
lower-bound the fermionic seminorm
$\left\lVert[V,\ldots[V,T]]\right\rVert_{\eta}$. To this end, we define the
$\eta$-electron states for $\eta\leq\frac{n}{2}$: