01453nas a2200145 4500008004100000245007600041210006900117260001500186300001200201520099300213100002301206700002301229700001901252856003601271 2015 eng d00aHamiltonian simulation with nearly optimal dependence on all parameters0 aHamiltonian simulation with nearly optimal dependence on all par c2015/01/08 a792-8093 a 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$.
1 aBerry, Dominic, W.1 aChilds, Andrew, M.1 aKothari, Robin uhttp://arxiv.org/abs/1501.01715