Correctness and access cost of sparse block encoding

First consider the supplied-permutation mode. If $h=0$, the promised bound implies every entry of $H$ is zero. The returned $X_{\mathrm{f}\mathrm{l}\mathrm{a}\mathrm{g}}\otimes I$ is unitary and its compression against the clean flag $\mathrm{\mid }0⟩$ is $⟨0\mathrm{\mid }X\mathrm{\mid }0⟩I=0$, so normalization $1$ encodes $H=0$. Now suppose $h>0$. Each row and, by Hermiticity, each column has at most $d_H$ nonzero entries, each of magnitude at most $h$. For any vector $v$, Cauchy–Schwarz gives $\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)$. Summing over $i$ and using the row and column bounds gives $\mathrm{\parallel }Hv{\mathrm{\parallel }}^2\le (d_{H}h{)}^2\mathrm{\parallel }v{\mathrm{\parallel }}^2$, so $\mathrm{\parallel }H{\mathrm{\parallel }}_{\mathrm{o}\mathrm{p}}\le d_{H}h$ and the stated normalization is valid in [F3]. For each system label $i$, $V_L\mathrm{\mid }0,i⟩=d_H^{-1\mathrm{/}2}{\sum }_{k=1}^{d_H}\mathrm{\mid }i,\rho (i,k)⟩$, where $\rho (i,k)$ is its listed column or a distinct sentinel. For each system label $j$, $(D_{d_H}\otimes I)\mathrm{\mid }0,j⟩=d_H^{-1\mathrm{/}2}{\sum }_{\mathrm{\ell }=1}^{d_H}\mathrm{\mid }\mathrm{\ell },j⟩$; the register SWAP sends this to $d_H^{-1\mathrm{/}2}{\sum }_{\mathrm{\ell }=1}^{d_H}\mathrm{\mid }j,\mathrm{\ell }⟩$, so the supplied action of $O_c$ gives $V_R\mathrm{\mid }0,j⟩=d_H^{-1\mathrm{/}2}{\sum }_{\mathrm{\ell }=1}^{d_H}\mathrm{\mid }\kappa (j,\mathrm{\ell }),j⟩$. Each is normalized because its $d_H$ terms are orthonormal and have coefficient $d_H^{-1\mathrm{/}2}$.

For $\mathrm{\mid }h\mathrm{\mid }\le 1$, the two columns of the stated flag matrix have unit norm and inner product $\bar{h}(-\sqrt{1-\mathrm{\mid }h{\mathrm{\mid }}^2})+\sqrt{1-\mathrm{\mid }h{\mathrm{\mid }}^2}\bar{h}=0$; hence it is unitary and its flag-zero output amplitude from $\mathrm{\mid }0⟩$ is $h$. The value oracle is uncomputed after this rotation, so the good-flag overlap retains no value workspace.

With the root inner product linear in its first argument, the $(i,j)$ matrix entry of $U_L^{\ast }{U}_R$ is $⟨U_R(\mathrm{\mid }0⟩\otimes \mathrm{\mid }j⟩),U_L(\mathrm{\mid }0⟩\otimes \mathrm{\mid }i⟩){⟩}_{\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{t}}$, by the adjoint identity and the ordered-basis coordinate convention in [F5]. The row and column lists contain the pair $(i,j)$ once each exactly when $H_{ij}\mathrm{\ne }0$, by Hermiticity and the nonzero-entry enumeration. In that case the unique matching basis pair contributes $d_H^{-1}{h}_{ij}=H_{ij}\mathrm{/}(d_{H}h)$: the $U_R$ amplitude is first in the root pairing and equals $h_{ij}\mathrm{/}\sqrt{d_H}$, while the row-state amplitude is $1\mathrm{/}\sqrt{d_H}$. If $H_{ij}=0$, there is no valid matching pair, and the sentinel branch has flag-zero amplitude $0$. Thus every clean matrix entry is the stated one, proving the compressed block identity.

The displayed circuit for $U_L^{\ast }{U}_R$ applies the inverse row-location permutation once through $V_L^{\ast }$, the column-location permutation once through $V_R$, and the entry-value oracle twice to compute and uncompute the value. Its state preparations, inverses, arithmetic, flag rotations, controlled operations, and gate synthesis are separate declared costs, so no additional sparse-access operation has been counted as free.

In the optional sorted-XOR mode, apply [F7] to the supplied sorted QA20 interface and positive entry bound $h$. Its clean isometries insert $H_{ij}\mathrm{/}h$ only on the column side, give the padded block $(H\oplus 0)\mathrm{/}(d_{H}h)$, and clear the extra location and value work exactly on the prepared input subspaces. Its actual inverses and coherent controls have the same logarithmic location-query order. The supplied-permutation proof and counts in steps 1.1–3.1 are unchanged.