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

• URL: http://arxiv.org/abs/2512.03758v1
• Date: Wed, 03 Dec 2025 13:03:08 GMT
• Title: An end-to-end quantum algorithm for nonlinear fluid dynamics with bounded quantum advantage
• Authors: David Jennings, Kamil Korzekwa, Matteo Lostaglio, Richard Ashworth, Emanuele Marsili, Stephen Rolston,
• Abstract summary: We develop a novel algorithm for the incompressible lattice Boltzmann equation.<n>We find that for an end-to-end problem, a modest quantum advantage may be preserved for selected observables.<n>Our results give robust evidence that small, but nontrivial, quantum advantages can be achieved in the context of CFD.
• Score: 0.4618037115403289
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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(\mathrm{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(\mathrm{Re}^{\frac{3}{8}})$ for the drag force. This upper bounds the scaling improvement over classical algorithms by $O(\mathrm{Re}^{\frac{3D}{8}})$. However, our numerical investigations suggest a lower speedup, with a scaling estimate of $O(\mathrm{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.

Related papers

• FFT-Accelerated Auxiliary Variable MCMC for Fermionic Lattice Models: A Determinant-Free Approach with $O(N\log N)$ Complexity [52.3171766248012]
  We introduce a Markov Chain Monte Carlo (MCMC) algorithm that dramatically accelerates the simulation of quantum many-body systems.<n>We validate our algorithm on benchmark quantum physics problems, accurately reproducing known theoretical results.<n>Our work provides a powerful tool for large-scale probabilistic inference and opens avenues for physics-inspired generative models.
  arXiv  Detail & Related papers  (2025-10-13T07:57:21Z)
• Constant-Factor Improvements in Quantum Algorithms for Linear Differential Equations [0.4199844472131922]
  We prove constant factor bounds for a promising new quantum differential equation solver, the linear combination of Hamiltonian simulation algorithm.<n>Our new formulae improve over previous state of the art by at least two orders of magnitude, where the speedup can be far greater if state preparation has a significant cost.
  arXiv  Detail & Related papers  (2025-06-25T18:50:44Z)
• Distributed quantum algorithm for divergence estimation and beyond [12.925989807145301]
  We propose a distributed quantum algorithm framework to compute $rm Tr(f(A)g(B))$ within an additive error $varepsilon$.<n>This framework holds broad applicability across a range of distributed quantum computing tasks.
  arXiv  Detail & Related papers  (2025-03-12T14:28:22Z)
• On the practicality of quantum sieving algorithms for the shortest vector problem [42.70026220176376]
  lattice-based cryptography is one of the main candidates of post-quantum cryptography.<n> cryptographic security against quantum attackers is based on lattice problems like the shortest vector problem (SVP)<n>Asymptotic quantum speedups for solving SVP are known and rely on Grover's search.
  arXiv  Detail & Related papers  (2024-10-17T16:54:41Z)
• Optimization by Decoded Quantum Interferometry [38.063836468778895]
  We introduce Decoded Quantum Interferometry (DQI), a quantum algorithm that uses the quantum Fourier transform to reduce optimization problems to decoding problems.<n>For approximating optimal fits over finite fields, DQI achieves a superpolynomial speedup over known classical algorithms.
  arXiv  Detail & Related papers  (2024-08-15T17:47:42Z)
• A multiple-circuit approach to quantum resource reduction with application to the quantum lattice Boltzmann method [39.671915199737846]
  We introduce a multiple-circuit algorithm for a quantum lattice Boltzmann method (QLBM) solve of the incompressible Navier--Stokes equations.<n>The presented method is validated and demonstrated for 2D lid-driven cavity flow.
  arXiv  Detail & Related papers  (2024-01-20T15:32:01Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Stochastic Quantum Sampling for Non-Logconcave Distributions and Estimating Partition Functions [13.16814860487575]
  We present quantum algorithms for sampling from nonlogconcave probability distributions. $f$ can be written as a finite sum $f(x):= frac1Nsum_k=1N f_k(x)$.
  arXiv  Detail & Related papers  (2023-10-17T17:55:32Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  Quantum algorithms for topological data analysis seem to provide an exponential advantage over the best classical approach. We show that the central task of TDA -- estimating Betti numbers -- is intractable even for quantum computers. We argue that an exponential quantum advantage can be recovered if the input data is given as a specification of simplices.
  arXiv  Detail & Related papers  (2022-09-28T17:53:25Z)
• Improving Quantum Simulation Efficiency of Final State Radiation with Dynamic Quantum Circuits [1.3375143521862154]
  We make use of a new quantum hardware capability called dynamical quantum computing to improve the scaling of the QPS algorithm. We modify the quantum parton shower circuit to incorporate mid-circuit qubit measurements, resets, and quantum operations conditioned on classical information.
  arXiv  Detail & Related papers  (2022-03-18T15:31:19Z)
• Quantum algorithms for approximate function loading [0.0]
  We introduce two approximate quantum-state preparation methods for the NISQ era inspired by the Grover-Rudolph algorithm. A variational algorithm capable of loading functions beyond the aforementioned smoothness conditions is proposed.
  arXiv  Detail & Related papers  (2021-11-15T17:36:13Z)
• Quantum Topological Data Analysis with Linear Depth and Exponential Speedup [9.820545418277305]
  We completely overhaul the QTDA algorithm to achieve an improved exponential speedup depth complexity of $O(n4/(epsilon2 delta)). We present a theoretical error analysis, and the circuit and computational time and depth complexities for Betti number estimation.
  arXiv  Detail & Related papers  (2021-08-05T18:56:17Z)
• Quantum Gram-Schmidt Processes and Their Application to Efficient State Read-out for Quantum Algorithms [87.04438831673063]
  We present an efficient read-out protocol that yields the classical vector form of the generated state. Our protocol suits the case that the output state lies in the row space of the input matrix. One of our technical tools is an efficient quantum algorithm for performing the Gram-Schmidt orthonormal procedure.
  arXiv  Detail & Related papers  (2020-04-14T11:05:26Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.