{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,20]],"date-time":"2025-08-20T12:49:04Z","timestamp":1755694144684,"version":"3.40.5"},"reference-count":31,"publisher":"Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften","license":[{"start":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T00:00:00Z","timestamp":1747094400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["quantum-journal.org"],"crossmark-restriction":false},"short-container-title":["Quantum"],"abstract":"<jats:p>Quantum algorithms for Hamiltonian simulation and linear differential equations more generally have provided promising exponential speed-ups over classical computers on a set of problems with high real-world interest. However, extending this to a nonlinear problem has proven challenging, with exponential lower bounds having been demonstrated for the time scaling. We provide a quantum algorithm matching these bounds. Specifically, we find that for a non-linear differential equation of the form <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mfrac><mml:mrow><mml:mi>d<\/mml:mi><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo stretchy=\"false\">|<\/mml:mo><\/mml:mrow><mml:mi>u<\/mml:mi><mml:mo fence=\"false\" stretchy=\"false\">&amp;#x27E9;<\/mml:mo><\/mml:mrow><mml:mrow><mml:mi>d<\/mml:mi><mml:mi>t<\/mml:mi><\/mml:mrow><\/mml:mfrac><mml:mo>=<\/mml:mo><mml:mi>A<\/mml:mi><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo stretchy=\"false\">|<\/mml:mo><\/mml:mrow><mml:mi>u<\/mml:mi><mml:mo fence=\"false\" stretchy=\"false\">&amp;#x27E9;<\/mml:mo><mml:mo>+<\/mml:mo><mml:mi>B<\/mml:mi><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo stretchy=\"false\">|<\/mml:mo><\/mml:mrow><mml:mi>u<\/mml:mi><mml:msup><mml:mo fence=\"false\" stretchy=\"false\">&amp;#x27E9;<\/mml:mo><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mo>&amp;#x2297;<\/mml:mo><mml:mn>2<\/mml:mn><\/mml:mrow><\/mml:msup><\/mml:math> for evolution of time <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>T<\/mml:mi><\/mml:math>, error tolerance <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>&amp;#x03F5;<\/mml:mi><\/mml:math> and <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mi>c<\/mml:mi><\/mml:math> dependent on the strength of the nonlinearity, the number of queries to the differential operators that approaches the scaling of the quantum lower bound of <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msup><mml:mi>e<\/mml:mi><mml:mrow class=\"MJX-TeXAtom-ORD\"><mml:mi>o<\/mml:mi><mml:mo stretchy=\"false\">(<\/mml:mo><mml:mi>T<\/mml:mi><mml:mo fence=\"false\" stretchy=\"false\">&amp;#x2016;<\/mml:mo><mml:mi>B<\/mml:mi><mml:mo fence=\"false\" stretchy=\"false\">&amp;#x2016;<\/mml:mo><mml:mo stretchy=\"false\">)<\/mml:mo><\/mml:mrow><\/mml:msup><\/mml:math> queries in the limit of strong non-linearity. Finally, we introduce a classical algorithm based on the Euler method allowing comparably scaling to the quantum algorithm in a restricted case, as well as a randomized classical algorithm based on path integration that acts as a true analogue to the quantum algorithm in that it scales comparably to the quantum algorithm in cases where sign problems are absent.<\/jats:p>","DOI":"10.22331\/q-2025-05-13-1741","type":"journal-article","created":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T07:21:15Z","timestamp":1747120875000},"page":"1741","update-policy":"https:\/\/doi.org\/10.22331\/q-crossmark-policy-page","source":"Crossref","is-referenced-by-count":1,"title":["Quantum and classical algorithms for nonlinear unitary dynamics"],"prefix":"10.22331","volume":"9","author":[{"given":"Noah","family":"Brustle","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Toronto, Toronto, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nathan","family":"Wiebe","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Toronto, Toronto, Canada"},{"name":"Pacific Northwest National Laboratory, Richland, USA"},{"name":"Canadian Institute for Advanced Research, Toronto, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"9598","published-online":{"date-parts":[[2025,5,13]]},"reference":[{"key":"0","doi-asserted-by":"publisher","unstructured":"Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 333\u2013342, 2011. 10.1145\/1993636.19936.","DOI":"10.1145\/1993636.19936"},{"key":"1","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. URL https:\/\/doi.org\/10.1088.","DOI":"10.1088\/1751-8113\/47\/10\/105301"},{"key":"2","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 http:\/\/dx.doi.org\/10.22331\/q-2024-06-13-1369.","DOI":"10.22331\/q-2024-06-13-1369"},{"key":"3","doi-asserted-by":"publisher","unstructured":"Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders. Efficient quantum algorithms for simulating sparse hamiltonians. Communications in Mathematical Physics, 270 (2): 359\u2013371, 2006. ISSN 1432-0916. 10.1007\/s00220-006-0150-x. URL http:\/\/dx.doi.org\/10.1007\/s00220-006-0150-x.","DOI":"10.1007\/s00220-006-0150-x"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 792\u2013809, 2015a. 10.1109\/FOCS.2015.54.","DOI":"10.1109\/FOCS.2015.54"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Dominic W. Berry, Andrew M. Childs, and Robin Kothari. Hamiltonian simulation with nearly optimal dependence on all parameters. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science. IEEE, oct 2015b. 10.1109\/focs.2015.54. URL https:\/\/doi.org\/10.1109.","DOI":"10.1109\/focs.2015.54"},{"key":"6","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. URL https:\/\/doi.org\/10.1007.","DOI":"10.1007\/s00220-017-3002-y"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Gilles Brassard, Peter H\u00f8yer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305: 53\u201374, 2002. 10.48550\/arXiv.quant-ph\/0005055.","DOI":"10.48550\/arXiv.quant-ph\/0005055"},{"key":"8","doi-asserted-by":"publisher","unstructured":"Andrew M. Childs and Joshua Young. Optimal state discrimination and unstructured search in nonlinear quantum mechanics. Phys. Rev. A, 93: 022314, 2016. 10.1103\/PhysRevA.93.022314. URL https:\/\/doi.org\/10.1103\/PhysRevA.93.022314.","DOI":"10.1103\/PhysRevA.93.022314"},{"key":"9","doi-asserted-by":"publisher","unstructured":"I. Y. Dodin and E. A. Startsev. On applications of quantum computing to plasma simulations. arXiv:2005.14369, 2021. 10.48550\/arXiv.2005.14369.","DOI":"10.48550\/arXiv.2005.14369"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Richard P. Feynman. Simulating Physics with Computers. International Journal of Theoretical Physics, 21 (6-7): 467\u2013488, 1982. 10.1007\/BF02650179.","DOI":"10.1007\/BF02650179"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Marcelo Forets and Amaury Pouly. Explicit error bounds for Carleman linearization. arXiv preprint arXiv:1711.02552, 2017. 10.48550\/arXiv.1711.02552.","DOI":"10.48550\/arXiv.1711.02552"},{"key":"12","doi-asserted-by":"publisher","unstructured":"Eugene P Gross. Structure of a quantized vortex in boson systems. Il Nuovo Cimento (1955-1965), 20 (3): 454\u2013477, 1961. 10.1007\/BF02731494.","DOI":"10.1007\/BF02731494"},{"key":"13","doi-asserted-by":"publisher","unstructured":"B L Hammond, W A Lester, and P J Reynolds. Monte Carlo Methods in Ab Initio Quantum Chemistry. World Scientific, 1994. 10.1142\/1170. URL https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/1170.","DOI":"10.1142\/1170"},{"key":"14","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), 2009. 10.1103\/physrevlett.103.150502. URL https:\/\/doi.org\/10.1103.","DOI":"10.1103\/physrevlett.103.150502"},{"key":"15","unstructured":"Francis Begnaud Hildebrand. Introduction to numerical analysis. Courier Corporation, 1987."},{"key":"16","doi-asserted-by":"publisher","unstructured":"Ilon Joseph. Koopman\u2013von neumann approach to quantum simulation of nonlinear classical dynamics. Physical Review Research, 2 (4), 2020. 10.1103\/physrevresearch.2.043102. URL https:\/\/doi.org\/10.1103.","DOI":"10.1103\/physrevresearch.2.043102"},{"key":"17","unstructured":"M G Krein Ju L Daleckii. Stability of solutions of differential equations in Banach space. American Mathematical Society, 1974."},{"key":"18","doi-asserted-by":"publisher","unstructured":"Hari Krovi. Improved quantum algorithms for linear and nonlinear differential equations. Quantum, 7: 913, February 2023a. ISSN 2521-327X. 10.22331\/q-2023-02-02-913. URL http:\/\/dx.doi.org\/10.22331\/q-2023-02-02-913.","DOI":"10.22331\/q-2023-02-02-913"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Hari Krovi. Improved quantum algorithms for linear and nonlinear differential equations. Quantum, 7: 913, 2023b. 10.48550\/arxiv.2202.01054.","DOI":"10.48550\/arxiv.2202.01054"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Sarah K Leyton and Tobias J Osborne. A quantum algorithm to solve nonlinear differential equations. arXiv preprint arXiv:0812.4423, 2008. 10.48550\/arXiv.0812.4423.","DOI":"10.48550\/arXiv.0812.4423"},{"key":"21","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":"22","doi-asserted-by":"publisher","unstructured":"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, November 2020. 10.48550\/arXiv.2011.06571.","DOI":"10.48550\/arXiv.2011.06571"},{"key":"23","doi-asserted-by":"publisher","unstructured":"Guang Hao Low and Isaac L. Chuang. Optimal hamiltonian simulation by quantum signal processing. Phys. Rev. Lett., 118: 010501, 2017. 10.1103\/PhysRevLett.118.010501. URL https:\/\/doi.org\/10.1103\/PhysRevLett.118.010501.","DOI":"10.1103\/PhysRevLett.118.010501"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Guang Hao Low and Isaac L. Chuang. Hamiltonian Simulation by Qubitization. Quantum, 3: 163, 2019. ISSN 2521-327X. 10.22331\/q-2019-07-12-163. URL https:\/\/doi.org\/10.22331\/q-2019-07-12-163.","DOI":"10.22331\/q-2019-07-12-163"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Dorota Mozyrska and Zbigniew Bartosiewicz. On carleman linearization of linearly observable polynomial systems. Mathematical Control Theory and Finance, 01 2008. 10.1007\/978-3-540-69532-5_17.","DOI":"10.1007\/978-3-540-69532-5_17"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information, volume 2. Cambridge university press Cambridge, 2001. 10.1017\/CBO9780511976667.","DOI":"10.1017\/CBO9780511976667"},{"key":"27","unstructured":"Yu Tanaka and Keisuke Fujii. A polynomial time quantum algorithm for exponentially large scale nonlinear differential equations via hamiltonian simulation, 2025. URL https:\/\/arxiv.org\/abs\/2305.00653."},{"key":"28","doi-asserted-by":"publisher","unstructured":"Hsuan-Cheng Wu, Jingyao Wang, and Xiantao Li. Quantum algorithms for nonlinear dynamics: Revisiting carleman linearization with no dissipative conditions. arXiv preprint arXiv:2405.12714, 2024. 10.48550\/arXiv.2405.12714.","DOI":"10.48550\/arXiv.2405.12714"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Tao Xin, Shijie Wei, Jianlian Cui, Junxiang Xiao, I\u00f1igo 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, Mar 2020. 10.1103\/PhysRevA.101.032307. URL https:\/\/doi.org\/10.1103\/PhysRevA.101.032307.","DOI":"10.1103\/PhysRevA.101.032307"},{"key":"30","doi-asserted-by":"publisher","unstructured":"O.V. Zhdaneev, G.N. Serezhnikov, and A.Y. et al Trifonov. Semiclassical trajectory-coherent states of the nonlinear schr\u00f6dinger equation with unitary nonlinearity. Russ Phys J, page 598\u2013606, 1999. 10.1007\/BF02513223.","DOI":"10.1007\/BF02513223"}],"container-title":["Quantum"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-05-13-1741\/pdf\/","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2025,5,13]],"date-time":"2025-05-13T07:21:21Z","timestamp":1747120881000},"score":1,"resource":{"primary":{"URL":"https:\/\/quantum-journal.org\/papers\/q-2025-05-13-1741\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,13]]},"references-count":31,"URL":"https:\/\/doi.org\/10.22331\/q-2025-05-13-1741","archive":["CLOCKSS"],"relation":{},"ISSN":["2521-327X"],"issn-type":[{"value":"2521-327X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,5,13]]},"article-number":"1741"}}