@article {3512, title = {Multi-product Hamiltonian simulation with explicit commutator scaling}, year = {2024}, month = {3/13/2024}, abstract = {

The well-conditioned multi-product formula (MPF), proposed by [Low, Kliuchnikov, and Wiebe, 2019], is a simple high-order time-independent Hamiltonian simulation algorithm that implements a linear combination of standard product formulas of low order. While the MPF aims to simultaneously exploit commutator scaling among Hamiltonians and achieve near-optimal time and precision dependence, its lack of a rigorous error bound on the nested commutators renders its practical advantage ambiguous. In this work, we conduct a rigorous complexity analysis of the well-conditioned MPF, demonstrating explicit commutator scaling and near-optimal time and precision dependence at the same time. Using our improved complexity analysis, we present several applications of practical interest where the MPF based on a second-order product formula can achieve a polynomial speedup in both system size and evolution time, as well as an exponential speedup in precision, compared to second-order and even higher-order product formulas. Compared to post-Trotter methods, the MPF based on a second-order product formula can achieve polynomially better scaling in system size, with only poly-logarithmic overhead in evolution time and precision.

}, url = {https://arxiv.org/abs/2403.08922}, author = {Junaid Aftab and Dong An and Konstantina Trivisa} } @article {3426, title = {The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver}, year = {2023}, month = {12/12/2023}, abstract = {

The solution of linear systems of equations is the basis of many other quantum algorithms, and recent results provided an algorithm with optimal scaling in both the condition number κ and the allowable error ϵ [PRX Quantum \textbf{3}, 0403003 (2022)]. That work was based on the discrete adiabatic theorem, and worked out an explicit constant factor for an upper bound on the complexity. Here we show via numerical testing on random matrices that the constant factor is in practice about 1,500 times smaller than the upper bound found numerically in the previous results. That means that this approach is far more efficient than might naively be expected from the upper bound. In particular, it is over an order of magnitude more efficient than using a randomised approach from [arXiv:2305.11352] that claimed to be more efficient.

}, url = {https://arxiv.org/abs/2312.07690}, author = {Pedro C. S. Costa and Dong An and Ryan Babbush and Dominic Berry} } @article {3267, title = {Linear combination of Hamiltonian simulation for non-unitary dynamics with optimal state preparation cost}, journal = {Phys. Rev. Lett.}, volume = {131}, year = {2023}, month = {10/13/2023}, abstract = {

We propose a simple method for simulating a general class of non-unitary dynamics as a linear combination of Hamiltonian simulation (LCHS) problems. LCHS does not rely on converting the problem into a dilated linear system problem, or on the spectral mapping theorem. The latter is the mathematical foundation of many quantum algorithms for solving a wide variety of tasks involving non-unitary processes, such as the quantum singular value transformation (QSVT). The LCHS method can achieve optimal cost in terms of state preparation. We also demonstrate an application for open quantum dynamics simulation using the complex absorbing potential method with near-optimal dependence on all parameters.

}, doi = {https://journals.aps.org/prl/pdf/10.1103/PhysRevLett.131.150603}, url = {https://arxiv.org/abs/2303.01029}, author = {Dong An and Jin-Peng Liu and Lin Lin} } @article {3402, title = {Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters}, year = {2023}, month = {12/6/2023}, abstract = {

We introduce a family of identities that express general linear non-unitary evolution operators as a linear combination of unitary evolution operators, each solving a Hamiltonian simulation problem. This formulation can exponentially enhance the accuracy of the recently introduced linear combination of Hamiltonian simulation (LCHS) method [An, Liu, and Lin, Physical Review Letters, 2023]. For the first time, this approach enables quantum algorithms to solve linear differential equations with both optimal state preparation cost and near-optimal scaling in matrix queries on all parameters.

}, url = {https://arxiv.org/abs/2312.03916}, author = {Dong An and Andrew M. Childs and Lin Lin} } @article {3270, title = {A theory of quantum differential equation solvers: limitations and fast-forwarding}, year = {2023}, month = {3/2/2023}, abstract = {

We study the limitations and fast-forwarding of quantum algorithms for linear ordinary differential equation (ODE) systems with a 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 {\textquoteleft}{\textquoteleft}non-quantumness\&$\#$39;\&$\#$39;: real part gap and non-normality of the coefficient matrix. We then show that homogeneous ODEs in the absence of both types of {\textquoteleft}{\textquoteleft}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 improvements in the evolution time T for inhomogeneous ODEs with a negative semi-definite coefficient matrix, and exponential improvements in both T and the spectral norm of the coefficient matrix for inhomogeneous ODEs with efficiently implementable eigensystems, including various spatially discretized linear evolutionary partial differential equations. 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.

}, url = {https://arxiv.org/abs/2211.05246}, author = {Dong An and Jin-Peng Liu and Daochen Wang and Qi Zhao} } @article {3064, title = {Efficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation}, year = {2022}, month = {5/2/2022}, abstract = {

Nonlinear differential equations exhibit rich phenomena in many fields but are notoriously challenging to solve. Recently, Liu et al. [1] demonstrated the first efficient quantum algorithm for dissipative quadratic differential equations under the condition R\<1, where R measures the ratio of nonlinearity to dissipation using the l2 norm. Here we develop an efficient quantum algorithm based on [1] for reaction-diffusion equations, a class of nonlinear partial differential equations (PDEs). To achieve this, we improve upon the Carleman linearization approach introduced in [1] to obtain a faster convergence rate under the condition RD\<1, where RD measures the ratio of nonlinearity to dissipation using the l\∞ norm. Since RD is independent of the number of spatial grid points n while R increases with n, the criterion RD\<1 is significantly milder than R\<1 for high-dimensional systems and can stay convergent under grid refinement for approximating PDEs. As applications of our quantum algorithm we consider the Fisher-KPP and Allen-Cahn equations, which have interpretations in classical physics. In particular, we show how to estimate the mean square kinetic energy in the solution by postprocessing the quantum state that encodes it to extract derivative information.

}, url = {https://arxiv.org/abs/2205.01141}, author = {Dong An and Di Fang and Stephen Jordan and Jin-Peng Liu and Guang Hao Low and Jiasu Wang} } @article {3196, title = {Optimal scaling quantum linear systems solver via discrete adiabatic theorem}, journal = {PRX Quantum}, volume = {3}, year = {2022}, month = {10/7/2022}, pages = {040303}, abstract = {

Recently, several approaches to solving linear systems on a quantum computer have been formulated in terms of the quantum adiabatic theorem for a continuously varying Hamiltonian. Such approaches enabled near-linear scaling in the condition number κ of the linear system, without requiring a complicated variable-time amplitude amplification procedure. However, the most efficient of those procedures is still asymptotically sub-optimal by a factor of log(κ). Here, we prove a rigorous form of the adiabatic theorem that bounds the error in terms of the spectral gap for intrinsically discrete time evolutions. We use this discrete adiabatic theorem to develop a quantum algorithm for solving linear systems that is asymptotically optimal, in the sense that the complexity is strictly linear in κ, matching a known lower bound on the complexity. Our O(κlog(1/ϵ)) complexity is also optimal in terms of the combined scaling in κ and the precision ϵ. Compared to existing suboptimal methods, our algorithm is simpler and easier to implement. Moreover, we determine the constant factors in the algorithm, which would be suitable for determining the complexity in terms of gate counts for specific applications.

}, keywords = {FOS: Physical sciences, Quantum Physics (quant-ph)}, doi = {https://journals.aps.org/prxquantum/pdf/10.1103/PRXQuantum.3.040303}, url = {https://arxiv.org/abs/2111.08152}, author = {Costa, Pedro C. S. and Dong An and Sanders, Yuval R. and Su, Yuan and Babbush, Ryan and Berry, Dominic W.} } @article {3192, title = {A theory of quantum differential equation solvers: limitations and fast-forwarding}, year = {2022}, month = {11/9/2022}, abstract = {

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 {\textquoteleft}{\textquoteleft}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 {\textquoteleft}{\textquoteleft}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.

}, keywords = {FOS: Mathematics, FOS: Physical sciences, Numerical Analysis (math.NA), Quantum Physics (quant-ph)}, doi = {10.48550/ARXIV.2211.05246}, url = {https://arxiv.org/abs/2211.05246}, author = {Dong An and Liu, Jin-Peng and Wang, Daochen and Zhao, Qi} } @article {3197, title = {Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schr{\"o}dinger Equation}, journal = {Quantum}, volume = {6}, year = {2022}, month = {apr}, pages = {690}, abstract = {

We propose a simple quantum algorithm for simulating highly oscillatory quantum dynamics, which does not require complicated quantum control logic for handling time-ordering operators. To our knowledge, this is the first quantum algorithm that is both insensitive to the rapid changes of the time-dependent Hamiltonian and exhibits commutator scaling. Our method can be used for efficient Hamiltonian simulation in the interaction picture. In particular, we demonstrate that for the simulation of the Schr{\"o}dinger equation, our method exhibits superconvergence and achieves a surprising second order convergence rate, of which the proof rests on a careful application of pseudo-differential calculus. Numerical results verify the effectiveness and the superconvergence property of our method.

}, doi = {10.22331/q-2022-04-15-690}, url = {https://arxiv.org/abs/2111.03103v2}, author = {Dong An and Di Fang and Lin Lin} } @article {2926, title = {Optimal scaling quantum linear systems solver via discrete adiabatic theorem}, year = {2021}, month = {11/15/2021}, abstract = {

Recently, several approaches to solving linear systems on a quantum computer have been formulated in terms of the quantum adiabatic theorem for a continuously varying Hamiltonian. Such approaches enabled near-linear scaling in the condition number κ of the linear system, without requiring a complicated variable-time amplitude amplification procedure. However, the most efficient of those procedures is still asymptotically sub-optimal by a factor of log(κ). Here, we prove a rigorous form of the adiabatic theorem that bounds the error in terms of the spectral gap for intrinsically discrete time evolutions. We use this discrete adiabatic theorem to develop a quantum algorithm for solving linear systems that is asymptotically optimal, in the sense that the complexity is strictly linear in κ, matching a known lower bound on the complexity. Our O(κlog(1/ε)) complexity is also optimal in terms of the combined scaling in κ and the precision ε. Compared to existing suboptimal methods, our algorithm is simpler and easier to implement. Moreover, we determine the constant factors in the algorithm, which would be suitable for determining the complexity in terms of gate counts for specific applications.\ 

}, url = {https://arxiv.org/abs/2111.08152}, author = {Pedro C. S. Costa and Dong An and Yuval R. Sanders and Yuan Su and Ryan Babbush and Dominic W. Berry} } @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} }