3
$\begingroup$

tl;dr: How can I show that $e^k/k^k$ is less than $\epsilon^2/2$ when $k=\Omega\left(\frac{\log(1/\epsilon)}{\log \log(1/\epsilon)}\right)$, where $k,\epsilon\in \mathbb{R}$ and > 0?

Context: Berry et al. show a $d$-sparse Hamiltonian can be approximately simulated for time $t$ with precision $\epsilon$ using $O\left(\frac{\log(\tau/\epsilon)}{\log \log(\tau/\epsilon )}\right)$ queries to an oracle, where $\tau=d^2\|H\|_{\max}t$ (1). The authors prove a related query complexity in Appendix 2, Lemma 3.5 which hinges on the argument $e^k/k^k$ is less than $\epsilon^2/2$ when $k=\Omega\left(\frac{\log(1/\epsilon)}{\log \log(1/\epsilon)}\right)$, where $k,\epsilon\in \mathbb{R}$ and > 0. I am not sure how to show this is the case and would greatly appreciate any insight!

arXiv:1312.1414 [quant-ph]

$\endgroup$

1 Answer 1

1
$\begingroup$

Here's the argument essentially given in Robin Kothari's thesis (p. 29 in particular).

From Stirling's approximation, we have $e^k/k^k \sim 1/k!$, or equivalently, $\log(k!) \sim k\log k - k$. Set $k = c\left(\frac{\log(1/\epsilon)}{\log\log(1/\epsilon)}\right)$ for some constant $c$. Then

\begin{align*} k\log k -k &= c\left(\frac{\log(1/\epsilon)}{\log\log(1/\epsilon)}\right) \left[\log\left(c\left(\frac{\log(1/\epsilon)}{\log\log(1/\epsilon)}\right)\right) - 1 \right]\\ &= c\left(\frac{\log(1/\epsilon)}{\log\log(1/\epsilon)}\right) \left( \log c + \log\log(1/\epsilon) - \log\log\log(1/\epsilon) - 1 \right)\\ &= \frac{c(\log c - 1)\log(1/\epsilon)}{\log\log(1/\epsilon)} + c\log(1/\epsilon) - \frac{c\log(1/\epsilon) \log\log\log(1/\epsilon)}{\log\log(1/\epsilon)}, \end{align*} which is asymptotically dominated by the $c\log(1/\epsilon)$ term. Thus $\log(k!) \sim c\log(1/\epsilon)$, and in particular we can choose $c$ large enough such that $\log(k!) \geq 2\log(\sqrt{2}/\epsilon)$. This implies that $1/k! \leq \epsilon^2/2$.

$\endgroup$
1
  • $\begingroup$ This is great. Kothari's thesis is an excellent reference; thanks for putting it on my radar! $\endgroup$
    – muru
    Sep 12, 2023 at 1:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.