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.

Abstract

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 [1], 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 including singular matrices. The algorithm here is also exponentially faster than the bounds derived in [1] 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 [2]). 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 [3], but only for homogeneous nonlinear equations. Second, the present algorithm can handle any sparse matrix (that models dissipation) if it has a negative log-norm (including non-diagonalizable matrices), whereas [2] and [3] 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:/​/​doi.org/​10.1007/​s00220-017-3002-y.
https:/​/​doi.org/​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:/​/​doi.org/​10.1073/​pnas.2026805118.
https:/​/​doi.org/​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:/​/​doi.org/​10.1088/​1367-2630/​ac3eff.
https:/​/​doi.org/​10.1088/​1367-2630/​ac3eff

[4] S. Lloyd, ``Universal quantum simulators,'' Science, vol. 273, no. 5278, pp. 1073–1078, 1996. https:/​/​doi.org/​10.1126/​science.273.5278.1073.
https:/​/​doi.org/​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:/​/​doi.org/​10.1007/​s00220-006-0150-x.
https:/​/​doi.org/​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:/​/​doi.org/​10.1103/​PhysRevLett.118.010501.
https:/​/​doi.org/​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:/​/​doi.org/​10.22331/​q-2019-07-12-163.
https:/​/​doi.org/​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:/​/​doi.org/​10.4230/​LIPIcs.ICALP.2019.33.
https:/​/​doi.org/​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:/​/​doi.org/​10.22331/​q-2020-02-14-230.
https:/​/​doi.org/​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:/​/​doi.org/​10.1145/​3313276.3316366.
https:/​/​doi.org/​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:/​/​doi.org/​10.1103/​PhysRevLett.103.150502.
https:/​/​doi.org/​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:/​/​doi.org/​10.1088/​1751-8113/​47/​10/​105301.
https:/​/​doi.org/​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:/​/​doi.org/​10.22331/​q-2021-11-10-574.
https:/​/​doi.org/​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:/​/​doi.org/​10.1007/​s00220-020-03699-z.
https:/​/​doi.org/​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:/​/​doi.org/​10.48550/​arXiv.2011.06571.
https:/​/​doi.org/​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:/​/​doi.org/​10.4230/​LIPIcs.STACS.2012.636.
https:/​/​doi.org/​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:/​/​doi.org/​10.1137/​16M1087072.
https:/​/​doi.org/​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:/​/​doi.org/​10.1103/​PhysRevLett.122.060504.
https:/​/​doi.org/​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:/​/​doi.org/​10.1145/​3498331.
https:/​/​doi.org/​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:/​/​doi.org/​10.22331/​q-2020-11-11-361.
https:/​/​doi.org/​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:/​/​doi.org/​10.1103/​PRXQuantum.3.040303.
https:/​/​doi.org/​10.1103/​PRXQuantum.3.040303

[22] S. K. Leyton and T. J. Osborne, ``A quantum algorithm to solve nonlinear differential equations,'' 2008. https:/​/​doi.org/​10.48550/​arXiv.0812.4423.
https:/​/​doi.org/​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:/​/​doi.org/​10.1103/​PhysRevA.100.062315.
https:/​/​doi.org/​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:/​/​doi.org/​10.1063/​5.0056974.
https:/​/​doi.org/​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:/​/​doi.org/​10.1063/​5.0040313.
https:/​/​doi.org/​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:/​/​doi.org/​10.1103/​PhysRevResearch.2.043102.
https:/​/​doi.org/​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:/​/​doi.org/​10.1103/​PhysRevA.105.062444.
https:/​/​doi.org/​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:/​/​doi.org/​10.1103/​physreva.104.052420.
https:/​/​doi.org/​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:/​/​doi.org/​10.48550/​arXiv.2205.01141.
https:/​/​doi.org/​10.48550/​arXiv.2205.01141

[30] P. C. S. Costa, P. Schleich, M. E. S. Morales, and D. W. Berry, ``Further improving quantum algorithms for nonlinear differential equations via higher-order methods and rescaling,'' 2023. https:/​/​doi.org/​10.48550/​arXiv.2312.09518.
https:/​/​doi.org/​10.48550/​arXiv.2312.09518

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

[32] D. W. Berry and P. C. S. Costa, ``Quantum algorithm for time-dependent differential equations using dyson series,'' 2022. https:/​/​doi.org/​10.48550/​arXiv.2212.03544.
https:/​/​doi.org/​10.48550/​arXiv.2212.03544

[33] D. Jennings, M. Lostaglio, R. B. Lowrie, S. Pallister, and A. T. Sornborger, ``The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts,'' 2023. https:/​/​doi.org/​10.48550/​arXiv.2309.07881.
https:/​/​doi.org/​10.48550/​arXiv.2309.07881

[34] D. Jennings, M. Lostaglio, S. Pallister, A. T. Sornborger, and Y. Subaşı, ``Efficient quantum linear solver algorithm with detailed running costs,'' 2023. https:/​/​doi.org/​10.48550/​arXiv.2305.11352.
https:/​/​doi.org/​10.48550/​arXiv.2305.11352

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

[36] S. Jin, N. Liu, and Y. Yu, ``Quantum simulation of partial differential equations via schrodingerisation,'' 2022. https:/​/​doi.org/​10.48550/​arXiv.2212.13969.
https:/​/​doi.org/​10.48550/​arXiv.2212.13969

[37] D. An, J.-P. Liu, and L. Lin, ``Linear combination of hamiltonian simulation for nonunitary dynamics with optimal state preparation cost,'' Phys. Rev. Lett., vol. 131, p. 150603, Oct 2023. https:/​/​link.aps.org/​doi/​10.1103/​PhysRevLett.131.150603.
https:/​/​doi.org/​10.1103/​PhysRevLett.131.150603

[38] D. An, A. M. Childs, and L. Lin, ``Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters,'' 2023. https:/​/​doi.org/​10.48550/​arXiv.2312.03916.
https:/​/​doi.org/​10.48550/​arXiv.2312.03916

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

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

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

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

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

[44] 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:/​/​doi.org/​10.1016/​j.cpc.2016.05.004.
https:/​/​doi.org/​10.1016/​j.cpc.2016.05.004

[45] 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:/​/​doi.org/​10.1103/​PhysRevA.73.054101.
https:/​/​doi.org/​10.1103/​PhysRevA.73.054101

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

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

[48] 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:/​/​doi.org/​10.1137/​1.9780898717778.
https:/​/​doi.org/​10.1137/​1.9780898717778

[49] 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:/​/​doi.org/​10.1007/​978-3-540-78862-1.
https:/​/​doi.org/​10.1007/​978-3-540-78862-1

[50] 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:/​/​doi.org/​10.1090/​conm/​305/​05215.
https:/​/​doi.org/​10.1090/​conm/​305/​05215

Cited by

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

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

[3] Abtin Ameri, Erika Ye, Paola Cappellaro, Hari Krovi, and Nuno F. Loureiro, 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) 56 (2023) ISBN:979-8-3503-4323-6.

[4] Ryan Babbush, Dominic W. Berry, Robin Kothari, Rolando D. Somma, and Nathan Wiebe, "Exponential Quantum Speedup in Simulating Coupled Classical Oscillators", Physical Review X 13 4, 041041 (2023).

[5] Wael Itani, Katepalli R. Sreenivasan, and Sauro Succi, "Quantum algorithm for lattice Boltzmann (QALB) simulation of incompressible fluids with a nonlinear collision term", Physics of Fluids 36 1, 017112 (2024).

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

[7] Javier Gonzalez-Conde, Ángel Rodríguez-Rozas, Enrique Solano, and Mikel Sanz, "Efficient Hamiltonian simulation for solving option price dynamics", Physical Review Research 5 4, 043220 (2023).

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

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

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

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

[12] Dong An, Andrew M. Childs, and Lin Lin, "Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters", arXiv:2312.03916, (2023).

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

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

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

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

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

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

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

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

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

[22] Yue Wang and Qi Zhao, "Faster Quantum Algorithms with "Fractional''-Truncated Series", arXiv:2402.05595, (2024).

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