When Does Quantum Krylov Linear Solving Avoid Global Condition-Number Dependence?

A retained small eigenvalue is the harder test case

Most beyond-conditioning arguments become favorable when the globally ill-conditioned directions barely matter to the target solution. This paper studies the opposite, harder regime for time-evolution quantum Krylov linear solving: a vanishing eigenvalue stays solution-relevant and must be retained, so its inverse contribution can dominate the solution magnitude.

The central question is therefore whether quantum linear solving can remain efficient even when the eigenvalue responsible for the diverging condition number remains essential to the target solution. The paper answers within QKS, where time-evolved states e^{-ijτA}|b⟩ generated from the right-hand side |b⟩ span a reduced solution space, the original system is projected onto that subspace, and the small classical projected system is solved and used to reconstruct the quantum solution.

Global conditioning and normalized-state difficulty are different measures

The global condition number κ(A) describes the full spectrum of the input matrix. The paper's target is the difficulty of preparing the normalized solution state, which depends on how the input state is distributed across the spectrum and on how inverse amplification acts on the solution direction. These are not interchangeable quantities.

The paper separates two regimes. In the truncatable regime, globally small eigenvalues are solution-irrelevant and QKS recovers a familiar effective-conditioning picture in which the reduced problem itself stays uniformly well conditioned. In the directional regime central to the paper, the small eigenvalue is retained and solution-relevant, so the reduced inverse norm diverges even though the normalized solution direction remains stable.

Spectral compression keeps Krylov resources bounded

The first contribution is structural. When the normalized solution is concentrated on a compact set of spectrally resolvable modes, the solution-relevant inverse response admits a compact and stable time-evolution Krylov representation. The paper proves bounded subspace dimension m, bounded evolution time T, and bounded reconstruction overhead as the relevant eigenvalue vanishes.

Concretely, the sufficient Krylov dimension scales as m = O(max{ r / sin(δ_A/2), r / (β_A Δ_K sin(ρ/2)) }), with T = (m−1)τ and p_succ^{-1} ≤ m / s_0^2. If the solution-weighted spectral parameters r, δ_A, ρ, β_A, Δ_K, s_0, and τ stay bounded independently of the vanishing solution-relevant eigenvalue, then none of m, T, or p_succ^{-1} inherits its divergence. The bound is conditional on those parameters, not a claim that every instance compresses.

Directional stability decides normalized-state difficulty

The second contribution is geometric. The paper analyzes the projected problem in equivalent orthonormal coordinates and considers a retained-soft-mode regime in which one reduced eigenvalue approaches zero while the remaining reduced spectrum stays separated from zero. When the reduced right-hand side keeps persistent overlap with that soft direction, the reduced inverse norm diverges, yet the normalized directional sensitivity stays bounded.

The reason is that the divergent inverse amplification becomes increasingly parallel to the normalized solution direction. Normalization removes this solution-parallel component, leaving only the transverse response that can actually change the quantum state. The paper states this as: even an arbitrarily ill-conditioned reduced system can remain directionally stable when the amplification is solution-aligned.

Stability survives finite projected-system errors

The third contribution closes the gap between the idealized reduced picture and the actual algorithm. The paper proves that directional stability persists under finite projected-system errors and transfers to the actual QKS output, yielding an end-to-end complexity bound without inverse dependence on the retained small eigenvalue.

The end-to-end complexity separates implementation-specific access costs from the quantities through which the vanishing eigenvalue can act: the structural resources m, T, and p_succ^{-1}, together with the normalized-state sensitivity factors K_B and K_c, provided the Krylov Gram geometry remains stable. The paper notes that block-encoding, sparse-oracle, and Pauli/LCU realizations carry different precision and representation overheads, but none restores inverse dependence on the retained vanishing eigenvalue when its own access parameters remain bounded.

An explicit family separates divergence from bounded QKS quantities

To make the distinction concrete, the paper constructs a family in which a full inverse-amplification criterion can diverge while the corresponding QKS quantities remain bounded. In the two-dimensional construction, the reduced system retains the small eigenvalue with eigenvalues μ_1 = ε and μ_2 = 1, and the right-hand-side overlap on the soft eigendirection stays |c_1| = 1/√2 = Ω(1).

For that family, the full inverse amplification diverges as χ_filt = Θ(ε^{-1}), while m = 2, T = O(1), p_succ^{-1} = O(1), K_B = O(1), and K_c = O(ε). A high-dimensional embedding A_{ε,N} = A_ε ⊕ D_{N−2} with |b_N⟩ = |b⟩ ⊕ 0 keeps κ(A_{ε,N}) = Θ(ε^{-1}) and χ_filt = Θ(ε^{-1}) while the QKS dynamics stay confined to a two-dimensional invariant subspace, so the separation is not an artifact of the Krylov subspace coinciding with the full Hilbert space.

Where directional protection can fail

The paper is explicit that this is not a general removal of condition number from quantum linear solving. Directional protection can fail through distinct mechanisms. If active phases or significant inactive spectral mass become increasingly difficult to resolve, the required Krylov dimension or evolution horizon may grow; this is the spectral-resolution boundary captured by assumption (A2). If the Krylov Gram geometry becomes unstable, orthonormalization and reconstruction costs can become unfavorable. If several independent reduced directions become singular, normalization removes only the component parallel to the solution, while transverse singular directions may make K_B diverge.

The relation to existing beyond-condition-number methods is partial overlap rather than subsumption. QKS recovers an effective-truncation-type regime when globally small directions are solution-negligible, but it additionally requires compact time-evolution representability and stable basis geometry. The paper also frames the mechanism physically through linearized structural response near a simple mechanical instability, where a critical stiffness mode approaches zero while the remaining spectrum stays nonsingular; if the applied load has nonzero overlap with that critical mode, the unnormalized response grows along one soft direction while its normalized direction becomes increasingly stable.

Check solution-weighted representability before trusting the condition number

The practical priority this paper sets is to stop reading the global condition number as a complete descriptor of normalized QKS difficulty. The quantities that matter instead are solution-weighted spectral representability and the geometry of inverse amplification relative to the normalized solution direction.

For a concrete instance, the paper's own variables give the checklist: whether the solution-relevant spectrum compresses into a compact reduced space with bounded r, δ_A, ρ, β_A, Δ_K, s_0, and τ; whether the retained soft direction keeps nonvanishing right-hand-side overlap; whether the Krylov Gram geometry stays stable; and whether the divergent amplification stays solution-aligned rather than opening transverse singular directions. The separation family shows the decisive comparison directly: χ_filt = Θ(ε^{-1}) can diverge while m, T, p_succ^{-1}, and K_B remain O(1) and K_c = O(ε). The paper's own stated boundary is that this holds for the retained-soft-mode regime it analyzes, not for arbitrary multi-mode singular limits.

Sources used in this answer