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^{frac{3}{4}(1+frac{D}{2}\)} times q_M), where q_M is a multiplicative overhead for data extraction with q_M = O\(Re^{frac{3}{8}}\) for the drag force. This upper bounds the scaling improvement over classical algorithms by O\(Re^{frac{3D}{8}}\). However, our numerical investigations suggest a lower speedup, with a scaling estimate of O\(Re^1.936 times q_M\) 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.