



@article {2913,
	title = {Hamiltonian simulation with random inputs},
	journal = {Phys. Rev. Lett. 129, 270502},
	volume = {129},
	year = {2022},
	month = {12/30/2022},
	abstract = {<p>The algorithmic error of digital quantum simulations is usually explored in terms of the spectral norm distance between the actual and ideal evolution operators. In practice, this worst-case error analysis may be unnecessarily pessimistic. To address this, we develop a theory of average-case performance of Hamiltonian simulation with random initial states. We relate the average-case error to the Frobenius norm of the multiplicative error and give upper bounds for the product formula (PF) and truncated Taylor series methods. As applications, we estimate average-case error for digital Hamiltonian simulation of general lattice Hamiltonians and k-local Hamiltonians. In particular, for the nearest-neighbor Heisenberg chain with n spins, the error is quadratically reduced from O(n) in the worst case to O(n\&minus;\&minus;\&radic;) on average for both the PF method and the Taylor series method. Numerical evidence suggests that this theory accurately characterizes the average error for concrete models. We also apply our results to error analysis in the simulation of quantum scrambling.</p>},
	doi = {https://doi.org/10.1103/PhysRevLett.129.270502},
	url = {https://arxiv.org/abs/2111.04773},
	author = {Qi Zhao and You Zhou and Alexander F. Shaw and Tongyang Li and Andrew M. Childs}
}
@article {2543,
	title = {High-precision quantum algorithms for partial differential equations},
	journal = {Quantum 5, 574},
	volume = {5},
	year = {2021},
	month = {11/4/2021},
	abstract = {<p>Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm can produce an explicit description. However, while high-precision quantum algorithms for linear ordinary differential equations are well established, the best previous quantum algorithms for linear partial differential equations (PDEs) have complexity poly(1/ε), where ε is the error tolerance. By developing quantum algorithms based on adaptive-order finite difference methods and spectral methods, we improve the complexity of quantum algorithms for linear PDEs to be poly(d,log(1/ε)), where d is the spatial dimension. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound. We develop a finite difference algorithm for the Poisson equation and a spectral algorithm for more general second-order elliptic equations.\&nbsp;</p>},
	doi = {https://doi.org/10.22331/q-2021-11-10-574},
	url = {https://arxiv.org/abs/2002.07868},
	author = {Andrew M. Childs and Jin-Peng Liu and Aaron Ostrander}
}
@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}
}
@article {1227,
	title = {Hamiltonian Simulation Using Linear Combinations of Unitary Operations},
	journal = {Quantum Information and Computation},
	volume = {12},
	year = {2012},
	month = {2012/11/01},
	pages = {901-924},
	abstract = {  We present a new approach to simulating Hamiltonian dynamics based on
implementing linear combinations of unitary operations rather than products of
unitary operations. The resulting algorithm has superior performance to
existing simulation algorithms based on product formulas and, most notably,
scales better with the simulation error than any known Hamiltonian simulation
technique. Our main tool is a general method to nearly deterministically
implement linear combinations of nearby unitary operations, which we show is
optimal among a large class of methods.
},
	url = {http://arxiv.org/abs/1202.5822v1},
	author = {Andrew M. Childs and Nathan Wiebe}
}
