Clean sparse-state preparation from sorted XOR locations

For $x<M$ and $l<d$, let $F_x(l)$ be the listed column if $x<N$ and that slot exists, and $N+l$ otherwise; set $F_x(l)=0$ on $l\ge d$. This is a total function of finite bitstrings. On $[d]$ it is strictly increasing: actual indices are distinct, sorted and below $N$, followed by distinct pads $N+l$. All outputs are below $N+d\le M$. For an invalid $x$, use a valid dummy query input and mask its answer, giving exactly the padded branch. The same masking handles padded physical slot strings. Every masked or externally controlled XOR evaluation can use two ordinary calls: compute the function to clean work, conditionally XOR-copy it to the desired target, and uncompute. Thus no controlled oracle is assumed free.

For each $x,y<M$, compute a total inverse lookup $G_x(y)$ by lower_bound search of the strictly increasing list $F_x(0),\dots ,F_x(d-1)$. Start $lo=0,hi=d$; for $\lceil {\log }_2(d+1)\rceil +1$ rounds, if $lo<hi$, set $m=\lfloor (lo+hi)\mathrm{/}2\rfloor$ and update $lo=m+1$ if $F_x(m)<y$, otherwise $hi=m$. In inactive rounds use a masked dummy call. Each active interval shrinks to at most the ceiling of half its old width, and width one becomes zero at the next round, so the stated round count suffices. If the final $lo<d$ and $F_x(lo)=y$, output $lo$; otherwise output zero. Retain and then reverse the fixed finite search history after copying its answer, so all history and oracle workspace are clean. There are $O(\log (d+1))$ forward/reverse location calls including the final equality test. Strict increase gives $G_x(F_x(l))=l$ for every $l<d$, including $l=0$; off the image no inversion is asserted.

On two ${\log }_{2}M$-bit registers apply the total permutation circuit $\mathrm{\mid }l,0⟩\mapsto \mathrm{\mid }l,F_x(l)⟩\mapsto \mathrm{\mid }l<mrow><mi\; mathvariant="normal">X</mi><mi\; mathvariant="normal">O</mi><mi\; mathvariant="normal">R</mi></mrow>G_x(F_x(l)),F_x(l)⟩\mapsto \mathrm{\mid }{F}_x(l),0⟩$, where the middle map is XOR evaluation of $G_x$ into the first register and the final map swaps the registers. The displayed clean formula is asserted only on $l<d$ and follows from step 2.1. Each constituent is a total reversible gate sequence on every bitstring, so its actual inverse exists with the same query order. Coherent row labels and references are untouched. Applying the separately supplied uniform preparation first gives $d^{-1\mathrm{/}2}{\sum }_{l<d}\mathrm{\mid }{F}_x(l)⟩$ with all additional work zero. This constructs the required row-neighbor and column-neighbor isometries; Hermiticity identifies the column list at $j$ with the row list at $j$.

Let $V_L\mathrm{\mid }0,i⟩=d^{-1\mathrm{/}2}{\sum }_{l<d}\mathrm{\mid }i,F_i(l)⟩$ and $V_R\mathrm{\mid }0,j⟩=d^{-1\mathrm{/}2}{\sum }_{l<d}\mathrm{\mid }{F}_j(l),j⟩$, including the common zero work registers from step 3.1. Put $U_L=I_{\mathrm{f}\mathrm{l}\mathrm{a}\mathrm{g}}\otimes V_L$. After $V_R$, compute $a_{ij}={\tilde{H}}_{ij}\mathrm{/}h$ and apply the flag unitary with first column $(a_{ij},\sqrt{1-\mathrm{\mid }{a}_{ij}{\mathrm{\mid }}^2}{)}^T$ and second column $(-\sqrt{1-\mathrm{\mid }{a}_{ij}{\mathrm{\mid }}^2},\overline{a_{ij}}{)}^T$, then uncompute values and arithmetic. Its columns are orthonormal because $\mathrm{\mid }{a}_{ij}\mathrm{\mid }\le 1$, so this defines $U_R$. Only $U_R$ inserts the value amplitude; $U_L$ has good-flag amplitude one.

Each row and, by Hermiticity, each column has at most $d$ nonzero entries, each of magnitude at most $h$. For any vector $v$, $\mathrm{\mid }(Hv{)}_i{\mathrm{\mid }}^2\le ({\sum }_j\mathrm{\mid }{H}_{ij}\mathrm{\mid })({\sum }_j\mathrm{\mid }{H}_{ij}\mathrm{\mid }\mathrm{\mid }{v}_j{\mathrm{\mid }}^2)$ by Cauchy–Schwarz. Summing over $i$ and using the row and column bounds gives $\mathrm{\parallel }Hv{\mathrm{\parallel }}^2\le (dh{)}^2\mathrm{\parallel }v{\mathrm{\parallel }}^2$, so $\mathrm{\parallel }H{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le dh$. The zero extension has the same operator norm, so the normalization $dh$ is valid for the block encoding in [F3]. By [F3], the clean $(i,j)$ matrix entry of $U_L^{\ast }{U}_R$ is $⟨U_R(0,j),U_L(0,i)⟩$. For a valid nonzero $H_{ij}$, the ordered pair $(i,j)$ occurs once on each side, with coefficients $H_{ij}\mathrm{/}(h\sqrt{d})$ and $1\mathrm{/}\sqrt{d}$, respectively. Their root pairing is $H_{ij}\mathrm{/}(dh)$. A zero or invalid entry contributes zero even if its padded pair happens to match, since its good-flag value amplitude is zero. Every value workspace has been uncomputed, and each location workspace is zero by step 3.1, so no unmatched work suppresses the desired overlap. This proves the exact compressed block, including zero rows, $H=0$, $d>N$, $N=1$, $d=1$, padded labels and repeated sentinel replies.

Each clean location circuit uses $O(\log (d+1))$ QA20 location calls by step 1.1 and step 2.1 and step 3.1, and computing/uncomputing its value uses a constant number of value calls. Reversing the actual circuit has identical counts. Coherently controlling it controls all known gates, and step 1.1 replaces each controlled XOR query by a constant number of ordinary XOR queries; hence the same asymptotic holds. All other operations remain in [F4]'s separate cost coordinates. Finally $\mathrm{\mid }{H}_{ij}\mathrm{\mid }=\mathrm{\mid }⟨H{e}_j,e_i⟩\mathrm{\mid }\le \mathrm{\parallel }H{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}$, so $h=1$ is a valid supplied bound in the normalized HHL mode.