7
$\begingroup$

In many sources (like on Page 30 here), I found that the complexity of the original Harrow Hassidim Lloyd is stated as $\mathcal{O}(\log (N) s^2 \kappa^2/\epsilon)$ where $s$ is said to be the "matrix sparsity". What is a precise definition of the term "matrix sparsity"? I couldn't find it stated anywhere.

$\endgroup$
7
$\begingroup$

You have the definitions in your paper you link page 12. Simply said, it is a matrix with many 0s.
As an example take N = 16, and the polynomial function is just a simple function like 1.5*X, then your matrix has at most 1.5*log(16,2)=6 non-zero entries per row.

Definitions of sparsity

If you prefer a visual, you have it here:

enter image description here

$\endgroup$
2
$\begingroup$

I believe the way they use it is as

The maximum number of non-zero elements in any row.

Although that’s different to the way Wikipedia defines sparsity, which is essentially the average:

the total number of non-zero elements divided by the number of elements.

$\endgroup$

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.