Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra
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 <mml:math xmlns:mml="http://www.w3.org/1998...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften
2024
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/1721.1/153945 |
| _version_ | 1811075034287964160 |
|---|---|
| author | Nguyen, Quynh T. Kiani, Bobak T. Lloyd, Seth |
| author_facet | Nguyen, Quynh T. Kiani, Bobak T. Lloyd, Seth |
| author_sort | Nguyen, Quynh T. |
| collection | MIT |
| description | 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>x</mml:mi><mml:mo>,</mml:mo><mml:msup><mml:mi>x</mml:mi><mml:mo>&#x2032;</mml:mo></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math>, 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>N</mml:mi></mml:math> in time almost linear in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>N</mml:mi></mml:math> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>N</mml:mi></mml:math> to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>&#x03BA;</mml:mi><mml:mi>polylog</mml:mi><mml:mo>&#x2061;</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mfrac><mml:mi>N</mml:mi><mml:mi>&#x03B5;</mml:mi></mml:mfrac><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:math>, where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03BA;</mml:mi></mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03B5;</mml:mi></mml:math> are the condition number and error bound of the matrix operation. This runtime is near-optimal and, in terms of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>N</mml:mi></mml:math>, 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. |
| first_indexed | 2024-09-23T09:59:28Z |
| format | Article |
| id | mit-1721.1/153945 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T09:59:28Z |
| publishDate | 2024 |
| publisher | Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften |
| record_format | dspace |
| spelling | mit-1721.1/1539452024-04-20T06:13:53Z Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra Nguyen, Quynh T. Kiani, Bobak T. Lloyd, Seth Physics and Astronomy (miscellaneous) Atomic and Molecular Physics, and Optics 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>k</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>x</mml:mi><mml:mo>,</mml:mo><mml:msup><mml:mi>x</mml:mi><mml:mo>&#x2032;</mml:mo></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math>, 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>N</mml:mi></mml:math> in time almost linear in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>N</mml:mi></mml:math> 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 <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>N</mml:mi></mml:math> to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:mi>&#x03BA;</mml:mi><mml:mi>polylog</mml:mi><mml:mo>&#x2061;</mml:mo><mml:mo stretchy="false">(</mml:mo><mml:mfrac><mml:mi>N</mml:mi><mml:mi>&#x03B5;</mml:mi></mml:mfrac><mml:mo stretchy="false">)</mml:mo><mml:mo stretchy="false">)</mml:mo></mml:math>, where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03BA;</mml:mi></mml:math> and <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>&#x03B5;</mml:mi></mml:math> are the condition number and error bound of the matrix operation. This runtime is near-optimal and, in terms of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>N</mml:mi></mml:math>, 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. 2024-03-26T19:59:34Z 2024-03-26T19:59:34Z 2022-12-13 2024-03-26T19:44:13Z Article http://purl.org/eprint/type/JournalArticle 2521-327X https://hdl.handle.net/1721.1/153945 Nguyen, Quynh T., Kiani, Bobak T. and Lloyd, Seth. 2022. "Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra." Quantum, 6. en 10.22331/q-2022-12-13-876 Quantum Creative Commons Attribution https://creativecommons.org/licenses/by/4.0/ application/pdf Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften Verein zur Forderung des Open Access Publizierens in den Quantenwissenschaften |
| spellingShingle | Physics and Astronomy (miscellaneous) Atomic and Molecular Physics, and Optics Nguyen, Quynh T. Kiani, Bobak T. Lloyd, Seth Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra |
| title | Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra |
| title_full | Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra |
| title_fullStr | Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra |
| title_full_unstemmed | Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra |
| title_short | Block-encoding dense and full-rank kernels using hierarchical matrices: applications in quantum numerical linear algebra |
| title_sort | block encoding dense and full rank kernels using hierarchical matrices applications in quantum numerical linear algebra |
| topic | Physics and Astronomy (miscellaneous) Atomic and Molecular Physics, and Optics |
| url | https://hdl.handle.net/1721.1/153945 |
| work_keys_str_mv | AT nguyenquynht blockencodingdenseandfullrankkernelsusinghierarchicalmatricesapplicationsinquantumnumericallinearalgebra AT kianibobakt blockencodingdenseandfullrankkernelsusinghierarchicalmatricesapplicationsinquantumnumericallinearalgebra AT lloydseth blockencodingdenseandfullrankkernelsusinghierarchicalmatricesapplicationsinquantumnumericallinearalgebra |