# An Early Investigation of the HHL Quantum Linear Solver for Scientific Applications
## 2 Quantum Linear Systems and the Implementation of the Solver
### Overview of the Harrow-Hassidim-Lloyd (HHL) Algorithm
#### 2.1.4 Quantum-Classical Data Exchange in HHL  
There are two major input models for encoding both matrix \(A\) (or \(e^{\text{it}A}\)) and vector \(\ket{b}\) into a quantum computer. One is the sparse-access model, used in the HHL algorithm [3]. The sparse-access model is a quantum version of classical sparse matrix computation, and we assume access to unitaries that calculate the index of the \(l^{\text{th}}\) non-zero element of the \(k^{\text{th}}\) row of a matrix \(A\) when given \((k,l)\) as input. A different input model, now known as the quantum operator input model, is from [PERSON] [46]. This method is based on the block-encoding of \(A\) to allow efficient access to entry values. Its circuit implementation can be found in [47; 48]. Meanwhile, this encoding scheme can also be achieved using quantum random access memory [49; 50; 51; 52]. It requires the complexity \(O(\text{polylog}(N/\epsilon_{BE}))\) for realizing an \(\epsilon_{BE}\)-approximate block-encoding of \(A\in\mathbb{C}^{N\times N}\) with quantum random access memory [50].  
**Definition 2** (The block-encoding of a matrix).: _The block-encoding of a matrix \(A\in\mathbb{C}^{N\times N}\) is a unitary operator \(U\) such that_  
\[U=\begin{bmatrix}A/a&\cdot\\ \cdot&\cdot\end{bmatrix}\]_where \(a\geq\|A\|\) is a normalizing constant. In other words, \(U\) and \(A\) satisfy, for some constant \(a\) and \(n\),_  
\[a\Big{(}\langle 0|^{\otimes n}\otimes I_{N}\rangle\,U\Big{(}I_{N}\otimes|0 \rangle^{\otimes n}\Big{)}=A\]  
_where \(I_{N}\in\mathbb{R}^{N\times N}\) is the identity matrix._  
To construct the matrix exponential \(e^{itA}\) in QPE via block-encoding-based methods, block-encoding first embeds the coefficient matrix \(A\) into a larger unitary matrix, and then uses Quantum Signal Processing to achieve the Hamiltonian simulation \(e^{itA}\)[53]. However, limited by the size of tested matrices in our numerical experiments, block-encoding alone already does not show advantages over Quantum Shannon Decomposition (QSD), a method that directly decomposes \(e^{itA}\) into a sequence of basis gates, in terms of gate counts and the number of encoding qubits. We illustrate this in Table 1. Note that the coefficient matrix used in Section 5.1 is non-Hermitian, so its conversion to a Hermitian matrix using Equation (1) brings a disadvantage to QSD in terms of the number of gates.  
On the other hand, efficiency in reading \(|x\rangle\) could be a potential threat to quantum speedup. The current state-of-the-art quantum state tomography algorithm is from [PERSON] et al. [54]. For a state \(|\psi\rangle=\sum_{j=0}^{N-1}\beta_{j}\,|\vec{j}\rangle\in\mathbb{C}^{N}\), with probability \(1-\delta\), the pure-state tomography in [54] requires \(O\Big{(}\sqrt{N}/\sigma\cdot\log(N/\delta)\Big{)}\) queries to the unitary oracle that prepares \(|\psi\rangle\) from \(|00\ldots 0\rangle\) to output a vector \(\vec{\beta}_{est}\in\mathbb{R}^{N}\) such that \(\|\Re(\vec{\beta})-\vec{\beta}_{est}\|_{\infty}\leq\sigma\). The same routine can be applied to \(i\,|\psi\rangle\) to estimate the imaginary part.