Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra
1Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, USA
2Department of Physics, Massachusetts Institute of Technology, USA
3Research Laboratory of Electronics, Massachusetts Institute of Technology, USA
4Department of Mechanical Engineering, Massachusetts Institute of Technology, USA
5Turing Inc., Cambridge, MA, USA
| Published: | 2022-12-13, volume 6, page 876 |
| Eprint: | arXiv:2201.11329v4 |
| Doi: | https://doi.org/10.22331/q-2022-12-13-876 |
| Citation: | Quantum 6, 876 (2022). |
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
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(\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.
Featured image: A kernel matrix is decomposed into hierarchically structured blocks, enabling an efficient block-encoding on quantum computers.
► BibTeX data
► References
[1] Aram W. Harrow, Avinatan Hassidim, and Seth Lloyd, ``Quantum Algorithm for Linear Systems of Equations'' Physical Review Letters 103 (2009).
https://doi.org/10.1103/PhysRevLett.103.150502
[2] Andrew M. Childs, Robin Kothari, and Rolando D. Somma, ``Quantum Algorithm for Systems of Linear Equations with Exponentially Improved Dependence on Precision'' SIAM Journal on Computing 46, 1920–1950 (2017).
https://doi.org/10.1137/16M1087072
[3] András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe, ``Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics'' Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing 193–204 (2019).
https://doi.org/10.48550/arXiv.1806.01838
[4] Iordanis Kerenidisand Anupam Prakash ``Quantum Recommendation Systems'' (2016).
https://doi.org/10.48550/arXiv.1603.08675
[5] Leonard Wossnig, Zhikuan Zhao, and Anupam Prakash, ``Quantum Linear System Algorithm for Dense Matrices'' Physical Review Letters 120 (2018).
https://doi.org/10.1103/PhysRevLett.120.050502
[6] András Gilyén, Zhao Song, and Ewin Tang, ``An improved quantum-inspired algorithm for linear regression'' Quantum 6, 754 (2022).
https://doi.org/10.22331/q-2022-06-30-754
[7] Changpeng Shaoand Ashley Montanaro ``Faster quantum-inspired algorithms for solving linear systems'' (2021).
https://doi.org/10.48550/arXiv.2103.10309
[8] David P. Woodruff ``Sketching as a tool for numerical linear algebra'' Foundations and Trends in Theoretical Computer Science 10, 1–157 (2014).
https://doi.org/10.1561/0400000060
[9] Lin-Chun Wan, Chao-Hua Yu, Shi-Jie Pan, Fei Gao, Qiao-Yan Wen, and Su-Juan Qin, ``Asymptotic quantum algorithm for the Toeplitz systems'' Physical Review A 97 (2018).
https://doi.org/10.1103/physreva.97.062322
[10] A Mahasingheand J B Wang ``Efficient quantum circuits for Toeplitz and Hankel matrices'' Journal of Physics A: Mathematical and Theoretical 49, 275301 (2016).
https://doi.org/10.1088/1751-8113/49/27/275301
[11] Grecia Castelazo, Quynh T Nguyen, Giacomo De Palma, Dirk Englund, Seth Lloyd, and Bobak T Kiani, ``Quantum algorithms for group convolution, cross-correlation, and equivariant transformations'' Physical Review A 106, 032402 (2022).
https://doi.org/10.1103/PhysRevA.106.032402
[12] Andrew M. Childsand Wim van Dam ``Quantum algorithms for algebraic problems'' Reviews of Modern Physics 82, 1–52 (2010).
https://doi.org/10.1103/revmodphys.82.1
[13] R Beatsonand Leslie Greengard ``A short course on fast multipole methods'' Oxford University Press (1997).
[14] Kendall Atkinsonand Weimin Han ``Numerical solution of fredholm integral equations of the second kind'' Springer (2009).
https://doi.org/10.1007/978-1-4419-0458-4_12
[15] Carl Edward Rasmussen ``Gaussian processes in machine learning'' Summer school on machine learning 63–71 (2003).
https://doi.org/10.1007/978-3-540-28650-9_4
[16] W. Hackbusch ``A Sparse Matrix Arithmetic Based on $\mathcal{H}$-Matrices. Part I: Introduction to $\mathcal{H}$-Matrices'' Computing 62, 89–108 (1999).
https://doi.org/10.1007/s006070050015
[17] W. Hackbuschand B. N. Khoromskij ``A Sparse $\mathcal{H}$-Matrix Arithmetic. Part II: Application to Multi-Dimensional Problems'' Computing 64, 21–47 (2000).
https://doi.org/10.1007/PL00021408
[18] Guang Hao Lowand Isaac L. Chuang ``Hamiltonian Simulation by Qubitization'' Quantum 3, 163 (2019).
https://doi.org/10.22331/q-2019-07-12-163
[19] Shantanav Chakraborty, András Gilyén, and Stacey Jeffery, ``The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation'' ICALP (2019).
https://doi.org/10.4230/LIPIcs.ICALP.2019.33
[20] Guang Hao Lowand Isaac L. Chuang ``Optimal Hamiltonian Simulation by Quantum Signal Processing'' Physical Review Letters 118 (2017).
https://doi.org/10.1103/physrevlett.118.010501
[21] Joran van Apeldoornand András Gilyén ``Improvements in Quantum SDP-Solving with Applications'' ICALP (2019).
https://doi.org/10.4230/LIPIcs.ICALP.2019.99
[22] Pedro CS Costa, Dong An, Yuval R Sanders, Yuan Su, Ryan Babbush, and Dominic W Berry, ``Optimal Scaling Quantum Linear-Systems Solver via Discrete Adiabatic Theorem'' PRX Quantum 3, 040303 (2022).
https://doi.org/10.1103/PRXQuantum.3.040303
[23] Josh Barnesand Piet Hut ``A hierarchical O(N log N) force-calculation algorithm'' Nature 324, 446–449 (1986).
https://doi.org/10.1038/324446a0
[24] Steffen Börm, Lars Grasedyck, and Wolfgang Hackbusch, ``Introduction to hierarchical matrices with applications'' Engineering Analysis with Boundary Elements 27, 405–422 (2003).
https://doi.org/10.1016/S0955-7997(02)00152-2
[25] Markus Fennand Gabriele Steidl ``FMM and H-matrices: A Short Introduction to the Basic Idea'' report (2002).
https://madoc.bib.uni-mannheim.de/744/1/TR-02-008.pdf
[26] W. Hackbusch, B. Khoromskij, and S. A. Sauter, ``On $\mathcal{H}^2$-matrices'' Lectures on Applied Mathematics 9–29 (2000).
https://doi.org/10.1007/978-3-642-59709-1_2
[27] J. Carrier, L. Greengard, and V. Rokhlin, ``A Fast Adaptive Multipole Algorithm for Particle Simulations'' SIAM J. Sci. Stat. Comput. 9, 669–686 (1988).
https://doi.org/10.1137/0909044
[28] Jaswinder Pal Singh, Chris Holt, John L Hennessy, and Anoop Gupta, ``A parallel adaptive fast multipole method'' Proceedings of the 1993 ACM/IEEE Conference on Supercomputing 54–65 (1993).
https://doi.org/10.1145/169627.169651
[29] E. Tyrtyshnikov ``Mosaic-Skeleton approximations'' Calcolo 33, 47–57 (1996).
https://doi.org/10.1007/BF02575706
[30] Achi Brandt ``Multilevel computations of integral transforms and particle interactions with oscillatory kernels'' Computer Physics Communications 65, 24–38 (1991).
https://doi.org/10.1016/0010-4655(91)90151-A
https://www.sciencedirect.com/science/article/pii/001046559190151A
[31] Gregory Beylkin, Ronald R. Coifman, and Vladimir Rokhlin, ``Fast wavelet transforms and numerical algorithms I'' Communications on Pure and Applied Mathematics 44, 141–183 (1991).
https://doi.org/10.1002/cpa.3160440202
[32] Robin Kothari ``Efficient algorithms in quantum query complexity'' thesis (2014).
https://uwspace.uwaterloo.ca/handle/10012/8625
[33] Yihui Quekand Patrick Rebentrost ``Fast algorithm for quantum polar decomposition, pretty-good measurements, and the Procrustes problem'' (2021).
https://doi.org/10.48550/arXiv.2106.07634
[34] Lov Groverand Terry Rudolph ``Creating superpositions that correspond to efficiently integrable probability distributions'' (2002).
https://doi.org/10.48550/arXiv.quant-ph/0208112
[35] Michael A. Nielsenand Isaac Chuang ``Quantum Computation and Quantum Information'' Cambridge University Press chapter 3 (2011).
https://doi.org/10.1017/CBO9780511976667
[36] George B. Arfken, Hans J. Weber, and Frank E. Harris, ``Chapter 10 - Green's Functions'' Academic Press (2013).
https://doi.org/10.1016/B978-0-12-384654-9.00010-4
[37] Yuwei Fan, Lin Lin, Lexing Ying, and Leonardo Zepeda-Nún͂ez, ``A Multiscale Neural Network Based on Hierarchical Matrices'' Multiscale Modeling & Simulation 17, 1189–1213 (2019).
https://doi.org/10.1137/18M1203602
[38] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp, ``Quantum amplitude amplification and estimation'' Quantum Computation and Information 53–74 (2002).
https://doi.org/10.1090/conm/305/05215
[39] L. Greengardand V. Rokhlin ``A fast algorithm for particle simulations'' Journal of Computational Physics 73, 325–348 (1987).
https://doi.org/10.1016/0021-9991(87)90140-9
https://www.sciencedirect.com/science/article/pii/0021999187901409
[40] Kosuke Mitarai, Masahiro Kitagawa, and Keisuke Fujii, ``Quantum analog-digital conversion'' Physical Review A 99, 012301 (2019).
https://doi.org/10.1103/PhysRevA.99.012301
[41] P. K. Kythe ``An introduction to boundary element methods (1st ed.)'' CRC Press (1995).
[42] W. Hackbusch ``The Panel Clustering Method for BEM'' Discretization Methods in Structural Mechanics 299–306 (1990).
https://doi.org/10.1007/978-3-642-49373-7_28
[43] Yu Tong, Dong An, Nathan Wiebe, and Lin Lin, ``Fast inversion, preconditioned quantum linear system solvers, fast Green’s-function computation, and fast evaluation of matrix functions'' Physical Review A 104 (2021).
https://doi.org/10.1103/physreva.104.032422
[44] Lin Lin, Jianfeng Lu, and Lexing Ying, ``Fast construction of hierarchical matrix representation from matrix–vector multiplication'' Journal of Computational Physics 230, 4071–4087 (2011).
https://doi.org/10.1016/j.jcp.2011.02.033
[45] Yuwei Fan, Jordi Feliu-Faba, Lin Lin, Lexing Ying, and Leonardo Zepeda-Núnez, ``A multiscale neural network based on hierarchical nested bases'' Research in the Mathematical Sciences 6, 1–28 (2019).
https://doi.org/10.1007/s40687-019-0183-3
[46] Marco Cerezo, Andrew Arrasmith, Ryan Babbush, Simon C Benjamin, Suguru Endo, Keisuke Fujii, Jarrod R McClean, Kosuke Mitarai, Xiao Yuan, and Lukasz Cincio, ``Variational quantum algorithms'' Nature Reviews Physics 3, 625–644 (2021).
https://doi.org/10.1038/s42254-021-00348-9
[47] Dominic W. Berry, Graeme Ahokas, Richard Cleve, and Barry C. Sanders, ``Efficient Quantum Algorithms for Simulating Sparse Hamiltonians'' Communications in Mathematical Physics 270, 359–371 (2007).
https://doi.org/10.1007/s00220-006-0150-x
[48] Andris Ambainis ``Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations'' (2010).
https://doi.org/10.48550/arXiv.1010.4458
[49] Yiğit Subaşı, Rolando D. Somma, and Davide Orsucci, ``Quantum Algorithms for Systems of Linear Equations Inspired by Adiabatic Quantum Computing'' Phys. Rev. Lett. 122, 060504 (2019).
https://doi.org/10.1103/PhysRevLett.122.060504
[50] Dong Anand Lin Lin ``Quantum Linear System Solver Based on Time-optimal Adiabatic Quantum Computing and Quantum Approximate Optimization Algorithm'' ACM Transactions on Quantum Computing 3, 1–28 (2022).
https://doi.org/10.1145/3498331
[51] Lin Linand Yu Tong ``Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems'' Quantum 4, 361 (2020).
https://doi.org/10.22331/q-2020-11-11-361
[52] Jonathan M. Borweinand Peter B. Borwein ``Pi and the AGM: A Study in the Analytic Number Theory and Computational Complexity'' Wiley-Interscience (1987).
[53] Sanjeev Aroraand Boaz Barak ``Computational Complexity: A Modern Approach'' Cambridge University Press (2009).
https://doi.org/10.1017/CBO9780511804090
[54] Steffen Börm, Lars Grasedyck, and Wolfgang Hackbusch, ``Lecture notes on Hierarchical Matrices'' (2003).
[55] Wajih Halim Boukaram, George Turkiyyah, and David E. Keyes, ``Hierarchical Matrix Operations on GPUs: Matrix-Vector Multiplication and Compression'' (2019).
https://doi.org/10.48550/arXiv.1902.01829
Cited by
[1] Junpeng Hu, Shi Jin, Nana Liu, and Lei Zhang, "Quantum random feature method for solving partial differential equations", Discrete and Continuous Dynamical Systems 55, 497 (2026).
[2] Chunlin Yang, Zexian Li, Hongmei Yao, Zhaobing Fan, Guofeng Zhang, and Jianshe Liu, "Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth", Quantum 9, 1805 (2025).
[3] Joseph Peetz, Scott E. Smart, and Prineha Narang, "Quantum simulation via stochastic combination of unitaries", npj Quantum Information 12 1, 52 (2026).
[4] Jinchuan Yang, Shiping He, Mingqiang Bai, and Zhiwen Mo, "Quantum positive matrix-positive matrix multiplication algorithm", Journal of Physics A: Mathematical and Theoretical 57 43, 435305 (2024).
[5] Jing 静 Li 李, Yanqi 燕琪 Song 宋, Sujuan 素娟 Qin 秦, Wenmin 文敏 Li 李, and Fei 飞 Gao 高, "Quantum algorithm for marginal Fisher analysis", Chinese Physics B 34 12, 120302 (2025).
[6] Dong An, Akwum Onwunta, and Gengzhi Yang, "Fast-forwarding quantum algorithms for linear dissipative differential equations", Quantum 10, 1986 (2026).
[7] Matteo Scandi and Álvaro M. Alhambra, "Thermalization in Open Many-Body Systems and KMS Detailed Balance", Physical Review X 16 1, 011040 (2026).
[8] Haoya Li, Hongkang Ni, and Lexing Ying, "On efficient quantum block encoding of pseudo-differential operators", Quantum 7, 1031 (2023).
[9] Tyler Kharazi, Ahmad M. Alkadri, Jin-Peng Liu, Kranthi K. Mandadapu, and K. Birgitta Whaley, "Explicit block encodings of boundary value problems for many-body elliptic operators", Quantum 9, 1764 (2025).
[10] Xiantao Li, "From Linear Differential Equations to Unitaries: A Moment-Matching Dilation Framework with Near-Optimal Quantum Algorithms", PRX Quantum 7 2, 020350 (2026).
[11] Mauro E. S. Morales, Lirandë Pira, Philipp Schleich, Kelvin Koor, Pedro C. S. Costa, Dong An, Alán Aspuru-Guzik, Lin Lin, Patrick Rebentrost, and Dominic W. Berry, "Quantum linear system solvers: A survey of algorithms and applications", Reviews of Modern Physics 98 2, 025005 (2026).
[12] Cezary Pilaszewicz, 2026 IEEE Conference on Artificial Intelligence (CAI) 1968 (2026) ISBN:979-8-3315-6039-3.
[13] Junpeng Hu, Jinglai Li, Lei Zhang, and Shi Jin, "A quantum gradient descent algorithm for optimizing Gaussian process models", Mathematical Models and Methods in Applied Sciences 36 08, 1715 (2026).
[14] Yong-Mei Li, Hai-Ling Liu, Shi-Jie Pan, Su-Juan Qin, Fei Gao, and Qiao-Yan Wen, "General quantum matrix exponential dimensionality-reduction framework based on block encoding", Physical Review A 108 4, 042418 (2023).
[15] David Jennings, Matteo Lostaglio, Robert B. Lowrie, Sam Pallister, and Andrew T. Sornborger, "The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts", Quantum 8, 1553 (2024).
[16] Yunah Choi, Jeihee Cho, and Shiho Kim, Advances in Computers 140, 1 (2026) ISBN:9780443223822.
[17] Dong An, Andrew M. Childs, and Lin Lin, "Quantum Algorithm for Linear Non-unitary Dynamics with Near-Optimal Dependence on All Parameters", Communications in Mathematical Physics 407 1, 19 (2026).
[18] Christoph Sünderhauf, Earl Campbell, and Joan Camps, "Block-encoding structured matrices for data input in quantum computing", Quantum 8, 1226 (2024).
[19] Dekuan Dong, Yingzhou Li, and Jungong Xue, "Products between Block-encodings", (2026).
[20] Zexian Li, Xiao-Ming Zhang, Chunlin Yang, and Guofeng Zhang, "Binary Tree Block Encoding of Classical Matrix", IEEE Transactions on Quantum Engineering 7, 1 (2026).
[21] David Jennings, Matteo Lostaglio, Sam Pallister, Andrew T. Sornborger, and Yiğit Subaşı, "Randomized Adiabatic Quantum Linear Solver Algorithm with Optimal Complexity Scaling and Detailed Running Costs", PRX Quantum 6 4, 040373 (2025).
[22] Filippo Della Chiara, Martina Nibbi, Yizhi Shen, and Roel Van Beeumen, "Efficient LCU block encodings through Dicke states preparation", arXiv:2507.20887, (2025).
[23] Guang Hao Low, Yuan Su, Yu Tong, and Minh C. Tran, "Complexity of Implementing Trotter Steps", PRX Quantum 4 2, 020323 (2023).
[24] Xi-Ning Zhuang, Zhao-Yun Chen, Ming-Yang Tan, Jiaxuan Zhang, Chuang-Chao Ye, Tian-Hao Wei, Teng-Yang Ma, Cheng Xue, Huan-Yu Liu, Qing-Song Li, Tai-Ping Sun, Xiao-Fan Xu, Yun-Jie Wang, Yu-Chun Wu, and Guo-Ping Guo, "A Pathway to Practical Quantum Advantage in Solving Navier-Stokes Equations", arXiv:2509.08807, (2025).
[25] Ahmad M. Alkadri, Tyler D. Kharazi, K. Birgitta Whaley, and Kranthi K. Mandadapu, "A Quantum Algorithm for the Finite Element Method", arXiv:2510.18150, (2025).
[26] Guang Hao Low, Yuan Su, Yu Tong, and Minh C. Tran, "On the complexity of implementing Trotter steps", arXiv:2211.09133, (2022).
[27] Pingzhi Li, Junyu Liu, Hanrui Wang, and Tianlong Chen, "Q-Newton: Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent", arXiv:2405.00252, (2024).
[28] Haoya Li, Hongkang Ni, and Lexing Ying, "On efficient quantum block encoding of pseudo-differential operators", arXiv:2301.08908, (2023).
[29] Rakshit M. Gharat, Gopikrishnan Muraleedharan, Dominic W. Berry, and Gavin K. Brennen, "Quantum algorithm for solving differential equations using SLAC derivatives", arXiv:2605.04861, (2026).
[30] Alessandro Andrea Zecchi, Claudio Sanavio, Luca Cappelli, Simona Perotto, Alessandro Roggero, and Sauro Succi, "Block encoding of sparse matrices with a periodic diagonal structure", arXiv:2602.10589, (2026).
[31] Dekuan Dong, Yingzhou Li, and Jungong Xue, "Products between block-encodings", arXiv:2509.15779, (2025).
[32] Kun Tang and Jun Lai, "Beyond Sparsity: Quantum Block Encoding for Dense Matrices via Hierarchically Low Rank Compression", arXiv:2602.09745, (2026).
The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 15:31:48) and SAO/NASA ADS (last updated successfully 2026-08-09 15:31:50). The list may be incomplete as not all publishers provide suitable and complete citation data.
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.
Pingback: Research Roundup for December 2022 - Quantum Computing Report