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.
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.
Quantum subspace diagonalization and quantum Krylov algorithms offer a feasible, pre- or early-fault tolerant alternative to quantum phase estimation for using quantum computers to estimate the low-lying spectra of quantum systems. However, despite promising proof-of-principle results, such methods suffer from high sensitivity to noise (including intrinsic sources such as sampling noise), making their utility for realistic industry-relevant problems an open question. To improve the potential applicability of such methods, we introduce a new variant of thresholding for noisy generalized eigenvalue problems that arise in quantum subspace diagonalization that has the potential to better control sensitivity to noise. Our approach leverages eigenvector-preserving transformations (rotations) of the generalized eigenvalue problem prior to thresholding. We study this effect in practical settings by applying this rotation thresholding scheme to an iterative quantum Krylov algorithm for several chemical systems, including the industry-relevant Fe(III)-NTA chelate complex. We develop a particular heuristic to select the rotation angle from noisy data and find for certain systems and noise regimes that the samples required to reach a target error for ground state estimation can be reduced by a factor of up to 100. Furthermore, with oracle access to the optimal transformation, more dramatic improvements are possible and we observe reductions in sample requirements by up to 104, motivating the continued development of methods that can realize these improvements in practice. While we develop our approach in the context of quantum subspace diagonalization, the improved thresholding scheme we develop could be advantageous in any context where one must solve noisy, ill-conditioned generalized eigenvalue problems.
Krylov subspace methods are among the most extensively studied early fault-tolerant quantum algorithms for estimating ground-state energies of quantum systems. However, the rapid onset of ill-conditioning might make accurate energies difficult or even impossible to retrieve. In this communication, we analyse the numerical stability and statistical problems of these methods using numerical simulations both in the presence and absence of sampling noise. While in ideal numerical simulations the generalized eigenvalue problem indeed becomes unstable with increased Krylov subspace size, we find that, in realistic noisy settings, these methods do not primarily suffer from ill-conditioning. Instead, statistical fluctuations dominate and can prevent reliable solution extraction unless appropriate regularization or filtering techniques are employed. We consequently introduce two new metrics, the imaginary and unitary filters, that successfully assess the reliability of the obtained solutions without any knowledge of the true eigenspectrum.
Solving challenging problems in quantum chemistry is one of the most promising applications of quantum computers. Within the quantum algorithms proposed for problems in excited state quantum chemistry, subspace-based quantum algorithms, including quantum subspace expansion (QSE), quantum equation of motion (qEOM) and quantum self-consistent equation-of-motion (q-sc-EOM), are promising for pre-fault-tolerant quantum devices. The working equation of QSE and qEOM requires solving a generalized eigenvalue equation with associated matrix elements measured on a quantum computer. Our careful analytical and numerical analysis of the standard and generalized eigenvalue problems, especially in the context of excited-state methods, shows that the errors in eigenvalues magnify drastically with an increase in the condition number of the overlap matrix when a generalized eigenvalue equation is solved in the presence of statistical sampling errors. This makes methods such as QSE unstable to errors that are unavoidable when using quantum computers. Further, at very high condition numbers of the overlap matrix, the QSE's working equation could not be solved without any additional steps in the presence of sampling errors, as it becomes ill-conditioned. It was possible to use the thresholding technique in this case to solve the equation, but the solutions achieved had missing excited states, which may be a problem for future chemical studies. We also show that excited-state methods that have an eigenvalue equation as the working equation, such as q-sc-EOM, do not have the problems associated with the condition number and could be generally more stable to errors, and therefore, more suitable candidates for excited-state quantum chemistry calculations using quantum computers.
We present a comprehensive theoretical analysis of quantum subspace diagonalization methods for molecular electronic structure calculations, establishing rigorous complexity bounds and convergence guarantees. Building on recent developments in adaptive quantum algorithms for chemical systems, we formulate a general mathematical framework that describes how quantum computers can efficiently explore molecular potential energy surfaces through iterative subspace construction. Our theory characterizes the relationship between subspace dimension, basis set selection, and solution accuracy for ground and excited state calculations. We derive analytical expressions for the number of quantum measurements required to achieve chemical accuracy and establish conditions under which quantum subspace methods offer polynomial advantages over classical approaches. The framework incorporates realistic noise models, providing performance predictions for near-term quantum devices. We analyze trade-offs between circuit depth, measurement overhead, and solution quality, identifying optimal operating regimes for different molecular systems. Special attention is devoted to transition-state mapping for chemical reactions, where we prove that adaptive subspace selection achieves exponential reduction in required measurements compared to uniform sampling. Applications to battery electrolyte reactions, drug discovery, and materials design demonstrate the practical utility of our theoretical predictions. This work establishes quantum subspace methods as a rigorous alternative to variational approaches, offering theoretical guarantees absent in parameter-optimization-based algorithms while maintaining compatibility with near-term quantum hardware constraints.
Quantum Krylov subspace diagonalization (QKSD) is an emerging method used in place of quantum phase estimation in the early fault-tolerant era, where limited quantum circuit depth is available. In contrast to the classical Krylov subspace diagonalization (KSD) or the Lanczos method, QKSD exploits the quantum computer to efficiently estimate the eigenvalues of large-size Hamiltonians through a faster Krylov projection. However, unlike classical KSD, which is solely concerned with machine precision, QKSD is inherently accompanied by errors originating from a finite number of samples. Moreover, due to difficulty establishing an artificial orthogonal basis, ill-conditioning problems are often encountered, rendering the solution vulnerable to noise. In this work, we present a nonasymptotic theoretical framework to assess the relationship between sampling noise and its effects on eigenvalues. We also propose an optimal solution to cope with large condition numbers by eliminating the ill-conditioned bases. Numerical simulations of the one-dimensional Hubbard model demonstrate that the error bound of finite samplings accurately predicts the experimental errors in well-conditioned regions.
Solving challenging problems in quantum chemistry is one of the most promising applications of quantum computers. Within the quantum algorithms proposed for problems in excited-state quantum chemistry, subspace-based quantum algorithms, including quantum subspace expansion (QSE), quantum equation of motion (qEOM), and quantum self-consistent equation-of-motion (q-sc-EOM), are promising for pre-fault-tolerant quantum devices. The working equation of QSE and qEOM requires solving a generalized eigenvalue equation with associated matrix elements measured on a quantum computer. Our careful analytical and numerical analysis of the standard and generalized eigenvalue problems, especially in the context of excited-state methods, shows that the errors in eigenvalues magnify drastically with an increase in the condition number of the overlap matrix when a generalized eigenvalue equation is solved in the presence of statistical sampling errors. This makes methods such as QSE unstable for errors that are unavoidable when using quantum computers. Further, at very high condition numbers of the overlap matrix, the QSE's working equation could not be solved without any additional steps in the presence of sampling errors, as it becomes ill-conditioned. It was possible to use the thresholding technique in this case to solve the equation, but the solutions achieved had missing excited states, which may be a problem for future chemical studies. We also show that excited-state methods that have an eigenvalue equation as the working equation, such as q-sc-EOM, do not have the problems associated with the condition number and could be generally more stable to errors and therefore more suitable candidates for excited-state quantum chemistry calculations using quantum computers.