Does HHL implementation require a priori eigendecomposition?

Question

I am interested in HHL algorithm and despite all the problems related to current technologies, I am trying to understand how it has to be implemented.

I have seen from these two available circuits (arXiv:1804.03719, arXiv:1811.01726) that when you define a circuit it is necessary to apply a certain rotation of the ancilla qubit based on the eigenvalues. For what I understood from the original paper, the algorithm "extracts" the information about eigenvalues using the quantum phase estimation algorithm but this part is missing in the circuits.

My doubt is if I have to decompose my matrix to find eigenvalues I lose the possible advantage derived from the algorithm; is that correct?

Answer 1

Disclaimer: I am learning it right now, so I can only give a partially satisfying answer. Nobody answered so far, so I'll give you the best I know waiting for somebody to give a more detailed answer.

I suggest you have a look at the qiskit book, which has a simple tutorial that I found super useful. They literally say that you don't have to compute the eigenvalues. This is because a matrix $A$ that is $N\times N$ can have up to $N$ distinct eigenvalues and therefore computing them will take at least $O(N)$ time, which means the exponential advantage is lost.

In general, I think the idea is that when you perform a QPE you have a state that encodes the values of the eigenvalues, but you cannot access them. In a similar way, you cannot directly access the solution vector. Thus, the QC can perform a controlled rotation based on the value of those eigenvectors because they are encoded in a quantum state.