Explicit near-optimal quantum algorithm for solving the advection-diffusion equation

I. Novikau, I. Joseph · 2025

Read Explicit near-optimal quantum algorithm for solving the advection-diffusion equation by I. Novikau, I. Joseph (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-2501-11146.txt.

Introduction

Ivan Novikau and Ilon Joseph make a quantum algorithm for fading systems practical to build. Many equations of physics and engineering, including the advection-diffusion equation named in the catalog record, describe quantities that spread and decay, and quantum circuits natively do the opposite of decay. Their 2025 paper implements a method that writes the fading evolution as a weighted sum of ordinary, non-fading evolutions, then encodes that sum into a circuit far more cheaply than earlier attempts.

A change of variables turns the sum's index into a wave-like function, so a single circuit performs an exponential number of component runs at once. Error analysis shows better efficiency than rival encodings, and the selector cost grows slowly with the number of terms. Tests on an emulator of a fault-tolerant machine, solving the advection-diffusion equation itself, confirm the circuit works and scales as the mathematics promises.

Catalog record

CREATORI. Novikau, I. Joseph
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE28 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-11146

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Explicit near-optimal quantum algorithm for solving the advection-diffusion equation Preprint: AIP/123-QED I. Novikau, I. Joseph Abstract An explicit near-optimal quantum algorithm is proposed for modeling dissipative initial-value problems. This method, based on the Linear Combination of Hamiltonian Simulations (LCHS), approximates a target nonunitary operator as a weighted sum of Hamiltonian evolutions, thereby emulating a dissipative problem by mixing various time scales. We propose an efficient encoding of this algorithm into a quantum circuit based on a simple coordinate transformation that turns the dependence on the summation index into a trigonometric function and significantly simplifies block-encoding. The resulting circuit has high success probability and scales logarithmically with the number of terms in the LCHS sum and linearly with time. We verify the quantum circuit and its scaling by simulating it on a digital emulator of fault-tolerant quantum computers and, as a test problem, solve the advection-diffusion equation. The proposed algorithm can be used for modeling a wide class of nonunitary initial-value problems including the Liouville equation and linear embeddings of nonlinear systems. I Introduction Precise modeling of complex dynamics characterized by multiple scales in space and time needs high spatial resolution. As a result, accurate simulations of many classical problems of practical interest require large amounts of numerical resources. This significantly limits the number of problems that can be simulated on classical computers, and it seems suitable to consider quantum computers (QCs) as possible candidates for modeling these sorts of problems. By leveraging quantum effects such as entanglement and superposition of quantum states, QCs can process exponentially many complex numbers in parallel. Moreover, in advanced quantum algorithms for solving differential equations, the number of operations grows polynomially or even exponentially more slowly than in the corresponding classical methods. Yet, quantum computers can operate only with linear unitary operators that makes quantum simulations of dissipative problems challenging. To solve dissipative differential equations, one can transform them into a system of linear equations Krovi23 M\psi=b with a dilated matrix M . The scaling of the matrix condition number \kappa_{M} on the integration time depends on the Courant-Friedrichs-Lewy convergence condition and, for instance, is quadratic for the advection-diffusion or heat equations, Linden22 which have second-order spatial derivatives. The linear system can be solved by advanced quantum linear system algorithms such as those based on variable-time amplitude amplification Ambainis12 ; Childs17 ; Chakraborty19 or discrete adiabatic theorem, An22QLSA-adiab ; Costa21 whose query complexity is linear with the condition number. More precisely, the number of calls to the oracle encoding M and to the oracle encoding the right-hand-side vector b is linear with \kappa_{M} . Another option is to use the time-marching method, Fang23 whose success probability is maintained by using a combination of the uniform singular value amplification and compression gadgets. Generally, this algorithm scales quadratically with the simulated time. In Ref. Over24 , it was shown how to solve the advection-diffusion equation with the time-marching technique having linear complexity with time and high success probability. However, it is not clear whether this method would preserve the near-optimal scaling if the normalized advection-like component of the time-marching matrix cannot be block-encoded keeping the spectral norm of the encoded matrix equal to one. One can also use hybrid classical-quantum methods for solving dissipative problems on quantum computers as proposed, for instance, in Ref. Demirdjian22 ; Ingelmann24 . Yet, the hybrid methods usually suffer from the bottleneck related to the repetitive input/output (I/O) data transfer between classical and quantum processors. An alternative approach is based on recasting a nonunitary operator associated with dissipative dynamics into a combination of unitary evolution operators integrated over some additional Fourier space. This technique was initially proposed in Refs. Jin22Sch ; Jin23Sch ; Hu24Sch ; Lu24 ; An23 and is called “Schrödingerization” or Linear Combination of Hamiltonian Simulations (LCHS). The explicit implementation of the LCHS circuit and its numerical emulation was given in Ref. Novikau24KvN . Recently, the LCHS algorithm An23impr was advanced by exponentially improving its query complexity with respect to the truncation error \varepsilon_{\rm LCHS} . In this work, we propose an explicit quantum circuit of the improved LCHS method characterized by linear query complexity with the integration time t and logarithmic complexity with the truncation error \varepsilon_{\rm LCHS} . We simulate the LCHS circuit on a digital emulator of fault-tolerant quantum computers and verify the circuit by modeling the advection-diffusion equation. In these simulations, we demonstrate the near-optimal scaling of the improved LCHS algorithm and its high success probability. This paper is organized as follows. In Sec. II.1 , we review the LCHS method with an improved kernel and explain in detail how this algorithm can be mapped on a quantum circuit. In Sec. III , we test the LCHS circuit by modeling the advection-diffusion equation and analyze the algorithm scaling, precision, and the circuit success probability. In Sec. IV , we summarize the main results of this paper. II Improved Linear Combination of Hamiltonian Simulations (LCHS) II.1 Overview Figure 1: Plots showing the real (a) and imaginary (b) components of the LCHS weights for the special case ( 6 ) (black line) and the improved kernel ( 5 ) with various \beta (colored lines). (c): Absolute values of the LCHS weights. We consider a linear differential equation with a non-Hermitian time-independent generator A \partial_{t}\psi(t,x)=-A\psi(t,x). (1) Here, the evolution in time of the variable \psi(t,x) is described by the nonunitary operator e^{-At} : \psi(t,x)=e^{-At}\psi(0,x), (2) where \psi(0,x) encodes initial conditions. The initial-value problem ( 2 ) can be solved by LCHS An23 ; An23impr which represents the nonunitary operator e^{-At} as a weighted superposition of Hamiltonian evolutions integrated over additional Fourier space \displaystyle e^{-At}=\int_{\mathbb{R}}\frac{\xi(k)}{1-\mathrm{i}k}e^{-\mathrm{i}(A_{H}+kA_{L})t}\mathop{}\!\mathrm{d}k, (3) where the original generator A has been separated into Hermitian matrices \displaystyle A=A_{L}+\mathrm{i}A_{H}, (4a) \displaystyle A_{L}=(A+A^{\dagger})/2, (4b) \displaystyle A_{H}=(A-A^{\dagger})/(2\mathrm{i}). (4c) Equation ( 3 ) is valid as long as A_{L} is positive semi-definite. The kernel \xi(k) has the following form: An23impr \xi(k)=\frac{1}{2\pi e^{-2^{\beta}}\exp\left([1+\mathrm{i}k]^{\beta}\right)}, (5) with the real scalar \beta\in(0,1) . The LCHS algorithm with the special case of the kernel \xi(k) equal to \xi_{\rm sp}(k)=\frac{1}{\pi(1+\mathrm{i}k)} (6) was numerically tested in Ref. Novikau24KvN . It corresponds to the original LCHS method described in Ref. An23 and is equivalent to the Schrödingerization algorithm. Jin24 To efficiently map the LCHS equation ( 3 ) onto a quantum circuit, it is beneficial to apply the following coordinate transformation: Novikau24KvN \displaystyle k=k_{\rm max}\sin(\theta). (7) This allows one to recast the dependence on the Fourier coordinate k as a trigonometric function, \sin(\theta) , which is easy to block-encode. The LCHS computation ( 3 ) of the nonunitary operator e^{-At} is exact when one works in infinite Fourier space. Yet, to simulate Eq. ( 2 ) numerically, one must truncate Fourier space, i.e. by imposing |k|<k_{\rm max} and by discretizing the space with a grid with N_{k}=2^{n_{k}} points. In this case, the transformation ( 7 ) becomes \displaystyle k_{j}=k_{\rm max}\sin(\theta_{j}), (8) where the discretized angle \theta_{j} is \theta_{j}=-\frac{\pi}{2}+j\Delta\theta,\quad\Delta\theta=\frac{\pi}{N_{k}-1},\quad j=0,1,\dots N_{k}-1. (9) After the truncation of the Fourier space, one obtains a discretized version of the initial-value problem ( 2 ), \psi(t,x)=U_{\rm LCHS}\psi(0,x)+\varepsilon_{\rm LCHS}, (10) where \varepsilon_{\rm LCHS} is the truncation error. The discretized LCHS operator U_{\rm LCHS} approximates the nonunitary operator e^{-At} as e^{-At}\approx U_{\rm LCHS}=\sum_{j=0}^{N_{k}-1}w_{j}V_{j}(t), (11) where each unitary V_{j}

Read the complete text