Efficient Quantum Access Model for Sparse Structured Matrices using Linear Combination of Things

• URL: http://arxiv.org/abs/2507.03714v2
• Date: Sat, 26 Jul 2025 05:21:16 GMT
• Title: Efficient Quantum Access Model for Sparse Structured Matrices using Linear Combination of Things
• Authors: Abeynaya Gnanasekaran, Amit Surana,
• Abstract summary: 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.
• Score: 0.6138671548064355
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a novel framework for Linear Combination of Unitaries (LCU)-style decomposition tailored to structured sparse matrices, which frequently arise in the numerical solution of partial differential equations (PDEs). While LCU is a foundational primitive in both variational and fault-tolerant quantum algorithms, conventional approaches based on the Pauli basis can require a number of terms that scales quadratically with matrix size. We introduce the Sigma basis, a compact set of simple, non-unitary operators that can better capture sparsity and structure, enabling decompositions with only polylogarithmic scaling in the number of terms. We develop both numerical and semi-analytical methods for computing Sigma basis decompositions of arbitrary matrices. Given this new basis is comprised of non-unitary operators, we leverage the concept of unitary completion to design efficient quantum circuits for evaluating observables in variational quantum algorithms and for constructing block encodings in fault-tolerant quantum algorithms. We compare our method to related techniques like unitary dilation, and demonstrate its effectiveness through several PDE examples, showing exponential improvements in decomposition size while retaining circuit efficiency.

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)
• Beyond Sparsity: Quantum Block Encoding for Dense Matrices via Hierarchically Low Rank Compression [7.18483139409948]
  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.
  arXiv  Detail & Related papers  (2026-02-10T12:56:49Z)
• Amplitude-Phase Separation toward Optimal and Fast-Forwardable Simulation of Non-Unitary Dynamics [39.740772144144366]
  Amplitude-Phase Separation (APS) methods formulates any non-unitary evolution into separate simulation of a unitary operator and a Hermitian operator.<n>APS provides an effective and generic pathway for developing efficient quantum algorithms for general non-unitary dynamics.
  arXiv  Detail & Related papers  (2026-02-10T09:23:55Z)
• Quantum Approximate Optimization Algorithm for MIMO with Quantized b-bit Beamforming [47.98440449939344]
  Multiple-input multiple-output (MIMO) is critical for 6G communication, offering improved spectral efficiency and reliability.<n>This paper explores the use of the Quantum Approximate Optimization Algorithm (QAOA) and alternating optimization to address the problem of b-bit quantized phase shifters both at the transmitter and the receiver.<n>We demonstrate that the structure of this quantized beamforming problem aligns naturally with hybrid-classical methods like QAOA, as the phase shifts used in beamforming can be directly mapped to rotation gates in a quantum circuit.
  arXiv  Detail & Related papers  (2025-10-07T17:53:02Z)
• Efficient and Explicit Block Encoding of Finite Difference Discretizations of the Laplacian [0.0]
  We present an efficient and explicit block encoding method that enhances existing approaches in key aspects.<n>We detail the construction of the quantum algorithm and illustrate how it leverages the unique structure of finite difference discretizations.
  arXiv  Detail & Related papers  (2025-09-02T15:31:43Z)
• Understanding Incremental Learning with Closed-form Solution to Gradient Flow on Overparamerterized Matrix Factorization [44.278609916888065]
  gradient flow learns a target matrix by sequentially learning its singular values in decreasing order of magnitude over time.<n>We show that incremental learning emerges from some time-scale separation among dynamics corresponding to learning different components in the target matrix.
  arXiv  Detail & Related papers  (2025-08-28T01:36:42Z)
• An em algorithm for quantum Boltzmann machines [40.40469032705598]
  We develop a quantum version of the em algorithm for training quantum Boltzmann machines.<n>We implement the algorithm on a semi-quantum restricted Boltzmann machine, where quantum effects are confined to the hidden layer.
  arXiv  Detail & Related papers  (2025-07-29T07:59:22Z)
• Quantum Framework for Simulating Linear PDEs with Robin Boundary Conditions [0.6144680854063939]
  We propose an explicit, oracle-free quantum framework for numerically simulating general linear partial differential equations (PDEs)<n>Our approach begins with a general finite-difference discretization and applies the Schrodingerisation technique to transform the resulting system into one that admits unitary quantum evolution.
  arXiv  Detail & Related papers  (2025-06-25T14:23:38Z)
• High order schemes for solving partial differential equations on a quantum computer [0.0]
  We show that higher-order methods can reduce the number of qubits necessary for discretization, similar to the classical case.<n>This result has important consequences for the practical application of quantum algorithms based on Hamiltonian evolution.
  arXiv  Detail & Related papers  (2024-12-26T14:21:59Z)
• Double-Logarithmic Depth Block-Encodings of Simple Finite Difference Method's Matrices [0.0]
  Solving differential equations is one of the most computationally expensive problems in classical computing. Despite recent progress made in the field of quantum computing and quantum algorithms, its end-to-end application towards practical realization still remains unattainable.
  arXiv  Detail & Related papers  (2024-10-07T17:44:30Z)
• Non-Unitary Quantum Machine Learning [0.0]
  We introduce several probabilistic quantum algorithms that overcome the normal unitary restrictions in quantum machine learning. We show that residual connections between layers of a variational ansatz can prevent barren plateaus in models which would otherwise contain them. We also demonstrate a novel rotationally invariant encoding for point cloud data via Schur-Weyl duality.
  arXiv  Detail & Related papers  (2024-05-27T17:42:02Z)
• Efficient Variational Quantum Linear Solver for Structured Sparse Matrices [0.6138671548064355]
  We show that by using an alternate basis one can better exploit the sparsity and underlying structure of matrix. We employ the concept of unitary completion to design efficient quantum circuits for computing the global/local VQLS cost functions.
  arXiv  Detail & Related papers  (2024-04-25T19:22:05Z)
• Quantum eigenvalue processing [0.0]
  Problems in linear algebra can be solved on a quantum computer by processing eigenvalues of the non-normal input matrices. We present a Quantum EigenValue Transformation (QEVT) framework for applying arbitrary transformations on eigenvalues of block-encoded non-normal operators. We also present a Quantum EigenValue Estimation (QEVE) algorithm for operators with real spectra.
  arXiv  Detail & Related papers  (2024-01-11T19:49:31Z)
• 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 hybrid quantum-classical algorithm for multichannel quantum scattering of atoms and molecules [62.997667081978825]
  We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions. The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix. We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
  arXiv  Detail & Related papers  (2023-04-12T18:10:47Z)
• General quantum algorithms for Hamiltonian simulation with applications to a non-Abelian lattice gauge theory [44.99833362998488]
  We introduce quantum algorithms that can efficiently simulate certain classes of interactions consisting of correlated changes in multiple quantum numbers. The lattice gauge theory studied is the SU(2) gauge theory in 1+1 dimensions coupled to one flavor of staggered fermions. The algorithms are shown to be applicable to higher-dimensional theories as well as to other Abelian and non-Abelian gauge theories.
  arXiv  Detail & Related papers  (2022-12-28T18:56:25Z)
• Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
  tensor network (TN) algorithms can be mapped to parametrized quantum circuits (PQCs) We propose a new protocol for approximating TN states using realistic quantum circuits. Our results reveal one particular protocol, involving sequential growth and optimization of the quantum circuit, to outperform all other methods.
  arXiv  Detail & Related papers  (2022-09-01T17:08:41Z)
• Unitary Approximate Message Passing for Matrix Factorization [90.84906091118084]
  We consider matrix factorization (MF) with certain constraints, which finds wide applications in various areas. We develop a Bayesian approach to MF with an efficient message passing implementation, called UAMPMF. We show that UAMPMF significantly outperforms state-of-the-art algorithms in terms of recovery accuracy, robustness and computational complexity.
  arXiv  Detail & Related papers  (2022-07-31T12:09:32Z)
• Explicit Quantum Circuits for Block Encodings of Certain Sparse Matrices [4.2389474761558406]
  We show how efficient quantum circuits can be explicitly constructed for some well-structured matrices. We also provide implementations of these quantum circuits in sparse strategies.
  arXiv  Detail & Related papers  (2022-03-19T03:50:16Z)
• 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)
• Joint Network Topology Inference via Structured Fusion Regularization [70.30364652829164]
  Joint network topology inference represents a canonical problem of learning multiple graph Laplacian matrices from heterogeneous graph signals. We propose a general graph estimator based on a novel structured fusion regularization. We show that the proposed graph estimator enjoys both high computational efficiency and rigorous theoretical guarantee.
  arXiv  Detail & Related papers  (2021-03-05T04:42:32Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)

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.