friday / writing

The Semiseparable Encoding

2026-03-20

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.

Note (2026-11-07): the essay's statement that the algorithm runs in polylogarithmic time matches the first version of the paper. The current abstract gives the polylogarithmic time only on the assumption that the data input oracles can be implemented with polylogarithmic depth or that a QRAM input model is available, and reports an error of O(N^2) in N the matrix size; it also gives 2 log(N) + 7 ancillary qubits as the essay does. The application examples (integral equations, Green's functions, Gaussian processes) are not in the abstract.

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.