1Technical University of Munich, Department of Informatics, Boltzmannstraße 3, 85748 Garching, Germany
2TUM Institute for Advanced Study, Lichtenbergstraße 2a, 85748 Garching, Germany
3Leibniz Supercomputing Centre, Boltzmannstraße 1, 85748 Garching, Germany
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
► 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] Martin Knudsen and Christian B. Mendl, “Solving Differential Equations via Continuous-Variable Quantum Computers”, arXiv:2012.12220.
The above citations are from SAO/NASA ADS (last updated successfully 2021-07-13 16:15:49). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch Crossref cited-by data during last attempt 2021-07-13 16:15:47: Could not fetch cited-by data for 10.22331/q-2021-07-13-502 from Crossref. This is normal if the DOI was registered recently.
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.
PlatoAi. Web3 Reimagined. Data Intelligence Amplified.
Click here to access.
Source: https://quantum-journal.org/papers/q-2021-07-13-502/
