Beyond Sparsity: Quantum Block Encoding for Dense Matrices via Hierarchically Low Rank Compression

• URL: http://arxiv.org/abs/2602.09745v2
• Date: Wed, 11 Feb 2026 06:21:44 GMT
• Title: Beyond Sparsity: Quantum Block Encoding for Dense Matrices via Hierarchically Low Rank Compression
• Authors: Kun Tang, Jun Lai,
• Abstract summary: Quantum algorithms for solving large scale systems of linear equations offer potential speedups.<n>This work extends the scope of these algorithms to a broad class of structured dense matrices.<n>We develop two distinct methods to make these systems amenable to quantum solvers.
• Score: 7.18483139409948
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: While quantum algorithms for solving large scale systems of linear equations offer potential 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.

Related papers

• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• On Encoding Matrices using Quantum Circuits [5.877573384886684]
  We study encodings matrices in the form of block encodings and state preparation circuits.<n>Two key results we establish are: (a) a general method for efficiently constructing a block encoding of an arbitrary matrix given in classical form, and (b) low-overhead, bidirectional conversion algorithms between block encodings and state preparation circuits.
  arXiv  Detail & Related papers  (2025-10-22T21:20:08Z)
• Efficient Quantum Access Model for Sparse Structured Matrices using Linear Combination of Things [0.6138671548064355]
  We present a novel framework for Linear Combination of Unitaries (LCU)-style decomposition tailored to structured sparse matrices.<n>LCU is a foundational primitive in both variational and fault-tolerant quantum algorithms.<n>We introduce the Sigma basis, a compact set of simple, non-unitary operators that can better capture sparsity and structure.
  arXiv  Detail & Related papers  (2025-07-04T17:05:07Z)
• Controlled measurement, Hermitian conjugation and normalization in matrix-manipulation algorithms [46.13392585104221]
  We introduce the concept of controlled measurement that solves the problem of small access probability to the desired state of ancilla.<n>Separate encoding of the real and imaginary parts of a complex matrix allows to include the Hermitian conjugation into the list of matrix manipulations.<n>We weaken the constraints on the absolute values of matrix elements unavoidably imposed by the normalization condition for a pure quantum state.
  arXiv  Detail & Related papers  (2025-03-27T08:49:59Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• A general quantum matrix exponential dimensionality reduction framework based on block-encoding [4.501305807267216]
  Matrix Exponential Dimensionality Reduction (MEDR) deals with the small-sample-size problem that appears in linear Dimensionality Reduction (DR) algorithms. High complexity is the bottleneck in this type of DR algorithm because one has to solve a large-scale matrix exponential eigenproblem. We design a general quantum algorithm framework for MEDR based on the block-encoding technique.
  arXiv  Detail & Related papers  (2023-06-16T03:36:03Z)
• Quantum algorithms for grid-based variational time evolution [36.136619420474766]
  We propose a variational quantum algorithm for performing quantum dynamics in first quantization. Our simulations exhibit the previously observed numerical instabilities of variational time propagation approaches.
  arXiv  Detail & Related papers  (2022-03-04T19:00:45Z)
• High-Dimensional Sparse Bayesian Learning without Covariance Matrices [66.60078365202867]
  We introduce a new inference scheme that avoids explicit construction of the covariance matrix. Our approach couples a little-known diagonal estimation result from numerical linear algebra with the conjugate gradient algorithm. On several simulations, our method scales better than existing approaches in computation time and memory.
  arXiv  Detail & Related papers  (2022-02-25T16:35:26Z)
• Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
  We propose quantum algorithms for matrix operations using the "Sender-Receiver" model. These quantum protocols can be used as subroutines in other quantum schemes.
  arXiv  Detail & Related papers  (2022-02-10T08:12:20Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59:55Z)
• Quantum-Inspired Algorithms from Randomized Numerical Linear Algebra [53.46106569419296]
  We create classical (non-quantum) dynamic data structures supporting queries for recommender systems and least-squares regression. We argue that the previous quantum-inspired algorithms for these problems are doing leverage or ridge-leverage score sampling in disguise.
  arXiv  Detail & Related papers  (2020-11-09T01:13:07Z)
• Block-encoding based quantum algorithm for linear systems with displacement structures [4.145426157018113]
  We present efficient and memory-reduced quantum algorithms for solving linear systems with displacement structures. The proposed block-encodings provide a quadratic speedup with respect to the dimension over classical algorithms. One of the quantum linear system solvers is applied to the linear prediction of time series.
  arXiv  Detail & Related papers  (2019-12-27T16:10:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.