A Theory of Quantum Subspace Diagonalization
- Creators
- Epperly, Ethan N.
- Lin, Lin
- Nakatsukasa, Yuji
Abstract
Quantum subspace diagonalization methods are an exciting new class of algorithms for solving large-scale eigenvalue problems using quantum computers. Unfortunately, these methods require the solution of an ill-conditioned generalized eigenvalue problem, with a matrix pencil corrupted by a nonnegligible amount of noise that is far above the machine precision. Despite pessimistic predictions from classical worst-case perturbation theories, these methods can perform reliably well if the generalized eigenvalue problem is solved using a standard truncation strategy. By leveraging and advancing classical results in matrix perturbation theory, we provide a theoretical analysis of this surprising phenomenon, proving that under certain natural conditions, a quantum subspace diagonalization algorithm can accurately compute the smallest eigenvalue of a large Hermitian matrix. We give numerical experiments demonstrating the effectiveness of the theory and providing practical guidance for the choice of truncation level. Our new results can also be of independent interest to solving eigenvalue problems outside the context of quantum computation.
Additional Information
The work of the first author was supported by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, Department of Energy Computational Science Graduate Fellowship grant DE-SC0021110. The second author was supported by the Department of Energy grant DE-SC0017867 and the NSF Quantum Leap Challenge Institute (QLCI)program through grant OMA-2016245. The second author is a Simons investigator.Additional details
- Eprint ID
- 117455
- Resolver ID
- CaltechAUTHORS:20221017-12147700.16
- DE-SC0021110
- Department of Energy (DOE)
- DE-SC0017867
- Department of Energy (DOE)
- OMA-2016245
- NSF
- Simons Foundation
- Created
-
2022-10-20Created from EPrint's datestamp field
- Updated
-
2022-10-20Created from EPrint's last_modified field