Probing Non-Hermitian Spectra on a Quantum Computer

While crucial for modern physics, computing the spectra of non-Hermitian systems is far more difficult than for their Hermitian counterparts. The precise nature of the hardness of this problem, however, has remained an open question. In this work, we establish the computational complexity of the problem and proposing an efficient quantum algorithm. We prove that estimating a non-Hermitian eigenvalue is PSPACE-hard, rendering it intractable for both classical and quantum computers. Crucially, we find that the related problem of computing the pseudo-spectrum (i.e., a generalized notion of spectrum) is QMA-complete, making it a more realistic target for quantum algorithms. Based on this finding, we develop a two-pronged quantum approach tailored for pseudo-spectrum estimation. Our method first leverages dissipative dynamics to efficiently prepare a suitable initial state, then uses a Heisenberg-limited signal processing technique to resolve the pseudo-spectrum. Through real machine demonstration for systems exhibiting exceptional points on trapped-ion quantum hardware, and numerical simulations on the non-Hermitian TFIM and SSH models, we provide strong evidence for the practical scalability and relevance of our proposed solution.