Undergrad HHL Algorithm for Solving Linear Equations

[dakshina gandikota]

I have a question about HHL algorithm https://arxiv.org/pdf/0811.3171.pdf for solving linear equations of the form:

A x = b

Where A, x and b are matrices

Take for example

4x₁ + 2x₂ =14
5x₁ + 3x₂ = 19

HHL apply the momentum operator e^iAτt_o/T on the state, do a Fourier Transform on |b> and *uncompute phase estimation*. I don't follow the last step. How can you uncompute, when you haven't computed the phase estimation?

Earlier in the paper they mention that let |u> be the eigen vector of |b> using phase estimation. Is this what they are referring to? There is no circuit to back their algorithm in that pdf.

I also checked a particular implementation of HHL https://arxiv.org/pdf/1110.2232v2.pdf where they mention

"Apply the quantum inverse Fourier transform to the register C. Denote the basis states after quantum Fourier transform as |k>"

It seems they didn't edit the sentence properly. So not much help.

Does anyone think these are not properly described in the papers? By the way, there has been a thread https://quantumcomputing.stackexcha...systems-of-equations-hhl09-step-2-preparation to discuss the paper but not address the specific issues.

Thanks

 

[azntoon]

. Yes, it does seem that the papers are not properly describing the steps of the HHL algorithm. Specifically, the last step of the algorithm involves using the phase estimation algorithm to estimate the eigenvalues of A and then applying the inverse Fourier transform on the register C. This step is often referred to as "uncomputing the phase estimation" because it essentially "undoes" the phase estimation. It is important to note that this step is necessary in order to obtain the correct solution for the linear system of equations.