An end-to-end quantum algorithm for nonlinear fluid dynamics with bounded quantum advantage

Computational fluid dynamics (CFD) is a cornerstone of classical scientific computing, and there is growing interest in whether quantum computers can accelerate such simulations. To date, the existing proposals for fault-tolerant quantum algorithms for CFD have almost exclusively been based on the Carleman embedding method, used to encode nonlinearities on a quantum computer. In this work, we begin by showing that these proposals suffer from a range of severe bottlenecks that negate conjectured quantum advantages: lack of convergence of the Carleman method, prohibitive time-stepping requirements, unfavorable condition-number scaling, and inefficient data extraction. With these roadblocks clearly identified, we develop a novel algorithm for the incompressible lattice Boltzmann equation that circumvents these obstacles, and then provide a detailed analysis of our algorithm, including all potential sources of algorithmic complexity, as well as gate-count estimates. We find that for an end-to-end problem, a modest quantum advantage may be preserved for selected observables in the high-error-tolerance regime.

We lower-bound the Reynolds-number scaling of our quantum algorithm in dimension D at Kolmogorov microscale resolution with O(Re³⁄⁴(1 + D⁄²) × qᴹ), where qᴹ is a multiplicative overhead for data extraction with qᴹ = O(Re³⁄⁸) for the drag force. This upper-bounds the scaling improvement over classical algorithms by O(Re³ᴰ⁄⁸). However, our numerical investigations suggest a lower speedup, with a scaling estimate of O(Re¹·⁹³⁶ × qᴹ) for D = 2. Our results give robust evidence that small, but nontrivial, quantum advantages can be achieved in the context of CFD, and motivate the need for additional rigorous end-to-end quantum algorithm development.