Quantum block encoding for one-pair semiseparable matrices

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 2log(N)+7 ancillary qubits. Assuming that the data input oracles can be implemented with polylogarithmic depth, or that a QRAM input model is available, our proposed method requires O(polylog(N)) time and has an error of O(N2), where N is the matrix size.