Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.09745 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911469336002560 |
|---|---|
| author | Tang, Kun Lai, Jun |
| author_facet | Tang, Kun Lai, Jun |
| contents | While quantum algorithms for solving large scale systems of linear equations offer potentially exponential speedups, their application has largely been confined to sparse matrices. This work extends the scope of these algorithms to a broad class of structured dense matrices arise in potential theory, covariance modeling, and computational physics, namely, hierarchically block separable (HBS) matrices. We develop two distinct methods to make these systems amenable to quantum solvers. The first is a pre-processing approach that transforms the dense matrix into a larger but sparse format. The second is a direct block encoding scheme that recursively constructs the necessary oracles from the HBS structure. We provide a detailed complexity analysis and rigorous error bounds for both methods. Numerical experiments are presented to validate the effectiveness of our approaches. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_09745 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Beyond Sparsity: Quantum Block Encoding for Dense Matrices via Hierarchically Low Rank Compression Tang, Kun Lai, Jun Quantum Physics While quantum algorithms for solving large scale systems of linear equations offer potentially exponential speedups, their application has largely been confined to sparse matrices. This work extends the scope of these algorithms to a broad class of structured dense matrices arise in potential theory, covariance modeling, and computational physics, namely, hierarchically block separable (HBS) matrices. We develop two distinct methods to make these systems amenable to quantum solvers. The first is a pre-processing approach that transforms the dense matrix into a larger but sparse format. The second is a direct block encoding scheme that recursively constructs the necessary oracles from the HBS structure. We provide a detailed complexity analysis and rigorous error bounds for both methods. Numerical experiments are presented to validate the effectiveness of our approaches. |
| title | Beyond Sparsity: Quantum Block Encoding for Dense Matrices via Hierarchically Low Rank Compression |
| topic | Quantum Physics |
| url | https://arxiv.org/abs/2602.09745 |