Exponential quantum advantages for practical non-Hermitian eigenproblems

While non-Hermitian physics has attracted considerable attention, current studies are limited to small or classically solvable systems. Quantum computing, as a powerful eigensolver, have predominantly been applied to Hermitian domain, leaving their potential for studying non-Hermitian problems largely unexplored. We extend the power of quantum computing to general non-Hermitian eigenproblems. Our approach works for finding eigenvalues without extra constrains, or eigenvalues closest to specified points or lines, thus extending results for ground energy and energy gap problems for Hermitian matrices. Our algorithms have broad applications, and as examples, we consider two central problems in non-Hermitian physics. Firstly, our approach is the first to offer an efficient quantum solution to the witness of spontaneous $PT$-symmetry breaking, and provide provable, exponential quantum advantage. Secondly, our approach enables the estimation of Liouvillian gap, which is crucial for characterizing relaxation times. Our general approach can also find applications in many other areas, such as the study of Markovian stochastic processes. These results underscore the significance of our quantum algorithms for addressing practical eigenproblems across various disciplines.