@article {1247,
title = {Hamiltonian simulation with nearly optimal dependence on all parameters},
journal = {Proceedings of the 56th IEEE Symposium on Foundations of Computer Science},
year = {2015},
month = {2015/01/08},
pages = {792-809},
abstract = { 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$.
},
doi = {10.1109/FOCS.2015.54},
url = {http://arxiv.org/abs/1501.01715},
author = {Dominic W. Berry and Andrew M. Childs and Robin Kothari}
}