Quantum block encoding for semiseparable matrices

• URL: http://arxiv.org/abs/2603.19130v1
• Date: Thu, 19 Mar 2026 16:49:13 GMT
• Title: Quantum block encoding for semiseparable matrices
• Abstract summary: We present a new block encoding approach that relies on a suitable factorization of the given matrix as the product of triangular and diagonal factors.<n>To encode the matrix, the algorithm needs $2log(N)+7$ ancillary qubits. This process takes polylogarithmic time and has an error of $mathcalO(N2)$, where $N$ is the matrix size.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Quantum block encoding (QBE) is a crucial step in the development of most quantum algorithms, as it provides an embedding of a given matrix into a suitable larger unitary matrix. Historically, the development of efficient techniques for QBE has mostly focused on sparse matrices; less effort has been devoted to data-sparse (e.g., rank-structured) matrices. In this work we examine a particular case of rank structure, namely, one-pair semiseparable matrices. We present a new block encoding approach that relies on a suitable factorization of the given matrix as the product of triangular and diagonal factors. To encode the matrix, the algorithm needs $2\log(N)+7$ ancillary qubits. This process takes polylogarithmic time and has an error of $\mathcal{O}(N^2)$, where $N$ is the matrix size.

Related papers

• Two-Tower Quantum Matrix Chain Multiplication: Trading Qubits for Depth [73.08853228981701]
  Matrix chain multiplication is a problem in scientific computing, machine learning, and graph analysis.<n>We present emphTwo-Tower Matrix, a quantum subroutine that encodes the product $mathcalW$ of the $K$ matrices into a quantum state in circuit depth.
  arXiv  Detail & Related papers  (2026-07-14T18:42:40Z)
• Quantum Eigenvalue Transformations for Arbitrary Matrices [0.19116784879310025]
  We propose a simple yet powerful method to extend these ideas to arbitrary square matrices by acting on their eigenvalues.<n>We show that applying QSP to any unitary with this property is equivalent to applying a degree at most $n$ to the block-encoded $0 matrix.<n>We also provide a simple construction that transforms any block encoding into an $n$-regular one using only $O(log n)$ ancillary operations.
  arXiv  Detail & Related papers  (2026-04-21T17:11:03Z)
• 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)
• Matrix encoding method in variational quantum singular value decomposition [49.494595696663524]
  We propose the variational quantum singular value decomposition based on encoding the elements of the considered $Ntimes N$ matrix into the state of a quantum system of appropriate dimension.<n> Controlled measurement is involved to avoid small success in ancilla measurement.
  arXiv  Detail & Related papers  (2025-03-19T07:01:38Z)
• Optimal Quantization for Matrix Multiplication [29.75700570685703]
  Algorithmically, we construct a universal quantizer based on nested lattices with an explicit guarantee of approximation error.<n>A practical low-complexity version of our quantizer achieves performance quite close to optimal.
  arXiv  Detail & Related papers  (2024-10-17T17:19:48Z)
• Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth [2.4487770108795393]
  We propose an efficient block-encoding protocol for sparse matrices based on a novel data structure.<n>Non-zero elements with the same values belong to the same classification in our block-encoding protocol's dictionary.<n>Our protocol connects to linear combinations of unitaries (LCU) and the sparse access input model (SAIM)
  arXiv  Detail & Related papers  (2024-05-28T09:49:58Z)
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems [43.53835128052666]
  We propose quantum algorithms, purely quantum in nature, for calculating the determinant and inverse of an $(N-1)times (N-1)$ matrix.<n>The basic idea is to encode each row of the matrix into a pure state of some quantum system.
  arXiv  Detail & Related papers  (2024-01-29T23:23:27Z)
• Quantum Time-Space Tradeoffs for Matrix Problems [0.0]
  We consider the time and space required for quantum computers to solve a range of problems involving matrices.<n>For almost all matrices $A$, we prove that quantum circuits with at most $T$ input queries and $S$ qubits of memory require $T=Omega(n2/S)$.<n>Because many of our lower bounds match deterministic algorithms with the same time and space complexity, we show that quantum computers cannot provide any advantage for these problems with any space bound.
  arXiv  Detail & Related papers  (2024-01-10T18:38:43Z)
• A square-root speedup for finding the smallest eigenvalue [0.6597195879147555]
  We describe a quantum algorithm for finding the smallest eigenvalue of a Hermitian matrix. This algorithm combines Quantum Phase Estimation and Quantum Amplitude Estimation to achieve a quadratic speedup. We also provide a similar algorithm with the same runtime that allows us to prepare a quantum state lying mostly in the matrix's low-energy subspace.
  arXiv  Detail & Related papers  (2023-11-07T22:52:56Z)
• 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)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
  arXiv  Detail & Related papers  (2021-06-16T04:07:48Z)
• Quantum algorithms for spectral sums [50.045011844765185]
  We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices. We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
  arXiv  Detail & Related papers  (2020-11-12T16:29:45Z)

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.