An Efficient Decomposition of the Carleman Linearized Burgers’ Equation
Reuben Demirdjian, Thomas Hogancamp, Daniel Gunlycke · 2025
Read An Efficient Decomposition of the Carleman Linearized Burgers’ Equation by Reuben Demirdjian, Thomas Hogancamp, Daniel Gunlycke (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-00285.txt.
Introduction
Demirdjian, Hogancamp, and Gunlycke find an efficient way to load a classic fluid equation onto a quantum computer. The Burgers equation is a basic model of flow with shocks. It is nonlinear, and a trick called Carleman linearization turns it into an endless linear system. That system can then be cut to a finite size. Their 2025 paper embeds the cut system in a larger one built for quantum hardware.
The larger system's matrix splits into pieces whose count grows only slowly with the grid size. That slow growth is called polylogarithmic. Each piece can be encoded with a simple procedure. A test run with a variational quantum solver gave accurate answers. Gate counts in their estimate also grow slowly, which they present as a first for this kind of loading.
Catalog record
| CREATOR | Reuben Demirdjian, Thomas Hogancamp, Daniel Gunlycke |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 55 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-00285
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An Efficient Decomposition of the Carleman Linearized Burgers’ Equation Reuben Demirdjian, Thomas Hogancamp, Daniel Gunlycke Abstract Herein, we present a polylogarithmic decomposition method to load the matrix from the linearized 1-dimensional Burgers’ equation onto a quantum computer. First, we use the Carleman linearization method to map the nonlinear Burgers’ equation into an infinite linear system of equations, which is subsequently truncated to order α \alpha . This new finite linear system is then embedded into a larger system of equations with the key property that its matrix can be decomposed into a linear combination of 𝒪 ( log n t + α 2 log n x ) \mathcal{O}(\log n_{t}+\alpha^{2}\log n_{x}) terms, where n t n_{t} is the number of time steps and n x n_{x} is the number of spatial grid points. While the terms in this linear combination are not unitary, we have extended the methods of [ 1 ] to block encode them and apply the variational quantuam linear solver (VQLS) [ 2 ] routine to obtain a solution. Finally, a complexity analysis of the required VQLS circuits shows that the upper bound of the two-qubit gate depth among all of the block encoded matrices is 𝒪 ( α ( log n x ) 2 ) \mathcal{O}(\alpha(\log n_{x})^{2}) . \fancyhead \fancyfoot \fancyfoot [LE,RO]1 \fancyfoot [RE,LO]DISTRIBUTION STATEMENT A. Approved for public release: Distribution is unlimited. 1 Introduction Partial differential equations (PDEs) are ubiquitous in nearly all scientific and engineering disciplines, however, their solutions are rarely analytically known. Instead, PDEs are typically solved numerically using high performance computers along with discretization methods to find approximate solutions [ 3 , 4 , 5 ] . In computational fluid dynamics (CFD) and numerical weather prediction (NWP), the computational resources available can limit model accuracy by constraining the grid size of spatial and temporal discretizations [ 6 ] . A spatially coarse CFD or NWP model may be unable to resolve important small-scale features of the fluid (e.g. turbulence and convection) and instead rely on parameterization methods to approximate their effects, ultimately leading to error growth that can eventually corrupt the solution [ 7 , 8 , 9 ] . Therefore, an increase in computational resources enables finer spatial discretizations, which may allow for fewer or more accurate parameterizations and thereby a more accurate solution [ 10 ] . Quantum computing is an emerging field that can exponentially speedup specific applications [ 11 , 12 , 13 ] such as solving linear systems of equations [ 2 , 14 , 15 , 16 ] . Since CFD models rely on solving nonlinear PDEs, the Carleman linearization method has been proposed to transform the original set of nonlinear PDEs into an infinite set of linear ordinary differential equations (ODEs), which are subsequently truncated into a finite set of linear ODEs [ 17 , 18 , 19 ] . The advantage of this method is that a quantum linear system algorithm (QLSA) may be applied to solve the set of linear ODEs and thereby obtain an approximate solution to the original nonlinear PDE. However, there are a number of challenges that must be solved if this is to be done efficiently, and it is currently an open question whether this, or any other method of solving nonlinear PDEs, are viable on quantum computers [ 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 ] . One such challenge comes about from the VQLS method [ 2 ] – a variational technique used to solve linear systems of equations of the form L\vec{x}=\vec{b} where L\in\mathbb{C}^{N\times N} and \vec{x},\vec{b}\in\mathbb{C}^{N} . The VQLS method relies on the linear combination of unitaries [ 35 ] , whereby L=\sum_{l=0}^{N_{s}-1}c_{l}A_{l} for complex coefficients c_{l} and unitary matrices A_{l}\in\mathbb{C}^{N\times N} . While any square matrix L is guaranteed to have a decomposition of this form, the VQLS algorithm is only efficient if N_{s}=\mathcal{O}(\text{poly}(\text{log}\,N)) . This restriction comes from the fact that the number of circuits in the VQLS cost function scales like \mathcal{O}(N_{s}^{2}) [ 18 ] . This means that N_{s} must have a practical bound; otherwise, the quantum advantage is lost simply by executing the large number of circuits. Similarly, each A_{l} circuit depth must also be bounded by \mathcal{O}(\text{poly}(\text{log}\,N)) , otherwise quantum advantage is again lost when preparing the individual circuits. Henceforth, we refer to the problem of finding a decomposition such that both the number of circuits N_{s} and the A_{l} circuit depths (or a block encoding thereof) are both bounded by \mathcal{O}(\text{poly}(\text{log}\,N)) as the decomposition problem . This is related to the data loading problem, which is not generally efficient and therefore requires bespoke methods for each application [ 36 , 37 , 38 , 39 , 40 , 41 ] . 1.1 Contributions In this study, we solve the decomposition problem for the 1-dimensional (1D) Carleman linearized Burgers’ equation – a paradigmatic nonlinear PDE. Figure 1.1 illustrates the methods introduced here and contrasts them with the ones used in [ 17 , 18 ] . Both the previous and proposed methods follow the same two initial steps, first the 1D Burgers’ equation is discretized (box a) and then the Carleman linearization method is applied (box b). At this point, our approaches deviate. In the previous method, one would decompose the matrix A (box c) and then use a linear solver like VQLS to obtain a solution (box d). However, there are no known \text{poly}(\log\,N) decompositions for the basic Carleman linearized Burgers’ equation and therefore quantum advantage is lost. In contrast, the proposed method embeds the Carleman linearized 1D Burgers’ equation into an even larger system of equations with matrix A^{(e)} (box e). The benefit of this additional layer of complexity is that A^{(e)} can be efficiently decomposed into \text{poly}(\log\,N) terms (box f) that can be implemented in the VQLS algorithm using circuits with \text{poly}(\log\,N) depths (box g). The proposed method therefore offers a quantum advantage when used in combination with VQLS, or any other QLSA that requires a linear combination of unitaries (box d). Figure 1.1: An illustration comparing the method proposed in this study (boxes a,b,e,f,g,d) with the previous method (boxes a,b,c,d). (a) The spatially discretized 1D Burgers’ equation. (b) The truncated Carleman linearized 1D Burgers’ equation. (c) Decomposition of the Carleman linearized matrix A . Note that the time discretization step is skipped in this simplification. (d) A QLSA to solve the linear system. (e) The Carleman embedding method whereby the original system of equations A are embedded in a larger system A^{(e)} . (f) The matrix A^{(e)} is decomposed efficiently into \text{poly}(\log\,N) terms. (g) Each A_{l}^{(e)} matrix is block encoded with poly(\log\,N) circuit depth. The key insights presented in this paper are two-fold: (1) the creation of the Carleman embedding method that enables us to decompose the matrix into a polylogarithmic number of terms, and (2) an extension of the block encoding method, introduced in Gnanasekaran and Surana [ 1 ] , that enables us to efficiently block encode each term. Together, these two insights provide a polylogarithmic decomposition for the 1D Carleman linearized Burgers’ equation. It