arXiv:2610.13228
Block encoding of semiseparable matrices via their generators
Giacomo Antonioli, Gianna M. Del Corso, Roel Van Beeumen
Abstract
We present an explicit quantum circuit that constructs a block encoding of a generator-representable semiseparable (one-pair) matrix directly from its two generators. For an $N\times N$ semiseparable matrix with $N=2^{n}$, the circuit uses $2n+2$ ancilla qubits and has $O({\rm polylog} N)$ depth, and it realizes a $(2\sqrt{N},\,2n+2,\,2 \sqrt{2}\ \varepsilon)$-block encoding, where $\varepsilon$ is controlled by the accuracy of the state-preparation routines that load the generators. The building blocks of the circuit are cyclic shifts, swaps, and Hadamard gates, each admitting an efficient implementation through the binary decomposition of the relevant indices.
AI Summary
The paper studies how to block-encode generator-representable, rank-one semiseparable matrices directly from their generators. In the symmetric case, these have entries $S_{ij}=u_{\min(i,j)}v_{\max(i,j)}$ and include inverses of irreducible symmetric tridiagonal matrices. For $N=2^n$ and unit-norm generators, the construction gives a $(2\sqrt N,\,2n+2,\,2\sqrt2\,\varepsilon)$-block encoding using $3n+2$ total qubits, where each prepared generator has Euclidean error at most $\varepsilon$. Circuit depth is $O(\log^3 N)+D_{\mathrm{sp}}$, conditional on generator-state-preparation depth $D_{\mathrm{sp}}$. The circuit loads the generators, uses controlled swaps to create lower- and upper-triangular branches, and applies controlled cyclic shifts to separate unwanted products and position matrix entries. Hadamard interference and register permutations assemble the leading block. Correctness follows by tracking these operations; a Frobenius-norm estimate establishes the dimension-independent error bound. Circuit simulations check reconstruction accuracy, error scaling, and resource counts against FABLE. An extension handles nonsymmetric matrices specified by four generators, with normalization $\alpha=\sqrt N(w_{\rm lo}+w_{\rm up})$ and error at most $2\sqrt{w_{\rm lo}^2+w_{\rm up}^2}\,\varepsilon$, where the weights are generator-norm products. The stated limitations are conditional efficient state preparation, restriction to globally generator-representable matrices, and nonoptimal normalization: for unit-norm generators, $\|S\|_2\le\sqrt2$, leaving a possible $\sqrt N$ overhead. Hierarchical encodings can achieve $O(\log N)$ normalization but require richer data-access oracles. Removing the normalization loss and extending beyond global generator representations remain open.
During the preparation of this work, the authors used Claude (Anthropic) to improve the readability of the text and to assist in identifying relevant literature.
Central claim may not hold: The abstract omits the unit-norm-generator assumption, without which its normalization 2√N can be smaller than the target matrix's spectral norm and hence impossible. The abstract's polylogarithmic depth requires an additional efficient-state-preparation assumption; the established depth is O(log³ N)+D_sp. The unsymmetric extension uses the same R_y rotation for branch preparation and recombination, giving the upper-triangular contribution the wrong sign.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.