Exponential Quantum Advantages for Practical Non-Hermitian Eigenproblems

Non-Hermitian physics has emerged as a rich field of study, with applications ranging from PT-symmetry breaking and skin effects to non-Hermitian topological phase transitions. Yet most studies remain restricted to small-scale or classically tractable systems. While quantum computing has shown strong performance in Hermitian eigenproblems, its extension to the non-Hermitian regime remains largely unexplored. Here, we develop a quantum algorithm to address general non-Hermitian eigenvalue problems, specifically targeting eigenvalues near a given line in the complex plane-thereby generalizing previous results on ground state energy and spectral gap estimation for Hermitian matrices. Our method combines a fuzzy quantum eigenvalue detector with a divide-and-conquer strategy to efficiently isolate relevant eigenvalues. This yields a provable exponential quantum speedup for non-Hermitian eigenproblems. Furthermore, we discuss the broad applications in detecting spontaneous PT-symmetry breaking, estimating Liouvillian gaps, and analyzing classical Markov processes. These results highlight the potential of quantum algorithms in tackling challenging problems across quantum physics and beyond.