  Many problems in linear algebra -- such as those arising from non-Hermitian
physics and differential equations -- can be solved on a quantum computer by
processing eigenvalues of the non-normal input matrices. However, the existing
Quantum Singular Value Transformation (QSVT) framework is ill-suited to this
task, as eigenvalues and singular values are different in general. We present a
Quantum EigenValue Transformation (QEVT) framework for applying arbitrary
polynomial transformations on eigenvalues of block-encoded non-normal
operators, and a related Quantum EigenValue Estimation (QEVE) algorithm for
operators with real spectra. QEVT has query complexity to the block encoding
nearly recovering that of the QSVT for a Hermitian input, and QEVE achieves the
Heisenberg-limited scaling for diagonalizable input matrices. As applications,
we develop a linear differential equation solver with strictly linear time
query complexity for average-case diagonalizable operators, as well as a ground
state preparation algorithm that upgrades previous nearly optimal results for
Hermitian Hamiltonians to diagonalizable matrices with real spectra.
Underpinning our algorithms is an efficient method to prepare a quantum
superposition of Faber polynomials, which generalize the nearly-best uniform
approximation properties of Chebyshev polynomials to the complex plane. Of
independent interest, we also develop techniques to generate $n$ Fourier
coefficients with $\mathbf{O}(\mathrm{polylog}(n))$ gates compared to prior
approaches with linear cost.
