%0 Journal Article
%J Proceedings of the 56th IEEE Symposium on Foundations of Computer Science
%D 2015
%T Hamiltonian simulation with nearly optimal dependence on all parameters
%A Dominic W. Berry
%A Andrew M. Childs
%A Robin Kothari
%X We present an algorithm for sparse Hamiltonian simulation that has optimal dependence on all parameters of interest (up to log factors). Previous algorithms had optimal or near-optimal scaling in some parameters at the cost of poor scaling in others. Hamiltonian simulation via a quantum walk has optimal dependence on the sparsity $d$ at the expense of poor scaling in the allowed error $\epsilon$. In contrast, an approach based on fractional-query simulation provides optimal scaling in $\epsilon$ at the expense of poor scaling in $d$. Here we combine the two approaches, achieving the best features of both. By implementing a linear combination of quantum walk steps with coefficients given by Bessel functions, our algorithm achieves near-linear scaling in $\tau := d \|H\|_{\max} t$ and sublogarithmic scaling in $1/\epsilon$. Our dependence on $\epsilon$ is optimal, and we prove a new lower bound showing that no algorithm can have sublinear dependence on $\tau$.
%B Proceedings of the 56th IEEE Symposium on Foundations of Computer Science
%P 792-809
%8 2015/01/08
%G eng
%U http://arxiv.org/abs/1501.01715
%R 10.1109/FOCS.2015.54