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?


1 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.