Introduction
Finding the ground-state energy of quantum many-body systems is a primary objective for quantum computing. Quantum subspace diagonalization (QSD), also known as quantum Krylov methods, has emerged as a leading algorithmic candidate for this task. QSD works by evolving an initial state through time on a quantum computer to construct a basis, then solving for the lowest energy state within that subspace on a classical computer.
Despite its empirical success, QSD faces a significant theoretical paradox. The algorithm requires solving a generalized eigenvalue problem ($Hc = ESc$) where the overlap matrix $S$ is often nearly singular and the entries are corrupted by Monte Carlo noise from quantum measurements. While classical matrix perturbation theory suggests such ill-conditioned problems should yield meaningless results, QSD remains robust in practice when paired with a "thresholding" technique. This paper provides the first rigorous theoretical justification for this robustness, explaining how and why QSD succeeds where classical theory predicts failure.
The Challenge of Ill-Conditioning and Noise
The core of the QSD difficulty lies in two factors:
- Ill-conditioning: The basis states generated by time evolution are often nearly linearly dependent, causing the overlap matrix $S$ to be nearly singular.
- Extreme Noise: Unlike classical numerical linear algebra, where noise is limited to floating-point round-off error, the entries of $H$ and $S$ in QSD are estimated via quantum measurements. This introduces stochastic noise that is often orders of magnitude larger than standard precision limits.
Standard perturbation theories, such as Stewart’s theory, rely on global properties of the matrix pair. When the overlap matrix is nearly singular, these global bounds explode, suggesting that any noise will destroy the accuracy of the eigenvalues. However, practitioners have long used a "thresholding" strategy—performing an eigendecomposition of $S$ and discarding components corresponding to eigenvalues below a certain threshold $\epsilon$—to stabilize the calculation. This work formalizes the success of this heuristic.
Theoretical Framework
The authors utilize advanced tools from numerical linear algebra to bridge the gap between empirical results and theory:
- Mathias-Li Perturbation Theory: Rather than looking at the global condition number, the authors apply Mathias-Li theory to demonstrate that the error in the ground-state energy depends on the local condition number of that specific eigenvalue. If the ground state is well-separated from the rest of the spectrum, it remains stable even if the overall matrix pair is ill-conditioned.
- Davis-Kahan sin Θ Theorem: This theorem is employed to prove that the subspace remaining after thresholding is itself stable against noise, ensuring that the truncated problem still contains the necessary physical information.
- Trigonometric Polynomial Approximation: To address the "Rayleigh-Ritz error" (the error inherent in using a finite-dimensional Krylov subspace), the authors use Chebyshev polynomials to prove that the approximation error decays exponentially as the number of time steps increases.
Key Insights and Results
The paper establishes several critical findings for the implementation of quantum algorithms:
1. Thresholding as a Mandatory Filter
The analysis confirms that thresholding is not merely an optimization but a requirement. Without it, even microscopic noise (e.g., $10^{-10}$) leads to spurious, wildly inaccurate results. Thresholding acts as a filter that removes the noise-dominated, nearly singular directions of the subspace.
2. Optimal Threshold Scaling
The authors derive an end-to-end error bound that combines Krylov approximation error and noise perturbation. They prove that if the noise level is $\eta$, the optimal threshold $\epsilon$ should scale as $\eta^{\frac{1}{1+\alpha}}$, where $\alpha$ is a parameter related to the geometric mean of the matrix elements. This scaling allows the algorithm to recover the ground state energy with an error proportional to the noise level times the eigenvalue's local condition number.
3. Empirical Validation
The theory was validated using numerical simulations of the 1D Transverse Field Ising Model (TFIM) and the 1D Hubbard model. While worst-case theoretical bounds suggest $\alpha = 1/2$, empirical tests on these physical systems showed $\alpha \approx 1/4$. This suggests that QSD performs even better on real-world physical systems than a conservative theoretical analysis might predict.
Limitations and Future Directions
While this work provides a robust foundation for QSD, some limitations remain. The current theoretical bounds exhibit a cubic dependence on the problem size ($O(n^3)$), which the authors believe is a pessimistic artifact of the proof technique rather than a reflection of actual algorithmic performance. Furthermore, the analysis focuses primarily on the ground state.
Future research will aim to extend these proofs to excited states (interior eigenvalues) and develop bounds for the accuracy of the computed eigenvectors (the quantum states themselves). Initial applications of Mathias-Li theory suggest that eigenvectors may be more sensitive to noise than eigenvalues, representing a vital area for further investigation in quantum chemistry and materials science applications.
Summary updated