9

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.

blunova
  • 201
  • 1
  • 3
  • 11
Sanchayan Dutta
  • 17,945
  • 8
  • 50
  • 112

2 Answers2

8

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

cnada
  • 4,802
  • 1
  • 9
  • 22
3

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.

DaftWullie
  • 62,671
  • 4
  • 55
  • 140