Quantum eigenvalue processing
This work addresses a bottleneck in quantum linear algebra for non-normal matrices, enabling more efficient algorithms in non-Hermitian physics and differential equations, though it builds incrementally on the QSVT framework.
The authors tackled the problem of processing eigenvalues of non-normal matrices on quantum computers, which existing frameworks like QSVT couldn't handle effectively, by developing a Quantum Eigenvalue Transformation (QEVT) framework and Quantum Eigenvalue Estimation (QEVE) algorithm. As a result, they achieved Heisenberg-limited scaling for diagonalizable matrices and linear time query complexity for solving linear differential equations with diagonalizable operators.
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 for 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.