Quantum-Centric Algorithm for Sample-Based Krylov Diagonalization

Jeffery Yu; Javier Robledo Moreno; Joseph T. Iosue; Luke Bertels; Daniel Claudino; Bryce Fuller; Peter Groszkowski; Travis S. Humble; Petar Jurcevic; William Kirby; Thomas A. Maier; Mario Motta; Bibek Pokharel; Alireza Seif; Amir Shehata; Kevin J. Sung; Minh C. Tran; Vinay Tripathi; Antonio Mezzacapo; Kunal Sharma

Source-linked AI summary

Quantum-Centric Algorithm for Sample-Based Krylov Diagonalization

Jeffery Yu, Javier Robledo Moreno, Joseph T. Iosue, Luke Bertels, Daniel Claudino, Bryce Fuller, Peter Groszkowski, Travis S. Humble, Petar Jurcevic, William Kirby, Thomas A. Maier, Mario Motta, Bibek Pokharel, Alireza Seif, Amir Shehata, Kevin J. Sung, Minh C. Tran, Vinay Tripathi, Antonio Mezzacapo, Kunal Sharma

arXiv:2501.09702v3Jan 16, 2025quant-phcond-mat.otherphysics.comp-ph

TL;DR

Estimating many-body ground states is difficult on current quantum processors because phase estimation requires excessive circuit depth. The paper introduces SKQD, combining Krylov-generated quantum states with sample-based classical diagonalization, and reports polynomial-time convergence under sparsity and large impurity-model simulations agreeing with DMRG.

Problem
Ground-state approximation is difficult because quantum phase estimation requires circuit depths beyond current processors, while scalable alternatives remain needed for physics and chemistry.
Method
SKQD samples computational-basis bitstrings from time-evolved Krylov states and classically diagonalizes the Hamiltonian in the resulting subspace.
Results
SKQD approximates the ground-state energy in polynomial time under ground-state sparsity and polynomial reference-state overlap, and its impurity-model simulations agree excellently with DMRG.
Takeaways & Limitations
SKQD enables ground-state simulations on pre-fault-tolerant quantum processors at impurity-model sizes beyond exact diagonalization.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper addresses the difficulty of estimating low-energy spectra on current quantum processors by introducing SKQD, which combines Krylov subspaces with sample-based classical diagonalization. It proves polynomial-time convergence under stated assumptions and demonstrates large impurity-model simulations agreeing with DMRG.

Low-energy spectrum estimation is a major bottleneck in physics and chemistry, while phase estimation requires circuit depths beyond pre-fault-tolerant devices.
VQE is more hardware-efficient but its parametric optimization and stochastic observable estimation can limit scaling through measurement costs.
SKQD combines Krylov time-evolution states with quantum samples and classical Hamiltonian diagonalization to approximate the ground state.
Under ground-state sparsity and polynomial reference-state overlap, SKQD approximates the ground-state energy in polynomial time.
Experiments used 85 qubits for a 41-bath-site SIAM and 70 Heron qubits for a four-impurity model, with results in excellent agreement with DMRG.

II. SAMPLE-BASED KRYLOV QUANTUM DIAGONALIZATION (SKQD)

SKQD constructs Krylov states by time-evolving a reference state, samples their computational-basis bitstrings, and classically diagonalizes the Hamiltonian projected onto the sampled subspace. The method is designed for polynomial-size classical processing and noise resilience, with convergence analysis based on ground-state sparsity.

SKQD begins with time-evolved Krylov states generated from an initial reference state.
For each Krylov state, the algorithm prepares M = O(poly(n)) copies and measures them in the computational basis to obtain bitstrings.
The sampled bitstrings define a basis for projecting H into a polynomial-size matrix that can be diagonalized classically.
The lowest-eigenvalue eigenvector of the projected matrix supplies the sampled-subspace approximation to the ground state.
SKQD is noise-resilient and can use configuration recovery, but this robustness adds classical cost for recovery and diagonalization.
The convergence analysis assumes sparsity of the ground state in the computational basis.

A. Convergence guarantees

The convergence argument links Krylov-state sampling to recovery of the important computational-basis components of a sparse ground state. Under the stated overlap, timestep, and sampling conditions, SKQD achieves bounded ground-state-energy error with high probability.

SKQD can efficiently estimate the ground-state energy with bounded error when the ground state satisfies the defined sparsity condition.
All L important bitstrings must be sampled for the stated energy-error guarantee to apply.
The probability of sampling all L important bitstrings is at least 1 −η when each Krylov basis state receives sufficiently many samples.
The energy-error bound depends on the ground-state sparsity parameter α(0)_L.
The sample requirement scales inversely with the squared overlap |γ0|2 between the reference state and the true ground state.
The proof combines Krylov convergence, small state-approximation error, and sparsity to show that relevant bitstrings are recovered with high probability.

B. Experiments on impurity models

The experiments evaluate SKQD on single- and four-impurity Anderson models, using quantum processors and comparisons with classical reference calculations. SKQD achieves accurate energies and correlations, with further improvement from orbital optimization.

Model systems: The study examines SIAM with 41 bath modes and a four-impurity model with 7 bath modes per impurity.These systems contain 42 and 32 spinful fermionic modes, respectively.
Workflow: SKQD samples Krylov states, performs configuration recovery, and classically diagonalizes the recovered subspace to estimate ground-state properties.The workflow uses shallow Givens-rotation circuits and basis transformations involving k-adjacent natural orbitals.
Scaling: The SKQD error in SIAM does not increase when the bath size grows from K = 29 to K = 41.
Four-impurity results: The four-impurity calculation reaches a relative ground-state energy error of approximately 6 · 10^-5 after orbital optimization, compared with approximately 10^-4 in the k-adjacent natural-orbital basis.The procedure uses five self-consistent orbital-optimization cycles.

III. DISCUSSION

The discussion positions SKQD as a noise-resilient, lower-depth alternative to standard Krylov diagonalization for suitable lattice problems. Its convergence analysis assumes sparse ground states, while broader applicability remains an open practical question.

Scope: The presented implementation is limited to problems that map easily onto quantum-processor layouts, leaving ab-initio applications for future work.The authors state that near-term ab-initio use cases are out of reach for this implementation.
Advantages: SKQD combines Krylov convergence properties with reduced circuit depth because it avoids Hadamard-test subroutines.It also uses configuration recovery and classical diagonalization to improve resistance to noisy samples.
Scope: Although the convergence proof requires ground-state sparsity, the authors suggest SKQD may also be useful for non-sparse states when Krylov circuits capture relevant basis states.
Experimental reach: Experiments with up to 85 qubits and approximately 6 · 10^3 two-qubit gates agree excellently with DMRG and HCI calculations.The same agreement is reported for 70-qubit four-impurity experiments.

IV. CODE AND DATA AVAILABILITY

The paper describes the software and computational setup for Krylov-subspace construction, projection, configuration recovery, and diagonalization. These procedures reduce the Hamiltonian problem to a classically diagonalizable sampled subspace under stated assumptions.

Software: Fermionic time evolution is simulated with ffsim, while configuration recovery, projection, and diagonalization use qiskit-addon-sqd.Quantum circuits are generated and transpiled with Qiskit; DMRG uses block2, and HF/CCSD use PySCF.
Krylov construction: KQD constructs a dimension-d subspace from time-evolved reference states and solves a projected generalized eigenvalue problem.The resulting coordinate vector represents the approximate ground state in the Krylov subspace.
Krylov guarantees: In the ideal noise-free setting, the Krylov estimate satisfies 0 ≤ eE − E0 ≤ ε.The approximation can achieve constant energy error with d = O(log(1/ε)) under constant initial-state overlap and a well-behaved spectrum.
Sample-based diagonalization: SQD samples important bitstrings, forms the Hamiltonian projected into their span, and classically diagonalizes the resulting matrix to approximate E0.The approach requires sufficiently many samples to obtain the relevant bitstrings with high probability.
Near-term considerations: KQD requires O(1/ε^2) samples for matrix-element estimation and additional noise-mitigation overhead, motivating alternatives for near-term devices.SQD is described as natural for near-term devices when the target ground state is sparse.

A. Convergence proof

The convergence proof links Krylov sampling to recovery of the important bitstrings in a sparse ground state. With polynomial sparsity and polynomial initial-state overlap, SKQD can obtain these bitstrings efficiently.

Sparsity assumption: The proof assumes the ground state has L = O(poly(n)) important bitstrings under the paper’s sparsity definition.
Proof strategy: If KQD achieves additive energy error ε, the proof first bounds the error of the corresponding approximate ground state.
Bitstring recovery: Each important ground-state bitstring has overlap proportional to |γ0|^2 with at least one Krylov basis state.The argument uses expansions of Krylov states in the computational basis and bounds their coefficients.
Efficiency condition: The L important bitstrings can be sampled efficiently when the reference state has overlap |γ0|^2 ∈ O(1/poly(n)) with the exact ground state.The sampling efficiency also depends on the Krylov dimension through βL and the convergence of ε with increasing d.

B. Impurity model parameters

The impurity models use bath and hybridization representations chosen to balance physical structure with ground-state sparsity, and compare classical electronic-structure methods across hybridization strengths.

Model representation: The bath can be transformed into a basis where its non-interacting Hamiltonian is diagonal, with hybridization amplitudes V_k = V · Ξ_0k.This sacrifices locality of the hybridization term in favor of a sparse ground-state representation.
Four-impurity model: The four-impurity model uses a random bath dispersion with seven modes per impurity, scaled so min_k ε_k = −2 and max_k ε_k = 2.The random dispersion reduces the effect of a specific underlying lattice geometry.
Classical-method comparison: RHF and CISD overestimate the ground-state energy, while MP2 underestimates it increasingly as V decreases.For V > 0.16, CCSD and CCSD(T) agree with HCI and DMRG within 0.001 energy units.
Classical-method comparison: The largest reported HCI–DMRG energy deviation is ∼10−7 energy units.The comparison uses HCI with a truncation threshold of 10−7 and DMRG with bond dimension D = 4000.
Computational complexity: Both HCI and DMRG energy errors follow power-law dependence on the inverse cost-control parameter, with exponents and prefactors depending on V and method.The cost parameter is the HCI configuration-subspace size or the DMRG MPS bond dimension.
Computational complexity: Reducing HCI and DMRG errors below a threshold δ does not require exponential classical memory or runtime in 1/δ under the reported empirical scaling.Competitive systematically improvable methods would require a lower power-law exponent or prefactor.

E. Experiment details

The experiments evaluate SKQD on Heron processors with sampled Krylov dimensions, model-specific circuit costs, and a self-consistent recovery scheme for the four-impurity case.

Hardware and sampling: The experiments ran on IBM Quantum’s ibm fez, a Heron r2 processor with 156 fixed-frequency transmon qubits and tunable couplers.The hardware uses a heavy-hex lattice layout.
Hardware and sampling: Each Krylov dimension was sampled with 1 × 10^5 shots.Implementations included K = 29 in both the diagonal-bath and k-adjacent bases; K = 41 required 85 qubits.
Circuit costs: For SIAM circuits, two-qubit gates increased at 337 gates per Trotter step, reaching a maximum of 6153 gates.The reported readout error was 1.53 × 10−2, with single-qubit error 2.6 × 10−4 and two-qubit gate error 2.80 × 10−3.
Circuit costs: The four-impurity circuits used 28 bath sites and 64 qubits, with 613 two-qubit gates added per Trotter step.This represented a higher density of entangling operations than the SIAM circuits.
Configuration recovery: Self-consistent configuration recovery was used only in the four-impurity experiments, with threshold τ = 10−8 for retaining relevant basis states.States with wave-function weight above τ were included in subsequent recovery subspaces.

I. KRYLOV QUANTUM DIAGONALIZATION

Krylov quantum diagonalization estimates the ground-state energy by diagonalizing the Hamiltonian in a time-evolved subspace, with convergence controlled by subspace dimension, spectral gaps, and initial-state overlap.

Method: The Krylov states are |ψ_k⟩ := e^−ikH∆t|ψ_0⟩ for k ∈ {0, 1, . . . , d − 1}.The method then solves a generalized eigenvalue problem in the resulting subspace.
Method: The approximate ground-state energy is obtained from the lowest generalized eigenvalue associated with the Krylov-subspace projection of H.The coordinate vector v represents a state formed from the Krylov basis.
Convergence: The Krylov energy accuracy improves exponentially with subspace dimension d and worsens as the initial-state ground-state overlap |γ_0|^2 decreases.These dependencies summarize the stated convergence behavior.
Proof strategy: The proof uses a shifted Krylov space with the same Hamiltonian projection as the original space because time evolutions are unitary and commute with H.This lets the projected-space ground energy inherit the constructed approximation bound.
Convergence: For nontrivial overlap |γ_0|^2 = Θ(1) and a well-behaved spectrum, constant energy error ε is achieved with d = O(log(1/ε)).The condition requires ∆E_N−1 not to grow too quickly and ∆E_1 not to become too small.

II. PROOFS AND RELEVANT DETAILS FOR THEOREM 1

Theorem 1 establishes SKQD energy-error and sampling guarantees under ground-state sparsity, while supporting lemmas connect low energy error, sparsity, and sampled Krylov subspaces.

Algorithm: SKQD samples M computational-basis bitstrings from each of d Krylov states and classically diagonalizes H in the span of those sampled bitstrings.The Krylov states are obtained by time-evolving a reference state over multiple intervals.
Theorem 1: Theorem 1 bounds SKQD ground-state energy error when all L important bitstrings are sampled and gives a success probability of at least 1 − η for sufficiently many samples.The required sample count depends on the sparsity parameters and the Krylov reference-state overlap.
Supporting lemmas: A low-energy state is close to the ground state, with first-order 2-norm error bounded by ε/∆E1 + O(ε^2).The bound assumes a spectral gap ∆E1 and real ground-state overlap.
Supporting lemmas: If the ground state is sparse, every important bitstring appears nontrivially in at least one Krylov basis state, enabling its recovery by sampling.This property is the key link between Krylov convergence and the sampled subspace.
Theorem 1: The number of samples required to recover all L important bitstrings is inversely proportional to |γ0|^2, paralleling the corresponding KQD requirement.Here |γ0|^2 is the overlap of the initial KQD state with the ground state.
Ising-model sparsity: For the transverse-field Ising model, the ground state is sparse in the Z basis deep in the ordered phase and in the X basis deep in the disordered phase.The ordered-phase result supports O(n^k) relevant Z-basis states, while the disordered-phase result supports O(n^k) X-basis states.

V. COMPARISON BETWEEN THE SAMPLE COMPLEXITY IN SKD AND KQD IN THE TRANSVERSE FIELD ISING MODEL

The section compares SKQD and standard KQD on a perturbed transverse-field Ising model, examining sample-dependent performance and noise effects. Across tested qubit counts, SKQD outperforms standard KQD under the ground-state sparsity assumption.

Simulation setup: SKQD uses d = 15 Krylov basis states and varies the number of measured samples M per basis state.The simulations use initial state |χ0⟩ = |0n⟩ and h1 = h2 = 0.1.
Comparison: SKQD outperforms standard KQD across different numbers of qubits in the numerical simulations.The simulations extend beyond the analytical results under the ground-state sparsity assumption.
Comparison: SKQD achieves lower error than standard KQD for the perturbed transverse-field Ising model.Figure S1 compares SKQD markers with noisy KQD dashed lines.
Trotter-error analysis: The analysis assumes that the implemented time-evolution operators have bounded Trotter error γ, which induces a corresponding bound on sampled-distribution differences.The stated chain is ∥Uk − Vk∥ ≤ γ, implying ∥pk − p̂k∥1 ≤ γ.

VII. ADDITIONAL SKQD EXPERIMENTS FOR THE SINGLE IMPURITY ANDERSON MODEL

Additional SIAM experiments benchmark SKQD against DMRG for a 29-bath-site system and test whether noisy quantum-device samples contain useful signal. The reported energies and correlations agree closely with DMRG, and device samples outperform uniform samples.

Experimental setup: The 61-qubit SIAM experiment uses 29 bath sites and evaluates energy error plus two-point spin and density correlations against DMRG.The study varies the impurity onsite repulsion U and uses DMRG as the reference.
Energy accuracy: SKQD relative energy error decreases from approximately 10^-5 to approximately 10^-6 as U increases from 1 to 10.The passage attributes this trend to increased ground-state sparsity at larger U.
Correlation accuracy: SKQD spin-correlation estimates agree excellently with DMRG for most impurity-to-bath distances, with small deviations where correlations are negligible.The deviations occur for odd distances at larger j.
System-size scaling: The K = 29 bath-site accuracy does not significantly differ from the larger K = 41 result, indicating no significant deterioration with SIAM system size.This is the section’s reported system-size comparison.
Quantum-device signal: For K = 41, device-derived samples produce orders-of-magnitude lower relative energy error than uniform random samples at the same sample count.Both cases use D = 2.56 · 10^6 electronic configurations and 2.5 · 10^6 sampled bitstrings.