# A Cost-Efficient Approach towards Computational Fluid Dynamics Simulations on Quantum Devices
## 3 Preliminaries
### Quantum Solver for System of Linear Equations  
Various quantum algorithms for FEM have been proposed lately that claim to be exponentially faster than their classical counterparts, but it is hard to decide which method has the most potential as of now, especially with new algorithms being developed each year. Most of these algorithms utilize the famous Harrow-Hassidim-Lloyd (HHL) algorithm [32], which solves a system of linear equations. In this paper, we will treat it as a quantum black box, i.e., we are solely interested in the output returned by this quantum subroutine.  
The HHL algorithm prepares the state \(\ket{x}=\frac{\ket{x^{\prime}}}{\ket{x^{\prime}}}\) that encodes the solution of the equation  
\[A\ket{x^{\prime}}=\ket{b}. \tag{16}\]  
Let \(\ket{\cdot}\ket{\text{be a norm}}\) (usually taken as \(\ket{\cdot}\ket{\text{$\cdot$}}\ket{\text{$\cdot$}}\ket{\text{$\cdot$}}\ket{ \text{$\cdot$}}\ket{\text{$\cdot$}}\ket{  
where \((u_{j},\lambda_{j})\) is the \(j\)th eigenvector, eigenvalue pair of \(A\). In the eigenbasis, \(A\) is diagonal; therefore,  
\[A^{-1}=\sum_{j=0}^{N-1}\lambda_{j}^{-1}\ket{u_{j}}\bra{u_{j}}. \tag{18}\]  
The right-hand side of Equation (16) can also be rewritten in the eigenbasis as  
\[\ket{b}=\sum_{j=0}^{N-1}b_{j}\ket{u_{j}},\ \ \ \ \ b_{j}\ \in\ \mathbb{C}. \tag{19}\]  
The HHL algorithm solves the following equivalent equations  
\[\ket{x^{\prime}}=A^{-1}\ket{b}=\sum_{j=0}^{N-1}\lambda_{j}^{-1}b_{j}\ket{u_{j} },\ \ket{x}=\frac{\ket{x^{\prime}}}{||x^{\prime}||}, \tag{20}\]  
by producing the state \(\ket{x}\) up to accuracy \(\epsilon\) in \(l_{2}\) norm, with a bounded probability of failure, and makes  
\[O(sk\,\text{polylog}(sk/\epsilon))\]  
uses of \(\mathcal{P}_{A}\) and \(\mathcal{P}_{b}\), and the run time is the same up to a \(\text{polylog}(N)\) factor (where the \(\text{polylog}(x)\) denotes the polynomial in terms of \(\log(x)\)).  
As mentioned in [28; 29], if one hopes to preserve the quantum speedup, two operations are not allowed. The first one is the input state preparation \(\ket{b}\) with an encoded quantum circuit, where reading all data entries requires \(\mathcal{O}(N)\) time. The second one is measuring the output state to extract the state to a classical vector, which also requires \(\mathcal{O}(N)\) time. Solving a time-dependent problem iteratively requires the discretized physical governing equation to be solved at every time step; thus, the two problems mentioned above exist in every time step. An additional \(\mathcal{O}(N)\) time complexity cannot be allowed in the calculations if an exponential speedup is to be preserved.  
One of the workarounds for this problem is using QRAM as mentioned in [29; 43]. Following the work of [29], the runtime analysis concludes that the time complexity of their quantum procedure is  
\[\mathcal{O}\Bigg{(}\frac{(s^{3}+\log N)sk\log^{3}N}{\epsilon^{2}}\,\text{ polylog}(sk/\epsilon)\Bigg{)}.\]  
The classical counterpart's time complexity is  
\[\mathcal{O}(Nsk\log 1/\epsilon)\]  
when using the conjugate gradient (CG) as the linear solver. The accuracy parameter \(\epsilon\) has also been incorporated in their quantum time complexity, which is an important factor that has been left out in a few previous attempts claiming to reach exponential speedup incorrectly, as pointed out by [PERSON] [28]. The algorithm they developed outperforms the classical algorithm when the relation \(N\gg 1/\epsilon^{2}\) holds.