4
$\begingroup$

In their 2017 paper, Childs et al. gave the definition of QLSP beginning with : "Let $A$ be an $N\times N$ Hermitian matrix with known condition numbers $\kappa$, $||A|| = 1$ and at most $d$ non-zero entries in any row or column..."

I initially thought that by $||A|| = 1$ they meant that QLSP requires spectral norm (largest eigenvalue) of $A$ to be $1$, which sounds reasonable to me as even the original HHL paper they needed the eigenvalues of $A$ to lie in between $1/\kappa$ and $1$.

But, the paper: Quantum linear systems algorithms: a primer seems to have interpreted is as "the determinant of $A$ needs to be $1$" in page 28 definition 6.

Which interpretation is correct and why? In case the latter is correct, I'm not sure why it is so. I don't see why the restriction that $\text{det}(A)$ needs to be $1$ even make sense. It (the unit determinant condition) doesn't even guarantee that the eigenvalues of $A$ will be less than or equal to $1$, which is necessary for HHL to work.

$\endgroup$
4
$\begingroup$

Certainly it is meant as the largest eigenvalue. I have no idea why the linked review paper uses the determinant. I don't see anywhere that they use that property (from an admittedly brief skim).

I presume you could rewrite conditions in terms of the determinant (you would have to alter the time step $t_0$) but it's not clear to me why you would want to. It's also worth noting that definition 8 (page 39) in that paper defines matrix inversion, putting limits on the eigenvalues of the matrix: bounding between some minimum value and 1. So they're also implicitly acknowledging that structure, and certainly not setting the determinant (product of eigenvalues) to 1.

$\endgroup$
  • $\begingroup$ I think that was also a misinterpretation from them. But they say also that the unit determinant condition precludes that the matrix is not invertible. Maybe a simplification too unless $ || A || = 1 $ precludes the non-inversibility case. $\endgroup$ – cnada Aug 21 '18 at 16:22
  • $\begingroup$ @cnada You're right. A more complete definition can be found in Childs' paper (third page, bottom). $\endgroup$ – Sanchayan Dutta Aug 21 '18 at 16:29
  • 1
    $\begingroup$ Yes, non-invertible matrices have determinant 0, and this algorithm very much cares about keeping as far as possible from having an 0 eigenvalues, but that is already built in using the condition number. $\endgroup$ – DaftWullie Aug 21 '18 at 16:34

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.