Quantum eigenvalue processing

Quantum eigenvalue processing

11 Jan 2024 | Guang Hao Low and Yuan Su
The paper presents two quantum algorithms, Quantum EigenValue Estimation (QEVE) and Quantum EigenValue Transformation (QEV T), for processing eigenvalues of high-dimensional matrices accessed by a quantum computer. These algorithms focus on input matrices with real spectra and Jordan forms, which are broad classes of non-normal operators used in non-Hermitian physics and transcorrelated quantum chemistry. The main contributions include: 1. **QEVE**: This algorithm estimates an eigenvalue of a diagonalizable matrix using $\mathbf{O} ( \alpha \epsilon / \log(1/p) )$ queries to its block encoding and a unitary preparing the corresponding eigenstate, achieving Heisenberg-limited scaling for eigenvalue estimation. This is a significant improvement over existing quantum singular value algorithms. 2. **QEV T**: This algorithm implements transformations on eigenvalues of the input matrix through Chebyshev and Faber approximations, providing nearly optimal query complexity. It can be used to solve systems of linear differential equations with a strictly linear scaling in the evolution time for an average-case diagonalizable input with imaginary spectra, and to prepare the ground state of matrices with real spectra. The core technique underlying these algorithms is the efficient creation of a history state encoding Chebyshev polynomials of the input matrix in quantum superposition. This technique is extended to Faber polynomials for eigenvalue processing over the complex plane, providing a unified framework for processing eigenvalues of matrices on a quantum computer. The paper also discusses applications such as quantum differential equation algorithms and ground state preparation, demonstrating the versatility and efficiency of the proposed algorithms.The paper presents two quantum algorithms, Quantum EigenValue Estimation (QEVE) and Quantum EigenValue Transformation (QEV T), for processing eigenvalues of high-dimensional matrices accessed by a quantum computer. These algorithms focus on input matrices with real spectra and Jordan forms, which are broad classes of non-normal operators used in non-Hermitian physics and transcorrelated quantum chemistry. The main contributions include: 1. **QEVE**: This algorithm estimates an eigenvalue of a diagonalizable matrix using $\mathbf{O} ( \alpha \epsilon / \log(1/p) )$ queries to its block encoding and a unitary preparing the corresponding eigenstate, achieving Heisenberg-limited scaling for eigenvalue estimation. This is a significant improvement over existing quantum singular value algorithms. 2. **QEV T**: This algorithm implements transformations on eigenvalues of the input matrix through Chebyshev and Faber approximations, providing nearly optimal query complexity. It can be used to solve systems of linear differential equations with a strictly linear scaling in the evolution time for an average-case diagonalizable input with imaginary spectra, and to prepare the ground state of matrices with real spectra. The core technique underlying these algorithms is the efficient creation of a history state encoding Chebyshev polynomials of the input matrix in quantum superposition. This technique is extended to Faber polynomials for eigenvalue processing over the complex plane, providing a unified framework for processing eigenvalues of matrices on a quantum computer. The paper also discusses applications such as quantum differential equation algorithms and ground state preparation, demonstrating the versatility and efficiency of the proposed algorithms.
Reach us at info@study.space
[slides and audio] Quantum Eigenvalue Processing