Taylor simulation tail bound

By [F1], choose an orthonormal eigenbasis of $H$ with eigenvalues $\lambda$. For a unit eigenvector $u_{\lambda }$, $\mathrm{\mid }\lambda \mathrm{\mid }=\mathrm{\parallel }H{u}_{\lambda }\mathrm{\parallel }=\mathrm{\parallel }{\sum }_j{a}_j{V}_j{u}_{\lambda }\mathrm{\parallel }\le {\sum }_j\mathrm{\mid }{a}_j\mathrm{\mid }\mathrm{\parallel }{V}_j{u}_{\lambda }\mathrm{\parallel }=\mathrm{\Lambda }$ by [F2]–[F4]. On this basis, [L1] and [L2] make the difference diagonal with scalar entries ${\sum }_{k=0}^K(-ih\lambda {)}^k\mathrm{/}k!-\exp (-ih\lambda )$.

Since $x\ge 0$, the finite Taylor coefficient sum obeys $0\le s_K={\sum }_{k=0}^K{x}^k\mathrm{/}k!\le {\sum }_{k=0}^{\mathrm{\infty }}{x}^k\mathrm{/}k!=e^x$ by [L1] and [F5]. If $x\le \ln 2$, [F7] gives $s_K\le e^x\le 2$.

Put $n=K+1$. The absolute scalar-series tail at eigenvalue $\lambda$ is at most ${\sum }_{k=n}^{\mathrm{\infty }}(\mathrm{\mid }h\mathrm{\mid }\mathrm{\mid }\lambda \mathrm{\mid }{)}^k\mathrm{/}k!$. Writing $k=n+j$ and using $(n+j)!\ge n!j!$ bounds this by $(\mathrm{\mid }h\mathrm{\mid }\mathrm{\mid }\lambda \mathrm{\mid }{)}^n\mathrm{/}n!{\sum }_{j=0}^{\mathrm{\infty }}(\mathrm{\mid }h\mathrm{\mid }\mathrm{\mid }\lambda \mathrm{\mid }{)}^j\mathrm{/}j!=e^{\mathrm{\mid }h\mathrm{\mid }\mathrm{\mid }\lambda \mathrm{\mid }}(\mathrm{\mid }h\mathrm{\mid }\mathrm{\mid }\lambda \mathrm{\mid }{)}^n\mathrm{/}n!$ by [F5]–[F6]. If the diagonal error has entries $d_i$ in the eigenbasis and $z={\sum }_i{z}_i{u}_i$, then its squared output norm is ${\sum }_i\mathrm{\mid }{d}_i{\mathrm{\mid }}^2\mathrm{\mid }{z}_i{\mathrm{\mid }}^2\le ({\max }_i\mathrm{\mid }{d}_i\mathrm{\mid }{)}^2\mathrm{\parallel }z{\mathrm{\parallel }}^2$; an eigenbasis vector attaining the finite maximum gives equality in the operator norm [F4]. Hence the operator norm is ${\max }_i\mathrm{\mid }{d}_i\mathrm{\mid }$. Since $0\le \mathrm{\mid }h\mathrm{\mid }\mathrm{\mid }{\lambda }_i\mathrm{\mid }\le x$, the monotonicity of $e^u$ and $u^n$ on nonnegative reals gives $e^{\mathrm{\mid }h\mathrm{\mid }\mathrm{\mid }{\lambda }_i\mathrm{\mid }}\mathrm{\mid }h{\mathrm{\mid }}^n\mathrm{\mid }{\lambda }_i{\mathrm{\mid }}^n\mathrm{/}n!\le e^x{x}^n\mathrm{/}n!$. Taking the maximum proves the stated tail bound.

Assume $x\le \ln 2$, so $e^x\le 2$ by [F7]. Let $L=\ln (1\mathrm{/}\eta )$. The exponential series gives $2<e<3$: its first two terms sum to $2$, while $1\mathrm{/}k!\le 2^{-(k-1)}$ for $k\ge 2$, with strict inequality for $k\ge 3$, so the remaining sum is less than $1$. Thus $\exp (0)=1<2<\exp (1)=e$ by [F5], and the strict increase and inverse relation in [F7] give $0<\ln 2<1$. If $L<1$, $n=10$ gives $2x^{10}\mathrm{/}10!<2\mathrm{/}10!<1\mathrm{/}3<e^{-1}<\eta$. If $L\ge 1$, take $n=\lceil 16eL\mathrm{/}\ln (e+L)\rceil$. For $z\ge 1$, $g(z)=\sqrt{z}-\ln z$ has derivative $g^{\mathrm{\prime }}(z)=(\sqrt{z}-2)\mathrm{/}(2z)$, so it decreases up to $z=4$ and increases thereafter. Since $e>2$, $\exp (2)=e^2>4$, hence $\ln 4<2$ by [F7]; thus $g(z)\ge g(4)=2-\ln 4>0$. Also $e+L<4L$. Therefore $\frac{n}{e}\ge \frac{16L}{\ln (e+L)}\ge \frac{16L}{\sqrt{e+L}}>4\sqrt{e+L},$ so $\ln (n\mathrm{/}e)>\frac{1}{2}\ln (e+L)$. Hence $n\ln (n\mathrm{/}e)\ge 8eL\ge L+\ln 4$, using $e>2$, $L\ge 1$, and $\ln 4<2$. For the factorial estimate, monotonicity of $\ln s$ gives $\ln (n!)={\sum }_{k=1}^n\ln k\ge {\int }_1^n\ln sds=n\ln n-n+1$, so $n!\ge (n\mathrm{/}e{)}^n\ge e^{L+\ln 4}=4\mathrm{/}\eta$. Since $e^x{x}^n\mathrm{/}n!\le 2\mathrm{/}n!$, this choice gives a tail at most $\eta \mathrm{/}2\le \eta$. In both cases $n=O(1+L\mathrm{/}\ln (e+L))$. Since $\ln (e+e^L)\le L+\ln 2\le e+L$, this is also $O(1+L\mathrm{/}\ln \ln (e+e^L))$, the displayed order after changing logarithm bases. Hence $K=n-1$ has the stated order.