Detailed assessment of calculating drag force with quantum computers: Explicit time-evolution precludes exponential advantage for nonlinear differential equations

arXiv:2406.06323 · quant-ph · Submitted 2024-06-10 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: We're looking at the paper: "Detailed assessment of calculating drag force with quantum computers".

Title and authors: Kai: So to recap, this paper is checking the potential for quantum computers to accelerate drag force calculations in fluid dynamics by using a specific quantum algorithm involving Carleman linearization of the lattice Boltzmann method. It’s not about solving everything exponentially faster, though.

Mira: Exactly. The title itself says "Explicit time-evolution precludes exponential advantage for nonlinear differential equations," which is a pretty strong statement that sets the stage for what we're going to discuss next.

Lev: I wonder what kind of speedup they actually found in their analysis, because I’ve seen those kinds of claims before where the math looks good on paper but the hardware requirements make it impossible.

Kai: Well, the paper does develop these block encodings for the lattice Boltzmann method matrices and a way to encode drag force amplitudes. They then apply this to a simplified problem: fluid flow past a sphere across different Reynolds numbers.

Mira: And what they found there is that when you look at those required quantum resources, which are quantified as logical qubits times T-gates, they estimate needing something in the range of one thousand twenty-one to one thousand thirty-nine.

Lev: That’s a pretty small number for a problem that could be massive in scale, so I'm curious about how that relates to the complexity of the actual simulation they are running.

Kai: It turns out that when they look at the scaling relationship, it doesn't show exponential quantum advantage over classical methods. Instead, the quantum resource scaling exhibits only modest polynomial scaling of O of Reynolds number to two hundred sixty-eight.

Mira: That’s a key point because it suggests that for this specific approach, you don't get that massive speedup we hoped for when using these nonlinear differential equations in an explicit way.

Lev: If the scaling is polynomial, even if the constant factor is small, it doesn't solve the fundamental problem of time stepping when dealing with those nonlinear terms and that Courant-Freidrichs-Lewy condition they mentioned earlier.

Kai: That limitation they pointed out is really interesting because it ties directly into how explicit methods handle nonlinear differential equations when you have a grid resolution issue.

The paper's summary: Mira: Let’s talk about the core findings presented in this paper, "Detailed assessment of calculating drag force with quantum computers: Explicit time-evolution precludes exponential advantage for nonlinear differential equations." Basically, they thoroughly assess whether these quantum algorithms can actually surpass classical limits for fluid dynamics simulations.

Kai: They base their analysis on a quantum algorithm that uses Carleman linearization of the lattice Boltzmann method, which is what they hypothesized would offer an exponential speedup in theory.

Lev: So you’re saying the theoretical setup looks promising, but the practical reality of running it on an explicit time evolution is what limits it? That’s where I want to focus my attention.

Mira: Right. They develop efficient block encodings for those lattice Boltzmann matrices and a method for amplitude-encoding drag force. They then test this on two main problem instances: fluid flow past a sphere at various Reynolds numbers and ship hull design problems.

Kai: For the sphere flow, they found the required quantum resources, measured in logical qubits times T-gates, range from one thousand twenty-one to one thousand thirty-nine. That's what they found for that specific test case.

Lev: And you mentioned the scaling issue again? What does that O of Reynolds number to two hundred sixty-eight scaling actually tell us about whether we can expect a real quantum advantage here?

Mira: It tells us that this polynomial scaling means there isn't an exponential advantage over classical methods for these specific problem instances, which is a significant finding given the goal.

Kai: They also quantify the utility by benchmarking these quantum performances against classical solvers, setting thresholds based on runtimes relative to current classical solvers.

Lev: So they aren't just saying "quantum can't do it," but they are giving us concrete numbers on how long it would take to get a useful result, which is helpful for figuring out the practical utility.

The paper's improvements: Kai: Now, let’s look at the improvements this paper suggests for their approach. The authors are developing functions like S, F1, F2, and F3 that they need to build those block encodings for the lattice Boltzmann matrices.

Mira: These functions map first-order monomials to matrix elements in the encoding process. They also have these specific functions like T0 of one T1 of one and T2 of one which extract coefficients for certain terms in the expansion <ref:2406.06323#pg1>.

Lev: From an error correction standpoint, I’m looking at how complicated those encodings get when you move to a larger lattice constant setup, because that affects the overall qubit count significantly.

Kai: They then define functions like F2 and F3 to return elements of the F2 and F3 matrices based on first-order and second-order monomials. These are all pieces needed for the Carleman matrix block encoding strategy.

Mira: The improvement they establish is through the decomposition of that Carleman matrix A into A equals S plus F1 plus F2 plus F3, which is how they manage the complexity of encoding it.

Lev: When you look at their theorem about constructing a circuit for a specific block encoding, it says you need n T qubits plus alpha and three times the ceiling of the logarithm base two of T. That’s a lot of overhead just to get that one type of encoding done.

Kai: They also establish bounds on the spectral norm of that Carleman matrix A, showing it stays between five hundred fifty-nine and one thousand seventy-two, depending on a parameter tau being zero point six.

Mira: Those bounds are important because they feed directly into the qubit requirements they calculate for the T level truncation Carleman matrix. It shows how much size those matrices can grow before you run out of resources.

Conclusion: Kai: So, wrapping up this discussion on "Detailed assessment of calculating drag force with quantum computers: Explicit time-evolution precludes exponential advantage for nonlinear differential equations," the main point is that explicit time evolution limits the potential for exponential speedup here.

Mira: They show that while they can develop these tools, the scaling ends up being polynomial, specifically O of Reynolds number to two hundred sixty-eight which doesn't beat classical methods exponentially.

Lev: From a hardware perspective, that means we aren't looking at a near-term quantum advantage for this specific problem setup unless we fundamentally change how we handle those explicit time steps.

Kai: They also give us some utility estimates, showing that achieving accuracy comparable to current classical solvers might only pay off in the range of one thousand seven dollars to ten thousand dollars for all incompressible computational fluid dynamics applications.

Mira: That high resource estimate, suggesting runtimes on the order of hundreds of thousands of years even for simple problems, really puts things into perspective regarding economic benefit.

Lev: I just want to reiterate that their own limitation is that they are dealing with explicit methods, and they suggest either a new algorithm or restricting applications where the time steps don't depend polynomially on the number of grid points.

Kai: That’s the takeaway for now: quantum algorithms are not providing transformative utility in explicitly time-evolving fluids right now, but this kind of analysis helps us know where to look for better algorithmic improvements.

Mira: So we’ve seen how they quantify the resources needed and what those numbers mean when you compare them to classical runtimes.

Lev: That’s all on this paper for now, showing the limits of explicit quantum methods in this domain.

John Penuel, Amara Katabarwa, Peter D. Johnson, Parker Kuklinski, Benjamin Rempfer, Collin Farquhar, *Yudong Cao*, *Michael C. Garrett

L3Harris Technologies, Inc. · Georgia Tech Research Institute. · Zapata AI · MIT Lincoln Laboratory. · Boston Consulting Group

quant-ph

Submitted: 2024-06-10

Updated: 2026-11-18

Comments: Version 4: 93 pages, conclusions unchanged, improvements to streaming, acknowledgement of other contemporary work

Code: https://github.com/isi-usc-edu/qsub

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

The gist: This study investigates the feasibility of using fault-tolerant quantum computers to accelerate fluid dynamics simulations, specifically focusing on calculating drag force for ship hull design.

Key concepts

Lattice Boltzmann Method (LBM)
A computational method used to simulate fluid flow by modeling the behavior of particles on a discrete grid. It is often used in fluid dynamics simulations because it handles complex geometries and boundary conditions well, making it suitable for calculating forces like drag.
Carleman Linearization
A mathematical technique applied to the LBM equations that transforms them into a form suitable for quantum algorithms. This linearization is necessary to apply quantum speedup techniques, but its effectiveness is constrained by the underlying physics of explicit time-stepping methods.
Reynolds Number ($ ext{Re}$)
A dimensionless number used in fluid dynamics to characterize the flow regime, representing the ratio of inertial forces to viscous forces. The study found that the required quantum resources scale polynomially with $ ext{Re}$, specifically $O( ext{Re}^{268})$, which limits its practical advantage.
CFL Condition
A stability criterion in explicit numerical methods, requiring that the time step size is small enough relative to the spatial grid size and flow speed. This condition forces a polynomial dependence of time steps on grid points, negating potential exponential quantum advantages for explicit simulations.

Terminology

Summary

This study investigates the feasibility of using fault-tolerant quantum computers to accelerate fluid dynamics simulations, specifically focusing on calculating drag force for ship hull design. p. 0 The approach leverages a quantum algorithm based on Carleman linearization of the Lattice Boltzmann Method (LBM), which is hypothesized to offer an exponential speedup. p. 0

The research details the development of efficient block encodings for LBM matrices and a method for amplitude-encoding drag force. p. 0 When applied to the simplified problem of fluid flow past a sphere across various Reynolds numbers (Re), the required quantum resources, quantified as (logical qubits) times (T-gates), are estimated to range from 1021 to 1039. p. 0 However, a critical finding is that the quantum resource scaling exhibits only modest polynomial scaling of O(Re 268), which indicates no exponential quantum advantage over classical methods. p. 0 This limitation is attributed to an inherent power-law relationship between spatial grid resolution and time-stepping requirements in explicit methods for nonlinear differential equations, necessitated by the Courant-Freidrichs-Lewy (CFL) condition. p. 0

The paper further quantifies utility by benchmarking quantum performance against classical solvers, establishing incremental and transformative utility thresholds based on runtimes relative to current classical solvers. p. 8 For flow-past-a-sphere problem instances, the estimated quantum resources span from 10 15 to 10 18 T-gate counts and thousands to hundreds of thousands of logical qubits. p. 0 The relationship between these resource estimates and the Reynolds number confirms a power-law scaling, O(Re 268), rather than an exponential advantage. p. 4

The conclusion drawn is that current quantum algorithms are unlikely to provide significant utility in explicitly time-evolving fluids or other systems involving nonlinear differential equations, suggesting either the need for fundamental algorithmic improvements or restricting applications to scenarios where the number of time steps does not polynomially depend on the number of spatial grid points. p. 5 The study estimates that achieving a transformational utility threshold—defined as DNS-level accuracy at runtimes comparable to current classical RANS solvers—could yield economic benefits in the range of 10 7 to 10 8 dollars, with a weak upper bound approaching about 10 10 for all incompressible CFD applications. p. 8 The high resource estimates suggest that even for geometrically simple problems, the required runtime could be on the order of hundreds of thousands of years. p. 4

The technical derivation involves developing functions (S tilde, F tilde 1, F tilde 2, F tilde 3) necessary for block encoding. p. 2 The LBM dynamics are approximated by expanding the time derivative, leading to terms involving S f, F 1f, F 2f times squared, and F 3f times cubed. p. 0 The functions S tilde map first-order monomials to matrix elements, while T tilde 0[1], T tilde 1[1], and T tilde 2[1] extract coefficients for specific terms. p. 1 Functions like F tilde 2 and F tilde 3 are defined to return elements of the F 2 and F 3 matrices, respectively, based on first-order and second-order monomials.

The Carleman matrix block encoding is established through the decomposition of the Carleman matrix A = A tilde 1 + A tilde 2 + A tilde 3. p. 2 A theorem proves that given a set of block encodings F bar r, one can construct a circuit requiring n T + a + 3 2(T) + 2 D qubits to achieve a D T(T+1) beta squared, a + 2 2(T), D T(T+1) beta epsilon squared-block encoding of the T-level truncation Carleman matrix. p. 0 For the specific D3Q27 lattice constants, spectral norm bounds on the Carleman matrix A are established between 559 and 1072, with a bound of at most 901 when tau=0. p. 26, which is used for quantum resource estimates. p. 0 The total number of qubits required is T n + r n + 3 m + 2(T-r+1). p. 0

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Improved AI system can quantify return on investment for quantum processing units by providing estimated logical qubits and T-gate counts required to solve specific computational fluid dynamics problems, helping investors determine if funding is worthwhile.

  2. The system can assess the potential utility of fault-tolerant quantum computers in incompressible CFD by generating quantum resource estimates (QREs) in terms of logical qubits and T-gate counts for a given Reynolds number, showing the scaling relationship O(Re2.68) against classical O(Re3).

  3. The improved system can perform comparative benchmarking between classical and quantum solvers for fluid dynamics by estimating wall-clock runtimes on engineering grade laptops for specific problem instances, establishing utility thresholds that a QPU must surpass to provide transformative economic benefit or return on investment.

  4. It can identify applications where quantum advantage is unlikely by demonstrating that the predicted polylogarithmic scaling of query complexity is negated if the evolution time T has an implicit polynomial dependence on the number of spatial grid nodes n, due to the CFL condition and diffusive scaling in explicit methods.

  5. The system can estimate cost implications for current and near-future CFD platforms by providing order-of-magnitude estimates for software/compute market utility (around 10M–100M) and engineering services market utility (up to 100B), which serve as benchmarks against the transformational utility threshold.

Sources

Related papers