1
$\begingroup$

I have been going through the original HHL paper (2009), and I see that they call a linear system of equations "well behaved" / "well-conditioned", if $$ |\lambda| \in \left[\frac{1}{\kappa}, 1\right]$$ where $\kappa$ is the condition number. I am not that strong in Linear Algebra, but it is very obscure to me why they are combining eigenvalues and singular values. Could someone explain why this is being done either in the context of this particular algorithm, or in general?

$\endgroup$
2
$\begingroup$

In the HHL algorithm, they are solving a linear system $Ax=b$. This is achieved by embedding $A$ into a Hermitian matrix such as $$ H=\left(\begin{array}{cc} 0 & A \\ A^\dagger & 0 \end{array}\right). $$ If $A$ has singular values $\lambda$, then $H$ has eigenvalues $\pm\lambda$. So to all intents and purposes, they are the same thing in this context.

For a bit more context, there's basically two things that you need to know about for the algorithm: the spread of the eigenvalues, and how close to 0 the eigenvalues get. The spread is so that you can pick a $t$ such that $e^{iHt}$ has eigenvalues (to be determined by phase estimation) that do not loop past any $2\pi$ boundaries so there's never any ambiguity. i.e. you want $0<t\lambda<\pi$ for all singular values $\lambda$. The second issue is that the main part of the algorithm essentially calculates $1/\lambda$, which is bad news if we've identified $\lambda=0$, so we want to ensure that our phase estimation procedure is accurate enough to be able to detect that the eigenvalues are not 0.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Could you point me out to a pedagogical resource that captures the nuances of HHL? I've been going at it for a month now, and the semantics are not at all clear. $\endgroup$ – Sagnik Jan 3 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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