* [10] Bela Bauer, Sergey Bravyi, Mario Motta, and Garnet Kin-Lic Chan, _Quantum algorithms for quantum chemistry and quantum materials science_ , Chemical Reviews 120 (2020), no. 22, 12685–12717, arXiv:2001.03685 https://doi.org/10.1021/acs.chemrev.9b00829.
  * [11] Robert Beals, Stephen Brierley, Oliver Gray, Aram W. Harrow, Samuel Kutin, Noah Linden, Dan Shepherd, and Mark Stather, _Efficient distributed quantum computing_ , Proceedings of the Royal Society A 469 (2013), no. 2153, 20120686, arXiv:1207.2307 https://doi.org/10.1098/rspa.2012.0686.
  * [12] Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders, _Efficient quantum algorithms for simulating sparse Hamiltonians_ , Communications in Mathematical Physics 270 (2007), 359–371, arXiv:quant-ph/0508139 https://doi.org/10.1007/s00220-006-0150-x.
  * [13] Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and Rolando D Somma, _Simulating Hamiltonian dynamics with a truncated Taylor series_ , Physical Review Letters 114 (2015), no. 9, 090502, arXiv:1412.4687 https://doi.org/10.1103/PhysRevLett.114.090502.
  * [14] Dominic W. Berry, Andrew M. Childs, Yuan Su, Xin Wang, and Nathan Wiebe, _Time-dependent Hamiltonian simulation with ${L}^{1}$-norm scaling_, Quantum 4 (2020), 254, arXiv:1906.07115 https://doi.org/10.22331/q-2020-04-20-254.
  * [15] Dominic W. Berry, Craig Gidney, Mario Motta, Jarrod R. McClean, and Ryan Babbush, _Qubitization of arbitrary basis quantum chemistry leveraging sparsity and low rank factorization_ , Quantum 3 (2019), 208, arXiv:1902.02134 https://doi.org/10.22331/q-2019-12-02-208.
  * [16] Jean Bourgain, _On growth of Sobolev norms in linear Schrödinger equations with smooth time dependent potential_ , Journal d’Analyse Mathématique 77 (1999), no. 1, 315–348 https://doi.org/10.1007/BF02791265.
  * [17] John P. Boyd, _Chebyshev and Fourier spectral methods_ , Courier Corporation, 2001.
  * [18] Susanne C. Brenner and L. Ridgway Scott, _The mathematical theory of finite element methods_ , vol. 3, Springer, 2008 https://doi.org/10.1007/978-0-387-75934-0.
  * [19] Earl Campbell, _Random compiler for fast Hamiltonian simulation_ , Physical Review Letters 123 (2019), no. 7, 070503, arXiv:1811.08017 https://doi.org/10.1103/PhysRevLett.123.070503.
  * [20] Yudong Cao, Jonathan Romero, Jonathan P. Olson, Matthias Degroote, Peter D. Johnson, Mária Kieferová, Ian D. Kivlichan, Tim Menke, Borja Peropadre, Nicolas P. D. Sawaya, et al., _Quantum chemistry in the age of quantum computing_ , Chemical Reviews 119 (2019), no. 19, 10856–10915, arXiv:1812.09976 https://doi.org/10.1021/acs.chemrev.8b00803.
  * [21] Shouvanik Chakrabarti, Andrew M. Childs, Tongyang Li, and Xiaodi Wu, _Quantum algorithms and lower bounds for convex optimization_ , Quantum 4 (2020), 221, arXiv:1809.01731 https://doi.org/10.22331/q-2020-01-13-221.
  * [22] Andrew M. Childs, _Quantum information processing in continuous time_ , Ph.D. thesis, Massachusetts Institute of Technology, 2004.
  * [23] Andrew M. Childs and Robin Kothari, _Limitations on the simulation of non-sparse Hamiltonians_ , Quantum Information & Computation 10 (2010), no. 7, 669–684, arXiv:0908.4398 https://doi.org/10.26421/QIC10.7-8-7.
  * [24] Andrew M. Childs, Jin-Peng Liu, and Aaron Ostrander, _High-precision quantum algorithms for partial differential equations_ , Quantum 5 (2021), 574, arXiv:2002.07868 https://doi.org/10.22331/q-2021-11-10-574.
  * [25] Andrew M. Childs, Dmitri Maslov, Yunseong Nam, Neil J. Ross, and Yuan Su, _Toward the first quantum simulation with quantum speedup_ , Proceedings of the National Academy of Sciences 115 (2018), no. 38, 9456–9461, arXiv:1711.10980 https://doi.org/10.1073/pnas.1801723115.
  * [26] Andrew M. Childs, Yuan Su, Minh C. Tran, Nathan Wiebe, and Shuchen Zhu, _Theory of Trotter error with commutator scaling_ , Physical Review X 11 (2021), no. 1, 011020, arXiv:1912.08854 https://doi.org/10.1103/PhysRevX.11.011020.
  * [27] Andrew M. Childs and Nathan Wiebe, _Hamiltonian simulation using linear combinations of unitary operations_ , Quantum Information & Computation 12 (2012), no. 11-12, 901–924, arXiv:1202.5822 https://doi.org/10.26421/QIC12.11-12-1.
  * [28] Yann N. Dauphin, Razvan Pascanu, Caglar Gulcehre, Kyunghyun Cho, Surya Ganguli, and Yoshua Bengio, _Identifying and attacking the saddle point problem in high-dimensional non-convex optimization_ , Advances in Neural Information Processing Systems, pp. 2933–2941, 2014, arXiv:1406.2572.
  * [29] Richard P. Feynman, _Simulating physics with computers_ , International Journal of Theoretical Physics 21 (1982), no. 6, 467–488 https://doi.org/10.1007/BF02650179.
  * [30] Yan V. Fyodorov and Ian Williams, _Replica symmetry breaking condition exposed by random matrix calculation of landscape complexity_ , Journal of Statistical Physics 129 (2007), no. 5-6, 1081–1116, arXiv:cond-mat/0702601 https://doi.org/10.1007/s10955-007-9386-x.
  * [31] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe, _Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics_ , Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 193–204, 2019, arXiv:1806.01838 https://doi.org/10.1145/3313276.3316366.
  * [32] Gabriele Giuliani and Giovanni Vignale, _Quantum theory of the electron liquid_ , Cambridge University Press, 2005 https://doi.org/10.1017/CBO9780511619915.
  * [33] Leslie Greengard and Vladimir Rokhlin, _A fast algorithm for particle simulations_ , Journal of Computational Physics 73 (1987), no. 2, 325–348 https://doi.org/10.1016/0021-9991(87)90140-9.
  * [34] Jeongwan Haah, Matthew Hastings, Robin Kothari, and Guang Hao Low, _Quantum algorithm for simulating real time evolution of lattice Hamiltonians_ , Proceedings of the 59th Annual Symposium on Foundations of Computer Science, pp. 350–360, IEEE, 2018, arXiv:1801.03922 https://doi.org/10.1137/18M1231511.
  * [35] Matthew B. Hastings, Dave Wecker, Bela Bauer, and Matthias Troyer, _Improving quantum algorithms for quantum chemistry_ , Quantum Information & Computation 15 (2015), no. 1-2, 1–21, arXiv:1403.1539 https://doi.org/10.26421/QIC15.1-2-1.
  * [36] Francis Begnaud Hildebrand, _Introduction to numerical analysis_ , Courier Corporation, 1987 https://doi.org/10.1007/978-0-387-21738-3.
  * [37] Chi Jin, Praneeth Netrapalli, and Michael I. Jordan, _Accelerated gradient descent escapes saddle points faster than gradient descent_ , Conference on Learning Theory, pp. 1042–1085, 2018, arXiv:1711.10456.
  * [38] Shi Jin, Xiantao Li, and Nana Liu, _Quantum simulation in the semi-classical regime_ , Quantum 6 (2022), 739 arXiv:2112.13279 https://doi.org/10.22331/q-2022-06-17-739.
  * [39] Stephen P. Jordan, _Fast quantum algorithm for numerical gradient estimation_ , Physical Review Letters 95 (2005), no. 5, 050501, arXiv:quant-ph/0405146 https://doi.org/10.1103/PhysRevLett.95.050501.
  * [40] Stephen P. Jordan, Keith S.M. Lee, and John Preskill, _Quantum algorithms for quantum field theories_ , Science 336 (2012), no. 6085, 1130–1133, arXiv:1111.3633 https://doi.org/10.1126/science.1217069.
  * [41] Ivan Kassal, Stephen P. Jordan, Peter J. Love, Masoud Mohseni, and Alán Aspuru-Guzik, _Polynomial-time quantum algorithm for the simulation of chemical dynamics_ , Proceedings of the National Academy of Sciences 105 (2008), no. 48, 18681–18686, arXiv:0801.2986 https://doi.org/10.1073/pnas.0808245105.
  * [42] Ian D. Kivlichan, Nathan Wiebe, Ryan Babbush, and Alán Aspuru-Guzik, _Bounding the costs of quantum simulation of many-body physics in real space_ , Journal of Physics A: Mathematical and Theoretical 50 (2017), no. 30, 305301, arXiv:1608.05696 https://dx.doi.org/10.1088/1751-8121/aa77b8.
  * [43] Joonho Lee, Dominic Berry, Craig Gidney, William J. Huggins, Jarrod R. McClean, Nathan Wiebe, and Ryan Babbush, _Even more efficient quantum computations of chemistry through tensor hypercontraction_ , PRX Quantum 2 (2021), no. 3, 030305, arXiv:2011.03494 https://doi.org/10.1103/PRXQuantum.2.030305.
  * [44] Seth Lloyd, _Universal quantum simulators_ , Science (1996), 1073–1078 https://doi.org/10.1126/science.273.5278.1073.
  * [45] Guang Hao Low and Isaac L. Chuang, _Hamiltonian simulation by qubitization_ , Quantum 3 (2019), 163, arXiv:1610.06546 https://doi.org/10.22331/q-2019-07-12-163.
  * [46] Guang Hao Low and Nathan Wiebe, _Hamiltonian simulation in the interaction picture_ , 2018, arXiv:1805.00675.
  * [47] Richard M. Martin, _Electronic structure_ , Cambridge University Press, 2004 https://doi.org/10.1017/CBO9780511805769.
  * [48] Sam McArdle, Earl Campbell, and Yuan Su, _Exploiting fermion number in factorized decompositions of the electronic structure Hamiltonian_ , Physical Review A 105 (2022), no. 1, 012403, arXiv:2107.07238 https://doi.org/10.1103/PhysRevA.105.012403.
  * [49] Jarrod R. McClean, Ryan Babbush, Peter J. Love, and Alán Aspuru-Guzik, _Exploiting locality in quantum computation for quantum chemistry_ , The Journal of Physical Chemistry Letters 5 (2014), no. 24, 4368–4380 https://doi.org/10.1021/jz501649m.
  * [50] Mario Motta, Erika Ye, Jarrod R. McClean, Zhendong Li, Austin J. Minnich, Ryan Babbush, and Garnet Kin-Lic Chan, _Low rank representations for quantum simulation of electronic structure_ , npj Quantum Information 7 (2021), no. 1, 1–7, arXiv:1808.02625 https://doi.org/10.1038/s41534-021-00416-z.
  * [51] David Poulin, Matthew B. Hastings, David Wecker, Nathan Wiebe, Andrew C. Doberty, and Matthias Troyer, _The Trotter step size required for accurate quantum simulation of quantum chemistry_ , Quantum Information & Computation 15 (2015), no. 5-6, 361–384, arXiv:1406.4920 https://doi.org/10.26421/QIC15.5-6-1.
  * [52] John Preskill, _Simulating quantum field theory with a quantum computer_ , The 36th Annual International Symposium on Lattice Field Theory, vol. 334, p. 024, SISSA Medialab, 2019, arXiv:1811.10085 DOI:https://doi.org/10.22323/1.334.0024.
  * [53] Markus Reiher, Nathan Wiebe, Krysta M. Svore, Dave Wecker, and Matthias Troyer, _Elucidating reaction mechanisms on quantum computers_ , Proceedings of the National Academy of Sciences 114 (2017), no. 29, 7555–7560, arXiv:1605.03590 https://doi.org/10.1073/pnas.1619152114.
  * [54] Vivek Sarin, Ananth Grama, and Ahmed Sameh, _Analyzing the error bounds of multipole-based treecodes_ , SC’98: Proceedings of the 1998 ACM/IEEE Conference on Supercomputing, pp. 19–19, IEEE, 1998 https://doi.org/10.1109/SC.1998.10041.
  * [55] Jacob T. Seeley, Martin J. Richard, and Peter J. Love, _The Bravyi-Kitaev transformation for quantum computation of electronic structure_ , The Journal of Chemical Physics 137 (2012), no. 22, 224109, arXiv:1208.5986 https://doi.org/10.1063/1.4768229.
  * [56] Jie Shen and Tao Tang, _Spectral and high-order methods with applications_ , Science Press Beijing, 2006, https://www.math.purdue.edu/ shen7/sp_intro12/book.pdf.
  * [57] Bin Shi, Weijie J. Su, and Michael I. Jordan, _On learning rates and Schrödinger operators_ , 2020, arXiv:2004.06977.
  * [58] Yuan Su, Dominic W Berry, Nathan Wiebe, Nicholas Rubin, and Ryan Babbush, _Fault-tolerant quantum simulations of chemistry in first quantization_ , PRX Quantum 2 (2021), no. 4, 040332, arXiv:2105.12767 https://doi.org/10.1103/PRXQuantum.2.040332.
  * [59] Yuan Su, Hsin-Yuan Huang, and Earl T. Campbell, _Nearly tight Trotterization of interacting electrons_ , Quantum 5 (2021), 495, arXiv:2012.09194 https://doi.org/10.22331/q-2021-07-05-495.
  * [60] Masuo Suzuki, _General theory of fractal path integrals with applications to many-body theories and statistical physics_ , Journal of Mathematical Physics 32 (1991), no. 2, 400–407 https://doi.org/10.1063/1.529425.
  * [61] Barna Szabó and Ivo Babuška, _Finite element analysis_ , John Wiley & Sons, 1991.
  * [62] Borzu Toloui and Peter J. Love, _Quantum algorithms for quantum chemistry based on the sparsity of the CI-matrix_ , 2013, arXiv:1312.2579.
  * [63] Vera von Burg, Guang Hao Low, Thomas Häner, Damian S. Steiger, Markus Reiher, Martin Roetteler, and Matthias Troyer, _Quantum computing enhanced computational catalysis_ , Physical Review Research 3 (2021), no. 3, 033055, arXiv:2007.14460 https://doi.org/10.1103/PhysRevResearch.3.033055.
  * [64] Dave Wecker, Bela Bauer, Bryan K. Clark, Matthew B. Hastings, and Matthias Troyer, _Gate-count estimates for performing quantum chemistry on small quantum computers_ , Physical Review A 90 (2014), no. 2, 022305, arXiv:1312.1695 https://doi.org/10.1103/PhysRevA.90.022305.
  * [65] James D. Whitfield, Jacob Biamonte, and Alán Aspuru-Guzik, _Simulation of electronic structure Hamiltonians using quantum computers_ , Molecular Physics 109 (2011), no. 5, 735–750, arXiv:1001.3855 https://doi.org/10.1080/00268976.2011.552441.
  * [66] Stephen Wiesner, _Simulations of many-body quantum systems by a quantum computer_ , 1996, arXiv:quant-ph/9603028.
  * [67] Christof Zalka, _Efficient simulation of quantum systems by quantum computers_ , Fortschritte der Physik: Progress of Physics 46 (1998), no. 6-8, 877–879, arXiv:quant-ph/9603026.
  * [68] Chenyi Zhang, Jiaqi Leng, and Tongyang Li, _Quantum algorithms for escaping from saddle points_ , Quantum 5 (2021), 529, arXiv:2007.10253v3 https://doi.org/10.22331/q-2021-08-20-529.
  * [69] Chenyi Zhang and Tongyang Li, _Escape saddle points by a simple gradient-descent based algorithm_ , Advances in Neural Information Processing Systems, vol. 34, 2021, arXiv:2111.14069.

##  Appendix A Notation

Throughout the paper, $\mathbb{N}$ denotes the set of all positive integers,
and $\mathbb{N}_{0}:=\mathbb{N}\cup\\{0\\}$. We also let
$[n]:=\\{1,\ldots,n\\}$ and $[{n+1}]_{0}:=\\{0,1,\ldots,n\\}$. We introduce a
variety of norms that are used in our analysis.

######  Definition 1 (Vector norms).

For a vector $\mathbf{v}=(v_{1},...,v_{d})^{T}\in\mathbb{C}^{d}$, and $1\leq
p\leq\infty$, the vector $l_{p}$ norm of $\mathbf{v}$ is

$\displaystyle\|\mathbf{v}\|_{p}:=\begin{cases}\left(\sum^{d}_{j=1}|v_{j}|^{p}\right)^{1/p}&1\leq
p<\infty\\\ \max_{j=1,2,...,d}|v_{j}|&p=\infty.\end{cases}$ (160)

######  Definition 2 (Matrix norms).

For a matrix $A\in M^{d\times d}(\mathbb{C})$, the Schatten $p$-norm of $A$ is

$\displaystyle\|A\|_{p}:=\begin{cases}\operatorname{Tr}\left(\sqrt{A^{\dagger}A}\right)&p=1\\\
\sqrt{\operatorname{Tr}(A^{\dagger}A)}&p=2\\\
\max_{\|\ket{\psi}\|_{2}=1}\|A\ket{\psi}\|_{2}&p=\infty.\end{cases}$ (161)

The Schatten $\infty$-norm is also referred to as the spectral norm, as it
equals the largest singular value of $A$. In this paper, we usually let
$\|A\|$ denote the spectral norm of $A$ when the context is unambiguous.

######  Definition 3 (Function norms).

If $f\colon\Omega\to\mathbb{C}$ is a continuous function defined on a set
$\Omega\subset\mathbb{R}^{d}$, the $L^{p}$-norm of the function $f$ is

$\displaystyle\|f\|_{p}:=\begin{cases}\left(\int_{\Omega}|f(x)|^{p}\,\mathrm{d}x\right)^{1/p}&1\leq
p<\infty\\\ \sup_{x\in\Omega}|f(x)|&p=\infty.\end{cases}$ (162)

We combine these notations to define norms for vector-valued (or operator-
valued) functions. If $\mathbf{v}\colon[0,t]\to\mathbb{C}^{d}$ is a continuous
vector-valued function, where the $j$th coordinate at time $s$ is $v_{j}(s)$,
then the notation $\|\mathbf{v}\|_{p,q}$ indicates that we take the $l_{p}$
norm $\|\mathbf{v}(s)\|_{p}$ for every $s\in[0,t]$ and compute the
$L^{q}$-norm of the resulting scalar function. For instance,

$\displaystyle\|\mathbf{v}\|_{1,\infty}:=\sup_{s\in[0,t]}\sum^{d}_{j=1}|v_{j}(s)|.$
(163)

######  Definition 4.

The largest matrix element of $A$ in absolute value is denoted

$\displaystyle\|A\|_{\max}:=\max_{j,k}|A_{j,k}|.$ (164)

Note that $\|A\|_{\max}$ is a vector norm of $A$ but does not satisfy the sub-
multiplicative property of a matrix norm.

######  Lemma 14 ([23, Lemma 1]).

For any Hermitian matrix $A\in\mathbb{C}^{N}\times\mathbb{C}^{N}$, we have

$\displaystyle\|A\|_{\max}\leq\|A\|\leq N\|A\|_{\max}.$ (165)

Finally, we introduce the notion of block encoding and some related concepts.

######  Definition 5 (Block encoding).

Suppose that $A$ is an $s$-qubit operator, $\alpha,\epsilon\in\mathbb{R}^{+}$,
and $a\in\mathbb{N}$. Then we say the $(s+a)$-qubit unitary $U$ is an
$(\alpha,a,\epsilon)$-block-encoding of $A$ if

$\displaystyle\|A-\alpha\left(\bra{0}^{\otimes
a}\otimes\mathbbmss{1}_{s})U(\ket{0}^{\otimes
a}\otimes\mathbbmss{1}_{s})\right)\|\leq\epsilon.$ (166)

The following result shows that sparse matrices can be efficiently block-
encoded.

######  Lemma 15 ([31, Lemma 48]).

Let $\Gamma\in\mathbb{C}^{2^{\omega}\times 2^{\omega}}$ be a matrix that is
$s_{r}$-row-sparse and $s_{c}$-column-sparse, and each element of $\Gamma$ has
absolute value at most $1$. Suppose that we have access to the following
sparse-access oracles acting on two $\omega+1$ qubit registers:

$\displaystyle O_{r}\colon\ket{i}\ket{k}\to\ket{i}\ket{r_{ik}},]\qquad\forall
i\in[2^{\omega}]-1,\,k\in[s_{r}],$ (167)

and

$\displaystyle O_{c}\colon\ket{\ell}\ket{j}\to\ket{c_{\ell
j}}\ket{j}\qquad\forall\ell\in[s_{c}],\,j\in[2^{\omega}]-1,$ (168)

where $r_{ij}$ is the index of the $j$th non-zero entry in the $i$th row of
$\Gamma$, or $j+2^{\omega}$ if there are fewer than $i$ non-zero entries; and
similarly, $c_{ij}$ is the index of the $i$th non-zero entry in the $j$th
column of $\Gamma$, or $i+2^{\omega}$ if there are fewer than $j$ non-zero
entries. Additionally, assume that we have access to an oracle $O_{\Gamma}$
for the entries of $A$:

$\displaystyle O_{\Gamma}\colon\ket{i}\ket{j}\ket{0}^{\otimes
z}\to\ket{i}\ket{j}\ket{\Gamma_{ij}},\qquad\forall i,j\in[2^{\omega}]-1,$
(169)

where $\Gamma_{ij}$ is a $z$-bit binary encoding of the $ij$-matrix element of
$\Gamma$. Then we can implement a
$(\sqrt{s_{r}s_{c}},\omega+3,\epsilon)$-block-encoding of $\Gamma$ with a
single use of $O_{r}$, $O_{c}$, two uses of $O_{\Gamma}$, and
$O\big{(}\omega+\log^{2.5}\big{(}\frac{s_{r}s_{c}}{\epsilon}\big{)}\big{)}$
additional one- and two-qubit gates.

We also define a block encoding of a time-dependent Hamiltonian.

######  Definition 6 (HAM-T).

Let $\widetilde{H}_{I}(t)\colon[0,\varsigma]\rightarrow\mathbb{C}^{2^{w}\times
2^{w}}$ be the rescaled interaction-picture Hamiltonian in (94). We define a
block-encoding unitary oracle
$\operatorname{HAM-T}\in\mathbb{C}^{M2^{n_{a}+w}\times M2^{n_{a}+w}}$
satisfying

$\displaystyle\operatorname{HAM-T}=\begin{pmatrix}\mathfrak{H}&\cdot\\\
\cdot&\cdot\end{pmatrix}$ (170)

in which

$\displaystyle\mathfrak{H}=\operatorname{diag}\left[\widetilde{H}_{I}(t)(0),\widetilde{H}_{I}(\varsigma/M),\cdots,\widetilde{H}_{I}\left((M-1)\varsigma/M\right)\right].$
(171)

A direct calculation shows that

$\displaystyle(\bra{0}_{a}\otimes\mathbbmss{1})\operatorname{HAM-T}(\ket{0}_{a}\otimes\mathbbmss{1})=\sum_{m=0}^{M-1}\ket{m}\bra{m}\otimes\widetilde{H}_{I}(m\varsigma/M).$
(172)

##  Appendix B Exponential convergence of the Fourier spectral method

Here we establish a concrete error estimate for the Fourier spectral method.

######  Lemma 16 ([17, Theorem 20]).

Let $f(x)$ have the exact, infinite trigonometric polynomial representation

$\displaystyle
f(x)=\frac{\alpha_{0}}{2}+\sum_{k=0}^{\infty}\alpha_{k}\cos(kx)+\sum_{k=0}^{\infty}\beta_{k}\sin(kx).$
(173)

Let $S_{n+1}(x)$ denote the trigonometric polynomial that interpolates to a
function $f(x)$ on (26),

$\displaystyle
S_{n+1}(x)=\frac{a_{0}}{2}+\sum_{k=0}^{n/2}a_{k}\cos(kx)+\sum_{k=0}^{n/2}b_{k}\sin(kx).$
(174)

Then the error from the Fourier spectral method satisfies

$\displaystyle|f(x)-S_{n+1}(x)|\leq
2\sum_{k=n/2+1}^{\infty}(|\alpha_{k}|+|\beta_{k}|).$ (175)

Lemma 16 tells us that the error from the Fourier spectral method is bounded
by an infinite sum of the Fourier coefficients of $f(x)$. It is well-known
that the Fourier coefficients decay rapidly in terms of $n$, which is formally
established as follows.

######  Lemma 17.

Let $f(x)$ have the exact, infinite Fourier series representation

$\displaystyle f(x)=\sum_{k=-\infty}^{\infty}\hat{f}(k)e^{ikx}.$ (176)

Assume $f(x)\in\mathbb{C}^{p}$. Then the Fourier coefficient $\hat{f}(k)$
satisfies

$\displaystyle|\hat{f}(k)|\leq\frac{\|f^{(p)}\|_{L^{1}}}{k^{p}}.$ (177)

###### Proof.

The Fourier coefficient $\hat{f}(k)$ on $[-\pi,\pi]$ is

$\displaystyle\hat{f}(k)=\frac{1}{2\pi}\int_{-\pi}^{\pi}f(x)e^{-ikx}\mathrm{d}{x}.$
(178)

Using $f(x)\in\mathbb{C}^{p}$ and $f^{(k)}(-\pi)=f^{(k)}(\pi)$ for arbitrary
$k\in\mathbb{N}$, integrating by parts $p$ times, we obtain

$\displaystyle\hat{f}(k)=\frac{(-i)^{k}}{2\pi
k^{p}}\int_{-\pi}^{\pi}f^{(p)}(x)e^{-ikx}\mathrm{d}{x}.$ (179)

Thus, the magnitude of the Fourier coefficient has the gbound

$\displaystyle|\hat{f}(k)|\leq\frac{1}{2\pi
k^{p}}\int_{-\pi}^{\pi}|f^{(p)}(x)|\mathrm{d}{x}=\frac{\|f^{(p)}\|_{L^{1}}}{2\pi
k^{p}}$ (180)

as claimed. ∎

Note that the coefficients of the trigonometric polynomial and Fourier series
of $f(x)$ are related as

$\displaystyle\hat{f}(k)=\begin{cases}\frac{1}{2}(\alpha_{k}+i\beta_{k}),\qquad&k\in\mathbb{Z}^{+};\\\
\frac{1}{2}\alpha_{0},\qquad&k=0;\\\
\frac{1}{2}(\alpha_{k}-i\beta_{k}),\qquad&k\in\mathbb{Z}^{-}.\end{cases}$
(181)

Combining Lemma 16 with Lemma 17 gives an error bound for the Fourier spectral
method.

######  Lemma 18.

Under the same assumptions as Lemma 16, the error from the Fourier spectral
method satisfies

$\displaystyle|f(x)-S_{n+1}(x)|\leq\frac{2\|f^{(p)}\|_{L^{1}}}{\pi(p-1)(n/2+1)^{p-1}}.$
(182)

###### Proof.

Using (175) and (181), we upper bound the error by

$\displaystyle|f(x)-S_{n+1}(x)|\leq
2\sum_{k=n/2+1}^{\infty}(|\alpha_{k}|+|\beta_{k}|)\leq
4\sum_{k=n/2+1}^{\infty}|\hat{f}(k)|.$ (183)

Plugging in (177) gives

$\displaystyle\sum_{k=n/2+1}^{\infty}|\hat{f}(k)|\leq\sum_{k=n/2+1}^{\infty}\frac{\|f^{(p)}\|_{L^{1}}}{2\pi
k^{p}}.$ (184)

Such an infinite sum can be bounded by an infinite integral, using

$\displaystyle\sum_{k=n/2+1}^{\infty}\frac{1}{k^{p}}\leq\sum_{k=n/2+1}^{\infty}\int_{k-1}^{k}\frac{1}{y^{p}}\mathrm{d}{y}=\int_{n/2}^{\infty}\frac{1}{y^{p}}\mathrm{d}{y}=\frac{1}{(p-1)(n/2+1)^{p-1}}.$
(185)

Therefore

$\displaystyle|f(x)-S_{n+1}(x)|\leq\frac{2\|f^{(p)}\|_{L^{1}}}{\pi(p-1)(n/2+1)^{p-1}}$
(186)

as claimed. ∎

Since we are concerned with analytic $f(x)$, it suffices to choose $p=n/2$
(for $n\geq 6$) to obtain the following result.

######  Lemma 19.

If $f(x)$ is analytic, according to Lemma 16, the error from the Fourier
spectral method satisfies

$\displaystyle|f(x)-S_{n+1}(x)|\leq\frac{2}{\pi}\frac{\|f^{(n/2)}\|_{L^{1}}}{(n/2)^{n/2}}$
(187)

for any even integer $n\geq 6$.

This result implies an exponential convergence rate in terms of $n$.