Sparse Hermitian block encoding

Input. A finite $d_H$-row-sparse Hermitian matrix $H$, with $d_H\ge 1$. Put $h_{\max }={\max }_{i,j}\mathrm{\mid }{H}_{ij}\mathrm{\mid }$ and supply a certified nonnegative entry bound $h\ge h_{\max }$. Supply exact row and column enumerations. Write their neighbor labels as $\rho (i,k)$ and $\kappa (j,k)$, including $d_H$ distinct labels per row or column: every nonzero entry occurs once, and padded labels are sentinels. Supply reversible in-place permutations whose action on every valid row/slot and column/slot basis state is $O_r\mathrm{\mid }i,k⟩=\mathrm{\mid }i,\rho (i,k)⟩,O_c\mathrm{\mid }j,k⟩=\mathrm{\mid }\kappa (j,k),j⟩,$ with their full reversible extensions, inverses, and actual query and gate costs. These permutations are explicit inputs; the row/column lists alone do not imply them. Supply an exact unitary $D_{d_H}$ preparing $d_H^{-1\mathrm{/}2}{\sum }_{k=1}^{d_H}\mathrm{\mid }k⟩$, its inverse, and their costs. A classical table is not a free state-preparation circuit. If $h=0$, then $H=0$; use one flag qubit and return $X_{\mathrm{f}\mathrm{l}\mathrm{a}\mathrm{g}}\otimes I$ with normalization $1$, whose all-zero flag compression is $0=H$. Otherwise set $\alpha =d_{H}h$ and supply a total reversible value-decoding query that writes a finite exact encoding of $h_{ij}=H_{ij}\mathrm{/}h$ on valid pairs and $0$ on invalid or sentinel pairs, together with its inverse and any controlled forms used, with their costs. Classical matrix entries alone do not provide this coherent access.

Instructions when $h>0$. Put $\widehat{H}=H\mathrm{/}h$, so every queried entry $h_{ij}={\widehat{H}}_{ij}$ obeys $\mathrm{\mid }{h}_{ij}\mathrm{\mid }\le 1$. On the paired row/column index registers define $V_L=O_r(I\otimes D_{d_H})\mathrm{S}\mathrm{W}\mathrm{A}\mathrm{P},V_R=O_c\mathrm{S}\mathrm{W}\mathrm{A}\mathrm{P}(D_{d_H}\otimes I)\mathrm{.}$ Let $U_L=I_{\mathrm{f}\mathrm{l}\mathrm{a}\mathrm{g}}\otimes V_L$. Define $U_R$ by first applying $V_R$, then querying $h_{ij}$, applying to the flag $\left(\begin{array}{cc}{h}_{ij}& -\sqrt{1-\mathrm{\mid }{h}_{ij}{\mathrm{\mid }}^2}\\ \sqrt{1-\mathrm{\mid }{h}_{ij}{\mathrm{\mid }}^2}& \overline{h_{ij}}\end{array}\right),$ and unquerying the value and arithmetic workspace. The square root is the nonnegative real root. Invalid sentinel pairs use $h_{ij}=0$. Return $U_L^{\ast }{U}_R$ with the all-zero auxiliary block designated as the encoded block. Every index, flag, value, state-preparation, inverse, controlled, arithmetic, and finite-precision operation is supplied or charged separately, including both register SWAPs and their controlled forms.

The supplied-permutation mode requires the in-place location permutations as explicit input. The total XOR row-location oracle of Sparse Hamiltonian row and value oracles does not itself supply an $O(1)$-query in-place permutation or its inverse. Any scan or inverse-location construction must be specified and charged before claiming such a sparse-oracle cost.

The block identity and its exact query accounting are proved in Correctness and access cost of sparse block encoding ↗.

Sorted-XOR specialization. As an alternative input mode, supply the exact sorted XOR location/value interface of Sparse Hamiltonian row and value oracles, or the sorted distinct support-superset variant allowing listed zero entries in Clean sparse-state preparation from sorted XOR locations, a certified positive bound $h\ge {\max }_{i,j}\mathrm{\mid }{H}_{ij}\mathrm{\mid }$, and the same separately charged uniform preparation and value/flag arithmetic. Execute the explicit compute-location, binary-search inverse, slot-erasure and row/column-overlap construction of Clean sparse-state preparation from sorted XOR locations. It pads the system to $M=2^{\lceil {\log }_2(N+d_H)\rceil }$ and returns a clean block encoding of $(H\oplus 0)\mathrm{/}(d_{H}h)$, with normalization $\alpha =d_{H}h$. The location workspace is exactly clean on every prepared slot state. Each encoding, actual adjoint or coherent controlled encoding costs $O(\log (d_H+1))$ original location calls and $O(1)$ value calls; its sorting assumption is part of this mode's input. If $\mathrm{\parallel }H\mathrm{\parallel }\le 1$, choose $h=1$ without computing a maximum. Keep the one-sided value amplitude on $U_R$ exactly as above. The original supplied-permutation mode and its sharper call count remain available.