Does HHL implementation require a priori eigendecomposition?

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?

• Apr 24, 2019 at 14:47
• Hi Macalcubo! What is your application to which you are trying to gain an advantage? Can you describe elements in your $N\times N$ matrix $A$ easily enough with quantum gates? Is $A$ sparse enough? Can you prepare your input vector $\vec b$ efficiently, say, for example, as a uniform superposition over all $N$ states? Is it OK to sample $\vec x$? Apr 26, 2019 at 23:57
• Hi Mark! I am just trying to estimate a linear model using the HHL, which is the same thing I saw in the papers. In the end, my idea would be to estimate a GLM using matrix inversion, but first I want to get an implementation of HHL to perform simulation. May 20, 2019 at 15:31

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.