1 Introduction

Quantum computing has drawn a lot of attention in the last few years. Twenty years following the foundations of quantum computing have been established by discovery of Grover search algorithm [1], phase (eigenvalue) estimation algorithm [2], quantum Fourier transformation [3] and Shor’s algorithm for integer factorization [4], entirely new researcher areas that can benefit from quantum computation emerged thanks to the quantum computing simulators and processors introduced by companies like IBM, Rigetti and Microsoft. Available through the cloud services, these quantum processors stimulated researchers and computational enthusiast of various fields of interest to work on developing new quantum procedures and techniques which can be applied on quantum devices. New quantum algorithms were discovered, yielding potential quantum speed-up and applications in various fields of science such as linear algebra [5,6,7,8,9], quantum chemistry [10], optimization [11, 12] or machine learning [13,14,15]. However, the currently available quantum devices are error-prone mostly due to the noise produced by the fact that the physical and natural systems do not exist in isolation (Noisy Intermediate-Scale Quantum devices—NISQ). As a consequence, the concept of variational quantum computing (VQC), where the evaluation of the cost function is delegated to a quantum computer while the optimization of variational parameters is performed on a conventional classical computer, attracted considerable interest. While the VQC is proven to be most suitable for machine learning [16,17,18,19] and chemistry [10, 20], significant research has been done in the area of linear algebra [21, 22] and optimization [23,24,25] as well.

From engineering perspective, complex processes involving time-space dynamics are described mainly by the differential equations (DE). Generally, solving differential equations by classical computers is a hard problem, in particular when the size of the configuration space is large (fluid dynamics). A possible way to overcome the above difficulty is to utilize quantum computing. In case of inhomogeneous linear differential equations, Berry [26] and Childs et al. [27] first formed a system of linear equations by discretizing the differential equation using the finite difference method (FDM), which then are solved by applying the quantum algorithm to the linear systems of equations. Examples of this approach for the Vlasov equation are presented by Costa et al. [28], while in case of Poisson equation Cao et al. [29] and Wang et al. [30] applied HHL [5] algorithm for solving system of linear equations. Another approach, where the Taylor expansion of the analytical solution of the linear differential equations (LDE) is described by the quantum states and the corresponding operators, is firstly proposed by the Berry et al. [31], while application on 4-dimensional LDE with a 4\( \times \)4 non-unitary matrix is done by Xin et al. [32]. On the other hand, since most of the differential equations used for describing the physical phenomena are essentially nonlinear (Navier–Stokes equations), first attempt to solve systems of nonlinear differential equations, whose nonlinear terms are polynomials, was investigated by Leyton and Osborne [33]. However, since quantum mechanics is represented by linear operators where the time evolution of the quantum state vector is described by the linear differential equation, the presented algorithm turns out to be too ambitious, i.e., it is possible to obtain an algorithm that is far more efficient than the proposed one. This highlights very important fact where the linearity of the quantum state propagation is a perquisite for developing the quantumly efficient algorithm.

Quantum algorithm for solving the advection–diffusion equation is presented in this work. Since the ADE is actually partial differential equation used to describe transport phenomena in time-space domain, the solution of this kind of equation is, in general obtained by using some of the traditional methods from the numerical analysis (FDM). However, in this paper, the lattice Boltzmann method (LBM) as a numerical technique for an indirect solution of flow equations through a microscopic approach to a macroscopic phenomenon [34,35,36,37] is utilized. The main reason for using this implicit numerical procedure over previously mentioned FDM lies primarily in its simple mathematical structure, where it consists of simple arithmetic calculations of only one single variable, the microscopic distribution function. It is suitable for flows in complex geometry such as flows through porous media for the straightforward implementation of the boundary conditions providing an opportunity for easy simulation of complex flows. The first attempt to solve the processes of fluid dynamics by quantum computing was made by Yepez [38], Berman et al. [39] and Micci and Yepez [40], and mainly involves lattice-gas models and type II quantum computers. Type II machines consist of a number of small type I quantum computers (‘pure’ quantum computers called nodes) with as few as two qubits in each, connected by classical communications channels carrying bits instead of qubits [41]. However, it is known that lattice-gas model suffers from various problems, like non-isotropic advection, violation of Galilei invariance, and noise due to the usage of Boolean variables. Hence, most recent work on solving the collisionless Boltzmann equation is performed by N.Todorova and Steijl [42], where the quantum circuit implementations for the advection step as a quantum walk process are presented. The most recent attempt to derive quantum algorithm for one-dimensional Navier–Stokes equations by applying quantum amplitude estimation algorithm (QAEA) for solving ordinary differential equations (ODEs) is done by Gaitan [43]. However, it is not clear from the paper how this approach can be further extended to the two- and three-dimensional space and at what cost.

In this work, a quantum algorithm for transport phenomena (ADE) utilizing the complete lattice Boltzmann equation is presented. The non-unitary collision operator is solved by using the standard-form encoding approach [44], while the quantum walk is used for the propagation step. The quantum circuit for the collision and propagation operator is constructed from multiple controlled-NOT gates, as well as single qubit X and \( R_z \) gates, and two-qubit SWAP gate. The constructed algorithm is implemented on IBM’s open-source quantum computing software development framework Qiskit [45] and it is tested for the case of unsteady one-dimensional and two-dimensional heat transport. The main contribution of the present work is a quantum algorithm simulating the transport phenomena, solving the full lattice Boltzmann equation, i.e., both the collision and propagation step. Besides the re-normalization of the post-selected state vector preformed at the end of each time step, the entire computation within a particular time step is performed solely on the quantum processor. Furthermore, to be suitable for different mesh sizes, the scalability of the presented algorithm is also elaborated. To the best of the author’s knowledge, the presented quantum algorithm is the very first algorithm related to fluid dynamics that solves the full lattice Boltzmann equation, which is also tested on the actual platform for quantum computation.

2 Mathematical formulation

2.1 The advection and diffusion equation

The advection–diffusion process is a process where both advection and diffusion take place simultaneously, and both phenomena are governed by the advection–diffusion equation,

$$\begin{aligned} \frac{\partial \phi }{\partial t}+\frac{\partial \left( u_i \phi \right) }{\partial x_i}=\frac{\partial }{\partial x_i}\left( D\frac{\partial \phi }{\partial x_i}\right) , \end{aligned}$$
(1)

where \( \phi \) is the depended variable (mass, momentum, energy, species, etc.), t is time, \( x_i \) is a Cartesian coordinate, \( u_i \) is the fluid velocity in the i-direction and D is the diffusion coefficient. The above equation is valid for general advection and diffusion phenomena, including both steady and unsteady situations.

2.2 The lattice Boltzmann method

The single relaxation time lattice Boltzmann equation [46] is formulated as

$$\begin{aligned} f_\alpha (\mathbf {x}+\mathbf{e} _\alpha \Delta t,t+\Delta t)=\left( 1-\omega \right) f_\alpha (\mathbf {x},t) +\omega f^{eq} _\alpha , \end{aligned}$$
(2)

where \(f_\alpha \) is the particle distribution function along the \(\alpha \) link, \(f^{eq} _\alpha \) is the local equilibrium distribution function, \( \mathbf {e}_\alpha \) is the particle velocity vector, \( \mathbf {x} \) is the space vector defined by Cartesian coordinates, t is time, \(\Delta t\) is the time step and \( \omega \)=\( \Delta t \)/\(\tau \), where \(\tau \) is the single relaxation time. Depending on the spatial dimensions being used, \( \mathbf {x} \) is the space vector defined by Cartesian coordinates, i.e., \( \mathbf {x}=\left( x\right) \) for one-dimensional space and \( \mathbf {x}=\left( x,y\right) \) in two-dimensional space.

In this paper, two spatial lattice models for advection–diffusion equation have been considered. First, a 1D model with the D1Q2 configuration (in DnQm classification Dn stands for n dimensions, while Qm stands for m speeds) is used (Fig. 1). This arrangement uses just two velocity vectors, \( e_1=-e_2=\Delta x/\Delta t \) for distribution functions \( f_1 \) and \( f_2 \), respectively, streaming along the links in opposite directions. Equality between two velocity vectors is imposed by the symmetry of the LBM. Furthermore, the crucial part of the lattice Boltzmann method is the local equilibrium distribution function [37], which is for advection–diffusion equation defined as

$$\begin{aligned} f_{\alpha }^{eq}\left( \mathbf {x},t\right) =w_\alpha \phi \left( \mathbf {x},t\right) \left( 1+\frac{e_\alpha \cdot \overrightarrow{u}}{c_s^2}\right) , \end{aligned}$$
(3)

where \( \overrightarrow{u} \) is the advection velocity vector, \( c_s \) is the speed of sound and \( w_\alpha \) is the weighting factor in the direction \( \alpha \). In case of a one-dimensional D1Q2 scheme, the weighting factors are \( w_{1,2}=0.5 \), while for the speed of sound \( c_s=1 \) is used.

For the two-dimensional problem, the D2Q5 scheme with rest particle is utilized (Fig. 2). This model consists of four velocity vectors and a rest particle, defined as

$$\begin{aligned} \displaystyle e_\alpha =\left\{ \begin{array}{ll}\displaystyle (0,0),&{}\alpha =0\\ \\ \displaystyle \left( \pm e_x,0\right) ,&{}\alpha =1,2\\ \\ \displaystyle \left( 0,\pm e_y \right) ,&{}\alpha =3,4 \end{array}\right. \end{aligned}$$
(4)

where \( e_x=e_y=\Delta x(y)/\Delta t \). Furthermore, the equilibrium distribution function is solved by using Eq. (3), while the corresponding weight coefficients and the speed of sound are set to \( w_0=2/6 \), \( w_{1,2,3,4}=1/6 \) and \( c_s=1/\sqrt{3} \), respectively. The advection velocity vector for 2D case is \( \overrightarrow{u}=ui+vj \), where i and j are unit vectors along x and y direction. It should be noted that following the work of Zhou [47] parameter \( \omega \) is set to 1.0 in both cases.

The solution procedure for the LBM, in general, consists of two major steps, collision and streaming. In the collision step, relaxation to local equilibrium is performed only

$$\begin{aligned} \hat{f}_\alpha (\mathbf {x},t)=\left( 1-\omega \right) f_\alpha (\mathbf {x},t) +\omega f^{eq} _\alpha , \end{aligned}$$
(5)

while in the streaming step propagation of the relaxed distribution functions \( f_\alpha \) along the links \( \alpha \) is conducted as

$$\begin{aligned} {f}_\alpha (\mathbf {x}+\mathbf{e} _\alpha \Delta t,t+\Delta t)=\hat{f}_\alpha (\mathbf {x},t). \end{aligned}$$
(6)

The macroscopic variable \( \phi \left( \mathbf {x},t\right) \) at the end of each time step is calculated as the zero-order discrete moment of the particle distribution function \( f_\alpha \) as

$$\begin{aligned} \phi \left( \mathbf {x},t\right) =\sum _{\alpha } f_\alpha \left( \mathbf {x},t\right) . \end{aligned}$$
(7)

The recovery of the advection–diffusion equation Eq. (1) by applying the Chapman–Enskog expansion procedure can be found in [37].

Fig. 1
figure 1

D1Q2 lattice configuration

Full size image
Fig. 2
figure 2

D2Q5 lattice configuration

Full size image

3 The quantum algorithm

3.1 The D1Q2 model

The entire procedure of establishing the quantum algorithm for D1Q2 lattice Boltzmann model can be divided into four major steps: encoding, collision, propagation and macroscopic variable calculation. In the encoding segment, transformation of the initial variable \( \phi \left( \mathbf {x},0\right) \) into a quantum state vector is performed by employing the normalization procedure and the encoding state protocol, while in the collision and propagation steps corresponding operations based on Eqs. (5) and (6) are utilized. In the last step, addition according to Eq. (7) is conducted, where the output state is used as the input quantum state for the new time step.

In the encoding step, two quantum registers, q and ancilla a are installed. In the first register, q, having the \( \log _2 (2M) \) qubits, the initial distribution of variable \( \phi (\mathbf {x},0) \) in form of vector \( \varvec{\upphi }=[\phi _{1,0},\dots ,\phi _{1,M-1},\phi _{2,0},\dots ,\phi _{2,M-1}]^T \), where the first index denotes the link \( \alpha \) and the second index marks the location number of the lattice site, is encoded into the quantum state as

$$\begin{aligned} {|{\psi _{0}}\rangle }={|{0}\rangle }_a \sum _{i=0}^{2M-1} \phi _{\alpha ,i}/\Vert \phi \Vert {|{i}\rangle }_q. \end{aligned}$$
(8)

The \( {|{i}\rangle } \) is the 2M-dimensional computational basis state, while the \( \Vert \phi \Vert \) is the Euclidean norm. To achieve this initial state, where the \( {|{000...}\rangle } \) state is adapted to be, conditionally speaking, a desired arbitrary state, the reverse iterative procedure proposed by Shende et al. [48] is used as part of the built-in functions of the Qiskit [45] quantum framework. It should be noted that this initialization of the desired state is performed only once, at the beginning of the simulation.

The collision step is responsible for the relaxation of the distribution function to the local equilibrium (Eq. (5)). To simplify the collision step without destroying the very core of the lattice Boltzmann method, according to Zhou [47], parameter \( \omega \) is set to 1.0. As a result, the left side of Eq. (5) now depends only on \( f_{eq} \), hence, the collision step is reduced to derivation of the \( f_{eq} \) alone. To perform this step, point-wise multiplication of the vector \( \varvec{\upphi } \) and corresponding block-diagonal matrix A with two \( M \times M \) main-diagonal blocks is required according to Eq. (3). However, since this block-diagonal matrix is a non-unitary, implementation of the corresponding operator is performed by applying the linear combination of unitaries approach [44]. Hence, controlled operations in form

$$\begin{aligned} (H^{\dagger }\otimes I_q)({|{0}\rangle }{\langle {0}|}_a\otimes C_1 + {|{1}\rangle }{\langle {1}|}_a\otimes C_2)(H\otimes I_q), \end{aligned}$$
(9)

is applied, where \( C_1 \) and \( C_2 \) are the unitary diagonal operators defined as \( C_1=A+i\sqrt{I-A^2} \) and \( C_2=A-i\sqrt{I-A^2} \), while \( A=1/2({C}_1+{C}_2) \) represents the non-unitary block-diagonal operator, whose entries, \( a_{i,i} \), are calculated according to Eq. (3), excluding the depended variable \( \phi (\mathbf {x},t) \). Since there is just one qubit in ancilla register required to achieve control operation, superposition is accomplished by applying the Hadamard operator \( \hat{H} {|{0}\rangle }_a \). It should be noted also that by increasing the number of computational points, i.e., the number of qubits in q register, the two block-diagonal matrix structure of the collision operator does not change, leaving unaffected the ancillary register in terms of the used qubits. Following the collision step, the initial quantum state \( \psi _{0} \) has evolved into:

$$\begin{aligned} {|{\psi _{1}}\rangle }={|{0}\rangle }_a \sum _{i=0}^{2M-1} a_{i,i} \phi _{\alpha ,i}/\Vert \phi \Vert {|{i}\rangle }_q+{|{1_\phi ^\bot }\rangle }_{aq}, \end{aligned}$$
(10)

where \( {|{1_\phi ^\bot }\rangle }_{aq} \) denotes some orthogonal state of lesser interest. The quantum circuit responsible for achieving the state described by Eq. (10) is given in Fig. 3, while the details of the operator \( C_1 \) are shown in Fig. 4. The \( U_1=\left( \begin{matrix} 1 &{} 0 \\ 0 &{} e^{i\lambda } \end{matrix} \right) \) gate in Fig. 4 represents the standard Qiskit phase shift gate, which correspond to \( R_z \) rotation up to global phase \( e^{-i\lambda /2} \), while the parameters \( \lambda _{1} \) and \( \lambda _{2} \) corresponds to the first and second block of the diagonal operator \( C_1 \), respectively. From the scalability point of view, increasing the number of qubits do not affect operators \( C_1 \) and \( C_2 \) in terms of required gates, i.e., the qubits are simply added with no additional modifications of the current gate structure and depth whatsoever.

Fig. 3
figure 3

Quantum circuit for solving the 1D advection–diffusion equation by using the D1Q2 lattice Boltzmann model. For the typesetting quantum circuit diagrams, a Quantikz package [49] is used

Full size image
Fig. 4
figure 4

Quantum circuit for implementing the operator \( C_1 \) in case of the D1Q2 LBM

Full size image

In the propagation step, quantum walk [50, 51] as a procedure for the propagation of the distribution functions along the corresponding links is utilized. In general, this procedure implies shifting the distribution function \( f_1 \) along the link \( \alpha =1 \) with speed \( e_1=1 \), and function \( f_2 \) along the link \( \alpha =2 \) with speed \( e_2=-1 \). To achieve this, corresponding operations in form of matrices for the right and the left shift, \( P_r \) and \( P_l \), respectively, are introduced. These operations are implemented into the circuit in form of operators R and L (Fig. 3), where the corresponding sub-circuits are shown in Figs. 5 and 6. It should be noted that the propagation step is implemented as a controlled operation of the quantum walk procedure on the first qubit in register q as \( {|{0}\rangle }{\langle {0}|}\otimes R_w + {|{1}\rangle }{\langle {1}|}\otimes L_w \), where \( R_w \) and \( L_w \) represents the quantum walk in right and left direction, respectively. Following the propagation step, the quantum state of the entire system is

$$\begin{aligned} {|{\psi _{2}}\rangle }={|{0}\rangle }_a LR\left( \sum _{i=0}^{2M-1} a_{i,i} \phi _{\alpha ,i}/\Vert \phi \Vert {|{i}\rangle }_q\right) +{|{1_\phi ^\bot }\rangle }_{aq}, \end{aligned}$$
(11)

where again \( {|{1_\phi ^\bot }\rangle }_{aq} \) represents some state of lesser interest.

In the last step, the calculation of the macroscopic variables by Eq. (7), i.e., the point-wise addition of the two quantum states, is performed. Since state \( \psi _{2} \) (Eq. (11)) indicates that both distribution functions are located in the subsystem controlled by the \( {|{0}\rangle }_a \), for the procedure of addition it is required first to perform the SWAP gate between ancilla register a and the last qubit \( q_n \) in the q register (Fig. 3). This operation actually switches between the states of the register q controlled by the \( {|{0}\rangle }_a \) and \( {|{1}\rangle }_a \) in the ancilla register, positioning, therefore, the sub-state of the second distribution function, controlled by \( {|{0}\rangle }_a \), to the state controlled by \( {|{1}\rangle }_a \). The last step includes application of the Hadamard gate in the ancilla register, followed by the re-normalization of the post-selected \( {|{0}\rangle }_a \) state by the factor \( 2\Vert \phi \Vert /\sqrt{2} \). As a result, the spatial distribution of the variable \( \phi \) for the next time level \( t+1 \) is obtained, and the entire procedure is then repeated to achieve desired time level. In order to retrieve this post-selected state on real devices, the state tomography is required.

$$\begin{aligned} P_r = \begin{bmatrix} 0 &{} 0 &{} 0 &{} \cdots &{} 1 \\ 1 &{} \ddots &{} \ddots &{} \ddots &{} \vdots \\ 0 &{} \ddots &{} \ddots &{} 0 &{} 0 \\ \vdots &{} \ddots &{} 1 &{} 0 &{} 0 \\ 0 &{} \cdots &{} 0 &{} 1 &{} 0 \\ \end{bmatrix} , P_l= \begin{bmatrix} 0 &{} 1 &{} 0 &{} \cdots &{} 0 \\ 0 &{} \ddots &{} \ddots &{} \ddots &{} \vdots \\ 0 &{} \ddots &{} \ddots &{} 1 &{} 0 \\ \vdots &{} \ddots &{} 0 &{} 0 &{} 1 \\ 1 &{} \cdots &{} 0 &{} 0 &{} 0 \\ \end{bmatrix}. \end{aligned}$$
Fig. 5
figure 5

Quantum circuit for implementing the operator R

Full size image
Fig. 6
figure 6

Quantum circuit for implementing the operator L

Full size image

3.2 The D2Q5 model

In case of the two-dimensional D2Q5 lattice Boltzmann model, 5 distribution functions have been utilized, where, in comparison with the 1D case, two distribution functions along y axis and a rest particle have been added (Fig. 2). Hence, variable \( \phi (\mathbf {x,0}) \) in this case is represented in vector form as \( \varvec{\upphi }=[(\phi _{0,i,j},\dots ,\phi _{0,M-1,M-1}), \dots ,(\phi _{4,i,j},\dots ,\phi _{4,M-1,M-1}) ]^T \), where \( i,j=0,\dots ,M-1 \). The corresponding quantum state following the encoding step is

$$\begin{aligned} {|{\psi _{0}}\rangle }={|{0}\rangle }_a \sum _{k=0}^{8M^2-1} \phi _{\alpha ,k}/\Vert \phi \Vert {|{k}\rangle }_q. \end{aligned}$$
(12)

The number of required qubits in the q register is determined as \( \log _2(5(M\times M))+1\), where an additional qubit is introduced for the purpose of the collision step only. Again, the encoding step is performed by the previously mentioned procedure [48].

In the collision step, the same procedure is applied as in the case of the D1Q2 model (Fig. 3). In contrast to the one-dimensional case, operators \( C_1 \) and \( C_2 \) now have eight-block diagonal form, therefore modifying the corresponding quantum sub-circuit which is shown in Fig. 7. Following the collision step, the initial quantum state \( \psi _{0} \) evolves into

$$\begin{aligned} {|{\psi _{1}}\rangle }={|{0}\rangle }_a \sum _{k=0}^{8M^2-1} a_{k,k} \phi _{\alpha ,k}/\Vert \phi \Vert {|{k}\rangle }_q+{|{1_\phi ^\bot }\rangle }_{aq}. \end{aligned}$$
(13)

It should be noted that the \( a_{k,k} \) are the entries of the eight-block diagonal operator, where each block corresponds to one of the quantum sub-states representing the distribution functions. Since we have only 5 distribution functions (Fig. 2), the remaining 3 are not taken into account, having their values a set to 1.0. In the circuit terminology, these states are introduced with the identity operator.

Fig. 7
figure 7

Quantum circuit for implementing the operator \( C_1 \) in case of the D2Q5 LBM

Full size image

For the propagation step, there are now four distribution functions that need to be shifted in four different directions with the velocity vectors defined by Eq. (4), and one distribution function assigned to the rest particle which is excluded from this process. To implement this step into the quantum circuit, two operators R (Fig. 5) and L (Fig. 6) from the 1D case are utilized, where some additional modification in terms of controlled operations are introduced to account the 2D case. The resulting quantum circuit is shown in Fig. 8. It can be seen in Fig. 8 that the whole propagation process refers to the \( {|{0}\rangle }_a \) state, meaning that the quantum states encoding the valid distribution functions are concentrated in the sub-state when the ancilla is in \( {|{0}\rangle } \), while the state \( {|{1_{\phi }^\perp }\rangle } \) is of lesser interest and do not contains any relevant information. However, this \( {|{1_{\phi }^\perp }\rangle } \) will be used for the procedure of addition as a state that will receive the switched sub-state from the orthogonal counterpart, forming, therefore, the required state configuration for the addition to be performed.

To calculate the macroscopic variables based on Eq. 7, point-wise addition between quantum sub-states corresponding to the particular distribution function needs to be performed. This can be done by switching the quantum sub-states which need to be added between the states \( {|{0}\rangle }_a \) and \( {|{1}\rangle }_a \) by applying the SWAP gate, and then reordering them if it is necessary to obtain the right state configuration for the addition protocol. Finally, the post-selection of the state \( {|{0}\rangle }_a{|{00\psi }\rangle }_q \) followed by normalization with the factor \( 2\Vert \phi \Vert /\sqrt{2} \) gives as a result the desired solution of the variable \( \phi (x,y) \) for the next time level \( t+1 \). The corresponding quantum circuit for determining the macroscopic variables of the D2Q5 lattice Boltzmann model is given in Fig. 8.

Fig. 8
figure 8

Quantum circuit for the propagation step and calculation of the macroscopic variables in case of D2Q5 LBM

Full size image

3.3 Complexity

The complexity of the proposed algorithm can be analyzed through four major steps, encoding, collision, propagation and macros calculation. The main question is: how does the resolution of the computational domain relate to the depth of quantum algorithm? For the encoding step, according to Shende et al. [48], \( 2^n-1 \) state preparation steps and 1 diagonal operator are used, where the final CNOT count is \( 2\times 4^n-\left( 2n+3\right) \times 2^n+2n \). For the collision step, it can be seen that both for the 1D and 2D cases, change in number of qubits to achieve a higher resolution of the computational model doesn’t affect the size of ancillary register, while in the q register the number of multi-qubit gate operations scales with the number of qubits n as \(\mathcal {O}(1)\). The reason for this lies in dependency between the multi-qubit gate operations and the total number of distribution function \( \alpha \) being used, which, consequently imposes relation \(\mathcal {O}(\alpha )\), while the number of controls per gate scales as \(\mathcal {O}(\lceil \alpha /2\rceil )\).

For the propagation step, the number of multi-qubit gate operations scales with the number of qubits for each link \( \alpha \) as \( \mathcal {O} (\log _2 D) \), where for the D1Q2 model \( D=2M \), while for the D2Q5 case \( D=5M^2 \). The propagation for each link is implemented by applying one of the operators R or L, where the entry of control operations per gate, excluding the ancilla register and the qubit \( q_n \) introduced for the collision purposes only, scales as \( \mathcal {O} (\log _2 \alpha ) \).

The last segment is used for the calculation of the macroscopic variables by performing the point-wise addition of the distribution function encoded as the sub-states of the quantum state \( \psi \). This part of the algorithm is composed of blocks each having one Hadamard, SWAP and multi-control gate, which primarily depends on the number of links \( \alpha \) as \( \mathcal {O} (\alpha -1) \). However, increasing the number of qubits for particular model does not affect the circuit in terms of quantum gates, i.e., the macros block scales with the number of qubits n as \(\mathcal {O}(1)\). Finally, the complexity of the whole algorithm, excluding the encoding step, can be defined as \( \mathcal {O} (\log _2 (\alpha D)) \).

4 Validation and numerical simulation

To demonstrate the proposed quantum algorithm for solving the unsteady 1D and 2D advection–diffusion equation by using the LBM as a numerical procedure, transport of conservative tracer, having the concentration C in a schematic channel is considered. For both the 1D and 2D cases, a periodic boundary condition on closed boundaries is imposed, while for the initial concentration, C(x, 0) , some arbitrary Gauss like distribution is specified. The unsteady simulation is then performed by using Qiskit [45] platform, where the ‘statevector simulator’ backend as a part of the high-performance simulator framework Aer is used.

4.1 The motion of 1D Gaussian Hill—D1Q2 model

The movements of 1D Gaussian hills in a uniform flow are simulated. In the computations, 64 lattice cells are used with \( \Delta x=1.0 \), \( \Delta t=1.0 \), \( u=0.2 \), \( \omega =1 \) and \( D=0.5 \), all in lattice units. Equilibrium function is calculated according to Eq. (3) as \( f_{1}^{eq}\left( \mathbf {x},t\right) =0.6\phi \left( \mathbf {x},t\right) \) and \( f_{2}^{eq}\left( \mathbf {x},t\right) =0.4\phi \left( \mathbf {x},t\right) \), which is further used for the calculation of the operators \( C_1 \) and \( C_2 \). For this purpose, 7 qubits in the q register, and one qubit in ancillary register are utilized. The initial concentration is 0.1 everywhere, except for the point at \( x=12 \) with a unit point source of \( C=0.2 \). The results shown in Fig. 9 demonstrate good agreements with the analytical solutions.

$$\begin{aligned} \begin{aligned} C_1 = \begin{bmatrix} e^{i\overbrace{\log (0.6+0.8i)}^{\lambda _{1}}} &{} 0 &{} \cdots &{} \cdots &{} \cdots &{} 0 \\ 0 &{} \ddots &{} \ddots &{} \ddots &{} \ddots &{} \vdots \\ \vdots &{} \ddots &{} e^{i\log (0.6+0.8i)} &{} 0 &{} 0 &{} \vdots \\ \vdots &{} \ddots &{} 0 &{} e^{i\overbrace{\log (0.4+0.916515i)}^{\lambda _{2}}} &{} \cdots &{} 0 \\ 0 &{} \ddots &{} \ddots &{} \ddots &{} \ddots &{} 0 \\ 0 &{} \cdots &{} 0 &{} 0 &{} 0 &{} e^{i\log (0.4+0.916515i)} \\ \end{bmatrix}, \\ C_2= \begin{bmatrix} e^{i\overbrace{\log (0.6-0.8i)}^{\lambda _{1}}} &{} 0 &{} \cdots &{} \cdots &{} \cdots &{} 0 \\ 0 &{} \ddots &{} \ddots &{} \ddots &{} \ddots &{} \vdots \\ \vdots &{} \ddots &{} e^{i\log (0.6-0.8i)} &{} 0 &{} 0 &{} \vdots \\ \vdots &{} \ddots &{} 0 &{} e^{i\overbrace{\log (0.4-0.916515i)}^{\lambda _{2}}} &{} \cdots &{} 0 \\ 0 &{} \ddots &{} \ddots &{} \ddots &{} \ddots &{} 0 \\ 0 &{} \cdots &{} 0 &{} 0 &{} 0 &{} e^{i\log (0.4-0.916515i)} \\ \end{bmatrix}. \end{aligned} \end{aligned}$$
Fig. 9
figure 9

Comparison of the numerical results \( (\circ ) \) to the analytical solution \( (-) \) for the 1D ADE simulated with the D1Q2 LBM

Full size image
Fig. 10
figure 10

Comparison of the numerical results obtained by the quantum algorithm, the classical FORTRAN code, and the analytical solution of the 2D ADE simulated with the D2Q5 LBM

Full size image

4.2 Movements of 2D Gaussian Hill - D2Q5 model

For the 2D case, the evolution of the Gaussian hill in a square domain with a \( 16 \times 16 \) lattice configuration is considered. The following parameters set has been adopted: \( \Delta x=1.0 \), \( \Delta t=1.0 \), \( u=0.2 \), \( v=0.15 \), \( \omega =1 \) and \( D=0.166\dot{7} \), all in lattice units. The numerical simulation is conducted using an instantaneous drop of pollution at point \( C(x=4,y=4)=0.3 \), while the concentration of 0.1 is imposed along the rest of the domain. A periodic boundary condition is assigned to all four boundaries. For this purpose, 11 qubits in the q register and one qubit in ancillary register are utilized. To validate the proposed algorithm, comparison with analytical solution and results obtained by the ‘classical’ FORTRAN [52] code for the D2Q5 model [37] is shown in Fig. 10. Overlapping of the results of the FORTRAN code solution and the proposed quantum algorithm solution is demonstrated, while some discrepancies can be seen compared to the analytic solution. However, these deviations are not produced by the quantum algorithm solely, which is demonstrated previously, but by the low resolution of the computational mesh as one of the major issues when numerical methods for solving differential equations are used. Of course, to increase the accuracy of the model finer mesh with higher resolution and, hence, a greater number of qubits is required.

5 Conclusion

In this paper, a novel quantum algorithm for solving the advection–diffusion equation by using the full lattice Boltzmann method as a numerical scheme is proposed and validated. For this purpose, the unsteady form of the one-dimensional and two-dimensional ADE discretized with the D1Q2 and D2Q5 lattice Boltzmann model, respectively, is utilized. Due to the basic nature of the LBM, the proposed quantum algorithm consists of three major segments, collision, propagation, and calculation of the macroscopic variables, for which a corresponding circuit configuration using the gate based quantum computing platform Qiskit has been developed and tested. The evolution of the 1D and 2D Gaussian Hill is used for validation of the algorithm, while the analytic solution and the ‘classic’ FORTRAN code are exploited for the comparison. The obtained results show excellent agreement with the compared values. Furthermore, the complexity analysis shows that for the particular model collision the macros segment of the algorithm is not affected by the change in the size of the computational domain. Developing quantum algorithms for other, more complex physical processes related to fluid dynamics using the lattice Boltzmann method is the major goal of the forthcoming work, where nonlinearity in the equilibrium function is one of the main obstacles that need to be overcome.