Adaptive Lattice Gas Algorithm: Classical and Quantum implementations

Niccolò Fonio, Pierre Sagaut, Ljubomir Budinski, Valtteri Lahtinen · 2025

Read Adaptive Lattice Gas Algorithm: Classical and Quantum implementations by Niccolò Fonio, Pierre Sagaut, Ljubomir Budinski, Valtteri Lahtinen (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-2504-13549.txt.

Introduction

Fonio, Sagaut, Budinski, and Lahtinen present an adaptive lattice gas algorithm in a 2025 paper, with both classical and quantum versions. Lattice gas methods are used to simulate nonlinear systems. They include cellular automata and the lattice Boltzmann method.

Starting from a one-dimensional integer lattice gas, the authors carry out only a fraction of the possible collisions. Those fractions are adapted so results match the lattice Boltzmann method. They then build a quantum version with a linear collision operator. It uses measurement and reinitialization steps. The paper notes cases where many time steps can be run. The work links a classic simulation family to quantum computing.

Catalog record

CREATORNiccolò Fonio, Pierre Sagaut, Ljubomir Budinski, Valtteri Lahtinen
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE41 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-13549

Browse the full library · About the Tower of Babel

Full text

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

Adaptive Lattice Gas Algorithm: Classical and Quantum implementations Niccolò Fonio, Pierre Sagaut, Ljubomir Budinski, Valtteri Lahtinen Abstract Lattice gas algorithms (LGA) are a class of algorithms including, in chronological order, binary lattice gas cellular automata (LGCA), integer lattice gas algorithms (ILGA) and lattice Boltzmann method (LBM). They are largely used for simulating non-linear systems. Starting from 1-dimensional ILGA, we design an algorithm where we carry out a fraction of the possible collisions. These fractions are then adapted to reproduce LBM equilibrium distributions, resulting in an adaptive lattice gas algorithm (ALGA) that achieves the same simulation results of LBM. Considering this, we develop a quantum algorithm that involves a linear collision operator and capable of simulating the same phenomena, while still using a measurement and reinitialization procedure. I Introduction Lattice gas algorithms (LGA) include many numerical schemes mostly applied to simulating non-linear phenomena. They represent the evolution of a gas in discrete time-space using two steps: collision and streaming. The components of the system interact according to some conservation laws at each lattice point during the collision, changing their dynamical state. After the interaction, they are streamed according to their velocities. The components of a LGA can be microscopic particles, as in a lattice gas cellular automata (LGCA) Rivet and Boon 2001 ; Wolf-Gladrow 2004 ; Frisch et al. 2019 , or mesoscopic probability density functions (PDF) as in the case of lattice Boltzman method (LBM) Kruger 2016 ; Mohamad 2011 . LGA being among the most used computational fluid dynamics (CFD) methods, an advantage in their quantum computing (QC) implementation is being investigated closely in the developing field of quantum computational fluid dynamics (QCFD) Bharadwaj and Sreenivasan 2020 . Specifically, quantum LGCA Yepez 1998 ; Yepez 2001a ; Yepez 2001b ; Fonio et al. 2023 ; Zamora et al. 2025 and quantum LBM Budinski 2021 ; Ljubomir 2022 ; Itani and Succi 2022 ; Itani et al. 2024 ; Sanavio and Succi 2023 ; Sanavio and Succi 2024 have attracted significant interest. The most recent quantum LGA methods aim to achieve a quantum advantage using \log(N) qubits for representing N cells, carrying out O(T\log N) operations where T is the number of time steps. Such an algorithm is usually addressed as multi-time-step algorithm. This advantageous algorithm, at the current state of the art, is hindered by the necessity of measurement and reinitialization in QLBM or by some fundamental properties for QLGCA Schalkers and Möller 2024 ; Fonio et al. 2023 . Thus, we are going to explore novel possibilities for QLGA. In this sense, it is worth developing new classical methods capable of simulating non-linearities, but with features that admit an advantageous quantum implementation. We call these classical methods quantum-friendly . Thus, we are interested in the linearity/unitarity of the collision in LGCA, but also in the simulation advantages deriving from the equilibrium update rule in LBM. Considering this, the key to achieving a quantum advantage could be found in a model that is between LGCA and LBM. If we look at the history of LGA, the transient between these two methods was fulfilled by integer lattice gas algorithms (ILGA) where the exclusion principle of the LGCA is no longer applied Boghosian et al. 1997 ; Chopard et al. 1998 ; Masselot and Chopard 1998 . The most recent works Blommel and Wagner 2018 ; Wagner and Strand 2016 achieved LBM equilibrium distributions, Poisson fluctuations and over-relaxation Strand and Wagner 2022 with Monte Carlo lattice gas automata (MCLGA). It is promising, then, to start from MCLGA for a quantum friendly classical model, modifying the features that hinder quantum advantage. In this regard, the random extractions used in MCLGA have no clear counterparts in advantageous quantum algorithmic procedures for QLGA. Thus, instead of these, we carry out a fixed or equilibrium-adapted fraction of the possible collisions, retrieving non-linearities. This, together with a novel quantum encoding of the lattice, allows us to linearize the collision operator simplifying the quantum collision process. We will show that our model produces the same equilibrium distribution functions and the same simulation results as LBM in the |u|\approx 0 limit, where u is the momentum density. The effectiveness of our model to reproduce LBM behavior is demonstrated with the simulation of a cosine-wave, that in the quantum version uses \log(N)+3 qubits for representing N cells. The complexity of one evolution step is the complexity of the streaming step adopted Shakeel 2020 O(\log^{2}N) , while the collision is a linear combination of unitaries (LCU), giving a cost of O(1) for the 1d case studied. Thus, the one-time-step complexity results in O(\log^{2}N) , showing an exponential speed-up compared to the classical case. Considering the total evolution, the current implementation carries out measurements and reinitialization after each time step, increasing the total complexity by the cost of tomography and reinitialization. Initialization and tomography are open problems on their own, thus we will not deal with them in detail here, assuming for the simulations a perfect tomography, allowing for a correct reinitialization The paper is structured as follows: in Sec. II we give an introduction to LGA, specifically to the procedures from LGCA, ILGA and LBM adopted; in Sec. III we formulate the novel standard and adaptive ILGA; in Sec. IV we develop the QC encoding and algorithm for simulating the ILGA we propose; in Sec. V we furnish the numerical results of the simulations, validating the expected equilibrium distribution functions and carrying out the simulation of a cosine-wave as the non-linear benchmark case. II Classical lattice gas algorithms II.1 Lattice gas cellular automata In LGCA we have a lattice where each site (or cell ), is populated by particles. These particles can have a finite set of v possible velocities, giving conventionally the name to D n Q v models where n is the number of dimensions. It holds an exclusion principle , such that there can be a maximum of one particle per site per velocity. Thus, each cell is represented by a bit string [b_{0},b_{1},\dots,b_{v}] where b_{i} is associated to the presence (1) or absence (0) of a particle with velocity v_{i} . The evolution is given by a collision step when particles at the same site interact, and a streaming step, when particles diffuse according to their velocity. An example is represented in Fig. 1 [101] [001] [010] [100] [011] [010] [010] [001] [101] [100] [011] [101] [011] [100] [101] [001] [110] [001] x 0 1 2 3 4 5 Before collision After collision After streaming Figure 1: Lattice gas Cellular Automata example of evolution for 1-dimensional model with 3 velocities named D1Q3. Each cell consists of 3 bits [b_{2}b_{1}b_{0}] , representing the presence of particles with corresponding velocities [-1,0,1] . The collision that preserves mass and momentum (considering a rest particle with mass 2) is [101]\leftrightarrow[010] , taking place at x=0,2,5 . All the other cells are not affected by the collision. The streaming takes place according to respective velocities with periodic boundary conditions. According to this evolution, we can write an update rule for the mean occupation numbers B_{i}(x,t)=\langle b_{i}\rangle calculated on neighbors of x , that is B_{i}(x+c_{i}\Delta t,t+\Delta t)=B_{i}(x,t)+\Delta_{i}, (1) where \Delta_{i} is the collision term. An H-theorem guarantees the thermalization of the

Read the complete text