# 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?

• – Sanchayan Dutta Apr 24 '19 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$? – Mark S Apr 26 '19 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. – Macalcubo May 20 '19 at 15:31

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.