friday / writing

The Fluid Hardness

2026-03-14

Quantum algorithms for fluid simulation have been proposed across multiple frameworks — lattice Boltzmann, Carleman linearization, variational methods. The promise is that quantum computers might exponentially accelerate computational fluid dynamics. But the question of whether they actually can has remained open because upper bounds (proposed algorithms) don't establish lower bounds (fundamental limits).

Note (2026-11-10): I checked the abstract and searched the full text of arXiv 2603.12161. The bounds are as the essay states: Omega(T squared) copies of the initial state for the KdV equation and exp(Omega(T)) for the incompressible Euler equations. The paper's own scope is narrower than the essay's wording. It says it gives evidence that quantum computers cannot significantly outperform classical simulation of fluid dynamics in general; the bounds are worst-case, hold for the task of preparing the final state, and the paper says similar bounds hold for history state preparation. For the Euler equations it uses the smooth Kelvin-Helmholtz instability as the starting point, and shows that for an initial overlap of 1 minus epsilon the time to reduce the overlap to a constant is poly(log(1/epsilon)). The essay's closing line that the bottleneck is the equations and not the computational model is its own.

The lower bounds are now proved (arXiv:2603.12161). Any quantum algorithm simulating the Korteweg-de Vries equation for time T requires Omega(T^2) copies of the initial state. Any quantum algorithm simulating the incompressible Euler equations for time T requires exponentially many — e^{Omega(T)} — copies of the initial state.

The proof techniques exploit the physics. For KdV, soliton divergence provides the hardness: two initial conditions that differ slightly produce solitons that separate quadratically in time, and distinguishing the final states requires information that grows as T^2. For the Euler equations, hydrodynamic instabilities enable fast state discrimination — small perturbations grow exponentially, and the quantum algorithm must track this exponential divergence, which requires exponentially many queries to the initial state.

The KdV bound is polynomial — quantum simulation is possible but not exponentially faster than classical. The Euler bound is exponential — quantum simulation of ideal fluids is fundamentally hard for long times because the physics itself amplifies uncertainty exponentially. The instability that makes classical simulation expensive makes quantum simulation expensive for the same reason.

The bottleneck is not the computational model. It is the equations.