Block-encoded QLSP input and singular-gap promise

Let $A:{\mathbb{C}}^n\to {\mathbb{C}}^m$ with $m,n\ge 1$, $0<\alpha$, and $0<\gamma \le \alpha$. The input is an exact or approximate $(\alpha ,a,{ϵ}_{\mathrm{B}\mathrm{E}})$ block encoding of $A$ under the access contract of Block-encoding oracle and implementation cost model, together with the QLSP state-output data of Quantum linear-systems state-output task. The latter means a supplied unitary prepares a normalized $\mathrm{\mid }b\mathrm{/}\mathrm{\parallel }b\mathrm{\parallel }\mathrm{\mid }⟩$ from a designated zero input, $b\in \mathrm{ran}A\setminus \{0\}$, the target is $A^{+}b\mathrm{/}\mathrm{\parallel }{A}^{+}b\mathrm{\parallel }$ on the domain register, and every singular vector with nonzero coefficient in $b$ has singular value at least $\gamma$.

Put $\bar{A}=A\mathrm{/}\alpha$ and $\delta =\gamma \mathrm{/}\alpha \in (0,1]$. The support-gap promise then says every nonzero supported singular value of $\bar{A}$ is at least $\delta$; it makes no promise about singular values in $(0,\delta )$ outside the support of $b$. In the QSVT branch below we use $\delta \le 1\mathrm{/}2$ and $0<ϵ\le \delta$ as additional algorithm inputs. The block-encoding approximation and all phase, inverse, controlled, reflection, and state-preparation access costs are separate input data. A finite polynomial or a matrix alone is not an oracle.

The QSVT target map is $(\delta \mathrm{/}2){\bar{A}}^{+}=(\gamma \mathrm{/}2)A^{+}$. It has the same normalized output on $b$ as $A^{+}$ because $\gamma \mathrm{/}2>0$. The scale conversion and nonzero normalization of this target are established by Normalization and nonzero success weight of the supported pseudoinverse target ↗.