



02005nas a2200181   4500008004100000245004600041210004500087260001400132300000800146490000600154520152300160100002301683700001601706700001701722700001801739700001801757856004801775       2022                        eng d00aQuantum simulation of real-space dynamics0 aQuantum simulation of realspace dynamics  c11/8/2022  a8600 v63 a<p>Quantum simulation is a prominent application of quantum computers. While there is extensive previous work on simulating finite-dimensional systems, less is known about quantum algorithms for real-space dynamics. We conduct a systematic study of such algorithms. In particular, we show that the dynamics of a d-dimensional Schrödinger equation with η particles can be simulated with gate complexity O~(ηdFpoly(log(g&prime;/ϵ))), where ϵ is the discretization error, g&prime; controls the higher-order derivatives of the wave function, and F measures the time-integrated strength of the potential. Compared to the best previous results, this exponentially improves the dependence on ϵ and g&prime; from poly(g&prime;/ϵ) to poly(log(g&prime;/ϵ)) and polynomially improves the dependence on T and d, while maintaining best known performance with respect to η. For the case of Coulomb interactions, we give an algorithm using η3(d+η)Tpoly(log(ηdTg&prime;/(Δϵ)))/Δ one- and two-qubit gates, and another using η3(4d)d/2Tpoly(log(ηdTg&prime;/(Δϵ)))/Δ one- and two-qubit gates and QRAM operations, where T is the evolution time and the parameter Δ regulates the unbounded Coulomb interaction. We give applications to several computational problems, including faster real-space simulation of quantum chemistry, rigorous analysis of discretization error for simulation of a uniform electron gas, and a quadratic improvement to a quantum algorithm for escaping saddle points in nonconvex optimization.</p>1 aChilds, Andrew, M.1 aLeng, Jiaqi1 aLi, Tongyang1 aLiu, Jin-Peng1 aZhang, Chenyi  uhttps://doi.org/10.22331%2Fq-2022-11-17-860