  Numerical simulation of turbulent fluid dynamics needs to either parameterize
turbulence-which introduces large uncertainties-or explicitly resolve the
smallest scales-which is prohibitively expensive. Here we provide evidence
through analytic bounds and numerical studies that a potential quantum
exponential speedup can be achieved to simulate the Navier-Stokes equations
governing turbulence using quantum computing. Specifically, we provide a
formulation of the lattice Boltzmann equation for which we give evidence that
low-order Carleman linearization is much more accurate than previously believed
for these systems and that for computationally interesting examples. This is
achieved via a combination of reformulating the nonlinearity and accurately
linearizing the dynamical equations, effectively trading nonlinearity for
additional degrees of freedom that add negligible expense in the quantum
solver. Based on this we apply a quantum algorithm for simulating the
Carleman-linearized lattice Boltzmann equation and provide evidence that its
cost scales logarithmically with system size, compared to polynomial scaling in
the best known classical algorithms. This work suggests that an exponential
quantum advantage may exist for simulating fluid dynamics, paving the way for
simulating nonlinear multiscale transport phenomena in a wide range of
disciplines using quantum computing.
