Quantum Koopman Algorithms
Key insights
The work introduces Quantum Koopman Algorithms (QKAs): a framework where the quantum computer evolves a carefully chosen space of observables rather than the full state trajectory.
The key mathematical move comes from Koopman theory. Even when the underlying dynamics is nonlinear, the evolution of observables is linear in a larger space.
QKAs come in two forms. Dynamic-QKAs estimate how chosen observables change over time, while Spectral-QKAs extract modes, frequencies, decay rates, and other spectral information.
For structured open free-fermion systems, the paper gives algorithms that output heat flows and decay rates with gate costs that scale polylogarithmically in the number of fermionic modes, yielding an exponential quantum advantage.
For nonlinear classical dynamics, the paper proposes a nonlinear interaction picture: expand around a solvable nonlinear flow, which allows one to go beyond existing approaches that only apply to weakly nonlinear systems. It also develops spectral methods for extracting eigen-frequencies of late-time nonlinear dynamics.
Setting the scene
Many of the most important problems in science and engineering involve the simulation of dynamics. Electrons move through materials, heat flows into an environment, populations grow and compete, fluids mix, plasmas oscillate, and chemical systems relax toward equilibrium. A simulation usually starts from a state, evolves it forward in time, and only afterward asks for a quantity of interest: a heat current, a density profile, a frequency, a decay rate, a force, or a correlation function.
That “compute first, ask questions later” strategy is natural, but it is not always the best route to construct an efficient quantum algorithm. First, it may be inefficient to extract the observable of interest from the state. Second, for most high-impact classical dynamical systems, the state evolves according to a nonlinear ordinary differential equation (nonlinear ODE). This nonlinearity clashes with the fundamental linearity of the quantum computer, and is currently a core bottleneck to the application of quantum algorithms to areas such as plasma and fluids.
This is where the new paper changes the perspective. Instead of treating observables as a post-processing step, it makes them the primary object of the computation. The mathematical language behind this is Koopman theory. In ordinary dynamics, a state x(t) follows an equation of motion. Koopman theory looks instead at functions of the state, such as temperature, density, energy, or more abstract coordinates. The crucial fact is that these functions evolve linearly, even when the state itself follows nonlinear equations. The price one pays for this linearity is that the dynamics are lifted from the original state space to an infinite-dimensional space of observables.
The algorithm begins by deciding which observables matter, asks whether they form a closed or approximately closed dynamical system, and only then designs a quantum encoding. The full Koopman space of relevant observables can be enormous. The opportunity is that quantum computers are designed to work with enormous linear spaces. The value of an exponentially large number of observables can, under the right circumstances, be encoded in the amplitudes of a quantum state.
A quantum algorithmic framework for observable space
The central object in a Quantum Koopman Algorithm is a vector of observables, call it g. Each entry is a function of the underlying system state. If these observables are chosen well, their evolution can be written as a linear equation, schematically g'(t) = K g(t) + b. Here K is the finite-dimensional Koopman generator induced by the chosen observables, and b accounts for possible source terms.
The paper identifies three requirements that make such a problem a good QKA candidate. First, the observables must be dynamically closed: their time derivatives should be expressible using the same observable set, at least to a controlled approximation. Second, the initial observable data and the matrix K must be encodable by efficient quantum circuits. Third, the final physical quantity of interest must be decodable.
The paper introduces two classes of algorithms.
A Dynamic-QKA solves an initial-value problem for observables. Given the initial observable vector, the quantum algorithm prepares a state proportional to the observable vector at a later time, or a history state that stores states at multiple times in superposition. This is useful when the desired answer is a time-dependent quantity such as a heat profile, a covariance matrix, or a trajectory of selected variables.
A Spectral-QKA instead extracts spectral information from K: decay rates, invariant modes, oscillation frequencies, or other long-time structures. This is analogous in spirit to quantum phase estimation, but generalized to settings where the Koopman generator may describe dissipative or nonlinear dynamics rather than a closed quantum system.
Figure 1: Schematic diagram for the construction of a Koopman system to be solved via a Dynamic- or Spectral-QKA.
Application 1: open free fermions and heat flow
The first major application is an open quantum system made of exponentially many free fermionic modes coupled linearly to an environment. Free-fermion models are important in materials, transport, and condensed-matter physics.
For these systems, a natural observable object is the covariance matrix. Its entries summarize the expectation values of quadratic Majorana operators. The paper tracks this covariance matrix through a closed set of linear equations. For a structured problem with N fermionic modes, target times and errors that scale polylogarithmically, and suitable state-preparation assumptions, the paper constructs a quantum algorithm with O(polylog(N)) gate cost for preparing the covariance-matrix state – exponentially faster than prior classical and quantum methods. The paper then shows how this observable-space state can be used to estimate physically meaningful quantities, including the total dissipated heat per fermion.
The same setting also has a spectral side. Under standard secular approximation assumptions, the decay rates of the covariance matrix can be sampled with probabilities given by their spectral weights. In practical terms, the algorithm preferentially samples the decay channels that matter most for the initial condition. The paper also gives a construction for steady-state covariance data, with a cost that depends on the inverse Lindbladian gap as well as polylogarithmic factors in system size.
Application 2: a nonlinear interaction picture
Nonlinear dynamics are harder. Quantum mechanics is linear, and standard quantum algorithms can implement linear evolution. A common strategy is therefore to embed a nonlinear system into a larger linear system. One well-known method is Carleman embedding, which tracks monomials such as \(x\), \(x^{\otimes 2}\), \(x^{\otimes 3}\), and so on, up to some truncation order.
Carleman embedding is powerful, but it can be restrictive. Known convergence criteria often require the nonlinear part of the dynamics to be weak compared with a stabilizing linear part. That is a major limitation because the interesting nonlinearities in fluids, plasmas, chemistry, ecosystems, and many other systems are often not weak in that sense.
The paper introduces a way around this bottleneck inspired by the interaction picture from quantum mechanics. Instead of splitting the dynamics into “linear part plus nonlinear perturbation,” it splits them into “solvable nonlinear part plus perturbation.” The solvable nonlinear part supplies a better coordinate system: its Koopman modes. The remaining perturbation can then be small relative to this nonlinear reference flow, even when the original system looks strongly nonlinear in ordinary coordinates. In other words, “strongly nonlinear” can depend on the coordinates used to describe the problem. The paper illustrates this with a population model (see Fig 2).
Figure 2: [Left] Nonlinear population dynamics simulation in a strongly nonlinear regime using Carleman linear embedding (blue) and the nonlinear interaction approach (red). The latter follows the exact solution (black-dashed) whereas the former incurs large errors. [Right] Errors vs truncation parameter for Carleman (blue) and the nonlinear interaction picture approach (red). Only the latter converges, hence allowing simulation with controlled errors.
This illustrates that a nonlinear system may be hard because we are expanding around the wrong baseline. QKAs try to choose a baseline that already captures the dominant nonlinear behavior, and then let the quantum computer handle the large observable hierarchy that remains.
Application 3: late-time oscillations
The final application is spectral. Many nonlinear systems have transients that decay away while persistent oscillations remain. These late-time frequencies can reveal coherent structures, limit cycles, metastable behavior, or other reduced descriptions of a complicated system. Extracting them classically can be expensive when the underlying observable space is huge.
A direct use of quantum phase estimation is not enough here because the Koopman generator need not be Hermitian or anti-Hermitian. Decay and oscillation are mixed together. The paper instead uses a quantum ODE solver to filter out decaying modes and then applies a frequency-estimation step to the remaining oscillatory content.
To control the probability of frequency-estimation errors, the paper introduces a windowed quantum ODE solver. Windowing is a familiar idea from signal processing: rather than abruptly cutting off a time signal, one samples it with a smooth envelope that suppresses artifacts. In the QKA setting, this helps turn late-time Koopman data into reliable frequency samples.
Figure 3: Spectral-QKA separates decaying transients from persistent oscillatory modes and estimates the late-time frequencies using a windowed quantum ODE solver.
What’s next
Quantum Koopman Algorithms offer an alternative answer to a basic question: which dynamical features should a quantum computer simulate? The conventional answer is “simulate the state.” The Koopman answer is “simulate the observables that carry the information we want.”
That shift brings together three ideas that fit naturally: Koopman theory supplies linear evolution in observable space; quantum algorithms supply compact encodings of large linear systems; and problem-specific decoding focuses the computation on physically meaningful outputs. The result is a framework that applies both to quantum dynamics and to nonlinear classical dynamics, where observable-space structure may be the difference between a useful algorithm and an intractable problem.
Our work establishes broad classes of algorithms centered on physical observables, providing new tools and modalities to unlock quantum speedups. The work ahead is to identify – beyond the illustrative applications discussed above – physical systems whose important observables form the right kind of structured space.
Terminology
Observable: A quantity computed from the state of a system over time, such as energy, heat, density, covariance, or a frequency-relevant signal.
Koopman operator: A linear operator describing how observables evolve in time, even when the underlying state dynamics are nonlinear.
Dynamical closure: A property that a chosen set of observables evolves within itself, exactly or approximately, so that a finite linear system can describe it.
Block-encoding: A standard quantum-algorithm technique that represents a matrix inside a larger unitary operation.
Dynamic-QKA: A Quantum Koopman Algorithm that solves for observable data as a function of time.
Spectral-QKA: A Quantum Koopman Algorithm that extracts modal information such as decay rates, frequencies, or invariant components.
Carleman embedding: A method that turns nonlinear dynamics into a larger linear system by tracking powers and products of variables.
Nonlinear interaction picture: The paper’s approach of expanding around a solvable nonlinear flow and treating only the remaining interaction as the perturbation.
History state: A quantum state that stores the solution at many times in superposition, rather than only at one final time.