Improved quantum algorithms for linear and nonlinear differential equations

Hari Krovi

Riverlane Research, Cambridge, MA

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


We present substantially generalized and improved quantum algorithms over prior work for inhomogeneous linear and nonlinear ordinary differential equations (ODE). Specifically, we show how the norm of the matrix exponential characterizes the run time of quantum algorithms for linear ODEs opening the door to an application to a wider class of linear and nonlinear ODEs. In Berry et al., (2017), a quantum algorithm for a certain class of linear ODEs is given, where the matrix involved needs to be diagonalizable. The quantum algorithm for linear ODEs presented here extends to many classes of non-diagonalizable matrices. The algorithm here is also exponentially faster than the bounds derived in Berry et al., (2017) for certain classes of diagonalizable matrices. Our linear ODE algorithm is then applied to nonlinear differential equations using Carleman linearization (an approach taken recently by us in Liu et al., (2021)). The improvement over that result is two-fold. First, we obtain an exponentially better dependence on error. This kind of logarithmic dependence on error has also been achieved by Xue et al., (2021), but only for homogeneous nonlinear equations. Second, the present algorithm can handle any sparse, invertible matrix (that models dissipation) if it has a negative log-norm (including non-diagonalizable matrices), whereas Liu et al., (2021) and Xue et al., (2021) additionally require normality.

Differential equations are an important part of many physics models from high-energy physics to fluid dynamics and plasma physics. There are several quantum algorithms that solve differential equations by producing a quantum state proportional to the solution. These quantum algorithms, however, are applicable only to certain types of differential equations. Specifically, for linear ODEs, they impose conditions such as normality or diagonalizability on the matrix $A$ encoding the linear ODE. This work develops quantum algorithms that can be applied to a substantially larger class of linear and nonlinear ordinary differential equations. We remove the condition of diagonalizability and replace it with one that has been studied in the theory of stability of differential equations, namely the norm of the exponential of the matrix $A$. This can then be used to give a quantum algorithm that applies to larger class of nonlinear differential equations as well.

► BibTeX data

► References

[1] 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, vol. 356, no. 3, pp. 1057–1081, 2017. https:/​/​​10.1007/​s00220-017-3002-y.

[2] 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, vol. 118, no. 35, 2021. https:/​/​​10.1073/​pnas.2026805118.

[3] C. Xue, Y.-C. Wu, and G.-P. Guo, ``Quantum homotopy perturbation method for nonlinear dissipative ordinary differential equations,'' New Journal of Physics, vol. 23, p. 123035, dec 2021. https:/​/​​10.1088/​1367-2630/​ac3eff.

[4] S. Lloyd, ``Universal quantum simulators,'' Science, vol. 273, no. 5278, pp. 1073–1078, 1996. https:/​/​​10.1126/​science.273.5278.1073.

[5] D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders, ``Efficient quantum algorithms for simulating sparse Hamiltonians,'' Communications in Mathematical Physics, vol. 270, p. 359–371, 2007. https:/​/​​10.1007/​s00220-006-0150-x.

[6] G. H. Low and I. L. Chuang, ``Optimal hamiltonian simulation by quantum signal processing,'' Phys. Rev. Lett., vol. 118, p. 010501, Jan 2017. https:/​/​​10.1103/​PhysRevLett.118.010501.

[7] G. H. Low and I. L. Chuang, ``Hamiltonian Simulation by Qubitization,'' Quantum, vol. 3, p. 163, July 2019. https:/​/​​10.22331/​q-2019-07-12-163.

[8] S. Chakraborty, A. Gilyén, and S. Jeffery, ``The Power of Block-Encoded Matrix Powers: Improved Regression Techniques via Faster Hamiltonian Simulation,'' in 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) (C. Baier, I. Chatzigiannakis, P. Flocchini, and S. Leonardi, eds.), vol. 132 of Leibniz International Proceedings in Informatics (LIPIcs), (Dagstuhl, Germany), pp. 33:1–33:14, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2019. https:/​/​​10.4230/​LIPIcs.ICALP.2019.33.

[9] J. van Apeldoorn, A. Gilyén, S. Gribling, and R. de Wolf, ``Quantum SDP-Solvers: Better upper and lower bounds,'' Quantum, vol. 4, p. 230, Feb. 2020. https:/​/​​10.22331/​q-2020-02-14-230.

[10] A. Gilyén, Y. Su, G. H. Low, and N. Wiebe, ``Quantum singular value transformation and beyond: Exponential improvements for quantum matrix arithmetics,'' in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, (New York, NY, USA), p. 193–204, Association for Computing Machinery, 2019. https:/​/​​10.1145/​3313276.3316366.

[11] A. W. Harrow, A. Hassidim, and S. Lloyd, ``Quantum algorithm for linear systems of equations,'' Physical Review Letters, vol. 103, no. 15, p. 150502, 2009. https:/​/​​10.1103/​PhysRevLett.103.150502.

[12] D. W. Berry, ``High-order quantum algorithm for solving linear differential equations,'' Journal of Physics A: Mathematical and Theoretical, vol. 47, no. 10, p. 105301, 2014. https:/​/​​10.1088/​1751-8113/​47/​10/​105301.

[13] A. M. Childs, J.-P. Liu, and A. Ostrander, ``High-precision quantum algorithms for partial differential equations,'' Quantum, vol. 5, p. 574, Nov. 2021. https:/​/​​10.22331/​q-2021-11-10-574.

[14] A. M. Childs and J.-P. Liu, ``Quantum spectral methods for differential equations,'' Communications in Mathematical Physics, vol. 375, pp. 1427–1457, 2020. https:/​/​​10.1007/​s00220-020-03699-z.

[15] 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. https:/​/​​10.48550/​arXiv.2011.06571.

[16] A. Ambainis, ``Variable time amplitude amplification and quantum algorithms for linear algebra problems,'' in 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) (C. Dürr and T. Wilke, eds.), vol. 14 of Leibniz International Proceedings in Informatics (LIPIcs), (Dagstuhl, Germany), pp. 636–647, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2012. https:/​/​​10.4230/​LIPIcs.STACS.2012.636.

[17] A. M. Childs, R. Kothari, and R. D. Somma, ``Quantum algorithm for systems of linear equations with exponentially improved dependence on precision,'' SIAM Journal on Computing, vol. 46, no. 6, pp. 1920–1950, 2017. https:/​/​​10.1137/​16M1087072.

[18] Y. Subasi, R. D. Somma, and D. Orsucci, ``Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing,'' Phys. Rev. Lett., vol. 122, p. 060504, 2 2019. https:/​/​​10.1103/​PhysRevLett.122.060504.

[19] D. An and L. Lin, ``Quantum linear system solver based on time-optimal adiabatic quantum computing and quantum approximate optimization algorithm,'' ACM Transactions on Quantum Computing, vol. 3, 3 2022. https:/​/​​10.1145/​3498331.

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

[21] 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, vol. 3, p. 040303, Oct 2022. https:/​/​​10.1103/​PRXQuantum.3.040303.

[22] S. K. Leyton and T. J. Osborne, ``A quantum algorithm to solve nonlinear differential equations,'' 2008. https:/​/​​10.48550/​arXiv.0812.4423.

[23] A. Engel, G. Smith, and S. E. Parker, ``Quantum algorithm for the Vlasov equation,'' Physical Review A, vol. 100, no. 6, p. 062315, 2019. https:/​/​​10.1103/​PhysRevA.100.062315.

[24] I. Y. Dodin and E. A. Startsev, ``On applications of quantum computing to plasma simulations,'' Physics of Plasmas, vol. 28, no. 9, p. 092101, 2021. https:/​/​​10.1063/​5.0056974.

[25] A. Engel, G. Smith, and S. E. Parker, ``Linear embedding of nonlinear dynamical systems and prospects for efficient quantum algorithms,'' Physics of Plasmas, vol. 28, no. 6, p. 062305, 2021. https:/​/​​10.1063/​5.0040313.

[26] I. Joseph, ``Koopman–von neumann approach to quantum simulation of nonlinear classical dynamics,'' Phys. Rev. Res., vol. 2, p. 043102, Oct 2020. https:/​/​​10.1103/​PhysRevResearch.2.043102.

[27] I. Novikau, E. A. Startsev, and I. Y. Dodin, ``Quantum signal processing for simulating cold plasma waves,'' Phys. Rev. A, vol. 105, p. 062444, Jun 2022. https:/​/​​10.1103/​PhysRevA.105.062444.

[28] J. Hubisz, B. Sambasivam, and J. Unmuth-Yockey, ``Quantum algorithms for open lattice field theory,'' Physical Review A, vol. 104, 11 2021. https:/​/​​10.1103/​physreva.104.052420.

[29] 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. https:/​/​​10.48550/​arXiv.2205.01141.

[30] D. Fang, L. Lin, and Y. Tong, ``Time-marching based quantum solvers for time-dependent linear differential equations,'' 2022. https:/​/​​10.48550/​arXiv.2208.06941.

[31] D. W. Berry, A. M. Childs, Y. Su, X. Wang, and N. Wiebe, ``Time-dependent Hamiltonian simulation with $L^1$-norm scaling,'' Quantum, vol. 4, p. 254, Apr. 2020. https:/​/​​10.22331/​q-2020-04-20-254.

[32] D. An, J.-P. Liu, D. Wang, and Q. Zhao, ``A theory of quantum differential equation solvers: limitations and fast-forwarding,'' 2022. https:/​/​​10.48550/​ARXIV.2211.05246.

[33] W. Coppel, Stability and Asymptotic Behavior of Differential Equations. Heath mathematical monographs, Heath, 1965.

[34] C. F. Van Loan, ``A study of the matrix exponential,'' tech. rep., University of Manchester, 2006.

[35] G. G. Dahlquist, ``A special stability problem for linear multistep methods,'' BIT Numerical Mathematics, vol. 3, pp. 27–43, Mar 1963. https:/​/​​10.1007/​BF01963532.

[36] L. Trefethen, M. Embree, and M. Embree, Spectra and Pseudospectra: The Behavior of Nonnormal Matrices and Operators. Princeton University Press, 2005. https:/​/​​10.2307/​j.ctvzxx9kj.

[37] R. Bhatia, Matrix Analysis. Graduate Texts in Mathematics, Springer New York, 1996. https:/​/​​10.1007/​978-1-4612-0653-8.

[38] N. F. Loureiro, W. Dorland, L. Fazendeiro, A. Kanekar, A. Mallet, M. S. Vilelas, and A. Zocco, ``Viriato: A Fourier–Hermite spectral code for strongly magnetised fluid-kinetic plasma dynamics,'' Computer Physics Communications, vol. 206, pp. 45–63, 2016. https:/​/​​10.1016/​j.cpc.2016.05.004.

[39] R. A. Bertlmann, W. Grimus, and B. C. Hiesmayr, ``Open-quantum-system formulation of particle decay,'' Phys. Rev. A, vol. 73, p. 054101, May 2006. https:/​/​​10.1103/​PhysRevA.73.054101.

[40] B. Kågström, ``Bounds and perturbation bounds for the matrix exponential,'' BIT Numerical Mathematics, vol. 17, pp. 39–57, Mar 1977. https:/​/​​10.1007/​BF01932398.

[41] L. Elsner and M. Paardekooper, ``On measures of nonnormality of matrices,'' Linear Algebra and its Applications, vol. 92, pp. 107–123, 1987. https:/​/​​10.1016/​0024-3795(87)90253-9.

[42] N. Higham, Functions of Matrices: Theory and Computation. Other Titles in Applied Mathematics, Society for Industrial and Applied Mathematics (SIAM, 3600 Market Street, Floor 6, Philadelphia, PA 19104), 2008. https:/​/​​10.1137/​1.9780898717778.

[43] E. Hairer, S. Nørsett, and G. Wanner, Solving Ordinary Differential Equations I: Nonstiff Problems. Springer Series in Computational Mathematics, Springer Berlin Heidelberg, 2008. https:/​/​​10.1007/​978-3-540-78862-1.

[44] M. M. Gilles Brassard, Peter Høyer and A. Tapp, ``Quantum amplitude amplification and estimation,'' in Quantum Computation and Information (J. Samuel J. Lomonaco and H. E. Brandt, eds.), vol. 305, pp. 53–74, Contemporary Mathematics, 2002. https:/​/​​10.1090/​conm/​305/​05215.

Cited by

[1] Abtin Ameri, Erika Ye, Paola Cappellaro, Hari Krovi, and Nuno F. Loureiro, "Quantum algorithm for the linear Vlasov equation with collisions", Physical Review A 107 6, 062412 (2023).

[2] I. Joseph, Y. Shi, M. D. Porter, A. R. Castelli, V. I. Geyko, F. R. Graziani, S. B. Libby, and J. L. DuBois, "Quantum computing for fusion energy science applications", Physics of Plasmas 30 1, 010501 (2023).

[3] 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).

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

[5] David Jennings, Matteo Lostaglio, Sam Pallister, Andrew T Sornborger, and Yiğit Subaşı, "Efficient quantum linear solver algorithm with detailed running costs", arXiv:2305.11352, (2023).

[6] Dong An, Di Fang, Stephen Jordan, Jin-Peng Liu, Guang Hao Low, and Jiasu Wang, "Efficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation", arXiv:2205.01141, (2022).

[7] Amit Surana, Abeynaya Gnanasekaran, and Tuhin Sahai, "An efficient quantum algorithm for simulating polynomial differential equations", arXiv:2212.10775, (2022).

[8] Cheng Xue, Xiao-Fan Xu, Yu-Chun Wu, and Guo-Ping Guo, "Quantum algorithm for solving a quadratic nonlinear system of equations", Physical Review A 106 3, 032427 (2022).

[9] Shi Jin, Nana Liu, Xiantao Li, and Yue Yu, "Quantum Simulation for Quantum Dynamics with Artificial Boundary Conditions", arXiv:2304.00667, (2023).

[10] Di Fang, Lin Lin, and Yu Tong, "Time-marching based quantum solvers for time-dependent linear differential equations", Quantum 7, 955 (2023).

[11] Koichi Miyamoto and Hiroshi Ueda, "Extracting a function encoded in amplitudes of a quantum state by tensor network and orthogonal function expansion", Quantum Information Processing 22 6, 239 (2023).

[12] Dominic W. Berry and Pedro C. S. Costa, "Quantum algorithm for time-dependent differential equations using Dyson series", arXiv:2212.03544, (2022).

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

The above citations are from Crossref's cited-by service (last updated successfully 2023-09-28 03:19:17) and SAO/NASA ADS (last updated successfully 2023-09-28 03:19:18). The list may be incomplete as not all publishers provide suitable and complete citation data.