Time-marching based quantum solvers for time-dependent linear differential equations

Di Fang1,2,3, Lin Lin1,4,3, and Yu Tong5,1

1Department of Mathematics, University of California, Berkeley, CA 94720, USA
2Simons Institute for the Theory of Computing, University of California, Berkeley, CA 94720, USA
3Challenge Institute for Quantum Computation, University of California, Berkeley, CA 94720, USA
4Applied Mathematics and Computational Research Division, Lawrence Berkeley National Laboratory, Berkeley, CA 94720, USA
5Institute for Quantum Information and Matter, California Institute of Technology, Pasadena, CA 91125, USA

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.


The time-marching strategy, which propagates the solution from one time step to the next, is a natural strategy for solving time-dependent differential equations on classical computers, as well as for solving the Hamiltonian simulation problem on quantum computers. For more general homogeneous linear differential equations $\frac{\mathrm{d}}{\mathrm{d} t} |\psi(t)\rangle = A(t) |\psi(t)\rangle, |\psi(0)\rangle = |\psi_0\rangle$, a time-marching based quantum solver can suffer from exponentially vanishing success probability with respect to the number of time steps and is thus considered impractical. We solve this problem by repeatedly invoking a technique called the uniform singular value amplification, and the overall success probability can be lower bounded by a quantity that is independent of the number of time steps. The success probability can be further improved using a compression gadget lemma. This provides a path of designing quantum differential equation solvers that is alternative to those based on quantum linear systems algorithms (QLSA). We demonstrate the performance of the time-marching strategy with a high-order integrator based on the truncated Dyson series. The complexity of the algorithm depends linearly on the amplification ratio, which quantifies the deviation from a unitary dynamics. We prove that the linear dependence on the amplification ratio attains the query complexity lower bound and thus cannot be improved in the worst case. This algorithm also surpasses existing QLSA based solvers in three aspects: (1) $A(t)$ does not need to be diagonalizable. (2) $A(t)$ can be non-smooth, and is only of bounded variation. (3) It can use fewer queries to the initial state $|\psi_0\rangle$. Finally, we demonstrate the time-marching strategy with a first-order truncated Magnus series, which simplifies the implementation compared to high-order truncated Dyson series approach, while retaining the aforementioned benefits. Our analysis also raises some open questions concerning the differences between time-marching and QLSA based methods for solving differential equations.

Quantum computers are naturally suited for simulating unitary dynamics, offering the prospect of simulating quantum systems that the best known classical algorithms cannot handle. Recent years have seen much effort in extending this advantage to general linear ordinary differential equations (ODEs) which are not necessarily unitary. On classical computers, these ODEs are usually solved via the time-marching strategy, i.e., dividing the time into short segments and evolving for one segment at a time. It was previously believed that implementing this strategy on a quantum computer would result in a computational cost that is exponential in the number of time steps. In this study, we present an efficient algorithm for solving linear ODEs using the time-marching strategy. Our algorithm can handle non-smooth coefficient matrices, requires fewer queries to the initial state, and is free of some of the technical constraints present in previous works. One main technical tool we develop is a "compression gadget" that enhances the success probability of a sequence of non-unitary operations, which could have independent interest.

► BibTeX data

► References

[1] A. Ambainis. Variable time amplitude amplification and quantum algorithms for linear algebra problems. In Leibniz Int. Proc. Informatics, LIPIcs, volume 14, pages 636–647, 2012. doi:10.4230/​LIPIcs.STACS.2012.636.

[2] D. An, D. Fang, S. Jordan, J.-P. Liu, G. H. Low, and J. Wang. Efficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation, 2022. URL: http:/​/​arxiv.org/​abs/​2205.01141, arXiv:2205.01141, doi:10.48550/​ARXIV.2205.01141.

[3] D. An, D. Fang, and L. Lin. Time-dependent unbounded Hamiltonian simulation with vector norm scaling. Quantum, 5:1–49, may 2021. URL: https:/​/​doi.org/​10.22331/​q-2021-05-26-459, arXiv:2012.13105, doi:10.22331/​Q-2021-05-26-459.

[4] D. An, D. Fang, and L. Lin. Time-dependent Hamiltonian Simulation of Highly Oscillatory Dynamics and Superconvergence for Schrödinger Equation. Quantum, 6:690, apr 2022. doi:10.22331/​q-2022-04-15-690.

[5] D. An and L. Lin. Quantum Linear System Solver Based on Time-optimal Adiabatic Quantum Computing and Quantum Approximate Optimization Algorithm. ACM Trans. Quantum Comput., 3(2):1–28, 2022. arXiv:1909.05500, doi:10.1145/​3498331.

[6] C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani. Strengths and weaknesses of quantum computing. SIAM journal on Computing, 26(5):1510–1523, 1997. doi:10.1137/​S0097539796300933.

[7] D. Berry, A. M. Childs, Y. Su, X. Wang, and N. Wiebe. Time-dependent Hamiltonian simulation with $L^{1}$-norm scaling. Quantum, 4:254, 2020. doi:10.22331/​q-2020-04-20-254.

[8] D. W. Berry. High-order quantum algorithm for solving linear differential equations. Journal of Physics A: Mathematical and Theoretical, 47(10):105301, feb 2014. doi:10.1088/​1751-8113/​47/​10/​105301.

[9] D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders. Efficient quantum algorithms for simulating sparse hamiltonians. Commun. Math. Phys., 270(2):359–371, 2007. arXiv:0508139, doi:10.1007/​s00220-006-0150-x.

[10] D. W. Berry and A. M. Childs. Black-box hamiltonian simulation and unitary implementation. Quantum Inf. Comput., 12(1-2):29–62, 2012. arXiv:0910.4157, doi:10.26421/​QIC12.1-2.

[11] D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma. Exponential improvement in precision for simulating sparse Hamiltonians. In Proc. Annu. ACM Symp. Theory Comput., pages 283–292, 2014. arXiv:1312.1414, doi:10.1145/​2591796.2591854.

[12] D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma. Simulating hamiltonian dynamics with a truncated taylor series. Phys. Rev. Lett., 114(9):90502, 2015. arXiv:1412.4687, doi:10.1103/​PhysRevLett.114.090502.

[13] D. W. Berry, A. M. Childs, and R. Kothari. Hamiltonian Simulation with Nearly Optimal Dependence on all Parameters. Proc. - Annu. IEEE Symp. Found. Comput. Sci. FOCS, 2015-December:792–809, 2015. arXiv:1501.01715, doi:10.1109/​FOCS.2015.54.

[14] D. W. Berry, A. M. Childs, A. Ostrander, and G. Wang. Quantum algorithm for linear differential equations with exponentially improved dependence on precision. Communications in Mathematical Physics, 356(3):1057–1081, 2017. doi:10.1007/​s00220-017-3002-y.

[15] D. W. Berry, R. Cleve, and S. Gharibian. Gate-efficient discrete simulations of continuous-time quantum query algorithms. Quantum Inf. Comput., 14(1-2):1–30, 2014. doi:10.26421/​qic14.1-2-1.

[16] D. W. Berry and P. C. S. Costa. Quantum algorithm for time-dependent differential equations using dyson series, 2022. URL: https:/​/​arxiv.org/​abs/​2212.03544, doi:10.48550/​ARXIV.2212.03544.

[17] G. Brassard, P. Høyer, M. Mosca, and A. Tapp. Quantum amplitude amplification and estimation. Contemp. Math., 305:53–74, 2002. arXiv:0005055, doi:10.1090/​conm/​305/​05215.

[18] F. Brauer and J. A. Nohel. The Qualitative Theory of Ordinary Differential Equations: An Introduction. Dover Books on Mathematics. Dover Publications, 2012. URL: https:/​/​books.google.com/​books?id=9qPsbRl7hBkC.

[19] R. L. Burden, J. D. Faires, and A. C. Reynolds. Numerical analysis. Brooks Cole, 2000.

[20] E. Campbell. Random Compiler for Fast Hamiltonian Simulation. Phys. Rev. Lett., 123(7):70503, 2019. arXiv:1811.08017, doi:10.1103/​PhysRevLett.123.070503.

[21] S. Chakraborty, A. Gilyén, and S. Jeffery. The power of block-encoded matrix powers: Improved regression techniques via faster Hamiltonian simulation. Leibniz Int. Proc. Informatics, LIPIcs, 132, 2019. arXiv:1804.01973, doi:10.4230/​LIPIcs.ICALP.2019.33.

[22] R. Chao, D. Ding, A. Gilyen, C. Huang, and M. Szegedy. Finding Angles for Quantum Signal Processing with Machine Precision. 2020. URL: http:/​/​arxiv.org/​abs/​2003.02831, arXiv:2003.02831, doi:10.48550/​arXiv.2003.02831.

[23] C.-F. Chen, Hsin-Yuan, Huang, R. Kueng, and J. a. Tropp. Concentration for random product formulas. arXiv:2008.11751, page 25, 2020. URL: http:/​/​arxiv.org/​abs/​2008.11751, arXiv:2008.11751, doi:10.1103/​PRXQuantum.2.040305.

[24] Y. H. Chen, A. Kalev, and I. Hen. Quantum Algorithm for Time-Dependent Hamiltonian Simulation by Permutation Expansion. PRX Quantum, 2(3):30342, sep 2021. URL: https:/​/​doi.org/​10.1103/​PRXQuantum.2.030342, arXiv:2103.15334, doi:10.1103/​PRXQuantum.2.030342.

[25] A. M. Childs, R. Kothari, and R. D. Somma. Quantum algorithm for systems of linear equations with exponentially improved dependence on precision. SIAM J. Comput., 46(6):1920–1950, 2017. arXiv:1511.02306, doi:10.1137/​16M1087072.

[26] A. M. Childs and J. P. Liu. Quantum Spectral Methods for Differential Equations. Commun. Math. Phys., 375(2):1427–1457, 2020. arXiv:1901.00961, doi:10.1007/​s00220-020-03699-z.

[27] A. M. Childs, D. Maslov, Y. Nam, N. J. Ross, and Y. Su. Toward the first quantum simulation with quantum speedup. Proc. Natl. Acad. Sci. U. S. A., 115(38):9456–9461, 2018. arXiv:1711.10980, doi:10.1073/​pnas.1801723115.

[28] A. M. Childs, A. Ostrander, and Y. Su. Faster quantum simulation by randomization. Quantum, 3:182, 2019. arXiv:1805.08385, doi:10.22331/​q-2019-09-02-182.

[29] A. M. Childs and Y. Su. Nearly Optimal Lattice Simulation by Product Formulas. Phys. Rev. Lett., 123(5):50503, 2019. arXiv:1901.00564, doi:10.1103/​PhysRevLett.123.050503.

[30] A. M. Childs, Y. Su, M. C. Tran, N. Wiebe, and S. Zhu. Theory of Trotter Error with Commutator Scaling. Phys. Rev. X, 11(1):11020, 2021. doi:10.1103/​PhysRevX.11.011020.

[31] A. M. Childs and N. Wiebe. Hamiltonian simulation using linear combinations of unitary operations. Quantum Inf. Comput., 12(11-12):901–924, nov 2012. URL: http:/​/​dx.doi.org/​10.26421/​QIC12.11-12, arXiv:1202.5822, doi:10.26421/​qic12.11-12-1.

[32] P. C. Costa, D. An, Y. R. Sanders, Y. Su, R. Babbush, and D. W. Berry. Optimal scaling quantum linear-systems solver via discrete adiabatic theorem. PRX Quantum, 3:040303, Oct 2022. URL: https:/​/​doi.org/​10.1103/​PRXQuantum.3.040303, doi:10.1103/​PRXQuantum.3.040303.

[33] P. C. S. Costa, S. Jordan, and A. Ostrander. Quantum algorithm for simulating the wave equation. Physical Review A, 99(1):012323, 2019. arXiv:1711.05394. doi:10.1103/​PhysRevA.99.012323.

[34] I. Y. Dodin and E. A. Startsev. On applications of quantum computing to plasma simulations. Physics of Plasmas, 28(9):092101, 2021. doi:10.1063/​5.0056974.

[35] Y. Dong, X. Meng, K. B. Whaley, and L. Lin. Efficient phase-factor evaluation in quantum signal processing. Phys. Rev. A, 103(4), 2021. arXiv:2002.11649, doi:10.1103/​PhysRevA.103.042419.

[36] A. Engel, G. Smith, and S. E. Parker. Linear embedding of nonlinear dynamical systems and prospects for efficient quantum algorithms. Physics of Plasmas, 28(6):062305, 2021. arXiv:2012.06681. doi:10.1063/​5.0040313.

[37] A. Gilyén, Y. Su, G. H. Low, and N. Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. arXiv preprint arXiv:1806.01838, 2018. doi:10.48550/​arXiv.1806.01838.

[38] A. Gilyén, Y. Su, G. H. Low, and N. Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proc. 51st Annu. ACM SIGACT Symp. Theory Comput., pages 193–204, 2019. doi:10.1145/​3313276.3316366.

[39] D. Gottlieb and C.-W. Shu. On the Gibbs phenomenon and its resolution. SIAM Rev., 39(4):644–668, 1997. doi:10.1137/​S0036144596301390.

[40] M. Grant and S. Boyd. CVX: Matlab software for disciplined convex programming, version 2.1. http:/​/​cvxr.com/​cvx, Mar. 2014.

[41] J. Haah. Product decomposition of periodic functions in quantum signal processing. Quantum, 3:190, 2019. arXiv:1806.10236, doi:10.22331/​q-2019-10-07-190.

[42] E. Hairer, C. Lubich, and G. Wanner. Geometric Numerical Integration: Structure-Preserving Algorithms for Ordinary Differential Equations (Springer Series in Computational Mathematics), volume 31. Springer, 2006.

[43] E. Hairer, S. P. Nørsett, and G. Wanner. Solving ordinary differential equations I. nonstiff problems, volume 29. Springer, 1987. doi:10.1016/​0378-4754(87)90083-8.

[44] A. W. Harrow, A. Hassidim, and S. Lloyd. Quantum algorithm for linear systems of equations. Phys. Rev. Lett., 103(15):150502, 2009. doi:10.1103/​PhysRevLett.103.150502.

[45] S. Jin and N. Liu. Quantum algorithms for computing observables of nonlinear partial differential equations, 2022. arXiv:2202.07834. doi:10.48550/​arXiv.2202.07834.

[46] I. Joseph. Koopman-von Neumann approach to quantum simulation of nonlinear classical dynamics. Physical Review Research, 2(4):043102, 2020. arXiv:2003.09980. doi:10.1103/​PhysRevResearch.2.043102.

[47] M. Kieferová, A. Scherer, and D. W. Berry. Simulating the dynamics of time-dependent Hamiltonians with a truncated Dyson series. Phys. Rev. A, 99(4), apr 2019. URL: http:/​/​dx.doi.org/​10.1103/​PhysRevA.99.042314, arXiv:1805.00582, doi:10.1103/​PhysRevA.99.042314.

[48] H. Krovi. Improved quantum algorithms for linear and nonlinear differential equations, 2022. URL: http:/​/​arxiv.org/​abs/​2202.01054, arXiv:2202.01054, doi:10.48550/​ARXIV.2202.01054.

[49] L. Lin and Y. Tong. Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems. Quantum, 4:361, 2020. doi:10.22331/​q-2020-11-11-361.

[50] N. Linden, A. Montanaro, and C. Shao. Quantum vs. classical algorithms for solving the heat equation. Comm. Math. Phys., 395(2):601–641, 2022. doi:10.1007/​s00220-022-04442-6.

[51] J.-P. Liu, H. Ø. Kolden, H. K. Krovi, N. F. Loureiro, K. Trivisa, and A. M. Childs. Efficient quantum algorithm for dissipative nonlinear differential equations. Proceedings of the National Academy of Sciences, 118(35), 2021. arXiv:2011.03185. doi:10.1073/​pnas.2026805118.

[52] S. Lloyd, G. De Palma, C. Gokler, B. Kiani, Z.-W. Liu, M. Marvian, F. Tennie, and T. Palmer. Quantum algorithm for nonlinear differential equations, 2020. arXiv:2011.06571. doi:10.48550/​arXiv.2011.06571.

[53] G. H. Low. Hamiltonian simulation with nearly optimal dependence on spectral norm. In Proc. Annu. ACM Symp. Theory Comput., pages 491–502, 2019. arXiv:1807.03967, doi:10.1145/​3313276.3316386.

[54] G. H. Low and I. L. Chuang. Hamiltonian simulation by uniform spectral amplification. arXiv:1707.05391, 2017. doi:10.48550/​arXiv.1707.05391.

[55] G. H. Low and I. L. Chuang. Optimal Hamiltonian Simulation by Quantum Signal Processing. Phys. Rev. Lett., 118(1):10501, 2017. arXiv:1606.02685, doi:10.1103/​PhysRevLett.118.010501.

[56] G. H. Low and I. L. Chuang. Hamiltonian simulation by qubitization. Quantum, 3:163, 2019. arXiv:1610.06546, doi:10.22331/​q-2019-07-12-163.

[57] G. H. Low and N. Wiebe. Hamiltonian Simulation in the Interaction Picture. arXiv:1805.00675, 2018. URL: http:/​/​arxiv.org/​abs/​1805.00675, arXiv:1805.00675, doi:10.48550/​arXiv.1805.00675.

[58] Y. Subaşl, R. D. Somma, and D. Orsucci. Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing. Phys. Rev. Lett., 122(6):60504, 2019. arXiv:1805.10549, doi:10.1103/​PhysRevLett.122.060504.

[59] S. Takahira, A. Ohashi, T. Sogabe, and T. S. Usuda. Quantum algorithm for matrix functions by cauchy's integral formula. Quantum Inf. Comput., 20(1-2):14–36, 2020. arXiv:2106.08075, doi:10.26421/​qic20.1-2-2.

[60] Y. Tong, V. V. Albert, J. R. McClean, J. Preskill, and Y. Su. Provably accurate simulation of gauge theories and bosonic systems, 2021. URL: https:/​/​arxiv.org/​abs/​2110.06942, doi:10.48550/​ARXIV.2110.06942.

[61] Y. Tong, D. An, N. Wiebe, and L. Lin. Fast inversion, preconditioned quantum linear system solvers, fast Green's-function computation, and fast evaluation of matrix functions. Phys. Rev. A, 104(3), 2021. doi:10.1103/​PhysRevA.104.032422.

[62] L. N. Trefethen. Approximation Theory and Approximation Practice, Extended Edition, volume 164. SIAM, 2019. doi:10.1137/​1.9781611975949.

[63] L. N. Trefethen and J. A. Weideman. The exponentially convergent trapezoidal rule. SIAM Rev., 56(3):385–458, 2014. doi:10.1137/​130932132.

[64] C. Tronci and I. Joseph. Koopman wavefunctions and Clebsch variables in Vlasov-Maxwell kinetic theory, 2021. doi:10.1017/​S0022377821000805.

[65] J. Wang, Y. Dong, and L. Lin. On the energy landscape of symmetric quantum signal processing. Quantum, 6:850, Nov. 2022. doi:10.22331/​q-2022-11-03-850.

[66] D. Wecker, M. B. Hastings, N. Wiebe, B. K. Clark, C. Nayak, and M. Troyer. Solving strongly correlated electron models on a quantum computer. Phys. Rev. A - At. Mol. Opt. Phys., 92(6):62318, 2015. arXiv:1506.05135, doi:10.1103/​PhysRevA.92.062318.

[67] N. Wiebe, D. Berry, P. Høyer, and B. C. Sanders. Higher order decompositions of ordered operator exponentials. J. Phys. A Math. Theor., 43(6), 2010. arXiv:0812.0562, doi:10.1088/​1751-8113/​43/​6/​065203.

[68] L. Ying. Stable factorization for phase factors of quantum signal processing. Quantum, 6:842, Oct. 2022. doi:10.22331/​q-2022-10-20-842.

[69] B. Şahinoğlu and R. D. Somma. Hamiltonian simulation in the low-energy subspace. npj Quantum Inf., 7(1), 2021. arXiv:2006.02660, doi:10.1038/​s41534-021-00451-w.

Cited by

[1] Alice V. Hu and Zbigniew J. Kabala, "Predicting and Reconstructing Aerosol–Cloud–Precipitation Interactions with Physics-Informed Neural Networks", Atmosphere 14 12, 1798 (2023).

[2] Koichi Miyamoto, Soichiro Yamazaki, Fumio Uchida, Kotaro Fujisawa, and Naoki Yoshida, "Quantum algorithm for the Vlasov simulation of the large-scale structure formation with massive neutrinos", Physical Review Research 6 1, 013200 (2024).

[3] Osama Muhammad Raisuddin and Suvranu De, "qRLS: quantum relaxation for linear systems in finite element analysis", Engineering with Computers (2024).

[4] Dong An, Jin-Peng Liu, and Lin Lin, "Linear Combination of Hamiltonian Simulation for Nonunitary Dynamics with Optimal State Preparation Cost", Physical Review Letters 131 15, 150603 (2023).

[5] Jin-Peng Liu, Dong An, Di Fang, Jiasu Wang, Guang Hao Low, and Stephen Jordan, "Efficient Quantum Algorithm for Nonlinear Reaction–Diffusion Equations and Energy Estimation", Communications in Mathematical Physics 404 2, 963 (2023).

[6] Yunya Liu, Jiakun Liu, Jordan R. Raney, and Pai Wang, "Quantum computing for solid mechanics and structural engineering – A demonstration with Variational Quantum Eigensolver", Extreme Mechanics Letters 67, 102117 (2024).

[7] Kaoru Mizuta and Keisuke Fujii, "Optimal Hamiltonian simulation for time-periodic systems", Quantum 7, 962 (2023).

[8] Alexander M. Dalzell, Sam McArdle, Mario Berta, Przemyslaw Bienias, Chi-Fang Chen, András Gilyén, Connor T. Hann, Michael J. Kastoryano, Emil T. Khabiboulline, Aleksander Kubica, Grant Salton, Samson Wang, and Fernando G. S. L. Brandão, "Quantum algorithms: A survey of applications and end-to-end complexities", arXiv:2310.03011, (2023).

[9] Shi Jin, Nana Liu, and Yue Yu, "Time complexity analysis of quantum algorithms via linear representations for nonlinear ordinary and partial differential equations", Journal of Computational Physics 487, 112149 (2023).

[10] Ivan Novikau, Ilya Y. Dodin, and Edward A. Startsev, "Encoding of linear kinetic plasma problems in quantum circuits via data compression", arXiv:2403.11989, (2024).

[11] Hari Krovi, "Quantum algorithms to simulate quadratic classical Hamiltonians and optimal control", arXiv:2404.07303, (2024).

[12] Hari Krovi, "Improved quantum algorithms for linear and nonlinear differential equations", Quantum 7, 913 (2023).

[13] Yulong Dong, Lin Lin, Hongkang Ni, and Jiasu Wang, "Infinite quantum signal processing", arXiv:2209.10162, (2022).

[14] Óscar Amaro and Diogo Cruz, "A Living Review of Quantum Computing for Plasma Physics", arXiv:2302.00001, (2023).

[15] Jin-Peng Liu and Lin Lin, "Dense outputs from quantum simulations", arXiv:2307.14441, (2023).

[16] Osama Muhammad Raisuddin and Suvranu De, "Quantum Relaxation for Linear Systems in Finite Element Analysis", arXiv:2308.01377, (2023).

[17] Osama Muhammad Raisuddin and Suvranu De, "Quantum Multigrid Algorithm for Finite Element Problems", arXiv:2404.07466, (2024).

[18] Nam Nguyen and Richard Thompson, "Solving Maxwells Equations using Variational Quantum Imaginary Time Evolution", arXiv:2402.14156, (2024).

The above citations are from Crossref's cited-by service (last updated successfully 2024-05-26 09:58:55) and SAO/NASA ADS (last updated successfully 2024-05-26 09:58:56). The list may be incomplete as not all publishers provide suitable and complete citation data.