Reduced basis algorithm for solving nonlinear differential equations on quantum computers
Pith reviewed 2026-06-27 05:47 UTC · model grok-4.3
The pith
A reduced basis algorithm reproduces the exact discrete nonlinear dynamics of polynomial ODEs and PDEs on quantum computers.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
After time discretization the resulting polynomial update map is composed over m timesteps; the reduced monomial basis appearing in this composed map is identified and a linear RBA operator is constructed whose action recovers the exact m-timestep nonlinear dynamics. Thus at the level of the chosen discrete update rule the method introduces no additional approximation error beyond the time discretization error. The qubit number requirement is governed by the size of the reduced monomial basis, yielding at most O(n m log p) qubits for ODEs and O(D log N + n m^{D+1} log p) for PDEs with locality.
What carries the argument
reduced monomial basis of the m-step composed polynomial update map, which exactly spans the nonlinear dynamics and permits a linear operator representation
If this is right
- The RBA reproduces the corresponding discrete time nonlinear dynamics exactly.
- The qubit requirement depends on the reduced monomial basis size rather than the full state space.
- For PDEs the grid size dependence remains logarithmic while nonlinear overhead is controlled by local reduced basis size.
- The computational burden of handling nonlinearity is moved to classical preprocessing.
- Numerical tests confirm exact reproduction for the Lorenz system and Burgers equation.
Where Pith is reading between the lines
- If the classical preprocessing cost stays manageable, the method could enable quantum simulation of nonlinear systems where direct linearization is not feasible.
- The exact discrete-level reproduction suggests testing whether accumulated errors over many windows remain controlled in long-time integrations.
- Similar reduced-basis lifting might apply to other quantum linear system solvers for time-dependent problems.
- The polynomial assumption limits direct use to systems where the discrete map is polynomial; non-polynomial cases would need additional approximation.
Load-bearing premise
The nonlinear update map after time discretization must be polynomial so its m-step composition can be exactly spanned by a reduced monomial basis of size bounded by the stated expressions.
What would settle it
Applying the constructed RBA operator to an initial state and comparing the result after one window to the result of iterating the original discrete polynomial map the same number of steps; any mismatch indicates the claim of exact reproduction does not hold.
Figures
read the original abstract
As quantum computing moves toward scientific computing applications, nonlinear differential equations remain a central challenge since quantum evolution is intrinsically linear. In this work, we introduce a reduced basis algorithm (RBA) for polynomial nonlinear ordinary differential equations (ODEs) and spatially discretized partial differential equations (PDEs). After time discretization, the method composes the resulting polynomial update map over $m$ timesteps, identifies the reduced monomial basis appearing in this composed map, and constructs a linear RBA operator whose action recovers the exact $m$-timestep nonlinear dynamics. Thus, at the level of the chosen discrete update rule, the method introduces no additional approximation error beyond the time discretization error. The qubit number requirement is governed by the size of the reduced monomial basis. For an $n$-dimensional polynomial ODE system of degree $p>1$, the lifted register requires at most $q_m^{\mathrm{ODE}} = O(nm\log p)$ qubits in the full basis scenario. For PDEs discretized on $N^D$ grid points, a locality-based construction requires at most $q_m^{\mathrm{PDE}} = O(D\log N + n m^{D+1}\log p)$ qubits. Hence, the dependence on the grid size remains logarithmic, while the nonlinear overhead is controlled by local reduced basis size. The main computational burden is moved from the quantum computer to a classical preprocessing step, where the reduced monomial basis and RBA operator are constructed for the chosen timestep window. Through numerical tests on the Lorenz system and the one-dimensional Burgers equation, we verify that the RBA reproduces the corresponding discrete time nonlinear dynamics exactly, while exposing the trade-off between timestep composition, reduced basis growth, and locality.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims to introduce a reduced basis algorithm (RBA) for polynomial nonlinear ODEs and PDEs on quantum computers. After time discretization, the m-step composed polynomial update map is exactly spanned by a reduced monomial basis; a linear RBA operator is constructed on this basis to recover the exact m-step nonlinear dynamics with no additional approximation error. Qubit counts are bounded by O(nm log p) for n-dimensional ODEs of degree p and O(D log N + n m^{D+1} log p) for PDEs on N^D grids. The computational burden is shifted to classical preprocessing for basis identification and operator construction. Numerical tests on the Lorenz system and 1D Burgers equation confirm exact reproduction of the discrete dynamics.
Significance. If the reduced monomial basis and RBA operator can be constructed efficiently in classical preprocessing, the approach would allow quantum simulation of nonlinear dynamics with only logarithmic dependence on spatial grid size and no extra discretization error beyond the chosen time-stepping rule, offering a concrete route to applying quantum computers to scientific computing tasks involving nonlinearity.
major comments (1)
- [Abstract] Abstract: the qubit bounds O(nm log p) and O(D log N + n m^{D+1} log p) are presented as governing the lifted register size, but these are upper bounds on the final reduced basis dimension; the manuscript provides no explicit algorithm or complexity proof showing that the reduced monomial basis support and the corresponding linear operator matrix can be identified and populated in time polynomial in the input parameters, as symbolic composition of the m-step map can generate an exponentially large intermediate term count before reduction.
minor comments (1)
- [Abstract] The abstract refers to a 'locality-based construction' for the PDE qubit bound; a brief description of how locality is used to control the reduced basis size would aid readability.
Simulated Author's Rebuttal
We thank the referee for the careful reading and for highlighting an important clarification needed regarding the classical preprocessing step. We address the major comment below.
read point-by-point responses
-
Referee: [Abstract] Abstract: the qubit bounds O(nm log p) and O(D log N + n m^{D+1} log p) are presented as governing the lifted register size, but these are upper bounds on the final reduced basis dimension; the manuscript provides no explicit algorithm or complexity proof showing that the reduced monomial basis support and the corresponding linear operator matrix can be identified and populated in time polynomial in the input parameters, as symbolic composition of the m-step map can generate an exponentially large intermediate term count before reduction.
Authors: The referee is correct that the stated qubit bounds are upper bounds on the dimension of the final reduced monomial basis after support identification. The manuscript does not include an explicit general algorithm or a complexity proof establishing that this identification (and the subsequent population of the linear operator matrix) can be performed in time polynomial in the input parameters n, m, p, D, N. As noted, naive symbolic composition of the m-step polynomial map can produce an exponentially large number of intermediate terms prior to reduction. The paper's emphasis is on the exact equivalence between the nonlinear m-step map and the linear RBA operator once the reduced basis is available, together with the resulting qubit scaling; the classical preprocessing cost is acknowledged as the dominant burden but is not analyzed in detail. For the concrete numerical examples (Lorenz system and 1D Burgers equation), the reduced bases are obtained by direct evaluation on a modest number of points or by limited symbolic expansion, which remains tractable. We will revise the abstract to make explicit that the qubit counts assume the reduced basis has already been identified, and we will add a dedicated paragraph in the methods section discussing the preprocessing complexity, its dependence on system structure and choice of m, and the fact that general polynomial-time guarantees are not provided. revision: yes
Circularity Check
No circularity; exact reproduction is by explicit classical construction of basis and operator
full rationale
The paper's central claim is that after identifying the monomial terms appearing in the composed m-step polynomial map, the linear RBA operator is defined so that its action on the reduced basis exactly reproduces the nonlinear update. This exactness is a direct consequence of the construction itself (the operator is built to match the map on the spanning set), not a derived prediction or self-referential fit. No self-citations are invoked for uniqueness or ansatz; the qubit bounds are stated as upper bounds on basis size rather than fitted quantities; and the method contains no parameter estimation or renaming of external results. The derivation is therefore self-contained as an algorithmic reduction whose correctness follows from linear algebra on the explicitly constructed space.
Axiom & Free-Parameter Ledger
axioms (1)
- domain assumption The governing equations are polynomial of finite degree p after spatial discretization.
invented entities (1)
-
Reduced monomial basis for the m-step composed map
no independent evidence
Reference graph
Works this paper leans on
-
[1]
arXiv preprint arXiv:0812.4423 , year =
A quantum algorithm to solve nonlinear differential equations , author =. arXiv preprint arXiv:0812.4423 , year =. 0812.4423 , archivePrefix =
-
[2]
arXiv preprint arXiv:2011.06571 , year =
Quantum algorithm for nonlinear differential equations , author =. arXiv preprint arXiv:2011.06571 , year =. 2011.06571 , archivePrefix =
arXiv 2011
-
[3]
Bulletin of the American Meteorological Society , volume =
Quantum Computers for Weather and Climate Prediction: The Good, the Bad, and the Noisy , author =. Bulletin of the American Meteorological Society , volume =. 2023 , doi =
2023
-
[4]
Physical Review Research , volume =
Tensor-programmable quantum circuits for solving differential equations , author =. Physical Review Research , volume =. 2026 , publisher =
2026
-
[5]
Acta Mathematica , volume =
Carleman, Torsten , title =. Acta Mathematica , volume =. 1932 , doi =
1932
-
[6]
Proceedings of the National Academy of Sciences , volume =
Efficient quantum algorithm for dissipative nonlinear differential equations , author =. Proceedings of the National Academy of Sciences , volume =. 2021 , doi =
2021
-
[7]
Quantum , volume =
Improved quantum algorithms for linear and nonlinear differential equations , author =. Quantum , volume =. 2023 , month = feb, doi =
2023
-
[8]
npj Quantum Information , volume =
Further improving quantum algorithms for nonlinear differential equations via higher-order methods and rescaling , author =. npj Quantum Information , volume =. 2025 , doi =
2025
-
[9]
Globalizing the
Novikau, Ivan and Joseph, Ilon , journal =. Globalizing the. 2025 , eprint =
2025
-
[11]
AVS Quantum Science , volume =
Sanavio, Claudio and Succi, Sauro , title =. AVS Quantum Science , volume =. 2024 , doi =
2024
-
[12]
Communications in Mathematical Physics , volume =
Liu, Jin-Peng and An, Dong and Fang, Di and Wang, Jiasu and Low, Guang Hao and Jordan, Stephen , title =. Communications in Mathematical Physics , volume =. 2023 , doi =
2023
-
[13]
Quantum , volume =
An, Dong and Trivisa, Konstantina , title =. Quantum , volume =. 2026 , month = jan, doi =
2026
-
[14]
SIAM Journal on Scientific Computing , volume =
Wu, Hsuan-Cheng and Wang, Jingyao and Li, Xiantao , title =. SIAM Journal on Scientific Computing , volume =. 2025 , doi =
2025
-
[15]
Solving nonlinear differential equations on Quantum Computers: A
Tennie, Felix and Magri, Luca , journal =. Solving nonlinear differential equations on Quantum Computers: A. 2024 , eprint =
2024
-
[16]
Physical Review A , volume =
Solving nonlinear differential equations with differentiable quantum circuits , author =. Physical Review A , volume =. 2021 , doi =
2021
-
[17]
Physical Review A , volume =
Variational quantum algorithms for nonlinear problems , author =. Physical Review A , volume =. 2020 , doi =
2020
-
[18]
Efficient quantum algorithm for solving differential equations with
Katz, Judd and Muraleedharan, Gopikrishnan and Alase, Abhijeet , journal =. Efficient quantum algorithm for solving differential equations with. 2025 , eprint =
2025
-
[19]
New Journal of Physics , volume =
Quantum homotopy perturbation method for nonlinear dissipative ordinary differential equations , author =. New Journal of Physics , volume =. 2021 , month = dec, doi =
2021
-
[20]
Physical Review A , volume =
Quantum algorithm for solving a quadratic nonlinear system of equations , author =. Physical Review A , volume =. 2022 , doi =
2022
-
[21]
Reducing
Li, Zexian and Zhang, Guofeng and Zhang, Xiao-Ming , journal =. Reducing. 2026 , eprint =
2026
-
[22]
author author S. K. \ Leyton \ and\ author T. J. \ Osborne ,\ title title A quantum algorithm to solve nonlinear differential equations , \ 10.48550/arXiv.0812.4423 journal journal arXiv preprint arXiv:0812.4423 \ ( year 2008 ),\ 10.48550/arXiv.0812.4423 ,\ http://arxiv.org/abs/0812.4423 arXiv:0812.4423 [quant-ph] NoStop
work page internal anchor Pith review Pith/arXiv arXiv doi:10.48550/arxiv.0812.4423 2008
-
[23]
author author S. Lloyd , author G. De Palma , author C. Gokler , author B. Kiani , author Z.-W. \ Liu , author M. Marvian , author F. Tennie , \ and\ author T. Palmer ,\ title title Quantum algorithm for nonlinear differential equations , \ 10.48550/arXiv.2011.06571 journal journal arXiv preprint arXiv:2011.06571 \ ( year 2020 ),\ 10.48550/arXiv.2011.0657...
-
[24]
author author F. Tennie \ and\ author T. N. \ Palmer ,\ title title Quantum computers for weather and climate prediction: The good, the bad, and the noisy , \ 10.1175/BAMS-D-22-0031.1 journal journal Bulletin of the American Meteorological Society \ volume 104 ,\ pages E488--E500 ( year 2023 ) NoStop
-
[25]
author author J.-P. \ Liu , author H. . \ Kolden , author H. K. \ Krovi , author N. F. \ Loureiro , author K. Trivisa , \ and\ author A. M. \ Childs ,\ title title Efficient quantum algorithm for dissipative nonlinear differential equations , \ 10.1073/pnas.2026805118 journal journal Proceedings of the National Academy of Sciences \ volume 118 ,\ pages e2...
-
[26]
author author H. Krovi ,\ title title Improved quantum algorithms for linear and nonlinear differential equations , \ 10.22331/q-2023-02-02-913 journal journal Quantum \ volume 7 ,\ pages 913 ( year 2023 ) NoStop
-
[27]
author author P. C. S. \ Costa , author P. Schleich , author M. E. S. \ Morales , \ and\ author D. W. \ Berry ,\ title title Further improving quantum algorithms for nonlinear differential equations via higher-order methods and rescaling , \ 10.1038/s41534-025-01084-z journal journal npj Quantum Information \ volume 11 ,\ pages 141 ( year 2025 ) NoStop
-
[28]
author author C. Sanavio \ and\ author S. Succi ,\ title title Lattice B oltzmann- C arleman quantum algorithm and circuit for fluid flows at moderate R eynolds number , \ 10.1116/5.0195549 journal journal AVS Quantum Science \ volume 6 ,\ pages 023802 ( year 2024 ) NoStop
-
[29]
author author D. Jennings , author K. Korzekwa , author M. Lostaglio , author R. Ashworth , author E. Marsili , \ and\ author S. Rolston ,\ title title An end-to-end quantum algorithm for nonlinear fluid dynamics with bounded quantum advantage , \ @noop journal journal arXiv preprint arXiv:2512.03758 \ ( year 2025 ) ,\ http://arxiv.org/abs/2512.03758 arXi...
arXiv 2025
-
[30]
author author J.-P. \ Liu , author D. An , author D. Fang , author J. Wang , author G. H. \ Low , \ and\ author S. Jordan ,\ title title Efficient quantum algorithm for nonlinear reaction-diffusion equations and energy estimation , \ 10.1007/s00220-023-04857-9 journal journal Communications in Mathematical Physics \ volume 404 ,\ pages 963--1020 ( year 20...
-
[31]
author author D. An \ and\ author K. Trivisa ,\ title title Quantum algorithms for linear and non-linear fractional reaction-diffusion equations , \ 10.22331/q-2026-01-19-1969 journal journal Quantum \ volume 10 ,\ pages 1969 ( year 2026 ) NoStop
-
[32]
author author I. Novikau \ and\ author I. Joseph ,\ title title Globalizing the C arleman linear embedding method for nonlinear dynamics , \ 10.48550/arXiv.2510.15715 journal journal arXiv preprint arXiv:2510.15715 \ ( year 2025 ),\ 10.48550/arXiv.2510.15715 ,\ http://arxiv.org/abs/2510.15715 arXiv:2510.15715 [quant-ph] NoStop
-
[33]
author author J. Katz , author G. Muraleedharan , \ and\ author A. Alase ,\ title title Efficient quantum algorithm for solving differential equations with F ourier nonlinearity via K oopman linearization , \ 10.48550/arXiv.2512.06488 journal journal arXiv preprint arXiv:2512.06488 \ ( year 2025 ),\ 10.48550/arXiv.2512.06488 ,\ http://arxiv.org/abs/2512.0...
-
[34]
author author F. Tennie \ and\ author L. Magri ,\ title title Solving nonlinear differential equations on quantum computers: A F okker- P lanck approach , \ 10.48550/arXiv.2401.13500 journal journal arXiv preprint arXiv:2401.13500 \ ( year 2024 ),\ 10.48550/arXiv.2401.13500 ,\ http://arxiv.org/abs/2401.13500 arXiv:2401.13500 [quant-ph] NoStop
-
[35]
author author C. Xue , author Y.-C. \ Wu , \ and\ author G.-P. \ Guo ,\ title title Quantum homotopy perturbation method for nonlinear dissipative ordinary differential equations , \ 10.1088/1367-2630/ac3eff journal journal New Journal of Physics \ volume 23 ,\ pages 123035 ( year 2021 ) NoStop
-
[36]
author author C. Xue , author X.-F. \ Xu , author Y.-C. \ Wu , \ and\ author G.-P. \ Guo ,\ title title Quantum algorithm for solving a quadratic nonlinear system of equations , \ 10.1103/PhysRevA.106.032427 journal journal Physical Review A \ volume 106 ,\ pages 032427 ( year 2022 ) NoStop
-
[37]
author author M. Lubasch , author J. Joo , author P. Moinier , author M. Kiffner , \ and\ author D. Jaksch ,\ title title Variational quantum algorithms for nonlinear problems , \ 10.1103/PhysRevA.101.010301 journal journal Physical Review A \ volume 101 ,\ pages 010301 ( year 2020 ) NoStop
-
[38]
author author O. Kyriienko , author A. E. \ Paine , \ and\ author V. E. \ Elfving ,\ title title Solving nonlinear differential equations with differentiable quantum circuits , \ 10.1103/PhysRevA.103.052416 journal journal Physical Review A \ volume 103 ,\ pages 052416 ( year 2021 ) NoStop
-
[39]
author author P. Siegl , author G. S. \ Reese , author T. Hashizume , author N.-L. \ van H \"u lst , \ and\ author D. Jaksch ,\ title title Tensor-programmable quantum circuits for solving differential equations , \ 10.1103/2qzh-yf49 journal journal Physical Review Research \ volume 8 ,\ pages 013052 ( year 2026 ) NoStop
-
[40]
note Higher-order ODEs can be rewritten as equivalent first-order systems by introducing auxiliary variables, so the same construction applies in that setting. Stop
-
[41]
Other time discretization schemes may be used, provided the resulting fully discrete update can be represented in the chosen lifted basis
note The RBA construction is not restricted to explicit Euler. Other time discretization schemes may be used, provided the resulting fully discrete update can be represented in the chosen lifted basis. We use explicit Euler here because it leads to the simplest polynomial update map and makes the construction of the RBA algorithm more transparent. Stop
-
[42]
note The constant monomial is included by allowing the multi-index = 0 , for which z ^ =z_1^0 z_n^0=1 . Stop
-
[43]
author author Z. Li , author G. Zhang , \ and\ author X.-M. \ Zhang ,\ title title Reducing C-NOT counts for state preparation and block encoding via diagonal matrix migration , \ 10.48550/arXiv.2603.16492 journal journal arXiv preprint arXiv:2603.16492 \ ( year 2026 ),\ 10.48550/arXiv.2603.16492 ,\ http://arxiv.org/abs/2603.16492 arXiv:2603.16492 [quant-...
-
[44]
author author T. Carleman ,\ title title Application de la th \'e orie des \'e quations int \'e grales lin \'e aires aux syst \`e mes d' \'e quations diff \'e rentielles non lin \'e aires , \ 10.1007/BF02546499 journal journal Acta Mathematica \ volume 59 ,\ pages 63--87 ( year 1932 ) NoStop
-
[45]
author author H.-C. \ Wu , author J. Wang , \ and\ author X. Li ,\ title title Quantum algorithms for nonlinear dynamics: Revisiting C arleman linearization with no dissipative conditions , \ 10.1137/24M1665799 journal journal SIAM Journal on Scientific Computing \ volume 47 ,\ pages A943--A970 ( year 2025 ) NoStop
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.