# 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.2 Quantum Phase Estimation  
The eigen-decomposition requires a subroutine called quantum phase estimation (QPE), as illustrated in the sky blue part of Figure 1. Given a unitary matrix \(U\) has an eigenstate \(\left|v_{j}\right\rangle\) with eigenvalue \(e^{2\pi i\theta_{j}}\), QPE is a quantum algorithm to solve the phase of the eigenvalue (\(\theta_{j}\)) [35]. After executing the QPE algorithm, the binary representation of  
Figure 1: HHL circuit. The unitary gates in quantum phase estimation (QPE) are \(U=e^{i\mu A}\) and \(U^{2}=e^{i2\mu A}\) where \(i^{2}=-1\) and \(t\) is a scaling factor. The top qubit is referred to as the ancillary qubit, and it is the most significant qubit.  
the phase angle \(\theta\) is stored in a qubit state. The qubits carrying the phase information are named \"clock qubits\". In the HHL algorithm, if \(\ket{v_{j}}\) is an eigenstate of a Hermitian matrix \(A\) with eigenvalue \(\lambda_{j}\), by constructing a unitary matrix \(U=e^{itA}\) with a scale factor \(t\), the state \(\ket{v_{j}}\) becomes an eigenstate of \(U\) with eigenvalue \(e^{it\lambda_{j}}\). Therefore, the eigenvalue \(\lambda_{j}\) can be estimated using the QPE algorithm.  
Suppose we have access to the gate \(U\); then it is clear that \(U^{l}\ket{v_{j}}=e^{2\pi i\theta_{j}l}\ket{v_{j}}\) for some positive integer \(l\). QPE requires a submodule called quantum Fourier transform (QFT). QFT maps  
\[QFT\ket{\vec{j}} = \frac{1}{\sqrt{2^{n_{c}}}}\sum_{k=0}^{2^{n_{c}}-1}\omega^{j_{k}} \ket{\vec{k}}\] \[= \frac{1}{\sqrt{2^{n_{c}}}}\Big{(}\ket{0}+e^{2\pi i\theta_{j_{nc}} }\ket{1}\Big{)}\Big{(}\ket{0}+e^{2\pi i\theta_{j_{nc}}-1j_{nc}}\ket{1}\Big{)} \cdots\Big{(}\ket{0}+e^{2\pi i\theta_{j}l_{j}l_{2}-j_{nc}}\ket{1}\Big{)}\]  
where \(\vec{j}\) has \(n_{c}\) bits and \(\omega=e^{2\pi i/(2^{n_{c}})}\). Intuitively, \(\vec{j}\) can be considered as binary number \(\vec{j}=j_{1}j_{2}\ldots j_{n_{c}}\) such that \(j_{l}\in\{0,1\}\) and QFT transforms this binary number from a state to the phases of bases in different accuracy. So, on the contrary, if we apply the inverse of the QFT operator, denoted by \(QFT^{\dagger}\), the phase value becomes a state, and we can measure the state to obtain the phase value in the binary representation.  
To summarize the process of a standalone QPE routine, we have  
\[\ket{0}^{\otimes n_{c}}\ket{v_{j}} \xrightarrow{H^{\otimes n_{c}}}\frac{1}{\sqrt{2^{n_{c}}}}\sum_{k =0}^{2^{n_{c}}-1}\ket{\vec{k}}\ket{v_{j}}\] \[\xrightarrow{\text{{\footnotesize{C}I} sequence}}\frac{1}{\sqrt{2^{n_{c}}}}\sum_{k =0}^{2^{n_{c}}-1}e^{2\pi i\theta_{j}k}\ket{\vec{k}}\ket{v_{j}}\] \[\xrightarrow{QFT^{\dagger}}\ket{\vec{\theta}_{j}}\ket{v_{j}}\]  
where the \(CU\) sequence is the controlled-\(U\) sequence in the sky blue part of Figure 1 and \(\vec{\theta}_{j}=\theta_{j}\) if \(\theta_{j}\) can be perfectly represented in \(n_{c}\) bits; otherwise, \(\vec{\theta}_{j}\) is an estimation of \(\theta_{j}\) in a finite accuracy. In other words, the number of clock qubits, \(n_{c}\), governs the accuracy of the estimated eigenvalue in QPE. To understand more details about QFT and QPE, we direct the interested reader to [35; 45].  
Note that, without circuit optimization, the increase in \(n_{c}\) will exponentially increase the gate counts in HHL circuits. Recall the HHL circuit in Figure 1: an extra clock qubit leads to an extra controlled \(U^{2^{n_{c}-1}}\) and an extra controlled inverse \(U^{2^{n_{c}-1}}\) in the HHL circuit, where \(U=e^{itA}\) and \(A\) is the coefficient matrix in a linear system. Generally, we should not explicitly compute the matrix \(U^{2^{n_{c}-1}}\), but apply gate \(U\) for \(2^{n_{c}-1}\) times in the circuit. Then, the QPE part of the circuit contains \(\sum_{j=0}^{n_{c}-1}2^{j}=2^{n_{c}}-1\) number of \(U\), and when there are \(n_{c}+1\) clock qubits, an extra \(2^{n_{c}}\) number of \(U\) is added into the QPE, which almost doubles the number of gates \(U\) in QPE. The same situation happens on the inverse QPE part of the HHL circuit.