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.
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.
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.
Approximating the ground state of many-body systems is a key computational bottleneck underlying important applications in physics and chemistry. The most widely known quantum algorithm for ground state approximation, quantum phase estimation, is out of reach of current quantum processors due to its high circuit-depths. Subspace-based quantum diagonalization methods offer a viable alternative for pre- and early-fault-tolerant quantum computers. Here, we introduce a quantum diagonalization algorithm which combines two key ideas on quantum subspaces: a classical diagonalization based on quantum samples, and subspaces constructed with quantum Krylov states. We prove that our algorithm converges in polynomial time under the working assumptions of Krylov quantum diagonalization and sparseness of the ground state. We then demonstrate the scalability of our approach by performing the largest ground-state quantum simulation of impurity models using a Heron quantum processors and the Frontier supercomputer. We consider both the single-impurity Anderson model with 41 bath sites, and a system with 4 impurities and 7 bath sites per impurity. Our results are in excellent agreement with Density Matrix Renormalization Group calculations.
Solving systems of linear equations,
Ax=b, is a ubiquitous task in computational science. The Harrow-Hassidim-Lloyd algorithm requires phase estimation, controlled rotations, and post-selection, impractical on noisy intermediate-scale quantum hardware. We extend sample-based quantum diagonalization (SQD), developed for quantum chemistry, to linear systems. Following the sample-based Krylov variant, the Hermitian matrix
A is decomposed in the Pauli basis, the Trotterized time evolution of
∣b⟩ is sampled at several times to select computational-basis configurations, and the system is solved classically by a Galerkin projection onto the selected subspace. We prove that the subspace solution is exact when the sampled configurations contain the Krylov support of
b and optimal in the energy norm for symmetric positive-definite matrices, so that noise-induced configurations cannot degrade it as long as they do not displace the ideal ones. On IBM Quantum hardware, the sampled distribution of a
4×4 example deviates from the exact one by eleven times the shot-noise level, yet the solution is recovered exactly. For a localized problem of dimension
N=1024, SQD selects 33 configurations, reaches a relative error of
10−5, and its truncated subspaces coincide with the optimal choice; readout errors enlarge the subspace without degrading the accuracy. The tests also show the limitations: the selected subspace coincides with that of inexpensive classical selection, banded matrices require exponentially many Pauli terms in the binary encoding, and Trotter errors populate spurious configurations unless the circuits are deep. An MIT-licensed Python package and notebooks that reproduce the numerical results are provided.
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.