Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra
Abstract
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(κpolylog⁡(Nε)), where κ and ε 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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Dec 13, 2022
- Source ID
- 10.22331/q-2022-12-13-876
Entities
People
- Bobak T. Kiani
- Quynh T. Nguyen
- Seth Lloyd
Organizations
- Air Force Office of Scientific Research
- Army Research Office
- Defense Advanced Research Projects Agency
- Massachusetts Institute of Technology