Condition number

The condition number of a matrix is the ratio of its largest singular value to its smallest. For a Hermitian matrix the singular values are the absolute values of the eigenvalues, so Harrow, Hassidim, and Lloyd can describe κ as the ratio of the largest eigenvalue magnitude to the smallest. They normalize the matrix so that this ratio is the only scale left: singular values between 1/κ and 1.

A large condition number means the matrix is close to one that cannot be inverted, and the solution moves a lot when the input is perturbed. In HHL the same quantity is a cost. The 2009 runtime grows as κ squared. A later algorithm brings the dependence on κ down to nearly linear and does not remove it. HHL's Theorem 4 says that a dependence better than κ to the power 1 minus δ, for a positive δ, would imply BQP equals PSPACE. If κ itself grows as a power of the dimension, the polylogarithmic dependence on the dimension stops being the leading term.

The phase estimation subroutine is how those eigenvalues are read. The condition number is not a property of that subroutine. It is a property of the matrix whose eigenvalues are being inverted.