  Many quantum algorithms for numerical linear algebra assume black-box access
to a block-encoding of the matrix of interest, which is a strong assumption
when the matrix is not sparse. Kernel matrices, which arise from discretizing a
kernel function $k(x,x')$, have a variety of applications in mathematics and
engineering. They are generally dense and full-rank. Classically, the
celebrated fast multipole method performs matrix multiplication on kernel
matrices of dimension $N$ in time almost linear in $N$ by using the linear
algebraic framework of hierarchical matrices. In light of this success, we
propose a block-encoding scheme of the hierarchical matrix structure on a
quantum computer. When applied to many physical kernel matrices, our method can
improve the runtime of solving quantum linear systems of dimension $N$ to
$O(\kappa \operatorname{polylog}(\frac{N}{\varepsilon}))$, where $\kappa$ and
$\varepsilon$ are the condition number and error bound of the matrix operation.
This runtime is near-optimal and, in terms of $N$, exponentially improves over
prior quantum linear systems algorithms in the case of dense and full-rank
kernel matrices. We discuss possible applications of our methodology in solving
integral equations and accelerating computations in N-body problems.
