Optimal Bounds, Barriers, and Extensions for Non-Hermitian Bivariate Quantum Signal Processing

Multivariate quantum signal processing (M-QSP) has recently been shown to be applicable for non-Hermitian Hamiltonian simulation, opening several problems regarding the optimization landscape, angle-finding, and constant-factor analysis. We resolve several of these problems here. We find the anti-Hermitian query complexity $d_I=\mathrm{\Theta }(\text{betaI}T+\log (1\mathrm{/}\epsilon )\mathrm{/}\log \log (1\mathrm{/}\epsilon ))$ to be tight, established via Chebyshev coefficient bounds, modified Bessel function asymptotics, and Lambert~$W$ inversion. Fast-forwarding to $d_I=\mathcal{O}(\sqrt{\text{betaI}T})$ is impossible in the bivariate polynomial model, though a linear state-dependent improvement to $d_I=\mathcal{O}{\beta }_{\mathrm{e}\mathrm{f}\mathrm{f}}T+\log (1\mathrm{/}\epsilon )\mathrm{/}\log \log (1\mathrm{/}\epsilon ))$ is achievable. The optimization landscape of M-QSP admits spurious local minima, but a warm-start basin guarantee ensures the two-stage algorithm converges. CRC-exploiting block peeling reduces angle-finding from $\mathcal{O}(d^3)$ to $\mathcal{O}(d^2)$ classical operations, and optimized error allocation yields a leading constant of approximately~$2$ relative to the information-theoretic lower bound. A constant-ratio condition extends to non-identical signal operators, enabling time-dependent non-Hermitian simulation with query complexity $\mathcal{O}({\int }_0^T(\text{alphaR}(s)+\text{betaI}(s))ds+\log (1\mathrm{/}\epsilon )\mathrm{/}\log \log (1\mathrm{/}\epsilon ))$. Block-encoding overhead $e^{-2\text{betaI}T}$ holds across all function classes within the walk-operator oracle model, and dilational methods (Schrödingerization) achieve the walk-operator barrier. A precisely characterized direct-access construction achieves the intrinsic barrier $e^{-2\omega T}$ (with $\omega <\text{betaI}$ for non-commuting Hamiltonians) on a restricted domain, though extension to the full bitorus remains open.