{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,5]],"date-time":"2026-03-05T00:37:10Z","timestamp":1772671030871,"version":"3.50.1"},"reference-count":49,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T00:00:00Z","timestamp":1733788800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000015","name":"U.S. Department of Energy","doi-asserted-by":"crossref","award":["ASC Beyond Moore\u2019s Law"],"award-info":[{"award-number":["ASC Beyond Moore\u2019s Law"]}],"id":[{"id":"10.13039\/100000015","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>How well can quantum computers simulate classical dynamical systems? There is increasing effort in developing quantum algorithms to efficiently simulate dynamics beyond Hamiltonian simulation, but so far exact resource estimates are not known. In this work, we provide two significant contributions. First, we give the first non-asymptotic computation of the cost of encoding the solution to general linear ordinary differential equations into quantum states \u2013 either the solution at a final time, or an encoding of the whole history within a time interval. Second, we show that the stability properties of a large class of classical dynamics allow their fast-forwarding, making their quantum simulation much more time-efficient. From this point of view, quantum Hamiltonian dynamics is a boundary case that does not allow this form of stability-induced fast-forwarding. In particular, we find that the history state can always be output with complexity <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>O<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:msup><mml:mi>T<\/mml:mi><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mn>1<\/mml:mn><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>\/<\/mml:mo><\/mml:mrow><mml:mn>2<\/mml:mn><\/mml:mrow><\/mml:msup><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:math> for any stable linear system. We present a range of asymptotic improvements over state-of-the-art in various regimes. We illustrate our results with a family of dynamics including linearized collisional plasma problems, coupled, damped, forced harmonic oscillators and dissipative nonlinear problems. In this case the scaling is quadratically improved, and leads to significant reductions in the query counts after inclusion of all relevant constant prefactors.<\/jats:p>","DOI":"10.22331\/q-2024-12-10-1553","type":"journal-article","created":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T12:43:38Z","timestamp":1733834618000},"page":"1553","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":5,"title":["The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts"],"prefix":"10.22331","volume":"8","author":[{"given":"David","family":"Jennings","sequence":"first","affiliation":[{"name":"PsiQuantum, 700 Hansen Way, Palo Alto, CA 94304, USA"}]},{"given":"Matteo","family":"Lostaglio","sequence":"additional","affiliation":[{"name":"PsiQuantum, 700 Hansen Way, Palo Alto, CA 94304, USA"}]},{"given":"Robert B.","family":"Lowrie","sequence":"additional","affiliation":[{"name":"Computational Physics and Methods Group (CCS-2), Computer, Computational and Statistical Sciences Division, Los Alamos National Laboratory, Los Alamos, NM 87545, USA"}]},{"given":"Sam","family":"Pallister","sequence":"additional","affiliation":[{"name":"PsiQuantum, 700 Hansen Way, Palo Alto, CA 94304, USA"}]},{"given":"Andrew T.","family":"Sornborger","sequence":"additional","affiliation":[{"name":"Information Sciences (CCS-3), Los Alamos National Laboratory, Los Alamos, New Mexico 87545, USA"}]}],"member":"9598","published-online":{"date-parts":[[2024,12,10]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Pedro C.S. Costa, Dong An, Yuval R. Sanders, Yuan Su, Ryan Babbush, and Dominic W. Berry. Optimal scaling quantum linear-systems solver via discrete adiabatic theorem. PRX Quantum, 3: 040303, Oct 2022. 10.1103\/PRXQuantum.3.040303. URL https:\/\/link.aps.org\/doi\/10.1103\/PRXQuantum.3.040303.","DOI":"10.1103\/PRXQuantum.3.040303"},{"key":"1","doi-asserted-by":"publisher","unstructured":"David Jennings, Matteo Lostaglio, Sam Pallister, Andrew T Sornborger, and Yi\u011fit Suba\u015f\u0131. Efficient quantum linear solver algorithm with detailed running costs. arXiv preprint arXiv:2305.11352, 2023. https:\/\/doi.org\/10.48550\/arXiv.2305.11352.","DOI":"10.48550\/arXiv.2305.11352"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Dominic W Berry, Andrew M Childs, Aaron Ostrander, and Guoming Wang. Quantum algorithm for linear differential equations with exponentially improved dependence on precision. Communications in Mathematical Physics, 356 (3): 1057\u20131081, 2017. 10.1007\/s00220-017-3002-y.","DOI":"10.1007\/s00220-017-3002-y"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Hari Krovi. Improved quantum algorithms for linear and nonlinear differential equations. Quantum, 7: 913, February 2023. ISSN 2521-327X. 10.22331\/q-2023-02-02-913. URL https:\/\/doi.org\/10.22331\/q-2023-02-02-913.","DOI":"10.22331\/q-2023-02-02-913"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Pedro Costa, Dong An, Ryan Babbush, and Dominic Berry. The discrete adiabatic quantum linear system solver has lower constant factors than the randomized adiabatic solver. arXiv preprint arXiv:2312.07690, 2023. 10.48550\/arXiv.2312.07690.","DOI":"10.48550\/arXiv.2312.07690"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Jin-Peng Liu, Herman \u00d8ie Kolden, Hari K Krovi, Nuno F Loureiro, Konstantina Trivisa, and Andrew M Childs. Efficient quantum algorithm for dissipative nonlinear differential equations. Proceedings of the National Academy of Sciences, 118 (35): e2026805118, 2021. 10.1073\/pnas.2026805118.","DOI":"10.1073\/pnas.2026805118"},{"key":"6","doi-asserted-by":"publisher","unstructured":"Shi Jin and Nana Liu. Quantum algorithms for computing observables of nonlinear partial differential equations. arXiv preprint arXiv:2202.07834, 2022. 10.48550\/arXiv.2202.07834.","DOI":"10.48550\/arXiv.2202.07834"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Bernard O Koopman. Hamiltonian systems and transformation in hilbert space. Proceedings of the National Academy of Sciences, 17 (5): 315\u2013318, 1931. 10.1073\/pnas.17.5.315.","DOI":"10.1073\/pnas.17.5.315"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Krzysztof Kowalski. Nonlinear dynamical systems and classical orthogonal polynomials. Journal of Mathematical Physics, 38 (5): 2483\u20132505, 1997. 10.1063\/1.531990.","DOI":"10.1063\/1.531990"},{"key":"9","doi-asserted-by":"publisher","unstructured":"Ilon Joseph. Koopman\u2013von neumann approach to quantum simulation of nonlinear classical dynamics. Physical Review Research, 2 (4): 043102, 2020. 10.1103\/PhysRevResearch.2.043102.","DOI":"10.1103\/PhysRevResearch.2.043102"},{"key":"10","doi-asserted-by":"publisher","unstructured":"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.1016\/j.jcp.2023.112149.","DOI":"10.1016\/j.jcp.2023.112149"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Yen Ting Lin, Robert B Lowrie, Denis Aslangil, Yi\u011fit Suba\u015f\u0131, and Andrew T Sornborger. Challenges for quantum computation of nonlinear dynamical systems using linear representations. arXiv preprint arXiv:2202.02188, 2022. 10.48550\/arXiv.2202.02188.","DOI":"10.48550\/arXiv.2202.02188"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Javier Gonzalez-Conde and Andrew T Sornborger. Mixed quantum-semiclassical simulation. arXiv preprint arXiv:2308.16147, 2023. 10.48550\/arXiv.2308.16147.","DOI":"10.48550\/arXiv.2308.16147"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Cheng Xue, Yu-Chun Wu, and Guo-Ping Guo. Quantum homotopy perturbation method for nonlinear dissipative ordinary differential equations. New Journal of Physics, 23 (12): 123035, 2021. 10.1088\/1367-2630\/ac3eff.","DOI":"10.1088\/1367-2630\/ac3eff"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Pedro CS Costa, Stephen Jordan, and Aaron Ostrander. Quantum algorithm for simulating the wave equation. Physical Review A, 99 (1): 012323, 2019. 10.1103\/PhysRevA.99.012323.","DOI":"10.1103\/PhysRevA.99.012323"},{"key":"15","doi-asserted-by":"publisher","unstructured":"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. 10.1103\/PhysRevX.13.041041.","DOI":"10.1103\/PhysRevX.13.041041"},{"key":"16","doi-asserted-by":"publisher","unstructured":"Shi Jin, Nana Liu, and Yue Yu. Quantum simulation of partial differential equations via Schrodingerisation: technical details. arXiv preprint arXiv:2212.14703, 2022. 10.48550\/arXiv.2212.14703.","DOI":"10.48550\/arXiv.2212.14703"},{"key":"17","doi-asserted-by":"publisher","unstructured":"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, 2023a. 10.1103\/PhysRevLett.131.150603.","DOI":"10.1103\/PhysRevLett.131.150603"},{"key":"18","doi-asserted-by":"publisher","unstructured":"Simon Apers, Shantanav Chakraborty, Leonardo Novo, and J\u00e9r\u00e9mie Roland. Quadratic speedup for spatial search by continuous-time quantum walk. Physical Review Letters, 129 (16): 160502, 2022. 10.1103\/PhysRevLett.129.160502.","DOI":"10.1103\/PhysRevLett.129.160502"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Dong An and Konstantina Trivisa. Quantum algorithms for linear and non-linear fractional reaction-diffusion equations. arXiv preprint arXiv:2310.18900, 2023. 10.48550\/arXiv.2310.18900.","DOI":"10.48550\/arXiv.2310.18900"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Dong An, Andrew M Childs, and Lin Lin. Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters. arXiv preprint arXiv:2312.03916, 2023b. 10.48550\/arXiv.2312.03916.","DOI":"10.48550\/arXiv.2312.03916"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Aram W Harrow, Avinatan Hassidim, and Seth Lloyd. Quantum algorithm for linear systems of equations. Physical Review Letters, 103 (15): 150502, 2009. 10.1103\/PhysRevLett.103.150502.","DOI":"10.1103\/PhysRevLett.103.150502"},{"key":"22","doi-asserted-by":"publisher","unstructured":"Dominic W Berry. High-order quantum algorithm for solving linear differential equations. Journal of Physics A: Mathematical and Theoretical, 47 (10): 105301, 2014. 10.1088\/1751-8113\/47\/10\/105301.","DOI":"10.1088\/1751-8113\/47\/10\/105301"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Andrew M Childs and Jin-Peng Liu. Quantum spectral methods for differential equations. Communications in Mathematical Physics, 375 (2): 1427\u20131457, 2020. 10.1007\/s00220-020-03699-z.","DOI":"10.1007\/s00220-020-03699-z"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Noah Linden, Ashley Montanaro, and Changpeng Shao. Quantum vs. classical algorithms for solving the heat equation. Communications in Mathematical Physics, 395 (2): 601\u2013641, 2022. 10.1007\/s00220-022-04442-6.","DOI":"10.1007\/s00220-022-04442-6"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Dominic W. Berry and Pedro C. S. Costa. Quantum algorithm for time-dependent differential equations using Dyson series. Quantum, 8: 1369, June 2024. ISSN 2521-327X. 10.22331\/q-2024-06-13-1369. URL https:\/\/doi.org\/10.22331\/q-2024-06-13-1369.","DOI":"10.22331\/q-2024-06-13-1369"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Mohsen Bagherimehrab, Kouhei Nakaji, Nathan Wiebe, and Al\u00e1n Aspuru-Guzik. Fast quantum algorithm for differential equations. arXiv preprint arXiv:2306.11802, 2023. 10.48550\/arXiv.2306.11802.","DOI":"10.48550\/arXiv.2306.11802"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Di Fang, Lin Lin, and Yu Tong. Time-marching based quantum solvers for time-dependent linear differential equations. Quantum, 7: 955, March 2023. ISSN 2521-327X. 10.22331\/q-2023-03-20-955. URL https:\/\/doi.org\/10.22331\/q-2023-03-20-955.","DOI":"10.22331\/q-2023-03-20-955"},{"key":"28","doi-asserted-by":"publisher","unstructured":"Abtin Ameri, Erika Ye, Paola Cappellaro, Hari Krovi, and Nuno F. Loureiro. Quantum algorithm for the linear vlasov equation with collisions. Phys. Rev. A, 107: 062412, Jun 2023. 10.1103\/PhysRevA.107.062412.","DOI":"10.1103\/PhysRevA.107.062412"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Jin-Peng Liu, Dong An, Di Fang, Jiasu Wang, Guang Hao Low, and Stephen Jordan. Efficient quantum algorithm for nonlinear reaction\u2013diffusion equations and energy estimation. Communications in Mathematical Physics, 404 (2): 963\u20131020, 2023. 10.1007\/s00220-023-04857-9.","DOI":"10.1007\/s00220-023-04857-9"},{"key":"30","doi-asserted-by":"publisher","unstructured":"Xiangyu Li, Xiaolong Yin, Nathan Wiebe, Jaehun Chun, Gregory K Schenter, Margaret S Cheung, and Johannes M\u00fclmenst\u00e4dt. Potential quantum advantage for simulation of fluid dynamics. arXiv preprint arXiv:2303.16550, 2023a. 10.48550\/arXiv.2303.16550.","DOI":"10.48550\/arXiv.2303.16550"},{"key":"31","doi-asserted-by":"publisher","unstructured":"Adrien Suau, Gabriel Staffelbach, and Henri Calandra. Practical quantum computing: Solving the wave equation using a quantum approach. ACM Transactions on Quantum Computing, 2 (1): 1\u201335, 2021. 10.1145\/3430030.","DOI":"10.1145\/3430030"},{"key":"32","doi-asserted-by":"publisher","unstructured":"Lin Lin. Lecture notes on quantum algorithms for scientific computation. arXiv preprint arXiv:2201.08309, 2022. 10.48550\/arXiv.2201.08309.","DOI":"10.48550\/arXiv.2201.08309"},{"key":"33","doi-asserted-by":"publisher","unstructured":"Daan Camps, Lin Lin, Roel Van Beeumen, and Chao Yang. Explicit quantum circuits for block encodings of certain sparse matrices. SIAM Journal on Matrix Analysis and Applications, 45 (1): 801\u2013827, 2024. 10.1137\/22M1484298.","DOI":"10.1137\/22M1484298"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Christoph S\u00fcnderhauf, Earl Campbell, and Joan Camps. Block-encoding structured matrices for data input in quantum computing. Quantum, 8: 1226, January 2024. ISSN 2521-327X. 10.22331\/q-2024-01-11-1226. URL https:\/\/doi.org\/10.22331\/q-2024-01-11-1226.","DOI":"10.22331\/q-2024-01-11-1226"},{"key":"35","doi-asserted-by":"publisher","unstructured":"Quynh T. Nguyen, Bobak T. Kiani, and Seth Lloyd. Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra. Quantum, 6: 876, December 2022. ISSN 2521-327X. 10.22331\/q-2022-12-13-876. URL https:\/\/doi.org\/10.22331\/q-2022-12-13-876.","DOI":"10.22331\/q-2022-12-13-876"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Haoya Li, Hongkang Ni, and Lexing Ying. On efficient quantum block encoding of pseudo-differential operators. Quantum, 7: 1031, June 2023b. ISSN 2521-327X. 10.22331\/q-2023-06-02-1031. URL https:\/\/doi.org\/10.22331\/q-2023-06-02-1031.","DOI":"10.22331\/q-2023-06-02-1031"},{"key":"37","unstructured":"Elmar Plischke. Transient effects of linear dynamical systems. PhD thesis, Universit\u00e4t Bremen, 2005. URL http:\/\/nbn-resolving.de\/urn:nbn:de:gbv:46-diss000102119."},{"key":"38","doi-asserted-by":"publisher","unstructured":"Gustaf S\u00f6derlind. The logarithmic norm. History and modern theory. BIT Numerical Mathematics, 46: 631\u2013652, 2006. 10.1007\/s10543-006-0069-9.","DOI":"10.1007\/s10543-006-0069-9"},{"key":"39","doi-asserted-by":"publisher","unstructured":"Dong An, Jin-Peng Liu, Daochen Wang, and Qi Zhao. A theory of quantum differential equation solvers: limitations and fast-forwarding. arXiv preprint arXiv:2211.05246, 2022. 10.48550\/arXiv.2211.05246.","DOI":"10.48550\/arXiv.2211.05246"},{"key":"40","unstructured":"Dong An. Private communication. private communication."},{"key":"41","doi-asserted-by":"publisher","unstructured":"Abhinav Gupta and Mrinal K Bose. Significance of non-classical damping in seismic qualification of equipment and piping. Nuclear Engineering and Design, 317: 90\u201399, 2017. 10.1016\/j.nucengdes.2017.03.020.","DOI":"10.1016\/j.nucengdes.2017.03.020"},{"key":"42","doi-asserted-by":"publisher","unstructured":"D McFarland and Lawrence Bergman. Sources and effects of nonclassical damping in discrete-distributed dynamical systems. In Dynamics Specialists Conference, page 1215, 1990. 10.2514\/6.1990-1215.","DOI":"10.2514\/6.1990-1215"},{"key":"43","unstructured":"Jens Roehner and Fritz-Otto Henkel. The influence of non-classical daming on subsystem response. 20th International Conference on Structural Mechanics in Reactor Technology (SMiRT 20), 2009. URL https:\/\/repository.lib.ncsu.edu\/server\/api\/core\/bitstreams\/156c2e33-d5ab-45de-929c-a9c66c286469\/content."},{"key":"44","doi-asserted-by":"publisher","unstructured":"Theodore J Yoder, Guang Hao Low, and Isaac L Chuang. Fixed-point quantum search with an optimal number of queries. Physical Review Letters, 113 (21): 210501, 2014. 10.1103\/PhysRevLett.113.210501.","DOI":"10.1103\/PhysRevLett.113.210501"},{"key":"45","doi-asserted-by":"publisher","unstructured":"Charles F Van Loan. A study of the matrix exponential. Numerical Analysis Report No. 10, University of Manchester, 2006. 10.1137\/S0036144595286488.","DOI":"10.1137\/S0036144595286488"},{"key":"46","unstructured":"Abdolhossein Hoorfar and Mehdi Hassani. Inequalities on the Lambert W function and hyperpower function. J. Inequal. Pure and Appl. Math, 9 (2): 5\u20139, 2008. URL http:\/\/eudml.org\/doc\/130024."},{"key":"47","doi-asserted-by":"publisher","unstructured":"Joonho Lee, Dominic W Berry, Craig Gidney, William J Huggins, Jarrod R McClean, Nathan Wiebe, and Ryan Babbush. Even more efficient quantum computations of chemistry through tensor hypercontraction. PRX Quantum, 2 (3): 030305, 2021. 10.1103\/PRXQuantum.2.030305.","DOI":"10.1103\/PRXQuantum.2.030305"},{"key":"48","doi-asserted-by":"publisher","unstructured":"Shouzhen Gu, Rolando D. Somma, and Burak \u015eahino\u011flu. Fast-forwarding quantum evolution. Quantum, 5: 577, November 2021. ISSN 2521-327X. 10.22331\/q-2021-11-15-577. URL https:\/\/doi.org\/10.22331\/q-2021-11-15-577.","DOI":"10.22331\/q-2021-11-15-577"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-12-10-1553\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T12:44:02Z","timestamp":1733834642000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2024-12-10-1553\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,10]]},"references-count":49,"URL":"https:\/\/doi.org\/10.22331\/q-2024-12-10-1553","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,10]]},"article-number":"1553"}}