Orthogonal Quantum Krylov Diagonalisation

Technical Summary: Orthogonal Quantum Krylov Diagonalization

Problem Statement
Quantum subspace-diagonalization methods, particularly Quantum Krylov Diagonalization (QKD), offer a promising route for computing low-energy spectra of quantum many-body Hamiltonians. However, existing quantum Krylov approaches (including the recent Chebyshev-based QKD or CQKD) rely on non-orthogonal Krylov bases. This non-orthogonality necessitates the solution of a generalized eigenvalue problem involving an overlap matrix ($S$). As the subspace dimension increases, the Krylov vectors become linearly dependent, causing the overlap matrix to become ill-conditioned. To mitigate numerical instability, existing methods require thresholding and regularization procedures. These steps introduce additional computational and measurement costs, degrade convergence properties, and prevent the exact reproduction of the stability and orthogonality characteristics found in the classical Lanczos algorithm. Furthermore, the measurement complexity of these methods often inherits an exponential dependence on system size due to the "orthogonality catastrophe" (small initial state overlap with the target eigenstate).

Methodology
The authors introduce Orthogonal Quantum Krylov Diagonalization (OQKD), a framework that reformulates the classical Lanczos recursion at the operator level to enable an orthogonal quantum implementation.

• Operator-Level Reformulation: Instead of generating non-orthogonal vectors and regularizing them, OQKD constructs Lanczos vectors $|\psi^\perp_n\rangle$ directly as normalized polynomial transformations of the rescaled Hamiltonian $\tilde{H}$ acting on an initial state $|\Phi_0\rangle$:
  $$|\psi^\perp_n\rangle = P_n(\tilde{H})|\Phi_0\rangle$$
  where $P_n$ satisfies the Lanczos three-term recurrence relation.
• Recursive Coefficient Determination: The normalization coefficients ($\tilde{\beta}_{i+1}$) required for the recurrence are determined a priori using measurable moments ($\langle \psi^\perp_i | \tilde{H}^2 | \psi^\perp_i \rangle$) rather than a posteriori vector normalization. This allows the construction of the polynomial coefficients without explicitly storing intermediate vectors or performing Hadamard tests for off-diagonal overlap elements.
• Quantum Implementation: The Lanczos polynomials are expanded in the Chebyshev basis and implemented using Block Encoding and Generalized Quantum Signal Processing (GQSP). This approach ensures the generated basis is orthonormal by construction, resulting in a projected Hamiltonian with a tridiagonal structure and an overlap matrix close to the identity ($S \approx I$).
• Restarted Protocol (ROQKD): To address the exponential decrease in success probability associated with implementing high-degree polynomials via GQSP, the authors propose a restarted state-preparation protocol. Instead of applying a single high-degree polynomial, the algorithm performs a sequence of OQKD cycles with a fixed, low maximum degree ($n_{max}$). The approximate ground state obtained at the end of each cycle is converted into a quantum state (via GQSP) and used as the initial state for the next cycle. This accumulates the polynomial transformations while maintaining a nearly constant success probability for state preparation.

Key Results

• Numerical Stability and Convergence: Numerical simulations on the $J_1-J_2$ Heisenberg model demonstrate that OQKD reproduces the convergence behavior of the classical Lanczos algorithm up to machine precision. Unlike QKD and CQKD, which deviate from the ideal convergence profile once overlap-matrix regularization becomes active, OQKD maintains a well-conditioned basis throughout the iteration.
• Measurement Complexity: The paper establishes analytically that OQKD eliminates the overlap-matrix regularization bottleneck. Consequently, the measurement complexity per projected matrix element becomes independent of the initial state overlap ($\gamma_0$). While the effective cost still depends on the GQSP success probability, this dependence is shifted from a fundamental property of the physical system (exponential decay with system size) to an implementation-dependent parameter.
• Restarted Protocol Performance: The ROQKD protocol achieves exponential convergence of infidelity toward the exact ground state. Crucially, the success probability of preparing the approximate ground state remains nearly constant throughout the restart cycles, contrasting with the exponential decay observed in restarted CQKD or direct high-degree polynomial implementations.

Significance and Claims
The paper claims to establish OQKD as a direct orthogonal quantum analog of the classical Lanczos algorithm. Its primary significance lies in:

1. Eliminating Regularization: It removes the need for overlap-matrix regularization, thereby preserving the numerical stability and convergence properties inherent to the classical Lanczos method.
2. Scalable State Preparation: The restarted protocol (ROQKD) provides a promising strategy for preparing high-fidelity initial states for Quantum Phase Estimation (QPE) with a nearly constant success probability, overcoming the limitations of single-step high-degree polynomial transformations.
3. Bridging Classical and Quantum: The work connects classical subspace-diagonalization techniques with modern quantum algorithms based on block encoding and GQSP, offering a scalable route toward robust quantum eigensolvers for large-scale, industrially relevant eigenvalue problems.

The authors note that the exponential overhead in GQSP success probability for high-degree polynomials is a practical implementation limitation of the current GQSP framework rather than a fundamental flaw in the OQKD algorithm itself, suggesting it may be alleviated by future advances in quantum signal processing.