Limitations for Quantum Algorithms to Solve Turbulent and Chaotic Systems

Dylan Lewis; Stephan Eidenbenz; Balasubramanya Nadiga; Yiğit Subaşı

doi:10.22331/q-2024-10-24-1509

Limitations for Quantum Algorithms to Solve Turbulent and Chaotic Systems

Dylan Lewis¹, Stephan Eidenbenz², Balasubramanya Nadiga², and Yiğit Subaşı²

¹Department of Physics and Astronomy, University College London, London WC1E 6BT, United Kingdom
²Los Alamos National Laboratory, Los Alamos, NM, USA

Published:	2024-10-24, volume 8, page 1509
Eprint:	arXiv:2307.09593v2
Doi:	https://doi.org/10.22331/q-2024-10-24-1509
Citation:	Quantum 8, 1509 (2024).

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

Abstract

We investigate the limitations of quantum computers for solving nonlinear dynamical systems. In particular, we tighten the worst-case bounds of the quantum Carleman linearisation (QCL) algorithm [Liu et al., PNAS 118, 2021] answering one of their open questions. We provide a further significant limitation for any quantum algorithm that aims to output a quantum state that approximates the normalized solution vector. Given a natural choice of coordinates for a dynamical system with one or more positive Lyapunov exponents and solutions that grow sub-exponentially, we prove that any such algorithm has complexity scaling at least exponentially in the integration time. As such, an efficient quantum algorithm for simulating chaotic systems or regimes is likely not possible.

Featured image: Illustration of solutions of nonlinear differential equations with no efficient quantum algorithm.

Popular summary

An ability to efficiently simulate differential equation systems is key to making advances in science, engineering and technology. While efficient quantum algorithms with an exponential speedup over the fastest classical algorithms exist for linear differential systems, a large fraction of differential equation systems of interest are nonlinear. In this context, previous analysis has demonstrated that such quantum algorithms remain efficient for nonlinear systems if the nonlinearity is not too great. In this work, we first tighten the worst-case bounds on the Quantum Carleman Linearisation (QCL) algorithm for nonlinear systems. We then prove that no efficient quantum algorithm can exist for highly nonlinear systems, in particular all chaotic (and therefore turbulent fluid flow) regimes, and for reasonable assumptions about the solutions. Finally, we give an example of such a system with numerical simulations.

► BibTeX data

@article{Lewis2024limitationsquantum,
  doi = {10.22331/q-2024-10-24-1509},
  url = {https://doi.org/10.22331/q-2024-10-24-1509},
  title = {Limitations for {Q}uantum {A}lgorithms to {S}olve {T}urbulent and {C}haotic {S}ystems},
  author = {Lewis, Dylan and Eidenbenz, Stephan and Nadiga, Balasubramanya and Suba{\c{s}}ı, Yi{\u{g}}it},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1509},
  month = oct,
  year = {2024}
}

► References

[1] Christian F. Klingenberg. ``Grand challenges in computational physics''. Frontiers in Physics 1 (2013).
https://doi.org/10.3389/fphy.2013.00002

[2] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd. ``Quantum algorithm for solving linear systems of equations''. Physical Review Letters 103, 150502 (2009).
https://doi.org/10.1103/PhysRevLett.103.150502

[3] Andris Ambainis. ``Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations'' (2010). arXiv:1010.4458.
arXiv:1010.4458

[4] Andrew M. Childs, Robin Kothari, and Rolando D. Somma. ``Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision''. SIAM Journal on Computing 46, 1920–1950 (2017).
https://doi.org/10.1137/16M1087072

[5] Leonard Wossnig, Zhikuan Zhao, and Anupam Prakash. ``Quantum Linear System Algorithm for Dense Matrices''. Physical Review Letters 120, 050502 (2018).
https://doi.org/10.1103/PhysRevLett.120.050502

[6] Dominic W. Berry. ``High-order quantum algorithm for solving linear differential equations''. Journal of Physics A: Mathematical and Theoretical 47, 105301 (2014).
https://doi.org/10.1088/1751-8113/47/10/105301

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

[8] Pedro C. S. Costa, Stephen Jordan, and Aaron Ostrander. ``Quantum Algorithm for Simulating the Wave Equation''. Physical Review A 99, 012323 (2019).
https://doi.org/10.1103/PhysRevA.99.012323

[9] Andrew M. Childs and Jin-Peng Liu. ``Quantum spectral methods for differential equations''. Communications in Mathematical Physics 375, 1427–1457 (2020).
https://doi.org/10.1007/s00220-020-03699-z

[10] Hari Krovi. ``Improved quantum algorithms for linear and nonlinear differential equations''. Quantum 7, 913 (2023).
https://doi.org/10.22331/q-2023-02-02-913

[11] B. D. Clader, B. C. Jacobs, and C. R. Sprouse. ``Preconditioned quantum linear system algorithm''. Physical Review Letters 110, 250504 (2013).
https://doi.org/10.1103/PhysRevLett.110.250504

[12] Yudong Cao, Anargyros Papageorgiou, Iasonas Petras, Joseph Traub, and Sabre Kais. ``Quantum algorithm and circuit design solving the Poisson equation''. New Journal of Physics 15, 013021 (2013).
https://doi.org/10.1088/1367-2630/15/1/013021

[13] Ashley Montanaro and Sam Pallister. ``Quantum algorithms and the finite element method''. Physical Review A 93, 032324 (2016).
https://doi.org/10.1103/PhysRevA.93.032324

[14] Alexander Engel, Graeme Smith, and Scott E. Parker. ``Quantum Algorithm for the Vlasov Equation''. Physical Review A 100, 062315 (2019).
https://doi.org/10.1103/PhysRevA.100.062315

[15] Juan Miguel Arrazola, Timjan Kalajdzievski, Christian Weedbrook, and Seth Lloyd. ``Quantum algorithm for non-homogeneous linear partial differential equations''. Physical Review A 100, 032306 (2019).
https://doi.org/10.1103/PhysRevA.100.032306

[16] Noah Linden, Ashley Montanaro, and Changpeng Shao. ``Quantum vs. Classical Algorithms for Solving the Heat Equation''. Communications in Mathematical Physics 395, 601–641 (2022).
https://doi.org/10.1007/s00220-022-04442-6

[17] Andrew M. Childs, Jin-Peng Liu, and Aaron Ostrander. ``High-precision quantum algorithms for partial differential equations''. Quantum 5, 574 (2021).
https://doi.org/10.22331/q-2021-11-10-574

[18] 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, e2026805118 (2021).
https://doi.org/10.1073/pnas.2026805118

[19] Cheng Xue, Yu-Chun Wu, and Guo-Ping Guo. ``Quantum homotopy perturbation method for nonlinear dissipative ordinary differential equations''. New Journal of Physics 23, 123035 (2021).
https://doi.org/10.1088/1367-2630/ac3eff

[20] Jin-Peng Liu, Dong An, Di Fang, Jiasu Wang, Guang Hao Low, and Stephen Jordan. ``Efficient Quantum Algorithm for Nonlinear Reaction–Diffusion Equations and Energy Estimation''. Communications in Mathematical Physics 404, 963–1020 (2023).
https://doi.org/10.1007/s00220-023-04857-9

[21] Sarah K. Leyton and Tobias J. Osborne. ``A quantum algorithm to solve nonlinear differential equations'' (2008). arXiv:0812.4423.
arXiv:0812.4423

[22] Daniel S. Abrams and Seth Lloyd. ``Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems''. Physical Review Letters 81, 3992–3995 (1998).
https://doi.org/10.1103/PhysRevLett.81.3992

[23] Andrew M. Childs and Joshua Young. ``Optimal state discrimination and unstructured search in nonlinear quantum mechanics''. Physical Review A 93, 022314 (2016).
https://doi.org/10.1103/PhysRevA.93.022314

[24] 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'' (2020). arXiv:2011.06571.
arXiv:2011.06571

[25] Marcelo Forets and Amaury Pouly. ``Explicit Error Bounds for Carleman Linearization'' (2017). arXiv:1711.02552.
arXiv:1711.02552

[26] Benito Hernández-Bermejo, Victor Fairén, and Léon Brenig. ``Algebraic recasting of nonlinear systems of ODEs into universal formats''. Journal of Physics A: Mathematical and General 31, 2415–2430 (1998).
https://doi.org/10.1088/0305-4470/31/10/016

[27] Chenjie Gu. ``QLMOR: A Projection-Based Nonlinear Model Order Reduction Approach Using Quadratic-Linear Representation of Nonlinear Systems''. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 30, 1307–1320 (2011).
https://doi.org/10.1109/TCAD.2011.2142184

[28] Carl W. Helstrom. ``Quantum detection and estimation theory''. Journal of Statistical Physics 1, 231–252 (1969).
https://doi.org/10.1007/BF01007479

[29] N.V. Kuznetsov and G.A. Leonov. ``On stability by the first approximation for discrete systems''. In Proceedings. 2005 International Conference Physics and Control, 2005. Pages 596–599. (2005).
https://doi.org/10.1109/PHYCON.2005.1514053

[30] Gerald Teschl. ``Ordinary Differential Equations and Dynamical Systems''. Graduate Studies in Mathematics, Volume 140, Amer. Math. Soc. (2012).
https://doi.org/10.1090/gsm/140

[31] Vijayakumar M. D., Anitha Karthikeyan, Jozef Zivcak, Ondrej Krejcar, and Hamidreza Namazi. ``Dynamical Behavior of a New Chaotic System with One Stable Equilibrium''. Mathematics 9, 3217 (2021).
https://doi.org/10.3390/math9243217

[32] Zoë Holmes, Nolan J. Coble, Andrew T. Sornborger, and Yiğit Subaşı. ``Nonlinear transformations in quantum computation''. Physical Review Research 5, 013105 (2023).
https://doi.org/10.1103/PhysRevResearch.5.013105

[33] Guanglei Xu, Andrew J. Daley, Peyman Givi, and Rolando D. Somma. ``Turbulent Mixing Simulation via a Quantum Algorithm''. AIAA Journal 56, 687–699 (2018).
https://doi.org/10.2514/1.J055896

Cited by

[1] Joseph Andress, Alexander Engel, Yuan Shi, and Scott Parker, "Quantum simulation of nonlinear dynamical systems using repeated measurement", Journal of Plasma Physics 91 2, E55 (2025).

[2] Reuben Demirdjian, Thomas Hogancamp, and Daniel Gunlycke, "Efficient decomposition of the Carleman linearized Burgers' equation", Physical Review A 113 3, 032408 (2026).

[3] Yunya Liu and Pai Wang, "Measurement-Efficient Variational Quantum Linear Solver for Carleman-Linearized Nonlinear Dynamics", (2026).

[4] Javier Gonzalez-Conde, Dylan Lewis, Sachin S. Bharadwaj, and Mikel Sanz, "Quantum Carleman linearization efficiency in nonlinear fluid dynamics", Physical Review Research 7 2, 023254 (2025).

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

[6] Hyoju Seo, Seokhyeon Lee, and Yongtae Kim, 2025 IEEE/ACM International Conference On Computer Aided Design (ICCAD) 1 (2025) ISBN:979-8-3315-1560-7.

[7] Muhammad Idrees Khan and Hua-Dong Yao, "A Reproducible D3Q19 Multiple-Relaxation-Time Lattice Boltzmann Benchmark and Quantum-Operator Audit for Forced Wall-Bounded Flow Simulations", Fluids 11 7, 175 (2026).

[8] Abhishek Setty, "A quantum linear systems pathway for solving differential equations", Journal of Physics A: Mathematical and Theoretical 59 18, 185303 (2026).

[9] Jin-Peng Liu and Lin Lin, "Dense outputs from quantum simulations", Journal of Computational Physics 514, 113213 (2024).

[10] Yuri Alexeev, Maximilian Amsler, Paul Baity, Marco Antonio Barroca, Sanzio Bassini, Torey Battelle, Daan Camps, David Casanova, Young Jai Choi, Frederic T. Chong, Charles Chung, Chris Codella, Antonio D. Corcoles, James Cruise, Alberto Di Meglio, Jonathan Dubois, Ivan Duran, Thomas Eckl, Sophia Economou, Stephan Eidenbenz, Bruce Elmegreen, Clyde Fare, Ismael Faro, Cristina Sanz Fernández, Rodrigo Neumann Barros Ferreira, Keisuke Fuji, Bryce Fuller, Laura Gagliardi, Giulia Galli, Jennifer R. Glick, Isacco Gobbi, Pranav Gokhale, Salvador de la Puente Gonzalez, Johannes Greiner, Bill Gropp, Michele Grossi, Emanuel Gull, Burns Healy, Benchen Huang, Travis S. Humble, Nobuyasu Ito, Artur F. Izmaylov, Ali Javadi-Abhari, Douglas Jennewein, Shantenu Jha, Liang Jiang, Barbara Jones, Wibe Albert de Jong, Petar Jurcevic, William Kirby, Stefan Kister, Masahiro Kitagawa, Joel Klassen, Katherine Klymko, Kwangwon Koh, Masaaki Kondo, Doga Murat Kurkcuoglu, Krzysztof Kurowski, Teodoro Laino, Ryan Landfield, Matt Leininger, Vicente Leyton-Ortega, Ang Li, Meifeng Lin, Junyu Liu, Nicolas Lorente, Andre Luckow, Simon Martiel, Francisco Martin-Fernandez, Margaret Martonosi, Claire Marvinney, Arcesio Castaneda Medina, Dirk Merten, Antonio Mezzacapo, Kristel Michielsen, Abhishek Mitra, Tushar Mittal, Kyungsun Moon, Joel Moore, Mario Motta, Young-Hye Na, Yunseong Nam, Prineha Narang, Yu-ya Ohnishi, Daniele Ottaviani, Matthew Otten, Scott Pakin, Vincent R. Pascuzzi, Ed Penault, Tomasz Piontek, Jed Pitera, Patrick Rall, Gokul Subramanian Ravi, Niall Robertson, Matteo Rossi, Piotr Rydlichowski, Hoon Ryu, Georgy Samsonidze, Mitsuhisa Sato, Nishant Saurabh, Vidushi Sharma, Kunal Sharma, Soyoung Shin, George Slessman, Mathias Steiner, Iskandar Sitdikov, In-Saeng Suh, Eric Switzer, Wei Tang, Joel Thompson, Synge Todo, Minh Tran, Dimitar Trenev, Christian Trott, Huan-Hsin Tseng, Esin Tureci, David García Valinas, Sofia Vallecorsa, Christopher Wever, Konrad Wojciechowski, Xiaodi Wu, Shinjae Yoo, Nobuyuki Yoshioka, Victor Wen-zhe Yu, Seiji Yunoki, Sergiy Zhuk, and Dmitry Zubarev, "Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions", arXiv:2312.09733, (2023).

[11] Javier Gonzalez-Conde and Andrew T. Sornborger, "Mixed Quantum-Semiclassical Simulation", arXiv:2308.16147, (2023).

[12] Hsuan-Cheng Wu, Jingyao Wang, and Xiantao Li, "Quantum Algorithms for Nonlinear Dynamics: Revisiting Carleman Linearization with No Dissipative Conditions", SIAM Journal on Scientific Computing 47 2, A943 (2025).

[13] Abtin Ameri, Joseph Carolan, Andrew M. Childs, and Hari Krovi, "Quantum lower bounds for simulating fluid dynamics", arXiv:2603.12161, (2026).

[14] Yen Ting Lin, Robert B. Lowrie, Denis Aslangil, Yiğit Subașı, and Andrew T. Sornborger, "Challenges for quantum computation of nonlinear dynamical systems using linear representations", arXiv:2202.02188, (2022).

[15] Xiantao Li, "A Quantum Path to Partial Differential Equations", arXiv:2607.09639, (2026).

[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] Vinamr Jain and Romit Maulik, "Higher order quantum reservoir computing for non-intrusive reduced-order models", arXiv:2407.21602, (2024).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-10 11:18:39) and SAO/NASA ADS (last updated successfully 2026-08-09 21:49:16). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch ADS cited-by data during last attempt 2026-08-10 11:18:39: Cannot retrieve data from ADS due to rate limitations.

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.