  The eigenvalue problem, a cornerstone in linear algebra, provides profound
insights into studying matrix properties. Quantum algorithms addressing this
problem have hitherto been constrained to special normal matrices assuming
spectral decomposition, leaving the extension to general matrices an open
challenge. In this work, we present a novel family of quantum algorithms
tailored for solving the eigenvalue problem for general matrices, encompassing
scenarios with complex eigenvalues or even defective matrices. Our approach
begins by tackling the task of searching for an eigenvalue without additional
constraints. For diagonalizable matrices, our algorithm has $\tilde
O(\varepsilon^{-1})$ complexity with an error $\varepsilon$, achieving the
nearly Heisenberg scaling. Subsequently, we study the identification of
eigenvalues closest to a specified point or line, extending the results for
ground energy and energy gap problems in Hermitian matrices. We achieve an
accuracy scaling of $\tilde O(\varepsilon^{-2})$ for general diagonalizable
matrices, further refining to $\tilde O(\varepsilon^{-1})$ under the condition
of real eigenvalues or constant distance from the reference point. The
algorithm's foundation lies in the synergy of three techniques: the
relationship between eigenvalues of matrix $A$ and the minimum singular value
of $A-\mu I$, quantum singular value threshold subroutine extended from quantum
singular-value estimation, and problem-specific searching algorithms. Our
algorithms find applications in diverse domains, including estimating the
relaxation time of Markov chains, solving Liouvillian gaps in open quantum
systems, and verifying PT-symmetry broken/unbroken phases. These applications
underscore the significance of our quantum eigensolvers for problems across
various disciplines.
