Quantum and classical algorithms for nonlinear unitary dynamics

Noah Brustle; Nathan Wiebe

doi:10.22331/q-2025-05-13-1741

Quantum and classical algorithms for nonlinear unitary dynamics

Noah Brustle¹ and Nathan Wiebe^1,2,3

¹Department of Computer Science, University of Toronto, Toronto, Canada
²Pacific Northwest National Laboratory, Richland, USA
³Canadian Institute for Advanced Research, Toronto, Canada

Published:	2025-05-13, volume 9, page 1741
Editor:	Álvaro Alhambra
Eprint:	arXiv:2407.07685v2
Doi:	https://doi.org/10.22331/q-2025-05-13-1741
Citation:	Quantum 9, 1741 (2025).

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

Abstract

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 $\frac{d|u\rangle}{dt} = A|u\rangle + B|u\rangle^{\otimes2}$ for evolution of time $T$, error tolerance $\epsilon$ and $c$ 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 $e^{o(T\|B\|)}$ 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.

► BibTeX data

@article{Brustle2025quantumclassical,
  doi = {10.22331/q-2025-05-13-1741},
  url = {https://doi.org/10.22331/q-2025-05-13-1741},
  title = {Quantum and classical algorithms for nonlinear unitary dynamics},
  author = {Brustle, Noah and Wiebe, Nathan},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1741},
  month = may,
  year = {2025}
}

► References

[1] 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–342, 2011. 10.1145/1993636.19936.
https://doi.org/10.1145/1993636.19936

[2] 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.
https://doi.org/10.1088/1751-8113/47/10/105301

[3] 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.
https://doi.org/10.22331/q-2024-06-13-1369

[4] 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–371, 2006. ISSN 1432-0916. 10.1007/s00220-006-0150-x. URL http://dx.doi.org/10.1007/s00220-006-0150-x.
https://doi.org/10.1007/s00220-006-0150-x

[5] 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–809, 2015a. 10.1109/FOCS.2015.54.
https://doi.org/10.1109/FOCS.2015.54

[6] 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.
https://doi.org/10.1109/focs.2015.54

[7] 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–1081, 2017. 10.1007/s00220-017-3002-y. URL https://doi.org/10.1007.
https://doi.org/10.1007/s00220-017-3002-y

[8] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305: 53–74, 2002. 10.48550/arXiv.quant-ph/0005055.
https://doi.org/10.48550/arXiv.quant-ph/0005055
arXiv:quant-ph/0005055

[9] 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.
https://doi.org/10.1103/PhysRevA.93.022314

[10] I. Y. Dodin and E. A. Startsev. On applications of quantum computing to plasma simulations. arXiv:2005.14369, 2021. 10.48550/arXiv.2005.14369.
https://doi.org/10.48550/arXiv.2005.14369
arXiv:2005.14369

[11] Richard P. Feynman. Simulating Physics with Computers. International Journal of Theoretical Physics, 21 (6-7): 467–488, 1982. 10.1007/BF02650179.
https://doi.org/10.1007/BF02650179

[12] Marcelo Forets and Amaury Pouly. Explicit error bounds for Carleman linearization. arXiv preprint arXiv:1711.02552, 2017. 10.48550/arXiv.1711.02552.
https://doi.org/10.48550/arXiv.1711.02552
arXiv:1711.02552

[13] Eugene P Gross. Structure of a quantized vortex in boson systems. Il Nuovo Cimento (1955-1965), 20 (3): 454–477, 1961. 10.1007/BF02731494.
https://doi.org/10.1007/BF02731494

[14] 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.
https://doi.org/10.1142/1170

[15] 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.
https://doi.org/10.1103/physrevlett.103.150502

[16] Francis Begnaud Hildebrand. Introduction to numerical analysis. Courier Corporation, 1987.

[17] Ilon Joseph. Koopman–von 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.
https://doi.org/10.1103/physrevresearch.2.043102

[18] M G Krein Ju L Daleckii. Stability of solutions of differential equations in Banach space. American Mathematical Society, 1974.

[19] 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.
https://doi.org/10.22331/q-2023-02-02-913

[20] Hari Krovi. Improved quantum algorithms for linear and nonlinear differential equations. Quantum, 7: 913, 2023b. 10.48550/arxiv.2202.01054.
https://doi.org/10.48550/arxiv.2202.01054

[21] 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.
https://doi.org/10.48550/arXiv.0812.4423
arXiv:0812.4423

[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. Proceedings of the National Academy of Sciences, 118 (35): e2026805118, 2021. 10.1073/pnas.2026805118.
https://doi.org/10.1073/pnas.2026805118

[23] 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.
https://doi.org/10.48550/arXiv.2011.06571
arXiv:2011.06571

[24] 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.
https://doi.org/10.1103/PhysRevLett.118.010501

[25] 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.
https://doi.org/10.22331/q-2019-07-12-163

[26] 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.
https://doi.org/10.1007/978-3-540-69532-5_17

[27] Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum information, volume 2. Cambridge university press Cambridge, 2001. 10.1017/CBO9780511976667.
https://doi.org/10.1017/CBO9780511976667

[28] 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.
arXiv:2305.00653

[29] 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.
https://doi.org/10.48550/arXiv.2405.12714
arXiv:2405.12714

[30] 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, Mar 2020. 10.1103/PhysRevA.101.032307. URL https://doi.org/10.1103/PhysRevA.101.032307.
https://doi.org/10.1103/PhysRevA.101.032307

[31] O.V. Zhdaneev, G.N. Serezhnikov, and A.Y. et al Trifonov. Semiclassical trajectory-coherent states of the nonlinear schrödinger equation with unitary nonlinearity. Russ Phys J, page 598–606, 1999. 10.1007/BF02513223.
https://doi.org/10.1007/BF02513223

Cited by

[1] Efstratios Koukoutsis, George Vahala, Min Soe, Kyriakos Hizanidis, Linda Vahala, and Abhay K. Ram, "Time-Marching Quantum Algorithm for Simulation of Nonlinear Lorenz Dynamics", Entropy 27 8, 871 (2025).

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

[3] Xiantao Li, "From Linear Differential Equations to Unitaries: A Moment-Matching Dilation Framework with Near-Optimal Quantum Algorithms", PRX Quantum 7 2, 020350 (2026).

[4] Zhaoyuan Meng and Yue Yang, "Quantum spin representation for the Navier-Stokes equation", Physical Review Research 6 4, 043130 (2024).

[5] Tamás Vaszary, Animesh Datta, Tom Goffrey, and Brian Appelbe, "Solving the Nonlinear Vlasov Equation on a Quantum Computer", arXiv:2411.19310, (2024).

[6] Abhinav Muraleedharan and Nathan Wiebe, "Simulating Time Dependent and Nonlinear Classical Oscillators through Nonlinear Schrödingerization", arXiv:2505.17170, (2025).

[7] Hsuan-Cheng Wu and Xiantao Li, "Structure-preserving quantum algorithms for linear and nonlinear Hamiltonian systems", arXiv:2411.03599, (2024).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-07 23:28:02) and SAO/NASA ADS (last updated successfully 2026-08-07 23:28:03). 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.