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.
$\begingroup$
$\endgroup$
0
asked Aug 11, 2018 at 7:51
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
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.
If you prefer a visual, you have it here:
$\begingroup$
$\endgroup$
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.
answered Aug 11, 2018 at 8:12