Quantum Algorithms for Solving Ordinary Differential Equations via Classical Integration Methods

Benjamin Zanger; Christian B. Mendl; Martin Schulz; Martin Schreiber

doi:10.22331/q-2021-07-13-502

Quantum Algorithms for Solving Ordinary Differential Equations via Classical Integration Methods

Benjamin Zanger¹, Christian B. Mendl^1,2, Martin Schulz^1,3, and Martin Schreiber¹

¹Technical University of Munich, Department of Informatics, Boltzmannstraße 3, 85748 Garching, Germany
²TUM Institute for Advanced Study, Lichtenbergstraße 2a, 85748 Garching, Germany
³Leibniz Supercomputing Centre, Boltzmannstraße 1, 85748 Garching, Germany

Published:	2021-07-13, volume 5, page 502
Eprint:	arXiv:2012.09469v2
Doi:	https://doi.org/10.22331/q-2021-07-13-502
Citation:	Quantum 5, 502 (2021).

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

Abstract

Identifying computational tasks suitable for (future) quantum computers is an active field of research. Here we explore utilizing quantum computers for the purpose of solving differential equations. We consider two approaches: (i) basis encoding and fixed-point arithmetic on a digital quantum computer, and (ii) representing and solving high-order Runge-Kutta methods as optimization problems on quantum annealers. As realizations applied to two-dimensional linear ordinary differential equations, we devise and simulate corresponding digital quantum circuits, and implement and run a 6$^{\mathrm{th}}$ order Gauss-Legendre collocation method on a D-Wave 2000Q system, showing good agreement with the reference solution. We find that the quantum annealing approach exhibits the largest potential for high-order implicit integration methods. As promising future scenario, the digital arithmetic method could be employed as an "oracle" within quantum search algorithms for inverse problems.

Featured image: Explicit Euler circuit for a 2D ODE.

► BibTeX data

@article{Zanger2021quantumalgorithms,
  doi = {10.22331/q-2021-07-13-502},
  url = {https://doi.org/10.22331/q-2021-07-13-502},
  title = {Quantum {A}lgorithms for {S}olving {O}rdinary {D}ifferential {E}quations via {C}lassical {I}ntegration {M}ethods},
  author = {Zanger, Benjamin and Mendl, Christian B. and Schulz, Martin and Schreiber, Martin},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {5},
  pages = {502},
  month = jul,
  year = {2021}
}

► References

[1] Héctor Abraham, AduOffei, Rochisha Agarwal, Ismail Yunus Akhalwaya, Gadi Aleksandrowicz, et al. Qiskit: An open-source framework for quantum computing. 2019. 10.5281/zenodo.2562110.
https://doi.org/10.5281/zenodo.2562110

[2] Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin, Rami Barends, et al. Quantum supremacy using a programmable superconducting processor. Nature, 574: 505–510, 2019. 10.1038/s41586-019-1666-5.
https://doi.org/10.1038/s41586-019-1666-5

[3] Samuel L. Braunstein and Peter van Loock. Quantum information with continuous variables. Rev. Mod. Phys., 77: 513–577, 2005. 10.1103/RevModPhys.77.513.
https://doi.org/10.1103/RevModPhys.77.513

[4] John C Butcher. Coefficients for the study of Runge-Kutta integration processes. J. Austral. Math. Soc., 3 (2): 185–201, 1963. 10.1017/S1446788700027932.
https://doi.org/10.1017/S1446788700027932

[5] Jun Cai, William G. Macready, and Aidan Roy. A practical heuristic for finding graph minors. arXiv:1406.2741, 2014. URL https://arxiv.org/abs/1406.2741.
arXiv:1406.2741

[6] Chia Cheng Chang, Arjun Gambhir, Travis S. Humble, and Shigetoshi Sota. Quantum annealing for systems of polynomial equations. Scientific Reports, 9 (1): 10258, Jul 2019. ISSN 2045-2322. 10.1038/s41598-019-46729-0.
https://doi.org/10.1038/s41598-019-46729-0

[7] P. C. S. Costa, S. Jordan, and A. Ostrander. Quantum algorithm for simulating the wave equation. Phys. Rev. A, 99: 012323, 2019. 10.1103/PhysRevA.99.012323.
https://doi.org/10.1103/PhysRevA.99.012323

[8] Thomas G Draper. Addition on a quantum computer. arXiv:quant-ph/0008033, 2000. URL https://arxiv.org/abs/quant-ph/0008033.
arXiv:quant-ph/0008033

[9] Dale R. Durran. Numerical Methods for Fluid Dynamics, volume 32. Springer New York, 2010. ISBN 978-1-4419-6411-3. 10.1007/978-1-4419-6412-0.
https://doi.org/10.1007/978-1-4419-6412-0

[10] Alok Dutt, Leslie Greengard, and Vladimir Rokhlin. Spectral deferred correction methods for ordinary differential equations. BIT Numerical Mathematics, 40: 241–266, 1998. 10.1023/A:1022338906936.
https://doi.org/10.1023/A:1022338906936

[11] Matthew Emmett and Michael Minion. Toward an efficient parallel in time method for partial differential equations. Comm. App. Math. Comp. Sci., 7: 105–132, 2012. 10.2140/camcos.2012.7.105.
https://doi.org/10.2140/camcos.2012.7.105

[12] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Quantum computation by adiabatic evolution. arXiv e-prints, art. quant-ph/0001106, January 2000. URL https://arxiv.org/abs/quant-ph/0001106.
arXiv:quant-ph/0001106

[13] Martin J. Gander. 50 years of time parallel time integration. In Multiple Shooting and Time Domain Decomposition. Springer, 2015. 10.1007/978-3-319-23321-5_3.
https://doi.org/10.1007/978-3-319-23321-5_3

[14] Fred Glover, Gary Kochenberger, and Yu Du. Quantum bridge analytics i: a tutorial on formulating and using QUBO models. 4OR, 17 (4): 335–371, nov 2019. 10.1007/s10288-019-00424-y.
https://doi.org/10.1007/s10288-019-00424-y

[15] Lov K. Grover. Quantum computers can search arbitrarily large databases by a single query. Phys. Rev. Lett., 79: 4709–4712, 1997. 10.1103/PhysRevLett.79.4709.
https://doi.org/10.1103/PhysRevLett.79.4709

[16] Ernst Hairer and Gerhard Wanner. Solving ordinary differential equations II: Stiff and differential-algebraic problems, volume 14. Springer, Berlin, Heidelberg, 1996. 10.1007/978-3-642-05221-7.
https://doi.org/10.1007/978-3-642-05221-7

[17] Ernst Hairer, Syvert P. Nørsett, and Gerhard Wanner. Solving ordinary differential equations I: Nonstiff problems. Springer, Berlin, Heidelberg, 1993. 10.1007/978-3-540-78862-1.
https://doi.org/10.1007/978-3-540-78862-1

[18] A. W. Harrow, A. Hassidim, and S. Lloyd. Quantum algorithm for linear systems of equations. Phys. Rev. Lett., 103: 150502, 2009. 10.1103/PhysRevLett.103.150502.
https://doi.org/10.1103/PhysRevLett.103.150502

[19] Ilon Joseph. Koopman–von neumann approach to quantum simulation of nonlinear classical dynamics. Phys. Rev. Research, 2: 043102, Oct 2020. 10.1103/PhysRevResearch.2.043102.
https://doi.org/10.1103/PhysRevResearch.2.043102

[20] Tadashi Kadowaki and Hidetoshi Nishimori. Quantum annealing in the transverse Ising model. Phys. Rev. E, 58 (5): 5355, 1998. 10.1103/PhysRevE.58.5355.
https://doi.org/10.1103/PhysRevE.58.5355

[21] Wolfgang Lechner, Philipp Hauke, and Peter Zoller. A quantum annealing architecture with all-to-all connectivity from local interactions. Sci. Adv., 1: e1500838, 2015. 10.1126/sciadv.1500838.
https://doi.org/10.1126/sciadv.1500838

[22] Jin-Peng Liu, Herman Øie Kolden, Hari K. Krovi, Nuno F. Loureiro, Konstantina Trivisa, and Andrew M. Childs. Efficient quantum algorithm for dissipative nonlinear differential equations. arXiv e-prints, art. arXiv:2011.03185, Nov 2020. URL https://arxiv.org/abs/2011.03185.
arXiv:2011.03185

[23] Seth Lloyd and Samuel L Braunstein. Quantum computation over continuous variables. In Quantum Information with Continuous Variables, pages 9–17. Springer, 1999a. 10.1007/978-94-015-1258-9_2.
https://doi.org/10.1007/978-94-015-1258-9_2

[24] Seth Lloyd and Samuel L. Braunstein. Quantum computation over continuous variables. Phys. Rev. Lett., 82: 1784–1787, 1999b. 10.1103/PhysRevLett.82.1784.
https://doi.org/10.1103/PhysRevLett.82.1784

[25] Seth Lloyd, Giacomo De Palma, Can Gokler, Bobak Kiani, Zi-Wen Liu, Milad Marvian, Felix Tennie, and Tim Palmer. Quantum algorithm for nonlinear differential equations. arXiv e-prints, art. arXiv:2011.06571, Nov 2020. URL https://arxiv.org/abs/2011.06571.
arXiv:2011.06571

[26] Michael Lubasch, Jaewoo Joo, Pierre Moinier, Martin Kiffner, and Dieter Jaksch. Variational quantum algorithms for nonlinear problems. Phys. Rev. A, 101: 010301, Jan 2020. 10.1103/PhysRevA.101.010301.
https://doi.org/10.1103/PhysRevA.101.010301

[27] Jarrod R. McClean, Jonathan Romero, Ryan Babbush, and Alan Aspuru-Guzik. The theory of variational hybrid quantum-classical algorithms. New J. Phys., 18: 023023, 2016. 10.1088/1367-2630/18/2/023023.
https://doi.org/10.1088/1367-2630/18/2/023023

[28] Michael L. Minion. A hybrid parareal spectral deferred corrections method. Comm. App. Math. Comp. Sci., 5: 265–301, 2010. 10.2140/camcos.2010.5.265.
https://doi.org/10.2140/camcos.2010.5.265

[29] D. O'Malley and V. V. Vesselinov. Toq.jl: A high-level programming language for d-wave machines based on julia. In 2016 IEEE High Performance Extreme Computing Conference (HPEC), pages 1–7, 2016. 10.1109/HPEC.2016.7761616.
https://doi.org/10.1109/HPEC.2016.7761616

[30] Ivo G Rosenberg. Reduction of bivalent maximization to the quadratic case. Cahiers du Centre d'études de Recherche Operationnelle, 1975.

[31] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM J. Comput., 26: 1484–1509, 1997. 10.1137/S0097539795293172.
https://doi.org/10.1137/S0097539795293172

[32] Chi-Wang Shu and Stanley Osher. Efficient implementation of essentially non-oscillatory shock capturing schemes. J. Comput. Phys., 77: 439–471, 1988. 10.1016/0021-9991(88)90177-5.
https://doi.org/10.1016/0021-9991(88)90177-5

[33] Daniel R. Simon. On the power of quantum computation. SIAM J. Comput., 26 (5): 1474–1483, 1997. 10.1137/S0097539796298637.
https://doi.org/10.1137/S0097539796298637

[34] Andrew Staniforth and John Thuburn. Horizontal grids for global weather and climate prediction models: A review. Q. J. R. Meteorol. Soc., 138 (662): 1–26, 2012. 10.1002/qj.958.
https://doi.org/10.1002/qj.958

[35] Kotaro Tanahashi, Shinichi Takayanagi, Tomomitsu Motohashi, and Shu Tanaka. Application of ising machines and a software development for ising machines. Journal of the Physical Society of Japan, 88 (6): 061010, 2019. 10.7566/JPSJ.88.061010.
https://doi.org/10.7566/JPSJ.88.061010

[36] Vlatko Vedral, Adriano Barenco, and Artur Ekert. Quantum networks for elementary arithmetic operations. Phys. Rev. A, 54: 147–153, 1996. 10.1103/PhysRevA.54.147.
https://doi.org/10.1103/PhysRevA.54.147

[37] Guillaume Verdon, Jason Pye, and Michael Broughton. A universal training algorithm for quantum deep learning. arXiv:1806.09729, 2018. URL https://arxiv.org/abs/1806.09729.
arXiv:1806.09729

[38] Christian Weedbrook, Stefano Pirandola, Raúl García-Patrón, Nicolas J. Cerf, Timothy C. Ralph, Jeffrey H. Shapiro, and Seth Lloyd. Gaussian quantum information. Rev. Mod. Phys., 84: 621–669, 2012. 10.1103/RevModPhys.84.621.
https://doi.org/10.1103/RevModPhys.84.621

[39] Tao Xin, Shijie Wei, Jianlian Cui, Junxiang Xiao, Iñigo Arrazola, Lucas Lamata, Xiangyu Kong, Dawei Lu, Enrique Solano, and Guilu Long. Quantum algorithm for solving linear differential equations: Theory and experiment. Phys. Rev. A, 101: 032307, 2020. 10.1103/PhysRevA.101.032307.
https://doi.org/10.1103/PhysRevA.101.032307

Cited by

[1] Akihiro Haga, "Quantum annealing-based computed tomography using variational approach for a real-number image reconstruction", Physics in Medicine & Biology 69 4, 04NT02 (2024).

[2] Julien Zylberman and Fabrice Debbasch, "Efficient quantum state preparation with Walsh series", Physical Review A 109 4, 042401 (2024).

[3] Zhao-Yun Chen, Cheng Xue, Si-Ming Chen, Bing-Han Lu, Yu-Chun Wu, Ju-Chun Ding, Sheng-Hong Huang, and Guo-Ping Guo, "Quantum Approach to Accelerate Finite Volume Method on Steady Computational Fluid Dynamics Problems", Quantum Information Processing 21 4, 137 (2022).

[4] Juan Carlos Criado and Michael Spannowsky, "Qade: solving differential equations on quantum annealers", Quantum Science and Technology 8 1, 015021 (2023).

[5] Jakub Buczkowski, Tomasz Koźmiński, Filip Szczepański, Michał Wiliński, and Tomasz P. Stefański, "Global Roots and Poles Finding Algorithm on Quantum Computer", IEEE Access 12, 181041 (2024).

[6] Andrea Carbone, Federico De Grossi, and Dario Spiller, "Cutting-Edge Trajectory Optimization through Quantum Annealing", Applied Sciences 13 23, 12853 (2023).

[7] Kip Nieman, Helen Durand, Saahil Patel, Daniel Koch, and Paul M. Alsing, "Parallelizing process model integration for model predictive control through oracle design and analysis for a Grover’s algorithm-inspired optimization strategy", Digital Chemical Engineering 13, 100179 (2024).

[8] Vinod P. Gehlot, Mark J. Balas, Marco B. Quadrelli, Saptarshi Bandyopadhyay, David S. Bayard, and Amir Rahmani, "A Path to Solving Robotic Differential Equations Using Quantum Computing", Journal of Autonomous Vehicles and Systems 2 3, 031004 (2022).

[9] Suman Debnath, Phani R V Marthi, Jongchan Choi, and Ryan Bennink, 2023 IEEE Energy Conversion Congress and Exposition (ECCE) 704 (2023) ISBN:979-8-3503-1644-5.

[10] Marian Stengl, Patrick Gelß, Stefan Klus, and Sebastian Pokutta, "Existence and uniqueness of solutions of the Koopman–von Neumann equation on bounded domains", Journal of Physics A: Mathematical and Theoretical 57 39, 395302 (2024).

[11] Giorgio Tosti Balducci, Boyang Chen, Matthias Möller, Marc Gerritsma, and Roeland De Breuker, "Review and perspectives in quantum computing for partial differential equations in structural mechanics", Frontiers in Mechanical Engineering 8, 914241 (2022).

[12] Alexandre C. Ricardo, Gabriel P. L. M. Fernandes, Eduardo I. Duzzioni, Vivaldo L. Campo, and Celso J. Villas-Boas, "Alternatives to a nonhomogeneous partial differential equation quantum algorithm", Physical Review A 106 5, 052431 (2022).

[13] Gabriel Marin-Sanchez, Javier Gonzalez-Conde, and Mikel Sanz, "Quantum algorithms for approximate function loading", Physical Review Research 5 3, 033114 (2023).

[14] Salvatore Certo, Andrew Vlasic, and Daniel Beaulieu, "$$\alpha $$QBoost: an iteratively weighted adiabatic trained classifier", Quantum Information Processing 22 12, 433 (2023).

[15] Igor Gaidai, Dmitri Babikov, Alexander Teplukhin, Brian K. Kendrick, Susan M. Mniszewski, Yu Zhang, Sergei Tretiak, and Pavel A. Dub, "Molecular dynamics on quantum annealers", Scientific Reports 12 1, 16824 (2022).

[16] Javier Gonzalez-Conde, Thomas W. Watts, Pablo Rodriguez-Grasa, and Mikel Sanz, "Efficient quantum amplitude encoding of polynomial functions", Quantum 8, 1297 (2024).

[17] Katherine Asztalos, René Steijl, and Romit Maulik, "Reduced-order modeling on a near-term quantum computer", Journal of Computational Physics 510, 113070 (2024).

[18] Matthias Möller, Computational Methods in Applied Sciences 58, 357 (2023) ISBN:978-3-031-29081-7.

[19] José E. Cruz Serrallés, Oluwadara Ogunkoya, Dog̃a Murat Kürkçüog̃lu, Nicholas Bornman, Norm M. Tubman, Silvia Zorzetti, and Riccardo Lattanzi, 2024 IEEE International Conference on Quantum Computing and Engineering (QCE) 50 (2024) ISBN:979-8-3315-4137-8.

[20] Martin Knudsen and Christian B. Mendl, "Solving Differential Equations via Continuous-Variable Quantum Computers", arXiv:2012.12220, (2020).

[21] Ahmed Hamid Elias, Igor Klebanov, and Salah A. Albermany, "A survey on some methods which used to solve equations: Case study the differential equations", American Institute of Physics Conference Series 3092 1, 120001 (2024).

[22] Hamza Jaffali, Jonas Bastos de Araujo, Nadia Milazzo, Marta Reina, Henri de Boutray, Karla Baumann, and Frédéric Holweck, "H-DES: a Quantum-Classical Hybrid Differential Equation Solver", arXiv:2410.01130, (2024).

The above citations are from Crossref's cited-by service (last updated successfully 2025-01-20 21:09:28) and SAO/NASA ADS (last updated successfully 2025-01-20 21:09:31). The list may be incomplete as not all publishers provide suitable and complete citation data.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.