A Reduced-Basis Algorithm for Solving Nonlinear Differential Equations on Quantum Computers

The methodology starts from a nonlinear polynomial ODE or PDE and first discretizes it in time, and, for PDEs, also in space. This gives a finite-dimensional nonlinear polynomial update map. Instead of applying this nonlinear map directly to the quantum state, the update is rewritten in a lifted reduced polynomial basis for an m-timestep evolution. In this representation, the nonlinear update is recovered exactly by constructing and applying a matrix, which we refer to as the RBA matrix, to the lifted vector. The quantum algorithm then encodes the lifted polynomial basis into the amplitudes of a quantum state. One register index the monomial stored in the lifted basis, while for PDEs an additional register stores the spatial position. The reduced linear matrix is then block-encoded and applied to the lifted state. In this work, the block-encoding step uses the low-rank method of Li et al. [1] which gives a CNOT count with leading-order scaling (K+11/12)2^n for a rank-(K) matrix of size (2^(n+1) x 2^(n+1)).After applying the block-encoded matrix, the resulting quantum state contains the updated field values after the m-timestep evolution. These values can either be measured directly, or an observable can be used to extract a quantity of interest. Overall, the classical computer constructs the reduced basis and matrix, while the quantum computer applies this matrix efficiently in the PDE setting, where the local constructions is applied in parallel over the spatial grid.

The algorithm is demonstrated on a quantum simulator using Qiskit for the Lorenz system and the one-dimensional viscous Burgers equation. In both cases, the equations are discretized using an explicit Euler scheme and the RBA representation is compared against the corresponding classical Euler solution. Since the degree and size of the lifted basis grow rapidly with the number of composed timesteps, constructing one global RBA matrix for the full-time interval is not practical. Therefore, for demonstration purposes, we use a short-time RBA representation and reinitialize the lifted state after a fixed number of timesteps. For the Lorenz system, this is done using repeated five-step RBA maps over a trajectory of 30,000 Euler timesteps. The resulting RBA trajectory agrees with the classical Euler trajectory up to floating-point round-off. The same strategy is applied to the one-dimensional viscous Burgers equation, where the RBA solution again recovers the fully discrete nonlinear dynamics exactly. We also aim to demonstrate this algorithm for the logistic equation on real quantum hardware by the time of the conference.

The proposed RBA algorithm is best understood as a hybrid quantum-classical method. The classical computer performs the problem-dependent preprocessing: it discretizes the ODE or PDE, composes the timestep map over a window of m-timesteps, identifies the reduced polynomial basis, and computes the RBA matrix coefficients. The quantum computer then amplitude-encodes the lifted monomial vector and applies the block-encoded RBA operator to recover the m-step discrete nonlinear update.

For PDE discretizations where stencil locality can be exploited, the quantum register scales as O(Dlog(N)+nm^(D+1)log p), where D is the number of spatial dimensions, N is the number of grid points per spatial direction, n is the number of fields, m is the number of composed timesteps, and p is the polynomial degree of the nonlinear update. Thus, the method achieves logarithmic scaling in the global grid size, giving an exponential compression of the spatial degrees of freedom compared with classical grid-based storage, while retaining polynomial scaling in the time. This time scaling improves over the copy-based approach of Leyton and Osborne [2], where quantum resources grow exponentially with integration time. It is closer to the mean-field nonlinear algorithms of Lloyd et al. [3], which also have polynomial time scaling, but RBA has the advantage that it represents the chosen fully discrete nonlinear dynamics exactly, rather than introducing mean-field errors that can accumulate over time. The approach is also competitive with Carleman linearization, where truncation, conditioning, and convergence restrictions can prevent accurate recovery of the nonlinear evolution.

The main limitation is the classical preprocessing cost. Although the quantum register scales favorably, constructing the reduced basis and RBA matrix can be exponentially expensive in m in the worst case, since the polynomial degree of the composed map grows as p^m. In practice, this cost may be lowered for local PDE discretizations because the reduced local basis and RBA matrix need only be constructed for each distinct stencil type and can then be reused across all grid points with the same local structure. Therefore, the approach is most promising for large PDE systems with local, repeated stencil structure and compact reduced bases. Reuse across different problems is also possible when the governing polynomial structure, discretization, timestep, parameters, and boundary treatment are sufficiently similar.