Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2307.16279 · Quantum

Sampling Error Analysis in Quantum Krylov Subspace Diagonalization

Gwonhak Lee, Dongkeun Lee, Joonsuk Huh

Published Sep 19, 2024• 15 citations
arXivHTMLPDF

Abstract

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.

DOI
10.22331/q-2024-09-19-1477

Related papers

Tackling instabilities of quantum Krylov subspace methods: an analysis of the numerical and statistical errors

Maria Gabriela Jordão Oliveira, Karl Michael Ziems, Nina Glaser

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.

quant-pharXiv:2604.11532•Apr 14, 2026•0 citations

Mirror subspace diagonalization: A real-time quantum Krylov algorithm with near-optimal sampling cost

Shota Kanasugi, Yuya O. Nakagawa, Norifumi Matsumoto +3 more

Quantum Krylov algorithms are a promising approach for ground-state energy estimation on near-term quantum computers. However, their sampling cost is inherently high because each Hamiltonian term is measured individually. Despite various mitigation techniques, this overhead remains a bottleneck for large-scale electronic structure problems. We introduce mirror subspace diagonalization (MSD), which approaches the theoretical lower bound on the sampling cost for quantum Krylov algorithms built upon real-time evolution. MSD uses a finite-difference formula to express the Hamiltonian as a linear combination of time-evolution unitaries with symmetrically shifted timesteps, enabling efficient estimation of the Hamiltonian matrix within the Krylov subspace. By optimizing the timestep and shifting the energy spectrum, finite-difference and statistical errors are minimized simultaneously, allowing MSD to attain the sampling-cost lower bound up to a logarithmic factor. We further apply classical post-processing to infer Hamiltonian moments, which mitigate the ground-state energy error via the Lanczos scheme. Our analysis shows MSD is particularly effective when the Hamiltonian's spectral norm is much smaller than its 1-norm, as in high-accuracy molecular simulations with large basis sets and strong electronic correlations. Numerical results for various molecular models show sampling-cost reductions of roughly 10 to 10,000 times over the conventional quantum Krylov algorithm.

quant-pharXiv:2511.20998•npj Quantum Information•Nov 27, 2025•0 citations

Quantum Krylov subspace algorithms for ground- and excited-state energy estimation

Cristian L. Cortes, Stephen K. Gray

Quantum Krylov subspace diagonalization (QKSD) algorithms provide a low-cost alternative to the conventional quantum phase estimation algorithm for estimating the ground- and excited-state energies of a quantum many-body system. While QKSD algorithms typically rely on using the Hadamard test for estimating Krylov subspace matrix elements of the form $\ensuremath{\langle}{\ensuremath{\phi}}_{i}|{e}^{\ensuremath{-}i\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{H}\ensuremath{\tau}}|{\ensuremath{\phi}}_{j}\ensuremath{\rangle}$, the associated quantum circuits require an ancilla qubit with controlled multiqubit gates that can be quite costly for near-term quantum hardware. In this paper, we show that a wide class of Hamiltonians relevant to condensed-matter physics and quantum chemistry contain symmetries that can be exploited to avoid the use of the Hadamard test. We propose a multifidelity estimation protocol that can be used to compute such quantities, showing that our approach, when combined with efficient single-fidelity estimation protocols, provides a substantial reduction in circuit depth. In addition, we develop a unified theory of quantum Krylov subspace algorithms and present three quantum-classical algorithms for the ground- and excited-state energy estimation problems, where each algorithm provides various advantages and disadvantages in terms of total number of calls to the quantum computer, gate depth, classical complexity, and stability of the generalized eigenvalue problem within the Krylov subspace.

arXiv:2109.06868•Physical Review A•Feb 14, 2022•109 citations

A New Angle on Quantum Subspace Diagonalization for Quantum Chemistry

Xeno De Vriendt, Jacob Bringewatt, Nik O. Gjonbalaj +5 more

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 $10^4$, 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.

quant-pharXiv:2602.11985•Feb 13, 2026•0 citations

Orthogonal Quantum Krylov Diagonalisation

Hadi Rammal, Alexandre Perrin, Oumaya Ladhari +3 more

Quantum subspace-diagonalization methods, particularly Quantum Krylov Diagonalization (QKD), provide a promising route for computing low-energy spectra of quantum many-body Hamiltonians. However, existing quantum Krylov approaches rely on non-orthogonal Krylov bases, requiring overlap-matrix regularization that limits numerical stability and accuracy. In this work, we introduce an Orthogonal Quantum Krylov Diagonalization (OQKD) framework that reformulates the classical Lanczos recursion at the operator level, enabling an orthogonal quantum implementation of Krylov-subspace diagonalization. By expressing Lanczos vectors as polynomial transformations of the Hamiltonian, OQKD reproduces the orthogonality, tridiagonal structure, and convergence behavior of the classical Lanczos algorithm thus eliminating the need for overlap-matrix regularization. We further show that the required Lanczos polynomials can be implemented using block encoding and Generalized Quantum Signal Processing with the same asymptotic query complexity as Chebyshev-based QKD methods. Numerical simulations of the $J_1$--$J_2$ Heisenberg model confirm the classical Lanczos convergence and numerical stability of the proposed method, while the measurement-complexity scaling is established analytically. Building upon the OQKD framework, we then introduce a restarted state-preparation protocol that replaces a single high-degree polynomial transformation with a sequence of fixed low-degree transformations, maintaining an affordable block encoding success probability while retaining comparable convergence. These results establish OQKD as an orthogonal quantum analog of the classical Lanczos algorithm and identify the restarted protocol as a promising state-preparation strategy for Quantum Phase Estimation.

quant-pharXiv:2607.09476•Jul 13, 2026•0 citations

Sample-Based Quantum Linear Solver and Bounds on Krylov-State Sampling

Byeongyong Park, Keunhong Jeong, Doyeol Ahn

To solve linear systems $Ax=b$, we propose a sample-based quantum linear solver combining quantum Krylov-state sampling with classical variational diagonalization. Rather than simulating the cost Hamiltonian $H_b(A)=A^\dagger(I-|b\rangle\langle b|)A$, we measure quantum Krylov states $e^{-iAT}|b\rangle$ generated by the original Hermitian operator $A$ in the computational basis. We then classically diagonalize the projected cost Hamiltonian to reconstruct an approximate solution. Using a representation of $A^{-1}|b\rangle$ as a linear combination of quantum Krylov states, we derive lower bounds on computational-basis sampling probabilities from solution amplitudes. We establish support-discovery guarantees for finite nonnegative-time grid sampling and signed-time sampling, which permits both positive and negative evolution times. The former bounds the maximum evolution time, whereas the latter improves ideal shot complexity at the cost of occasional long evolutions. For a condition-number bound $κ$ on $A$, a lower bound $β_L$ on the solution probability weight of each of $L$ target basis states, and failure probability $δ$, signed-time sampling achieves $O(κ^2β_L^{-1}\log(L/δ))$ shots, matching a worst-case lower bound up to constants within an evolution-only observation model in a specified parameter regime. Finally, we analyze the effects of finite-length qDRIFT compilation and circuit reuse on sampling and derive an infidelity bound for the reconstructed solution.

quant-pharXiv:2610.23138•Oct 19, 2026•0 citations
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.
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 algorithms are a promising approach for ground-state energy estimation on near-term quantum computers. However, their sampling cost is inherently high because each Hamiltonian term is measured individually. Despite various mitigation techniques, this overhead remains a bottleneck for large-scale electronic structure problems. We introduce mirror subspace diagonalization (MSD), which approaches the theoretical lower bound on the sampling cost for quantum Krylov algorithms built upon real-time evolution. MSD uses a finite-difference formula to express the Hamiltonian as a linear combination of time-evolution unitaries with symmetrically shifted timesteps, enabling efficient estimation of the Hamiltonian matrix within the Krylov subspace. By optimizing the timestep and shifting the energy spectrum, finite-difference and statistical errors are minimized simultaneously, allowing MSD to attain the sampling-cost lower bound up to a logarithmic factor. We further apply classical post-processing to infer Hamiltonian moments, which mitigate the ground-state energy error via the Lanczos scheme. Our analysis shows MSD is particularly effective when the Hamiltonian's spectral norm is much smaller than its 1-norm, as in high-accuracy molecular simulations with large basis sets and strong electronic correlations. Numerical results for various molecular models show sampling-cost reductions of roughly 10 to 10,000 times over the conventional quantum Krylov algorithm.
Quantum Krylov subspace diagonalization (QKSD) algorithms provide a low-cost alternative to the conventional quantum phase estimation algorithm for estimating the ground- and excited-state energies of a quantum many-body system. While QKSD algorithms typically rely on using the Hadamard test for estimating Krylov subspace matrix elements of the form $\ensuremath{\langle}{\ensuremath{\phi}}_{i}|{e}^{\ensuremath{-}i\stackrel{\ifmmode \hat{}\else \^{}\fi{}}{H}\ensuremath{\tau}}|{\ensuremath{\phi}}_{j}\ensuremath{\rangle}$, the associated quantum circuits require an ancilla qubit with controlled multiqubit gates that can be quite costly for near-term quantum hardware. In this paper, we show that a wide class of Hamiltonians relevant to condensed-matter physics and quantum chemistry contain symmetries that can be exploited to avoid the use of the Hadamard test. We propose a multifidelity estimation protocol that can be used to compute such quantities, showing that our approach, when combined with efficient single-fidelity estimation protocols, provides a substantial reduction in circuit depth. In addition, we develop a unified theory of quantum Krylov subspace algorithms and present three quantum-classical algorithms for the ground- and excited-state energy estimation problems, where each algorithm provides various advantages and disadvantages in terms of total number of calls to the quantum computer, gate depth, classical complexity, and stability of the generalized eigenvalue problem within the Krylov subspace.
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 10410^4104, 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.
Quantum subspace-diagonalization methods, particularly Quantum Krylov Diagonalization (QKD), provide a promising route for computing low-energy spectra of quantum many-body Hamiltonians. However, existing quantum Krylov approaches rely on non-orthogonal Krylov bases, requiring overlap-matrix regularization that limits numerical stability and accuracy. In this work, we introduce an Orthogonal Quantum Krylov Diagonalization (OQKD) framework that reformulates the classical Lanczos recursion at the operator level, enabling an orthogonal quantum implementation of Krylov-subspace diagonalization. By expressing Lanczos vectors as polynomial transformations of the Hamiltonian, OQKD reproduces the orthogonality, tridiagonal structure, and convergence behavior of the classical Lanczos algorithm thus eliminating the need for overlap-matrix regularization. We further show that the required Lanczos polynomials can be implemented using block encoding and Generalized Quantum Signal Processing with the same asymptotic query complexity as Chebyshev-based QKD methods. Numerical simulations of the J1J_1J1​--J2J_2J2​ Heisenberg model confirm the classical Lanczos convergence and numerical stability of the proposed method, while the measurement-complexity scaling is established analytically. Building upon the OQKD framework, we then introduce a restarted state-preparation protocol that replaces a single high-degree polynomial transformation with a sequence of fixed low-degree transformations, maintaining an affordable block encoding success probability while retaining comparable convergence. These results establish OQKD as an orthogonal quantum analog of the classical Lanczos algorithm and identify the restarted protocol as a promising state-preparation strategy for Quantum Phase Estimation.
To solve linear systems Ax=bAx=bAx=b, we propose a sample-based quantum linear solver combining quantum Krylov-state sampling with classical variational diagonalization. Rather than simulating the cost Hamiltonian Hb(A)=A†(I−∣b⟩⟨b∣)AH_b(A)=A^\dagger(I-|b\rangle\langle b|)AHb​(A)=A†(I−∣b⟩⟨b∣)A, we measure quantum Krylov states e−iAT∣b⟩e^{-iAT}|b\ranglee−iAT∣b⟩ generated by the original Hermitian operator AAA in the computational basis. We then classically diagonalize the projected cost Hamiltonian to reconstruct an approximate solution. Using a representation of A−1∣b⟩A^{-1}|b\rangleA−1∣b⟩ as a linear combination of quantum Krylov states, we derive lower bounds on computational-basis sampling probabilities from solution amplitudes. We establish support-discovery guarantees for finite nonnegative-time grid sampling and signed-time sampling, which permits both positive and negative evolution times. The former bounds the maximum evolution time, whereas the latter improves ideal shot complexity at the cost of occasional long evolutions. For a condition-number bound κκκ on AAA, a lower bound βLβ_LβL​ on the solution probability weight of each of LLL target basis states, and failure probability δδδ, signed-time sampling achieves O(κ2βL−1log⁡(L/δ))O(κ^2β_L^{-1}\log(L/δ))O(κ2βL−1​log(L/δ)) shots, matching a worst-case lower bound up to constants within an evolution-only observation model in a specified parameter regime. Finally, we analyze the effects of finite-length qDRIFT compilation and circuit reuse on sampling and derive an infidelity bound for the reconstructed solution.