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^{\prime })$, 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 \mathrm{polylog}(\frac{N}{\epsilon }))$, where $\kappa$ and $\epsilon$ 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.

arXiv commentAdded affiliations and acknowledgments

References in corpus (24)

• Quantum algorithm for solving linear systems of equations
• Variational Quantum Algorithms
• Quantum Amplitude Amplification and Estimation
• Hamiltonian Simulation by Qubitization
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Efficient quantum algorithms for simulating sparse Hamiltonians
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Sketching as a Tool for Numerical Linear Algebra
• Quantum algorithms for algebraic problems
• Creating superpositions that correspond to efficiently integrable probability distributions
• A quantum linear system algorithm for dense matrices
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Fast inversion, preconditioned quantum linear system solvers, and fast evaluation of matrix functions
• Quantum Recommendation Systems
• Quantum Analog-Digital Conversion
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations
• Asymptotic Quantum Algorithm for the Toeplitz Systems
• An improved quantum-inspired algorithm for linear regression
• Efficient quantum circuits for Toeplitz and Hankel matrices
• Quantum algorithms for group convolution, cross-correlation, and equivariant transformations
• Hierarchical Matrix Operations on GPUs: Matrix-Vector Multiplication and Compression
• Faster quantum-inspired algorithms for solving linear systems

Cited by in corpus (9)

• Block-encoding structured matrices for data input in quantum computing
• On efficient quantum block encoding of pseudo-differential operators
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters
• Explicit block encodings of boundary value problems for many-body elliptic operators
• Thermalization in open many-body systems and KMS detailed balance
• The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts
• Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth
• Randomized adiabatic quantum linear solver algorithm with optimal complexity scaling and detailed running costs
• Quantum Simulation via Stochastic Combination of Unitaries