@article {3187, title = {Quantum simulation of real-space dynamics}, journal = {Quantum}, volume = {6}, year = {2022}, month = {11/8/2022}, pages = {860}, abstract = {

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{\"o}dinger equation with η particles can be simulated with gate complexity O~(ηdFpoly(log(g\′/ϵ))), where ϵ is the discretization error, g\′ 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\′ from poly(g\′/ϵ) to poly(log(g\′/ϵ)) 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\′/(Δϵ)))/Δ one- and two-qubit gates, and another using η3(4d)d/2Tpoly(log(ηdTg\′/(Δϵ)))/Δ 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.

}, doi = {https://doi.org/10.22331/q-2022-11-17-860}, url = {https://doi.org/10.22331\%2Fq-2022-11-17-860}, author = {Andrew M. Childs and Jiaqi Leng and Tongyang Li and Jin-Peng Liu and Chenyi Zhang} } @article {2710, title = {Quantum-accelerated multilevel Monte Carlo methods for stochastic differential equations in mathematical finance}, journal = {Quantum 5, 481 (2021)}, volume = {5}, year = {2021}, month = {6/22/2021}, pages = {481}, abstract = {

Inspired by recent progress in quantum algorithms for ordinary and partial differential equations, we study quantum algorithms for stochastic differential equations (SDEs). Firstly we provide a quantum algorithm that gives a quadratic speed-up for multilevel Monte Carlo methods in a general setting. As applications, we apply it to compute expection values determined by classical solutions of SDEs, with improved dependence on precision. We demonstrate the use of this algorithm in a variety of applications arising in mathematical finance, such as the Black-Scholes and Local Volatility models, and Greeks. We also provide a quantum algorithm based on sublinear binomial sampling for the binomial option pricing model with the same improvement.

}, doi = {https://doi.org/10.22331/q-2021-06-24-481}, url = {https://arxiv.org/abs/2012.06283}, author = {Dong An and Noah Linden and Jin-Peng Liu and Ashley Montanaro and Changpeng Shao and Jiasu Wang} } @article {2702, title = {Quantum algorithms for the polynomial eigenvalue problems}, year = {2020}, month = {10/28/2020}, abstract = {

Polynomial eigenvalue problems (PEPs) arise in a variety of science and engineering applications, and many breakthroughs in the development of classical algorithms to solve PEPs have been made in the past decades. Here we attempt to solve PEPs in a quantum computer. Firstly, for generalized eigenvalue problems (GEPs) $A\x = \lambda B\x$ with A,B symmetric, and B positive definite, we give a quantum algorithm based on block-encoding and quantum phase estimation. In a more general case when B is invertible, B\−1A is diagonalizable and all the eigenvalues are real, we propose a quantum algorithm based on the Fourier spectral method to solve ordinary differential equations (ODEs). The inputs of our algorithms can be any desired states, and the outputs are superpositions of the eigenpairs. The complexities are polylog in the matrix size and linear in the precision. The dependence on precision is optimal. Secondly, we show that when B is singular, any quantum algorithm uses at least Ω(n\−\−\√) queries to compute the eigenvalues, where n is the matrix size. Thirdly, based on the linearization method and the connection between PEPs and higher-order ODEs, we provide two quantum algorithms to solve PEPs by extending the quantum algorithm for GEPs. We also give detailed complexity analysis of the algorithm for two special types of quadratic eigenvalue problems that are important in practice. Finally, under an extra assumption, we propose a quantum algorithm to solve PEPs when the eigenvalues are complex.

}, url = {https://arxiv.org/abs/2010.15027}, author = {Changpeng Shao and Jin-Peng Liu} } @article {2333, title = {Quantum spectral methods for differential equations}, journal = {Commun. Math. Phys. }, volume = {375}, year = {2020}, month = {2/18/2020}, pages = {1427-1457}, abstract = {

Recently developed quantum algorithms address computational challenges in numerical analysis by performing linear algebra in Hilbert space. Such algorithms can produce a quantum state proportional to the solution of a d-dimensional system of linear equations or linear differential equations with complexity poly(logd). While several of these algorithms approximate the solution to within ε with complexity poly(log(1/ε)), no such algorithm was previously known for differential equations with time-dependent coefficients. Here we develop a quantum algorithm for linear ordinary differential equations based on so-called spectral methods, an alternative to finite difference methods that approximates the solution globally. Using this approach, we give a quantum algorithm for time-dependent initial and boundary value problems with complexity poly(logd,log(1/ε)).

}, doi = {https://doi.org/10.1007/s00220-020-03699-z}, url = {https://arxiv.org/abs/1901.00961}, author = {Andrew M. Childs and Jin-Peng Liu} }