Quantum block encoding embeds a matrix into a larger unitary — the essential first step for most quantum algorithms that process classical data. For sparse matrices, efficient encodings exist. But many matrices arising in scientific computing are not sparse in the traditional sense — they are data-sparse, with structure captured by rank rather than nonzero count. Semiseparable matrices, where submatrices below and above the diagonal have bounded rank, are the canonical example.
This paper presents block encoding for one-pair semiseparable matrices — the simplest nontrivial case, where the off-diagonal rank is exactly one. The approach factors the matrix into products of triangular and diagonal matrices, each of which can be encoded separately. The algorithm needs 2 log(N) + 7 ancillary qubits and runs in polylogarithmic time.
The key insight is that rank structure translates into circuit depth. Sparse encoding exploits the small number of nonzero entries per row; semiseparable encoding exploits the low rank of off-diagonal blocks. These are different structural properties, and the latter covers matrices (like those from integral equations, Green's functions, and Gaussian processes) that are dense but data-sparse. The encoding makes a new class of matrices quantum-accessible.