Warning: Invalid argument supplied for foreach() in /home/www/wordpress/wp-content/plugins/o3po/includes/class-o3po-crossref.php on line 189
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] Guang Hao Low, Yuan Su, Yu Tong, and Minh C. Tran, "On the complexity of implementing Trotter steps", arXiv:2211.09133, (2022).
[2] Dong An, Andrew M. Childs, and Lin Lin, "Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters", arXiv:2312.03916, (2023).
[3] Christoph Sünderhauf, Earl Campbell, and Joan Camps, "Block-encoding structured matrices for data input in quantum computing", Quantum 8, 1226 (2024).
[4] Guang Hao Low, Yuan Su, Yu Tong, and Minh C. Tran, "Complexity of Implementing Trotter Steps", PRX Quantum 4 2, 020323 (2023).
[5] 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", arXiv:2407.18347, (2024).
[6] 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).
[7] Chunlin Yang, Hongmei Yao, Zexian Li, Zhaobing Fan, Guofeng Zhang, and Jianshe Liu, "Block encoding of sparse structured matrices coming from ocean acoustics in quantum computing", arXiv:2405.18007, (2024).
[8] Haoya Li, Hongkang Ni, and Lexing Ying, "On efficient quantum block encoding of pseudo-differential operators", arXiv:2301.08908, (2023).
[9] Pingzhi Li, Junyu Liu, Hanrui Wang, and Tianlong Chen, "Hybrid Quantum-Classical Scheduling for Accelerating Neural Network Training with Newton's Gradient Descent", arXiv:2405.00252, (2024).
The above citations are from SAO/NASA ADS (last updated successfully 2024-09-17 01:21:15). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref's cited-by service no data on citing works was found (last attempt 2024-09-17 01:21:14).
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