Answers are grounded in this paper and cite their sources.
This algorithm estimates eigenvalues for non-normal matrices using ground state energy estimation, suggesting a new approach in quantum computing.
Large-scale eigenvalue problems pose a significant challenge to classical computers. While there are efficient quantum algorithms for unitary or Hermitian matrices, eigenvalue problems for non-normal matrices remain open in quantum computing. In this work, we propose a quantum algorithm that given a non-normal matrix, outputs an estimate of an eigenvalue to within additive error $ε$ with probability at least 1-pfail. Our estimation strategy is to sample points on the complex plane and examine the distance between the sampled point and the eigenvalues. We show that the distance is related to the smallest singular value of the shifted matrix, hence reducing the problem to ground state energy estimation via Hermitianization. With the knowledge of an eigenvalue, we are able to prepare the associated eigenvector using ground state preparation. Our estimating scheme can also be modified to approximate the extreme eigenvalue, and in particular the spectral gap. The algorithm is implemented based on the block encoding input model and requires O(κ²ε⁻⁽²ᵐ⁻¹⁾log(1/pfail)) queries to the block encoding oracle. Our algorithm is the first general eigenvalue algorithm that achieves this scaling. We also perform numerical simulation to validate the algorithms.
No takes yet. Share an insight, caveat, or question.
Lin et al. (2025) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: