{"id":"arxiv/2603.16214","url":"https://arxiv.org/abs/2603.16214","tags":["quant-ph","math.NA"],"score":0,"title":"Quantum Estimation of Non-Hermitian Pseudospectra","domain":"quant-ph","source":"arxiv","authors":["Gengzhi Yang","Jiaqi Leng","Xiaodi Wu","Lin Lin"],"reviews":0,"subject":"quant-ph","summary":"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 more realistic computational target. We then present a concrete quantum…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-03-17","reactions":{}}