HHL Algorithm¶
HHL algorithm introduction
Proposed by Aram Harrow et al in 2009, the HHL algorithm is used to solve linear equations. Under the premise of some assumptions, this algorithm can solve the linear equations with exponential acceleration compared with the classical algorithm. HHL algorithm is the key step in the current quantum artificial intelligence algorithm.
The basic idea of HHL algorithm:
The HHL algorithm mainly solves the linear equations \({\rm{A}}\overrightarrow {\rm{x}} {\rm{ = \vec b}}\), where the matrix A and vector \(\vec b\) are known.
The approximate steps of the HHL algorithm are as follows:
Initialization: Initialize the vector \(\vec b\) to be quantum state \(\left| b \right\rangle\).
Estimate the eigenvalues of matrix A: Use the phase estimation algorithm to get the value of \(\lambda\) in \({e^{2\pi i\lambda }}\) which is also the eigenstate of matrix A.
Controlled rotation: Controlled rotation of auxiliary qubit is performed according to the estimated eigenvalues. Then use the approximate value \(\frac{\theta }{{{2^r}}}\) as \({\rm{sin}}\left( {\frac{\theta }{{{2^r}}}} \right)\), which is the reciprocal of the eigenvalue.
Reset \(\left| {{q_0}{q_1}} \right\rangle\) as \(\left| {00} \right\rangle\) using the reverse phase estimation algorithm.
Measure \(\left| {q_3} \right\rangle\); If the result is 1, the corresponding quantum state \(\left| {q_2} \right\rangle = \left| {x} \right\rangle\). Then the approximate solution of the equations can be obtained.
The quantum circuit diagram of the HHL algorithm is as follows:
References: