A Caltech Library Service

A Theory of Quantum Subspace Diagonalization

Epperly, Ethan N. and Lin, Lin and Nakatsukasa, Yuji (2022) A Theory of Quantum Subspace Diagonalization. SIAM Journal on Matrix Analysis and Applications, 43 (3). pp. 1263-1290. ISSN 0895-4798. doi:10.1137/21m145954x.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Epperly, Ethan N.0000-0003-0712-8296
Lin, Lin0000-0001-6860-9566
Nakatsukasa, Yuji0000-0001-7911-1501
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.
Funding AgencyGrant Number
Department of Energy (DOE)DE-SC0021110
Department of Energy (DOE)DE-SC0017867
Simons FoundationUNSPECIFIED
Issue or Number:3
Record Number:CaltechAUTHORS:20221017-12147700.16
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:117455
Deposited By: Research Services Depository
Deposited On:20 Oct 2022 16:57
Last Modified:20 Oct 2022 16:57

Repository Staff Only: item control page