



00782nas a2200229   4500008004100000245009900041210006900140260001500209490000700224653004300231653002100274653002700295653002900322653003900351653003100390100002300421700001700444700001800461700001800479700001800497856003700515       2022                        eng d00aQuantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants0 aQuantum Algorithms for Sampling LogConcave Distributions and Est  c10/12/20220 v3510aFOS: Computer and information sciences10aFOS: Mathematics10aFOS: Physical sciences10aMachine Learning (cs.LG)10aOptimization and Control (math.OC)10aQuantum Physics (quant-ph)1 aChilds, Andrew, M.1 aLi, Tongyang1 aLiu, Jin-Peng1 aWang, Chunhao1 aZhang, Ruizhe  uhttps://arxiv.org/abs/2210.0653902559nas a2200193   4500008004100000245008700041210006900128260001400197520194300211653002102154653002702175653003302202653003102235100001302266700001802279700001802297700001302315856003702328       2022                        eng d00aA theory of quantum differential equation solvers: limitations and fast-forwarding0 atheory of quantum differential equation solvers limitations and   c11/9/20223 a<p>We study the limitations and fast-forwarding of quantum algorithms for solving linear ordinary differential equation (ODE) systems with particular focus on non-quantum dynamics, where the coefficient matrix in the ODE is not anti-Hermitian or the ODE is inhomogeneous. On the one hand, for generic homogeneous linear ODEs, by proving worst-case lower bounds, we show that quantum algorithms suffer from computational overheads due to two types of ``non-quantumness&#39;&#39;: real part gap and non-normality of the coefficient matrix. We then show that ODEs in the absence of both types of ``non-quantumness&#39;&#39; are equivalent to quantum dynamics, and reach the conclusion that quantum algorithms for quantum dynamics work best. We generalize our results to the inhomogeneous case and find that existing generic quantum ODE solvers cannot be substantially improved. To obtain these lower bounds, we propose a general framework for proving lower bounds on quantum algorithms that are amplifiers, meaning that they amplify the difference between a pair of input quantum states. On the other hand, we show how to fast-forward quantum algorithms for solving special classes of ODEs which leads to improved efficiency. More specifically, we obtain quadratic to exponential improvements in terms of the evolution time T and the spectral norm of the coefficient matrix for the following classes of ODEs: inhomogeneous ODEs with a negative definite coefficient matrix, inhomogeneous ODEs with a coefficient matrix having an eigenbasis that can be efficiently prepared on a quantum computer and eigenvalues that can be efficiently computed classically, and the spatially discretized inhomogeneous heat equation and advection-diffusion equation. We give fast-forwarding algorithms that are conceptually different from existing ones in the sense that they neither require time discretization nor solving high-dimensional linear systems.</p>10aFOS: Mathematics10aFOS: Physical sciences10aNumerical Analysis (math.NA)10aQuantum Physics (quant-ph)1 aAn, Dong1 aLiu, Jin-Peng1 aWang, Daochen1 aZhao, Qi  uhttps://arxiv.org/abs/2211.05246