Towards End-to-End Quantum Estimation of Non-Hermitian Pseudospectra
This addresses a fundamental problem in quantum computing and non-Hermitian physics by providing a practical quantum algorithm for pseudospectrum estimation, though it is incremental as it builds on existing quantum singular value transformation techniques.
The paper tackles the computational challenge of determining pseudospectrum membership in non-Hermitian many-body systems, showing it is QMA-complete for 4-local operators and presenting an end-to-end quantum framework that achieves Heisenberg-limited scaling, with experimental validation on a trapped-ion quantum computer distinguishing points inside and outside the pseudospectrum.
Non-Hermitian many-body systems can be spectrally unstable, so small perturbations may induce large eigenvalue shifts. The pseudospectrum quantifies this instability and provides a perturbation-robust diagnostic. For inverse-polynomially small $ε$, we show that deciding whether a point $z\in\mathbb{C}$ is $ε$-close to the spectrum is PSPACE-hard for $5$-local operators, whereas deciding whether $z$ lies in the $ε$-pseudospectrum is QMA-complete for $4$-local operators. This identifies pseudospectrum membership as a natural computational target. We then present a concrete end-to-end quantum framework for deciding pseudospectrum membership, which combines a singular-value estimation step with a dissipative state preparation algorithm. Our Quantum Singular-value Gaussian-filtered Search (QSIGS) combines quantum singular value transformation (QSVT) with classical post-processing to achieve Heisenberg-limited query scaling for singular-value estimation. To prepare suitable input states, we introduce an algorithmic Lindbladian protocol for approximate ground right singular vectors and prove its effectiveness for the Hatano--Nelson model. Finally, we demonstrate the full pipeline on a trapped-ion quantum computer and distinguish points inside and outside the target pseudospectrum near the exceptional point of a minimal non-Hermitian qubit model.