INTRODUCTION
Kernel methods provide a principled framework for supervised learning, combining nonlinear decision boundaries with convex training and a clear geometric interpretation through reproducing kernel Hilbert spaces (RKHS) Hofmann et al. [11 ] ; Talitckii et al. [24 ] . In quantum machine learning, this perspective is particularly natural: a quantum feature map embeds a classical input into a quantum state, and pairwise similarities between the resulting states define a kernel that can subsequently be used by a classical kernel learner Havlíček et al. [9 ] ; Schuld and Killoran [21 ] ; Schuld [21 ] . This forms the foundation of quantum kernel methods and quantum support vector machines (QSVMs), a prominent paradigm for near-term quantum-enhanced supervised learning Havlíček et al. [9 ] ; Schuld and Killoran [21 ] ; Schuld [21 ] .
A central practical limitation of quantum kernel learning (QKL) is the cost of acquiring the kernel matrix Thanaslip et al. [25 ] ; Rodriguez-Grasa et al. [18 ] ; Coelho et al. [3 ] . For n n n training samples, a dense kernel method requires Θ ( n 2 ) \Theta(n^2) Θ ( n 2 ) distinct pairwise similarities Schuld [21 ] . In the quantum setting, each non-trivial similarity is itself estimated from repeated circuit measurements rather than obtained as an inexpensive deterministic function evaluation. Consequently, with N s N_s N s shots per queried entry, dense kernel acquisition incurs Θ ( n 2 N s ) \Theta(n^2N_s) Θ ( n 2 N s ) circuit repetitions in addition to the O ( n 2 ) O(n^2) O ( n 2 ) storage requirement Havlíček et al. [9 ] . For normalized fidelity kernels, the diagonal entries are known analytically, but the remaining n ( n − 1 ) / 2 n(n-1)/2 n ( n − 1 ) /2 off-diagonal similarities still scale quadratically with the number of training examples. This measurement burden can dominate the cost of the learning pipeline and limits the size of datasets for which a dense QSVM is practical.
Low-rank kernel approximation provides a natural route to reducing this cost. Classical approaches include randomized matrix approximations, Random Fourier Features, Nyström methods, and Cholesky-type factorizations Mahoney [15 ] ; Rahimi and Recht [17 ] ; Hayakawa et al. [10 ] ; Du et al. [5 ] . These methods were primarily developed for settings in which kernel entries can be accessed relatively cheaply and accurately. Their use with quantum kernels introduces an additional issue: the approximation algorithm itself determines which costly quantum similarities must be measured, while every such measurement is subject to finite-shot uncertainty. For example, a Nyström approximation queries similarities involving a selected landmark set, whereas pivoted Cholesky selects subsequent columns adaptively according to the residual structure of the approximation. Thus, in QKL, the low-rank approximation also acts as a query-allocation mechanism for a stochastic quantum-kernel oracle.
Motivated by this observation, we develop ICAQKL , a finite-shot adaptive low-rank framework for quantum kernel acquisition based on incomplete Cholesky factorization. We emphasize that pivoted incomplete Cholesky itself is a classical matrix approximation technique; our contribution is its formulation and analysis under adaptive finite-shot quantum-kernel access. Rather than constructing the dense Gram matrix, ICAQKL queries only the kernel entries required by the adaptively selected pivot columns and forms the rank-r r r positive-semidefinite surrogate
K ~ r Q , ( N s ) = G ^ r ( N s ) ( G ^ r ( N s ) ) ⊤ . (1) \widetilde{K}_r^{Q,(N_s)} = \widehat{G}_r^{(N_s)}\left(\widehat{G}_r^{(N_s)}\right)^\top. \tag*{(1)} K r Q , ( N s ) = G r ( N s ) ( G r ( N s ) ) ⊤ . (1)
Under symmetry, caching, and the analytically known fidelity diagonal, a rank-r r r construction requires at most O ( n r ) O(nr) O ( n r ) fresh quantum-kernel queries, compared with Θ ( n 2 ) \Theta(n^2) Θ ( n 2 ) for dense acquisition. When r ≪ n r \ll n r ≪ n , this reduces the corresponding measurement count from Θ ( n 2 N s ) \Theta(n^2N_s) Θ ( n 2 N s ) to O ( n r N s ) O(nrN_s) O ( n r N s ) .
The main technical challenge is that finite-shot noise enters an adaptive recursive factorization . An entrywise concentration bound alone is insufficient: measurement error in an early queried entry can perturb the current Cholesky column, alter residual scores, change later pivots, and recursively propagate through the final low-rank factor. To address this difficulty, we introduce an exact-entry comparator that is constrained to follow the same pivot sequence selected by the finite-shot algorithm. This path-conditioned construction separates two fundamentally different sources of error: the structural rank-r r r approximation error associated with the selected pivot path and the numerical perturbation induced by finite-shot kernel estimation .
Using this comparison, we develop a non-asymptotic perturbation analysis that begins with concentration for adaptively selected kernel queries, quantifies finite-shot perturbations of pivot scores and recursive Cholesky columns, and leads to a spectral error bound
E r ( N s ) : = ∥ K Q − K ~ r Q , ( N s ) ∥ 2 ≤ ε r ( P ^ r ) + ( 2 β r + Δ r ) Δ r , (2) \mathcal{E}_r^{(N_s)} := \left\|K^Q-\widetilde{K}_r^{Q,(N_s)}\right\|_2 \le\varepsilon_r(\widehat{P}_r)+(2\beta_r+\Delta_r)\Delta_r, \tag*{(2)} E r ( N s ) := K Q − K r Q , ( N s ) 2 ≤ ε r ( P r ) + ( 2 β r + Δ r ) Δ r , (2)
where ε r ( P ^ r ) \varepsilon_r(\widehat{P}_r) ε r ( P r ) is the exact structural error along the selected pivot path, Δ r \Delta_r Δ r measures the finite-shot factor perturbation, and β r \beta_r β r controls the norm of the corresponding exact path-conditioned factor. For a fixed stable rank, our analysis gives Δ r = O ( log ( M r / δ ) N s ) \Delta_r = O\left(\sqrt{\frac{\log(M_r/\delta)}{N_s}}\right) Δ r = O ( N s l o g ( M r / δ ) ) thereby making explicit how measurement precision and approximation rank enter the final kernel error.
We then propagate this kernel approximation through the complete QSVM learning problem. Rather than assuming a unique dual optimizer, we control the distance of the finite-shot solution to the exact optimal set under a quadratic-growth condition. The analysis further extends to previously unseen test points, where prediction requires only r r r additional pivot–test kernel measurements. By accounting explicitly for the conditioning of the associated triangular Cholesky extension and for the SVM intercept, we obtain decision-function perturbation and margin-preservation guarantees. The resulting theory therefore provides an end-to-end chain from finite-shot quantum measurements, through adaptive low-rank kernel construction and QSVM optimization, to out-of-sample classification.
We evaluate ICAQKL on standard and biomedical classification benchmarks [14 , 28 , 29 ] . On capped subsets where dense quantum-kernel construction is tractable, ICAQKL closely tracks the predictive performance of the full QSVM while requiring substantially fewer kernel evaluations. We additionally compare against a Nyström-QSVM baseline and observe that the relative performance of the two low-rank constructions depends on the approximation rank: Nyström can provide lower reconstruction error at small ranks, whereas the residual-driven ICAQKL construction becomes competitive or more accurate in several larger-rank settings. Across the reported capped biomedical tasks at rank r = 30 r = 30 r = 30 , ICAQKL also provides a favorable measured accuracy–runtime trade-off relative to the evaluated Nyström implementation.
Our main contributions are summarized as follows:
Query-efficient adaptive quantum-kernel acquisition. We formulate ICAQKL as an adaptive incomplete-Cholesky construction under finite-shot quantum-kernel access, which requires O ( n r ) O(nr) O ( n r ) fresh training-kernel queries through rank r r r , compared with Θ ( n 2 ) \Theta(n^2) Θ ( n 2 ) for dense kernel acquisition.
Finite-shot perturbation theory for adaptive factorization. We establish high-probability concentration for adaptively selected quantum-kernel queries in Theorem 1 and analyze how measurement noise propagates through residual scores, pivot selection, and recursively constructed Cholesky factors. The resulting path-conditioned bound in Theorem 2 separates structural low-rank approximation error from finite-shot perturbation.
End-to-end stability guarantees for QSVMs. We propagate finite-shot kernel perturbation via the complete learning problem. Theorem 3 establishes uniform QSVM dual-objective perturbation, exact-objective suboptimality, and, under quadratic growth, distance of finite-shot solution to the exact optimal set. We further derive out-of-sample kernel-vector, intercept-aware decision-function, and margin-preservation guarantees.
Empirical characterization of the accuracy–measurement trade-off. Experiments on standard and biomedical datasets show that ICAQKL remains close to dense QSVM performance on tractable matched subsets while substantially reducing the number of acquired kernel entries. Comparisons with the evaluated Nyström baseline characterize the rank-dependent trade-off between reconstruction quality, predictive accuracy, and measured runtime rather than asserting universal dominance of low-rank approximation method.
RELATED WORKS
Quantum kernel methods provide a direct connection between quantum feature maps and classical supervised learning. Early work shows that quantum devices can be used to estimate kernel functions associated with data embeddings in Hilbert space and combine them with classical SVMs Havlíček et al. [9 ] . Encoding data into quantum states can be interpreted as a nonlinear feature map, where inner products between quantum states naturally define kernels for classification Schuld and Killoran [21 ] . This has been later generalized by the observation that many supervised quantum learning models can be viewed as kernel methods Schuld [21 ] .
Subsequent work has studied both the promise and the limitations of quantum kernels. Several studies have shown that their effectiveness depends strongly on the choice of embedding, the induced inductive bias, and the alignment between the kernel geometry and the target task structure [13 , 12 ] . Recent analyses have also shown that quantum kernels may suffer from concentration and alignment issues, especially when chosen feature maps are not well suited to the data distribution, thereby limiting the effectiveness of the resulting classifier despite the high dimensionality of the underlying Hilbert space [22 , 19 ] (Thanasilp et al. 2024). These results have increased attention to task alignment, sample efficiency, and the practical cost of kernel estimation.
Additionally, even when a quantum kernel is informative, training requires constructing an ( n × n ) (n \times n) ( n × n ) Gram matrix, which becomes expensive as the dataset grows.
Studies have thus explored low-rank approximation and other resource-reduction strategies, including Nyström-based compression [4 , 16 ] for quantum kernel target alignment and related kernel-construction [3 , 23 ] . However, the quality of Nyström approximation depends strongly on the choice of landmark points and can deteriorate when the selected samples are not sufficiently representative of the full kernel matrix. Pivoted Cholesky decompositions provide an alternative that greedily selects pivots according to the residual structure of the matrix and constructs a factorization of the form K ≈ G G T \mathbf{K} \approx\mathbf{G}\mathbf{G}^{\mathsf{T}} K ≈ G G T [7 , 8 , 1 ] . Cholesky-type decompositions have been used as effective low-rank surrogates for dense PSD matrices, and recent work has studied pivoted Cholesky as a practical approximation tool for large kernel matrices with strong empirical and theoretical behavior [2 , 6 ] . While low-rank approximation has recently been considered in scalable quantum kernel learning, existing work has mainly focused on Nyström-based methods; in contrast, we study adaptive incomplete Cholesky as a PSD-low-rank surrogate alternative.
PRELIMINARIES
This section introduces the quantum fidelity kernel and its finite-shot estimation model used throughout the paper. These definitions establish the exact and stochastic kernel objects that will later be distinguished in the ICAQKL construction.
Quantum feature maps and fidelity kernels. Quantum kernel methods embed a classical input x ∈ X ⊆ R d \mathbf{x} \in\mathcal{X} \subseteq\mathbb{R}^{d} x ∈ X ⊆ R d into a complex high-dimensional Hilbert space H \mathcal{H} H via a data-dependent unitary, U ϕ : X → U ( 2 q ) U_{\phi} : \mathcal{X} \to U(2^{q}) U ϕ : X → U ( 2 q ) , where U ( 2 q ) U(2^{q}) U ( 2 q ) is the unitary group on q q q qubits, U ( 2 q ) = { U ∈ C 2 q × 2 q ∣ U † U = U U † = I } U(2^{q}) = \{U \in\mathbb{C}^{2^{q} \times2^{q}} \mid U^{\dagger}U = UU^{\dagger} = \mathbf{I}\} U ( 2 q ) = { U ∈ C 2 q × 2 q ∣ U † U = U U † = I } . The corresponding quantum feature state is obtained by applying U ϕ ( x ) U_{\phi}(\mathbf{x}) U ϕ ( x ) to the computational basis state, i.e., ∣ ϕ ( x ) ⟩ = U ϕ ( x ) ∣ 0 ⟩ ⊗ q \lvert\phi(\mathbf{x})\rangle= U_{\phi}(\mathbf{x})\lvert0\rangle^{\otimes q} ∣ ϕ ( x )⟩ = U ϕ ( x ) ∣ 0 ⟩ ⊗ q . Since dim ( H ) = 2 q \dim(\mathcal{H}) = 2^{q} dim ( H ) = 2 q , this embedding induces a feature space whose dimension grows exponentially with the number of qubits q q q . The geometry of this space is characterized by the embedded states { ∣ ϕ ( x ) ⟩ } x ∈ X \{\lvert\phi(\mathbf{x})\rangle\}_{\mathbf{x}\in\mathcal{X}} {∣ ϕ ( x )⟩ } x ∈ X , with pairwise similarity measured by their fidelity, where larger fidelity indicates greater similarity, while smaller fidelity indicates stronger separation.
Definition 1 (Quantum fidelity kernel). For x i , x j ∈ X \mathbf{x}_{i}, \mathbf{x}_{j} \in\mathcal{X} x i , x j ∈ X with feature states ∣ ϕ ( x i ) ⟩ \lvert\phi(\mathbf{x}_{i})\rangle ∣ ϕ ( x i )⟩ and ∣ ϕ ( x j ) ⟩ \lvert\phi(\mathbf{x}_{j})\rangle ∣ ϕ ( x j )⟩ , the fidelity-based quantum kernel is defined as k Q ( x i , x j ) = ∣ ⟨ ϕ ( x j ) ∣ ϕ ( x i ) ⟩ ∣ 2 = Tr [ ρ ϕ ( x i ) ρ ϕ ( x j ) ] k^{\mathrm{Q}}(\mathbf{x}_{i},\mathbf{x}_{j}) = \left|\langle\phi(\mathbf{x}_{j}) \mid\phi(\mathbf{x}_{i})\rangle\right|^{2} = \operatorname{Tr}[\rho_{\phi}(\mathbf{x}_{i})\rho_{\phi}(\mathbf{x}_{j})] k Q ( x i , x j ) = ∣ ⟨ ϕ ( x j ) ∣ ϕ ( x i )⟩ ∣ 2 = Tr [ ρ ϕ ( x i ) ρ ϕ ( x j )] .
This kernel measures similarity in the quantum feature space and is symmetric and positive semidefinite (PSD), enabling its use in kernel methods such as support vector machines (SVMs). For a dataset { x i } i = 1 n \{x_i\}_{i=1}^{n} { x i } i = 1 n , the corresponding quantum Gram matrix K Q ∈ R n × n \mathbf{K}^{Q} \in\mathbb{R}^{n \times n} K Q ∈ R n × n is defined by K i j Q = κ Q ( x i , x j ) K_{ij}^{Q}=\kappa^{Q}(x_i,x_j) K ij Q = κ Q ( x i , x j ) .
Finite shot-based kernel estimation. On quantum hardware, kernel entries are not computed exactly but estimated through repeated circuit executions. We adopt an overlap-based estimation procedure that avoids the ancilla qubits and controlled-SWAP operations Volkoff and Subaşı [26 ] required by SWAP-test methods. In particular, each kernel value is κ Q ( x i , x j ) = ∣ ⟨ 0 ∣ ⊗ q U ϕ † ( x j ) U ϕ ( x i ) ∣ 0 ⟩ ⊗ q ∣ 2 \kappa^{Q}(x_i,x_j)=\left|\langle0|^{\otimes q}U_{\phi}^{\dagger}(x_j)U_{\phi}(x_i)|0\rangle^{\otimes q}\right|^2 κ Q ( x i , x j ) = ⟨ 0 ∣ ⊗ q U ϕ † ( x j ) U ϕ ( x i ) ∣0 ⟩ ⊗ q 2 . Let X s ( i j ) ∈ { 0 , 1 } X_s^{(ij)} \in\{0,1\} X s ( ij ) ∈ { 0 , 1 } , s = 1 , … , N s s=1,\ldots,N_s s = 1 , … , N s indicate whether the s s s th circuit execution returns the all-zero outcome. Under the finite-shot sampling model, X s ( i j ) ∼ i . i . d . Bernoulli ( κ Q ( x i , x j ) ) X_s^{(ij)} \overset{\mathrm{i.i.d.}}{\sim} \operatorname{Bernoulli}\left(\kappa^{Q}(x_i,x_j)\right) X s ( ij ) ∼ i.i.d. Bernoulli ( κ Q ( x i , x j ) ) . The empirical quantum-kernel estimator is therefore
κ ^ N s Q ( x i , x j ) : = 1 N s ∑ s = 1 N s X s ( i j ) . \widehat{\kappa}_{N_s}^{Q}(x_i,x_j):=\frac{1}{N_s}\sum_{s=1}^{N_s}X_s^{(ij)}. κ N s Q ( x i , x j ) := N s 1 s = 1 ∑ N s X s ( ij ) .
Proposition 1 (Finite-shot overlap estimator). For any x , x ′ ∈ X x,x' \in\mathcal{X} x , x ′ ∈ X , let κ ^ N s Q ( x , x ′ ) \widehat{\kappa}_{N_s}^{Q}(x,x') κ N s Q ( x , x ′ ) denote the empirical estimator obtained from N s N_s N s independent circuit repetitions, defined as the empirical frequency of observing the all-zero outcome. Then, it is unbiased and satisfies E [ κ ^ N s Q ( x , x ′ ) ] = κ Q ( x , x ′ ) \mathbb{E}\left[\widehat{\kappa}_{N_s}^{Q}(x,x')\right]=\kappa^{Q}(x,x') E [ κ N s Q ( x , x ′ ) ] = κ Q ( x , x ′ ) and Var ( κ ^ N s Q ( x , x ′ ) ) = κ Q ( x , x ′ ) ( 1 − κ Q ( x , x ′ ) ) N s \operatorname{Var}\left(\widehat{\kappa}_{N_s}^{Q}(x,x')\right)=\frac{\kappa^{Q}(x,x')\left(1-\kappa^{Q}(x,x')\right)}{N_s} Var ( κ N s Q ( x , x ′ ) ) = N s κ Q ( x , x ′ ) ( 1 − κ Q ( x , x ′ ) ) .
Thus, the estimator is unbiased, with standard error scaling as O ( N s − 1 / 2 ) O(N_s^{-1/2}) O ( N s − 1/2 ) , implying that accurate kernel estimation may require a large number of measurements.
Computational bottleneck: Given n n n training samples, a symmetric n × n n \times n n × n Gram matrix contains n ( n + 1 ) / 2 n(n+1)/2 n ( n + 1 ) /2 distinct upper-triangular entries. For the normalized fidelity kernel, however, the n n n diagonal entries satisfy K i i Q = 1 K_{ii}^{Q}=1 K ii Q = 1 analytically. Hence dense finite-shot acquisition requires n ( n − 1 ) / 2 n(n-1)/2 n ( n − 1 ) /2 fresh off-diagonal quantum-kernel queries. With N s N_s N s shots per entry, the total number of circuit executions scales as O ( n 2 N s ) O(n^2N_s) O ( n 2 N s ) , which quickly becomes prohibitive as the dataset size increases. Since each evaluation involves executing both U ϕ U_{\phi} U ϕ and U ϕ † U_{\phi}^{\dagger} U ϕ † , the runtime additionally depends on circuit depth and hardware execution cost. This quadratic scaling in n n n is a primary computational bottleneck of QKL and motivates the scalable low-rank approximation framework developed in the next section.
METHODOLOGY
We now present ICAQKL, a query-efficient framework for quantum kernel learning under finite-shot access. The pivoted incomplete-Cholesky mechanism underlying the low-rank construction is classical; our focus is instead on how such an adaptive construction behaves when every required quantum-kernel entry must be estimated from stochastic circuit measurements. This distinction is important because finite-shot estimation affects not only individual kernel values, but also the residual scores that determine future pivots and the recursively constructed Cholesky factor.
Accordingly, our analysis separates an exact-entry comparator from the actual finite-shot ICAQKL recursion . The exact comparator follows a prescribed pivot sequence using the ideal quantum kernel and therefore retains the usual positive-semidefinite Cholesky residual structure. The finite-shot recursion instead operates on noisy overlap estimates. Although its constructed surrogate remains positive semidefinite by construction, its residual relative to the ideal kernel need not be positive semidefinite. This separation enables us to isolate structural low-rank approximation error from finite-shot numerical error and propagate both effects to the final QSVM classifier.
Finite-Shot Adaptive Quantum-Kernel Factorization
Let K Q ∈ R n × n \mathbf{K}^{Q}\in\mathbb{R}^{n\times n} K Q ∈ R n × n , K i j Q = κ Q ( x i , x j ) K_{ij}^{Q}=\kappa^{Q}(x_i,x_j) K ij Q = κ Q ( x i , x j ) be the ideal quantum Gram matrix. For every newly required off-diagonal entry, ICAQKL queries the finite-shot estimator κ ^ N s Q \widehat{\kappa}_{N_s}^{Q} κ N s Q introduced in Proposition Proposition 3, while the normalized fidelity diagonal K i i Q = 1 K_{ii}^{Q}=1 K ii Q = 1 is supplied analytically. We now describe how these queries are selected adaptively by the incomplete-Cholesky recursion.
Exact-entry reference construction. For comparison, consider first an exact-entry Cholesky recursion. After t t t iterations, define K ~ t Q : = G t G t T \widetilde{\mathbf{K}}_{t}^{Q}:=\mathbf{G}_{t}\mathbf{G}_{t}^{\mathsf{T}} K t Q := G t G t T , R t : = K Q − K ~ t Q \mathbf{R}_{t}:=\mathbf{K}^{Q}-\widetilde{\mathbf{K}}_{t}^{Q} R t := K Q − K t Q , d i , t : = ( R t ) i i d_{i,t}:=(\mathbf{R}_{t})_{ii} d i , t := ( R t ) ii . For the exact recursion, R t ⪰ 0 \mathbf{R}_{t}\succeq0 R t ⪰ 0 , and therefore d i , t ≥ 0 d_{i,t}\geq0 d i , t ≥ 0 . The greedy pivot is p t ∈ arg max i ∈ I t − 1 d i , t − 1 p_t\in\arg\max_{i\in\mathcal{I}_{t-1}}d_{i,t-1} p t ∈ arg max i ∈ I t − 1 d i , t − 1 , where I t − 1 \mathcal{I}_{t-1} I t − 1 is the set of indices not previously selected. The next column is
G i t = K i p t Q − ∑ ℓ = 1 t − 1 G i ℓ G p t ℓ d p t , t − 1 . (3) G_{it}=\frac{K_{ip_t}^{Q}-\sum_{\ell=1}^{t-1}G_{i\ell}G_{p_t\ell}}{\sqrt{d_{p_t,t-1}}}. \tag*{(3)} G i t = d p t , t − 1 K i p t Q − ∑ ℓ = 1 t − 1 G i ℓ G p t ℓ . (3)
The exact residual diagonals satisfy 0 ≤ d i , t = d i , t − 1 − G i t 2 ≤ d i , t − 1 0\leq d_{i,t}=d_{i,t-1}-G_{it}^{2}\leq d_{i,t-1} 0 ≤ d i , t = d i , t − 1 − G i t 2 ≤ d i , t − 1 . Moreover, if ρ = rank ( K Q ) \rho=\operatorname{rank}(\mathbf{K}^{Q}) ρ = rank ( K Q ) and the recursion executes ρ \rho ρ strictly positive pivots, then K Q = G ρ G ρ T \mathbf{K}^{Q}=\mathbf{G}_{\rho}\mathbf{G}_{\rho}^{\mathsf{T}} K Q = G ρ G ρ T . The detailed developments are provided in the Appendix.
Finite-shot ICAQKL recursion. The actual finite-shot algorithm does not observe d i , t d_{i,t} d i , t . Instead, it maintains scores s ^ i , t \widehat{s}_{i,t} s i , t initialized by s ^ i , 0 = 1 \widehat{s}_{i,0}=1 s i , 0 = 1 . At iteration t t t , ICAQKL selects p ^ t ∈ arg max i ∈ I t − 1 s ^ i , t − 1 \widehat{p}_t\in\arg\max_{i\in\mathcal{I}_{t-1}}\widehat{s}_{i,t-1} p t ∈ arg max i ∈ I t − 1 s i , t − 1 . The corresponding Cholesky column is computed using the finite-shot kernel estimates
G ^ i t ( N s ) = K ^ i p ^ t Q − ∑ ℓ = 1 t − 1 G ^ i ℓ ( N s ) G ^ p ^ t ℓ ( N s ) s ^ p ^ t , t − 1 . (4) \widehat{G}_{it}^{(N_s)}=\frac{\widehat{K}_{i\widehat{p}_t}^{Q}-\sum_{\ell=1}^{t-1}\widehat{G}_{i\ell}^{(N_s)}\widehat{G}_{\widehat{p}_t\ell}^{(N_s)}}{\sqrt{\widehat{s}_{\widehat{p}_t,t-1}}}. \tag*{(4)} G i t ( N s ) = s p t , t − 1 K i p t Q − ∑ ℓ = 1 t − 1 G i ℓ ( N s ) G p t ℓ ( N s ) . (4)
where K ^ i p ^ t Q = κ ^ N s Q ( x i , x p ^ t ) \widehat{K}_{i\widehat{p}_t}^{Q}=\widehat{\kappa}_{N_s}^{Q}(x_i,x_{\widehat{p}_t}) K i p t Q = κ N s Q ( x i , x p t ) for a newly queried off-diagonal entry while analytic diagonal values and previously queried symmetric entries are reused whenever available. The scores are updated according to s ^ i , t : = [ s ^ i , t − 1 − ( G ^ i t ( N s ) ) 2 ] + \hat{s}_{i,t} := [\hat{s}_{i,t-1}-(\hat{G}_{it}^{(N_s)})^2]_+ s ^ i , t := [ s ^ i , t − 1 − ( G ^ i t ( N s ) ) 2 ] + , [ a ] + : = max { a , 0 } [a]_+ := \max\{a,0\} [ a ] + := max { a , 0 } , where s ^ i , t \hat{s}_{i,t} s ^ i , t is a finite-shot pivot score rather than the diagonal of an assumed PSD residual. After r r r iterations, the resulting surrogate is
K ~ r Q , ( N s ) : = G ^ r ( N s ) ( G ^ r ( N s ) ) T . (5) \tilde{K}_{r}^{Q,(N_s)} := \hat{G}_{r}^{(N_s)}\left(\hat{G}_{r}^{(N_s)}\right)^{\mathsf{T}} . \tag*{(5)} K ~ r Q , ( N s ) := G ^ r ( N s ) ( G ^ r ( N s ) ) T . (5)
It is symmetric positive semidefinite and has rank at most r r r by construction.
Stopping rule and Query complexity. The recursion terminates either at a prescribed maximum rank r max r_{\max} r m a x or when max i ∈ I t s ^ i , t ≤ ϵ \max_{i\in\mathcal{I}_t}\hat{s}_{i,t}\leq\epsilon max i ∈ I t s ^ i , t ≤ ϵ . Under symmetry, and the analytic fidelity diagonal, iteration t t t requires at most n − t n-t n − t fresh off-diagonal circuit evaluations. Thus, M r = ∑ t = 1 r ( n − t ) ≤ n r M_r=\sum_{t=1}^{r}(n-t)\leq nr M r = ∑ t = 1 r ( n − t ) ≤ n r . In contrast, constructing the complete symmetric fidelity Gram matrix requires M f u l l = n ( n − 1 ) 2 M_{\mathrm{full}}=\frac{n(n-1)}{2} M full = 2 n ( n − 1 ) off-diagonal circuit evaluations.
Theorem 1 (Adaptive finite-shot concentration). Suppose ICAQKL performs at most M r M_r M r training-kernel queries through rank r r r . Then, for any δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , with probability at least 1 − δ 1-\delta 1 − δ ,
max 1 ≤ m ≤ M r ∣ κ ^ N s Q ( x i m , x j m ) − κ Q ( x i m , x j m ) ∣ ≤ η s , (6) \max_{1\leq m\leq M_r}\left|\hat{\kappa}_{N_s}^{Q}(x_{i_m},x_{j_m})-\kappa^{Q}(x_{i_m},x_{j_m})\right|\leq\eta_s , \tag*{(6)} 1 ≤ m ≤ M r max κ ^ N s Q ( x i m , x j m ) − κ Q ( x i m , x j m ) ≤ η s , (6) where η s : = log ( 2 M r / δ ) 2 N s \eta_s:=\sqrt{\frac{\log(2M_r/\delta)}{2N_s}} η s := 2 N s l o g ( 2 M r / δ ) , and q m = ( i m , j m ) q_m=(i_m,j_m) q m = ( i m , j m ) is the m m m -th adaptively selected fresh query.
Proof sketch. The key point is that the queried pair q m q_m q m may depend on all preceding finite-shot observations. Conditional on this history, however, the N s N_s N s shots used for the next query are fresh Bernoulli measurements. Hoeffding concentration therefore applies conditionally, and a union bound over the chronological query indices yields (6) . The full proof is given in the Appendix.
Theorem 1 establishes an O ( N s − 1 / 2 ) O(N_s^{-1/2}) O ( N s − 1/2 ) oracle-level accuracy guarantee despite adaptive query selection. This alone does not control the final Cholesky surrogate since an early kernel-estimation error can modify the factor, perturb future scores, and consequently alter subsequent pivots.
Path-Conditioned Finite-Shot Stability
To disentangle pivot-path effects from numerical finite-shot error, let P ^ r = ( p ^ 1 , … , p ^ r ) \hat{P}_r=(\hat{p}_1,\ldots,\hat{p}_r) P ^ r = ( p ^ 1 , … , p ^ r ) be the pivot sequence selected by finite-shot ICAQKL, and let G r P ^ r G_r^{\hat{P}_r} G r P ^ r be an exact-entry Cholesky factor constrained to follow this same pivot sequence. Define the finite-shot score discrepancy ζ t : = ∥ s ^ t − d t P ^ t ∥ ∞ , I t \zeta_t:=\left\|\hat{s}_t-d_t^{\hat{P}_t}\right\|_{\infty,\mathcal{I}_t} ζ t := s ^ t − d t P ^ t ∞ , I t . We shows that the finite-shot pivot remains approximately greedy
d p ^ t , t − 1 P ^ t − 1 ≥ max i ∈ I t − 1 d i , t − 1 P ^ t − 1 − 2 ζ t − 1 . d_{\hat{p}_t,t-1}^{\hat{P}_{t-1}}\geq\max_{i\in\mathcal{I}_{t-1}}d_{i,t-1}^{\hat{P}_{t-1}}-2\zeta_{t-1}. d p ^ t , t − 1 P ^ t − 1 ≥ i ∈ I t − 1 max d i , t − 1 P ^ t − 1 − 2 ζ t − 1 .
If the gap between
Table 1.
the largest and second-largest exact same-history residual diagonals exceeds 2 ζ t − 1 2\zeta_{t-1} 2 ζ t − 1 , then the exact and finite-shot pivot choices coincide. For the numerical factor error, define Δ r : = ∥ G ^ r ( N s ) − G r P ^ r ∥ 2 \Delta_r:=\left\|\hat{G}_{r}^{(N_s)}-G_r^{\hat{P}_r}\right\|_2 Δ r := G ^ r ( N s ) − G r P ^ r 2 . Our perturbation analysis assumes that the executed path is stable: exact and finite-shot pivot quantities remain bounded below by some τ > 0 \tau>0 τ > 0 , the factor rows remain bounded, and K i i Q ≤ κ K_{ii}^{Q}\leq\kappa K ii Q ≤ κ . For the normalized fidelity kernel, κ = 1 \kappa=1 κ = 1 . These conditions prevent the reciprocal square-root normalization in (4) from becoming arbitrarily ill-conditioned.
Theorem 2 (Path-conditioned finite-shot kernel stability). *Under the stable-path conditions and on the concentration event of Theorem 1, there exists, for every fixed stable rank r r r , a finite constant C r , τ , B , κ C_{r,\tau,B,\kappa} C r , τ , B , κ such that Δ r ≤ n C r , τ , B , κ η s \Delta_r\leq\sqrt{n}C_{r,\tau,B,\kappa}\eta_s Δ r ≤ n C r , τ , B , κ η s . Define E r ( P ^ r ) : = ∥ K Q − G r P ^ r ( G r P ^ r ) T ∥ 2 \mathcal{E}_r(\hat{P}_r):=\left\|K^{Q}-G_r^{\hat{P}_r}(G_r^{\hat{P}_r})^{\mathsf{T}}\right\|_2 E r ( P ^ r ) := K Q − G r P ^ r ( G r P ^ r ) T 2 and β r : = ∥ G r P ^ r ∥ 2 \beta_r:=\left\|G_r^{\hat{P}_r}\right\|_2 β r := G r P ^ r 2 . Then the total finite-shot kernel-surrogate error satisfies
E r ( N s ) : = ∥ K Q − K ~ r Q , ( N s ) ∥ 2 ≤ E r ( P ^ r ) + ( 2 β r + Δ r ) Δ r . (7) \mathcal{E}_r^{(N_s)}:=\left\|K^{Q}-\tilde{K}_r^{Q,(N_s)}\right\|_2\leq\mathcal{E}_r(\hat{P}_r)+(2\beta_r+\Delta_r)\Delta_r. \tag*{(7)} E r ( N s ) := K Q − K ~ r Q , ( N s ) 2 ≤ E r ( P ^ r ) + ( 2 β r + Δ r ) Δ r . (7)
Consequently, for fixed r , τ , B , κ r,\tau,B,\kappa r , τ , B , κ , it holds $\mathcal{E}_r^{(N_s)}\leq ε r ( P ~ r ) + O ( log ( M r / δ ) N s ) \varepsilon_r(\widetilde{\mathcal{P}}_r)+O\left(\sqrt{\frac{\log(M_r/\delta)}{N_s}}\right) ε r ( P r ) + O ( N s l o g ( M r / δ ) ) .
Theorem 2 is the central finite-shot approximation result. It separates two effects that are conflated by a direct entrywise perturbation bound. The first, ε r ( P ~ r ) \varepsilon_r(\widetilde{\mathcal{P}}_r) ε r ( P r ) , is the structural error of the rank-r r r path itself ; the second, ( 2 β r + Δ r ) Δ r (2\beta_r+\Delta_r)\Delta_r ( 2 β r + Δ r ) Δ r , is the additional error caused by evaluating the required quantum-kernel entries with finitely many shots . The proof proceeds by recursively controlling the error of each Cholesky column and the induced pivot-score discrepancy. In particular, if E t E_t E t denotes the largest rowwise factor error and a t a_t a t the maximum error in the newly constructed column, the Appendix derives a t ≤ η s + 2 B E t − 1 r + κ ζ t − 1 2 τ 3 / 2 a_t \le\frac{\eta_s+2BE_{t-1}}{\sqrt{r}}+\frac{\kappa\zeta_{t-1}}{2\tau^{3/2}} a t ≤ r η s + 2 B E t − 1 + 2 τ 3/2 κ ζ t − 1 , E t ≤ E t − 1 2 + a t 2 E_t\le\sqrt{E_{t-1}^2+a_t^2} E t ≤ E t − 1 2 + a t 2 , and ζ t ≤ ζ t − 1 + 2 B a t \zeta_t\le\zeta_{t-1}+2Ba_t ζ t ≤ ζ t − 1 + 2 B a t . These recursions provide the required bridge from finite-shot oracle errors to the final matrix approximation.
ICAQKL Integration with QSVM
Given the training set { ( x i , y i ) } i = 1 n \{(\mathbf{x}_i,y_i)\}_{i=1}^n {( x i , y i ) } i = 1 n , with x i ∈ R d \mathbf{x}_i\in\mathbb{R}^d x i ∈ R d , y i ∈ { − 1 , + 1 } y_i\in\{-1,+1\} y i ∈ { − 1 , + 1 } , define Y : = diag ( y 1 , … , y n ) Y:=\operatorname{diag}(y_1,\ldots,y_n) Y := diag ( y 1 , … , y n ) and A : = { α ∈ R n : 0 ≤ α i ≤ C , y ⊤ α = 0 } \mathcal{A}:=\{\alpha\in\mathbb{R}^n:0\le\alpha_i\le C,y^\top\alpha=0\} A := { α ∈ R n : 0 ≤ α i ≤ C , y ⊤ α = 0 } . For a kernel matrix K \mathbf{K} K , write the soft-margin SVM dual in minimization form as J K ( α ) : = 1 2 α ⊤ Y K Y α − 1 ⊤ α J_{\mathbf{K}}(\alpha):=\frac{1}{2}\alpha^\top Y\mathbf{K}Y\alpha-\mathbf{1}^\top\alpha J K ( α ) := 2 1 α ⊤ Y K Y α − 1 ⊤ α . The exact QSVM minimizes J K Q J_{\mathbf{K}_Q} J K Q , whereas ICAQKL solves α ~ r ( N s ) ∈ arg min α ∈ A J K ~ Q , r ( N s ) ( α ) \widetilde{\alpha}_r^{(N_s)}\in\arg\min_{\alpha\in\mathcal{A}}J_{\widetilde{\mathbf{K}}_Q,r}^{(N_s)}(\alpha) α r ( N s ) ∈ arg min α ∈ A J K Q , r ( N s ) ( α ) . Since the surrogate is factored, α ⊤ Y K ~ Q , r ( N s ) Y α = ∥ ( G ^ r ( N s ) ) ⊤ Y α ∥ 2 2 \alpha^\top Y\widetilde{\mathbf{K}}_{Q,r}^{(N_s)}Y\alpha=\lVert(\widehat{\mathbf{G}}_r^{(N_s)})^\top Y\alpha\rVert_2^2 α ⊤ Y K Q , r ( N s ) Y α = ∥( G r ( N s ) ) ⊤ Y α ∥ 2 2 , so training does not require storing the dense quantum Gram matrix. Let A Q , ⋆ : = arg min α ∈ A J K Q ( α ) \mathcal{A}_{Q,\star}:=\arg\min_{\alpha\in\mathcal{A}}J_{\mathbf{K}_Q}(\alpha) A Q , ⋆ := arg min α ∈ A J K Q ( α ) be the exact optimal set. We use the following standard quadratic-growth condition to convert objective perturbation into optimizer stability.
Assumption 1. There exists μ > 0 \mu>0 μ > 0 such that, for every α ∈ A \alpha\in\mathcal{A} α ∈ A , J K Q ( α ) − J K Q ⋆ ≥ μ 2 dist ( α , A Q , ⋆ ) 2 J_{\mathbf{K}_Q}(\alpha)-J_{\mathbf{K}_Q}^\star\ge\frac{\mu}{2}\operatorname{dist}(\alpha,\mathcal{A}_{Q,\star})^2 J K Q ( α ) − J K Q ⋆ ≥ 2 μ dist ( α , A Q , ⋆ ) 2 .
Assumption 1 ensures that any suboptimal feasible point is bounded away from the optimal set, while near-optimal objective values imply proximity to the set of optimal solutions A Q , ⋆ \mathcal{A}_{Q,\star} A Q , ⋆ .
Theorem 3 (QSVM learning stability). Let E r ( N s ) \mathcal{E}_r^{(N_s)} E r ( N s ) be the total kernel error. Then, for every α ∈ A \alpha\in\mathcal{A} α ∈ A ,
∣ J K Q ( α ) − J K ~ Q , r ( N s ) ( α ) ∣ ≤ 1 2 ∥ α ∥ 2 2 E r ( N s ) ≤ n C 2 2 E r ( N s ) . (8) \left|J_{\mathbf{K}_Q}(\alpha)-J_{\widetilde{\mathbf{K}}_{Q,r}^{(N_s)}}(\alpha)\right|\le\frac{1}{2}\lVert\alpha\rVert_2^2\mathcal{E}_r^{(N_s)}\le\frac{nC^2}{2}\mathcal{E}_r^{(N_s)}. \tag*{(8)} J K Q ( α ) − J K Q , r ( N s ) ( α ) ≤ 2 1 ∥ α ∥ 2 2 E r ( N s ) ≤ 2 n C 2 E r ( N s ) . (8)
Consequently, 0 ≤ J K Q ( α ~ r ( N s ) ) − J K Q ⋆ ≤ n C 2 E r ( N s ) 0\le J_{\mathbf{K}_Q}(\widetilde{\alpha}_r^{(N_s)})-J_{\mathbf{K}_Q}^\star\le nC^2\mathcal{E}_r^{(N_s)} 0 ≤ J K Q ( α r ( N s ) ) − J K Q ⋆ ≤ n C 2 E r ( N s ) . Under Assumption 1, dist ( α ~ r ( N s ) , A Q , ⋆ ) ≤ 2 n C 2 μ E r ( N s ) \operatorname{dist}(\widetilde{\alpha}_r^{(N_s)},\mathcal{A}_{Q,\star})\le\sqrt{\frac{2nC^2}{\mu}\mathcal{E}_r^{(N_s)}} dist ( α r ( N s ) , A Q , ⋆ ) ≤ μ 2 n C 2 E r ( N s ) . Moreover, for a fixed test point z z z with κ Q ( z , z ) ≤ κ \kappa_Q(z,z)\le\kappa κ Q ( z , z ) ≤ κ , choose α ∘ ∈ A Q , ⋆ \alpha^\circ\in\mathcal{A}_{Q,\star} α ∘ ∈ A Q , ⋆ nearest to α ~ r ( N s ) \widetilde{\alpha}_r^{(N_s)} α r ( N s ) . Then the exact and finite-shot decision functions satisfy
∣ f K Q ( z ) − f K ~ Q , r ( N s ) ( z ) ∣ ≤ κ n dist ( α ~ r ( N s ) , A Q , ⋆ ) + C n ∥ k z Q − k ~ r , z Q , ( N s ) ∥ 2 + ∣ b ∘ − b ~ r ( N s ) ∣ . (9) \left|f_{\mathbf{K}_Q}(z)-f_{\widetilde{\mathbf{K}}_{Q,r}^{(N_s)}}(z)\right|\le\kappa\sqrt{n}\operatorname{dist}(\widetilde{\alpha}_r^{(N_s)},\mathcal{A}_{Q,\star})+C\sqrt{n}\left\|\mathbf{k}_z^Q-\widetilde{\mathbf{k}}_{r,z}^{Q,(N_s)}\right\|_2+\left|b^\circ-\widetilde{b}_r^{(N_s)}\right|. \tag*{(9)} f K Q ( z ) − f K Q , r ( N s ) ( z ) ≤ κ n dist ( α r ( N s ) , A Q , ⋆ ) + C n k z Q − k r , z Q , ( N s ) 2 + b ∘ − b r ( N s ) . (9)
Theorem 3 propagates the finite-shot kernel approximation through the complete learning problem. The kernel error first controls the QSVM objective uniformly over the feasible set, then controls the distance from the approximate optimizer to the exact optimal set, and finally enters the decision-function error together with the out-of-sample kernel approximation and bias perturbation.
Out-of-sample extension and classification. For a new test point z z z , only the similarities between z z z and the selected pivots are required. The finite-shot Cholesky feature is computed recursively, ℓ = 1 , … , r \ell=1,\ldots,r ℓ = 1 , … , r ,
g ~ ℓ ( N s ) ( z ) = κ ~ N s Q ( x p ~ ℓ , z ) − ∑ m = 1 ℓ − 1 g ~ m ( N s ) ( z ) G ^ p ~ m ℓ ( N s ) G ^ p ~ ℓ ℓ ( N s ) . (10) \widetilde{g}_{\ell}^{(N_s)}(z)=\frac{\widetilde{\kappa}_{N_s}^{Q}(\mathbf{x}_{\widetilde{p}_\ell},z)-\sum_{m=1}^{\ell-1}\widetilde{g}_{m}^{(N_s)}(z)\widehat{G}_{\widetilde{p}_m\ell}^{(N_s)}}{\widehat{G}_{\widetilde{p}_\ell\ell}^{(N_s)}}. \tag*{(10)} g ℓ ( N s ) ( z ) = G p ℓ ℓ ( N s ) κ N s Q ( x p ℓ , z ) − ∑ m = 1 ℓ − 1 g m ( N s ) ( z ) G p m ℓ ( N s ) . (10)
The approximate train–test vector is then k ~ r , z Q , ( N s ) = G ^ r ( N s ) g ~ ( N s ) ( z ) \widetilde{\mathbf{k}}_{r,z}^{Q,(N_s)}=\widehat{\mathbf{G}}_r^{(N_s)}\widetilde{\mathbf{g}}^{(N_s)}(z) k r , z Q , ( N s ) = G r ( N s ) g ( N s ) ( z ) . Thus, after training, a single test point requires only r r r fresh quantum-kernel evaluations rather than n n n . Conditioned on the learned training factor, these fresh measurements satisfy
( ∑ ℓ = 1 r ∣ κ ~ N s Q ( x p ~ ℓ , z ) − κ Q ( x p ~ ℓ , z ) ∣ 2 ) 1 / 2 ≤ r 2 N s log ( 2 r δ z ) . (11) \left(\sum_{\ell=1}^{r}\left|\widetilde{\kappa}_{N_s}^{Q}(\mathbf{x}_{\widetilde{p}_\ell},z)-\kappa^Q(\mathbf{x}_{\widetilde{p}_\ell},z)\right|^2\right)^{1/2}\le\sqrt{\frac{r}{2N_s}\log\left(\frac{2r}{\delta_z}\right)}. \tag*{(11)} ( ℓ = 1 ∑ r κ N s Q ( x p ℓ , z ) − κ Q ( x p ℓ , z ) 2 ) 1/2 ≤ 2 N s r log ( δ z 2 r ) . (11)
with conditional probability at least 1 − δ z 1-\delta_z 1 − δ z . The Appendix further shows that the exact same-path extension satisfies ∥ k z Q − k ~ r , z Q ∥ 2 ≤ κ ∥ R ~ r ∥ 2 \left\|\mathbf{k}_z^Q-\widetilde{\mathbf{k}}_{r,z}^Q\right\|_2\le\kappa\left\|\widetilde{\mathbf{R}}_r\right\|_2 k z Q − k r , z Q 2 ≤ κ R r 2 and derives a finite-shot extension bound that additionally depends on the conditioning of the triangular pivot block. If the exact classifier satisfies y f K Q ( z ) ≥ γ > 0 yf_{\mathbf{K}_Q}(z)\ge\gamma>0 y f K Q ( z ) ≥ γ > 0 and the right-hand side of (9) is smaller than γ \gamma γ , then
sign ( f r Q , ( N s ) ( z ) ) = sign ( f K Q ( z ) ) . (12) \operatorname{sign}\left(f_r^{Q,(N_s)}(z)\right)=\operatorname{sign}\left(f_{\mathbf{K}_Q}(z)\right). \tag*{(12)} sign ( f r Q , ( N s ) ( z ) ) = sign ( f K Q ( z ) ) . (12)
Thus, exact reconstruction of every kernel entry is unnecessary for classification stability; only perturbations sufficiently large to cross the decision margin can change the predicted label.
Joint shot–rank convergence. For a fixed finite training set, our analysis gives sufficient conditions under which the complete finite-shot predictor converges to the exact QSVM. In particular, along a sequence of rank and shot budgets, it is sufficient that ε r ( P ^ r ) → 0 \varepsilon_r(\widehat{\mathbf{P}}_r)\to0 ε r ( P r ) → 0 , Δ r → 0 \Delta_r\to0 Δ r → 0 , r log ( 2 r / δ z ) N s → 0 \frac{r\log(2r/\delta_z)}{N_s}\to0 N s r l o g ( 2 r / δ z ) → 0 while the exact pivot blocks remain uniformly well conditioned and β r \beta_r β r remains bounded. Together with bias convergence, these conditions imply that f r Q , ( N s ) ( z ) → f K Q ( z ) f_r^{Q,(N_s)}(z)\to f_{\mathbf{K}_Q}(z) f r Q , ( N s ) ( z ) → f K Q ( z ) for every fixed z z z . For a finite training set, r ≤ ρ ≤ n r\le\rho\le n r ≤ ρ ≤ n , thus the rank limit is r ↑ ρ r\uparrow\rho r ↑ ρ rather than r → ∞ r\to\infty r → ∞ . At full exact rank ε ρ = 0 \varepsilon_\rho=0 ε ρ = 0 , and increasing the shot budget removes the remaining finite-shot contribution under the stability conditions.
Computational characteristics. The purpose of ICAQKL is to reduce the number of evaluations required to acquire a specified quantum kernel. We do not interpret this reduction as evidence that the underlying quantum kernel is classically hard to evaluate or that the resulting learning pipeline provides an end-to-end quantum computational advantage. Table 1 summarizes the principal costs. Standard low-rank landmark methods can also attain O ( n r ) O(nr) O ( n r ) kernel acquisition; ICAQKL differs in how the queried columns are selected, namely through adaptive residual information accumulated during factorization.
The resulting resource trade-off has two dimensions. Increasing the rank r r r acquires additional kernel structure and reduces structural approximation error, whereas increasing N s N_s N s improves the precision of each acquired quantum similarity. Theorems 1–3 connect these two resources to the stability of the low-rank kernel, the learned QSVM optimizer, and the resulting classifier.
EXPERIMENT RESULTS
Experimental setup
Datasets. We evaluate I C A Q K L ICAQKL I C A Q K L on both standard benchmarks and biomedical image datasets, including the Wisconsin Diagnostic Breast Cancer (WDBC) dataset Wolberg et al. [27 ] , MNIST LeCun et al. [14 ] , FashionMNIST Xiao et al. [28 ] , and several MedMNIST tasks Yang et al. [29 ] . WDBC enables exact dense-kernel comparisons, allowing direct evaluation of low-rank approximation quality. MNIST and FashionMNIST provide standard image benchmarks, while the MedMNIST datasets assess performance on biomedical classification tasks across diverse imaging modalities. Due to the quadratic cost of kernel construction and optimization, exact Full QSVM comparisons are performed on capped training subsets where dense kernel construction remains tractable. On these subsets, all methods are compared directly. For larger datasets, we focus on scalable low-rank approaches, namely Nyström-QSVM and I C A Q K L ICAQKL I C A Q K L .
Implementation details. All experiments employ q = 6 q = 6 q = 6 qubits with a fixed-depth quantum feature map, while experiments over varying approximation ranks consider r ∈ { 5 , 10 , 15 , 20 , 25 , 30 , 40 } r \in\{5, 10, 15, 20, 25, 30, 40\} r ∈ { 5 , 10 , 15 , 20 , 25 , 30 , 40 } . Reported results are averaged across multiple random seeds.
Evaluation metrics. We report test accuracy and standard classification metrics, including precision, recall, and F1-score. In addition, we evaluate computational efficiency using factorization time, total fit time, and the number of training kernel evaluations. Since fidelity-based quantum kernel estimation constitutes the primary computational bottleneck in QKL, kernel-query complexity provides a particularly informative measure of scalability. To quantify approximation quality on capped subsets where the exact kernel matrix is available, we compare the exact kernel K Q K^Q K Q and its I C A Q K L ICAQKL I C A Q K L approximation K ~ r Q , ( N s ) \widetilde{K}_{r}^{Q,(N_s)} K r Q , ( N s ) using the relative reconstruction Frobenius error, ϵ F ( K ~ r Q ) = ∥ K Q − K ~ r Q , ( N s ) ∥ F ∥ K Q ∥ F \epsilon_F(\widetilde{K}_{r}^{Q}) = \frac{\lVert K^Q-\widetilde{K}_{r}^{Q,(N_s)}\rVert_F}{\lVert K^Q\rVert_F} ϵ F ( K r Q ) = ∥ K Q ∥ F ∥ K Q − K r Q , ( N s ) ∥ F .
Main Results
Table 2 and Table 3 summarize predictive performance and computational costs. I C A Q K L ICAQKL I C A Q K L achieves strong predictive performance while substantially reducing computational costs.
Table 2. Results across standard benchmarks and MedMNIST. ICAQKL-f denotes ICAQKL trained on the full training split. Full QSVM-s and ICAQKL-s use the same capped subset. Higher is better.
Table 3: Efficiency comparison. Lower is better for fit time and training kernel evaluations.
Table 3.
Predictive performance. Table 2 shows that I C A Q K L ICAQKL I C A Q K L achieves strong accuracy across all datasets, including 95.61% on Breast Cancer, 100% on binary MNIST, 95.83% on binary FashionMNIST, and strong performance on biomedical tasks such as BreastMNIST, PneumoniaMNIST, PathMNIST, and OrganAMNIST. These results demonstrate that I C A Q K L ICAQKL I C A Q K L preserves the dominant classification-relevant structure of the quantum kernel despite aggressive low-rank approximation, while substantially reducing kernel-evaluation complexity.
Comparison with exact QSVM. On capped subsets where exact comparison is feasible, I C A Q K L ICAQKL I C A Q K L closely matches the Full QSVM baseline, achieving identical accuracy on Breast Cancer, binary MNIST, FashionMNIST, and PathMNIST and remaining within a narrow margin on the remaining datasets. These results indicate that I C A Q K L ICAQKL I C A Q K L preserves most of the predictive information contained in the dense quantum Gram matrix despite querying only a subset of kernel entries.
Computational efficiency. Table 3 shows that I C A Q K L ICAQKL I C A Q K L reduces fit time by approximately 4×–5× relative to capped Full QSVM, while substantially reducing the number of kernel evaluations. On MedMNIST datasets, Full QSVM requires 14,400 kernel evaluations, whereas I C A Q K L ICAQKL I C A Q K L uses only 3,135. These results are consistent with the theoretical O ( n r ) O(nr) O ( n r ) query complexity and demonstrate that I C A Q K L ICAQKL I C A Q K L effectively alleviates the kernel-construction bottleneck.
Comparison with classical kernels. Table 5 compares I C A Q K L ICAQKL I C A Q K L with a classical RBF-SVM on binary tasks. I C A Q K L ICAQKL I C A Q K L matches the classical baseline on Breast Cancer and binary MNIST, while outperforming it on several biomedical image datasets, including BreastMNIST, PneumoniaMNIST, PathMNIST, and OrganAMNIST. These results indicate that the low-rank quantum kernel remains competitive with strong classical kernels on medical image classification tasks.
Table 5: RBF-SVM comparison.
Table 5.
Finite-shot kernel estimation. Table 6 shows that increasing the shot budget from 64 to 512 substantially reduces the relative Frobenius error, from 1.5749 to 0.0680, while the classification accuracy remains comparatively stable. For an individual quantum-kernel entry, the finite-shot estimator has variance O ( N s − 1 ) O(N_{\mathrm{s}}^{-1}) O ( N s − 1 ) and hence standard deviation O ( N s − 1 / 2 ) O(N_{\mathrm{s}}^{-1/2}) O ( N s − 1/2 ) , as established in Proposition 3. The observed reduction in reconstruction error is therefore qualitatively consistent with decreasing finite-shot sampling uncertainty as the shot budget increases. While test accuracy changes only slightly across shot levels, the kernel reconstruction error decreases consistently with increasing shot budget, indicating improved kernel fidelity and convergence toward the analytic kernel. These results suggest that reconstruction error provides a more reliable measure of convergence than accuracy.
Table 6: BreastMNIST finite-shot ICAQKL kernel estimation. Higher is better for accuracy, lower is better for relative Frobenius error.
Table 6.
Table 1 (PDF p. 8). Complexity comparison under finite-shot quantum-kernel access.
Rank and shot ablation. Figure 1 summarizes the effect of approximation rank and shot budget on kernel quality and computational cost. Figure 1 a shows the relative Frobenius error as a function of rank. Both ICAQKL and Nyström exhibit monotonic error decay as the rank increases, consistent with the expected convergence of low-rank approximations. Nyström performs slightly better at small ranks due to its global landmark-based approximation, while ICAQKL achieves lower reconstruction error at larger ranks due to adaptive residual-driven pivot selection.
Figure 1. Rank vs. shot results. (a) Approximation error decreases with rank. (b) Runtime grows approximately linearly with rank. (c) Kernel estimation error decreases with increasing shot budget.
Figure 1 b reports runtime as a function of rank. Both ICAQKL and Nyström exhibit approximately linear growth with rank, consistent with the expected O ( n r ) O(nr) O ( n r ) scaling. ICAQKL consistently achieves lower runtime than Nyström, particularly at larger ranks where the additional O ( r 2 ) O(r^2) O ( r 2 ) landmark-kernel overhead of Nyström becomes increasingly significant. The Full QSVM baseline appears as a constant horizontal line since its cost is independent of rank. This highlights the key advantage of low-rank methods: they provide a tunable tradeoff between computational cost and approximation accuracy, while avoiding the quadratic complexity of the dense kernel approach.
Figure 1 c illustrates the effect of shot noise on kernel estimation. The relative Frobenius error decreases steadily as the number of shots increases, following the expected O ( N s − 1 / 2 ) O(N_{\mathrm{s}}^{-1/2}) O ( N s − 1/2 ) scaling of the estimator variance. As the shot budget increases, the variance of the kernel estimates decreases, leading to progressively more accurate approximations of the analytic kernel. The error bars remain small across all shot levels, indicating stable estimation. These results confirm that finite-shot quantum kernel estimation converges reliably toward the analytic kernel as measurement noise decreases.
Table 4 compares the classification accuracy and runtime of Full-QSVM, ICAQKL , and Nyström methods on subsets of the BreastMNIST, PneumoniaMNIST, and PathMNIST datasets. ICAQKL achieves predictive performance close to Full-QSVM while significantly reducing runtime. For example, on PathMNIST, ICAQKL achieves 98.03% accuracy versus 99.02% for Full-QSVM, while decreasing runtime from 162.08 s to 35.90 s. Similar trends are observed across the remaining datasets. Compared with the Nyström QSVM,
Table 4: Comparison of classification accuracy (%) and runtime (s) on a subset of data.
Table 4.
ICAQKL consistently achieves slightly higher accuracy together with lower runtime. These results suggest that adaptive residual-driven pivot selection preserves the dominant structure of the dense quantum kernel matrix more effectively than fixed landmark-based approximation while substantially reducing kernel-evaluation complexity.
CONCLUSION
We presented ICAQKL , a query-efficient framework for scalable quantum kernel learning based on adaptive incomplete Cholesky approximation. By selectively querying kernel entries, ICAQKL reduces quantum evaluation complexity from O ( n 2 ) O(n^2) O ( n 2 ) to O ( n r ) O(nr) O ( n r ) while preserving predictive performance. We established end-to-end theoretical guarantees linking finite-shot estimation and low-rank approximation to QSVM stability and prediction. We empirically showed that ICAQKL closely matches exact QSVM while outperforming Nyström-based methods at comparable ranks and achieving strong accuracy-cost tradeoffs. Empirically, ICAQKL closely matches exact QSVM on tractable subsets and consistently outperforms Nyström-based methods at comparable rank, achieving strong accuracy-cost tradeoffs. These results highlight the importance of adaptive, query-efficient kernel construction for scalable quantum machine learning. Future work includes incorporating hardware noise models and developing adaptive rank selection strategies.
MORE COMPREHENSIVE PRELIMINARIES
Classical Support Vector Machines
We consider a supervised classification dataset D = { ( x i , y i ) } i = 1 n \mathcal{D}=\{(\mathbf{x}_i,y_i)\}_{i=1}^{n} D = {( x i , y i ) } i = 1 n , where x i ∈ X ⊆ R d \mathbf{x}_i\in\mathcal{X}\subseteq\mathbb{R}^{d} x i ∈ X ⊆ R d is a d d d -dimension input vector and y i ∈ { − 1 , + 1 } y_i\in\{-1,+1\} y i ∈ { − 1 , + 1 } denotes the corresponding class label. The goal of SVM is to seek an affine decision function, f ( x ) = w ⊤ x + b f(\mathbf{x})=\mathbf{w}^{\top}\mathbf{x}+b f ( x ) = w ⊤ x + b , whose induced separating hyperplane achieves a large margin between the two classes. Here, w ∈ R d \mathbf{w}\in\mathbb{R}^{d} w ∈ R d defines the normal direction of the separating hyperplane, and b ∈ R b\in\mathbb{R} b ∈ R is a bias term. To accommodate non-separable or noisy observations, slack variables ξ = ( ξ 1 , … , ξ n ) ⊤ \boldsymbol{\xi}=(\xi_1,\ldots,\xi_n)^{\top} ξ = ( ξ 1 , … , ξ n ) ⊤ are introduced, yielding the soft-margin primal problem
min w , b , ξ 1 2 ∥ w ∥ 2 + C ∑ i = 1 n ξ i s.t. y i ( w ⊤ x i + b ) ≥ 1 − ξ i , i = 1 , … , n , ξ i ≥ 0 , i = 1 , … , n . (13) \begin{aligned}
\min_{\mathbf{w},b,\boldsymbol{\xi}}\quad&\frac{1}{2}\lVert\mathbf{w}\rVert^2+C\sum_{i=1}^{n}\xi_i \\
\text{s.t.}\quad&y_i(\mathbf{w}^{\top}\mathbf{x}_i+b)\geq1-\xi_i,\quad i=1,\ldots,n,\\
&\xi_i\geq0,\quad i=1,\ldots,n. \tag*{(13)}
\end{aligned} w , b , ξ min s.t. 2 1 ∥ w ∥ 2 + C i = 1 ∑ n ξ i y i ( w ⊤ x i + b ) ≥ 1 − ξ i , i = 1 , … , n , ξ i ≥ 0 , i = 1 , … , n . (13)
The first term in (13) promotes a large margin, whereas the slack penalty controls violations of the unit-margin constraints. The regularization C > 0 C>0 C > 0 determines the trade-off between these two objectives. Since (13) is a convex quadratic program, its dual can be obtained through Lagrangian duality. Introducing dual variables α = ( α 1 , … , α n ) ⊤ \boldsymbol{\alpha}=(\alpha_1,\ldots,\alpha_n)^{\top} α = ( α 1 , … , α n ) ⊤ , the dual problem is
max α ∑ i = 1 n α i − 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j x i ⊤ x j s.t. ∑ i = 1 n y i α i = 0 , 0 ≤ α i ≤ C , i = 1 , … , n . (14) \begin{aligned}
\max_{\boldsymbol{\alpha}}\quad&\sum_{i=1}^{n}\alpha_i-\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_i\alpha_jy_iy_j\mathbf{x}_i^{\top}\mathbf{x}_j \\
\text{s.t.}\quad&\sum_{i=1}^{n}y_i\alpha_i=0,\\
&0\leq\alpha_i\leq C,\quad i=1,\ldots,n. \tag*{(14)}
\end{aligned} α max s.t. i = 1 ∑ n α i − 2 1 i = 1 ∑ n j = 1 ∑ n α i α j y i y j x i ⊤ x j i = 1 ∑ n y i α i = 0 , 0 ≤ α i ≤ C , i = 1 , … , n . (14)
The equality constraint in (14b) follows from stationarity with respect to the unregularized intercept b b b . Consequently, the corresponding prediction function must also retain this intercept. The dual objective depends on the training inputs only through pairwise inner products x i ⊤ x j \mathbf{x}_i^{\top}\mathbf{x}_j x i ⊤ x j . This is crucial, as it enables the extension of linear SVMs to nonlinear classification via the kernel trick, where the inner products are replaced by a PSD kernel function, yielding a nonlinear classifier while preserving the convex optimization structure of the SVM. Let ϕ : X → H \phi:\mathcal{X}\to\mathcal{H} ϕ : X → H be a feature map into a Hilbert space H \mathcal{H} H , and let κ ( x i , x j ) = ⟨ ϕ ( x i ) , ϕ ( x j ) ⟩ H \kappa(\mathbf{x}_i,\mathbf{x}_j)=\langle\phi(\mathbf{x}_i),\phi(\mathbf{x}_j)\rangle_{\mathcal{H}} κ ( x i , x j ) = ⟨ ϕ ( x i ) , ϕ ( x j ) ⟩ H be the associated positive-semidefinite kernel. Replacing the Euclidean inner products in (14) by κ ( x i , x j ) \kappa(\mathbf{x}_i,\mathbf{x}_j) κ ( x i , x j ) yields
min α ∈ A J K ( α ) : = 1 2 α ⊤ Y K Y α − 1 ⊤ α , (15) \min_{\boldsymbol{\alpha}\in\mathcal{A}}J_{\mathcal{K}}(\boldsymbol{\alpha}):=\frac{1}{2}\boldsymbol{\alpha}^{\top}\mathbf{Y}\mathbf{K}\mathbf{Y}\boldsymbol{\alpha}-\mathbf{1}^{\top}\boldsymbol{\alpha}, \tag*{(15)} α ∈ A min J K ( α ) := 2 1 α ⊤ YKY α − 1 ⊤ α , (15)
where K i j = κ ( x i , x j ) \mathbf{K}_{ij}=\kappa(\mathbf{x}_i,\mathbf{x}_j) K ij = κ ( x i , x j ) , Y = diag ( y 1 , … , y n ) \mathbf{Y}=\operatorname{diag}(y_1,\ldots,y_n) Y = diag ( y 1 , … , y n ) , and A : = { α ∈ R n : 0 ≤ α i ≤ C , y ⊤ α = 0 } \mathcal{A}:=\{\boldsymbol{\alpha}\in\mathbb{R}^{n}:0\leq\alpha_i\leq C,\mathbf{y}^{\top}\boldsymbol{\alpha}=0\} A := { α ∈ R n : 0 ≤ α i ≤ C , y ⊤ α = 0 } . The corresponding decision function is
f K ( z ) = ∑ i = 1 n α i ⋆ y i κ ( x i , z ) + b ⋆ , (16) f_{\mathcal{K}}(\mathbf{z})=\sum_{i=1}^{n}\alpha_i^{\star}y_i\kappa(\mathbf{x}_i,\mathbf{z})+b^{\star}, \tag*{(16)} f K ( z ) = i = 1 ∑ n α i ⋆ y i κ ( x i , z ) + b ⋆ , (16)
where α ⋆ ∈ arg min α ∈ A J K ( α ) \boldsymbol{\alpha}^{\star}\in\arg\min_{\boldsymbol{\alpha}\in\mathcal{A}}J_{\mathcal{K}}(\boldsymbol{\alpha}) α ⋆ ∈ arg min α ∈ A J K ( α ) and b ⋆ b^{\star} b ⋆ is the SVM bias term. This kernelized formulation provides the starting point for the quantum-kernel construction considered in the following subsection.
Quantum Kernel Learning
Quantum kernel learning extends the kernel formulation of Section A.1 by replacing a classical feature map with a quantum-state embedding. Let U ϕ : X → U ( 2 q ) U_{\phi}:\mathcal{X}\to\mathcal{U}(2^{q}) U ϕ : X → U ( 2 q ) denote a data-dependent unitary acting on q q q qubits. For an input x ∈ X \mathbf{x}\in\mathcal{X} x ∈ X , the corresponding quantum feature state is:
∣ ϕ ( x ) ⟩ = U ϕ ( x ) ∣ 0 ⟩ ⊗ q . (17) |\phi(\mathbf{x})\rangle=U_{\phi}(\mathbf{x})|0\rangle^{\otimes q}. \tag*{(17)} ∣ ϕ ( x )⟩ = U ϕ ( x ) ∣0 ⟩ ⊗ q . (17)
We consider the fidelity-based quantum kernel
κ Q ( x i , x j ) : = ∣ ⟨ ϕ ( x j ) ∣ ϕ ( x i ) ⟩ ∣ 2 . (18) \kappa^{Q}(x_i,x_j) := \left|\langle\phi(x_j)\mid\phi(x_i)\rangle\right|^2 . \tag*{(18)} κ Q ( x i , x j ) := ∣ ⟨ ϕ ( x j ) ∣ ϕ ( x i )⟩ ∣ 2 . (18)
For a training set x i i = 1 n x_i{}_{i=1}^{n} x i i = 1 n , the corresponding ideal quantum Gram matrix is:
K Q : = [ K i j Q ] i , j = 1 n , K i j Q : = κ Q ( x i , x j ) . (19) \mathbf{K}^{Q} := \left[K_{ij}^{Q}\right]_{i,j=1}^{n}, \qquad K_{ij}^{Q} := \kappa^{Q}(x_i,x_j). \tag*{(19)} K Q := [ K ij Q ] i , j = 1 n , K ij Q := κ Q ( x i , x j ) . (19)
Overlap estimation. We adopt an overlap-based estimator to compute each kernel entry, avoiding the ancilla qubits and controlled-SWAP operations required by SWAP-test methods Volkoff and Subaşı [26 ] . For a pair of inputs ( x i , x j ) (x_i,x_j) ( x i , x j ) , from a reference state ∣ 0 ⟩ ⊗ q \lvert0\rangle^{\otimes q} ∣ 0 ⟩ ⊗ q the overlap circuit prepares:
∣ ψ f i n a l ( x i , x j ) ⟩ = U ϕ † ( x j ) U ϕ ( x i ) ∣ 0 ⟩ ⊗ q , (20) \lvert\psi_{\mathrm{final}}(x_i,x_j)\rangle= U_{\phi}^{\dagger}(x_j)U_{\phi}(x_i)\lvert0\rangle^{\otimes q}, \tag*{(20)} ∣ ψ final ( x i , x j )⟩ = U ϕ † ( x j ) U ϕ ( x i ) ∣ 0 ⟩ ⊗ q , (20)
with the corresponding density operator ρ f i n a l ( x i , x j ) : = ∣ ψ f i n a l ( x i , x j ) ⟩ ⟨ ψ f i n a l ( x i , x j ) ∣ \rho_{\mathrm{final}}(x_i,x_j) := \lvert\psi_{\mathrm{final}}(x_i,x_j)\rangle\langle\psi_{\mathrm{final}}(x_i,x_j)\rvert ρ final ( x i , x j ) := ∣ ψ final ( x i , x j )⟩ ⟨ ψ final ( x i , x j )∣ . Measuring this state in the computational basis, the probability of the all-zero outcome is:
p 0 ( x i , x j ) = Tr ( ∣ 0 ⟩ ⟨ 0 ∣ ⊗ q ρ f i n a l ( x i , x j ) ) = ∣ ⟨ 0 ∣ ⊗ q U ϕ † ( x j ) U ϕ ( x i ) ∣ 0 ⟩ ⊗ q ∣ 2 . (21) p_0(x_i,x_j) = \operatorname{Tr}\left(\lvert0\rangle\langle0\rvert^{\otimes q}\rho_{\mathrm{final}}(x_i,x_j)\right) = \left|\langle0\rvert^{\otimes q}U_{\phi}^{\dagger}(x_j)U_{\phi}(x_i)\lvert0\rangle^{\otimes q}\right|^2. \tag*{(21)} p 0 ( x i , x j ) = Tr ( ∣ 0 ⟩ ⟨ 0 ∣ ⊗ q ρ final ( x i , x j ) ) = ⟨ 0 ∣ ⊗ q U ϕ † ( x j ) U ϕ ( x i ) ∣ 0 ⟩ ⊗ q 2 . (21)
This Born-rule probability equals the fidelity kernel and can be estimated by repeated circuit executions and counting the frequency of the all-zero outcome.
Proposition 2. For any x i , x j ∈ X x_i,x_j \in\mathcal{X} x i , x j ∈ X , the probability of the all-zero measurement outcome under the overlap circuit equals the fidelity-based quantum kernel, that is:
p 0 ( x i , x j ) = κ Q ( x i , x j ) . (22) p_0(x_i,x_j) = \kappa^{Q}(x_i,x_j). \tag*{(22)} p 0 ( x i , x j ) = κ Q ( x i , x j ) . (22)
Proof of Proposition 2. Let A : = U ϕ † ( x j ) U ϕ ( x i ) A := U_{\phi}^{\dagger}(x_j)U_{\phi}(x_i) A := U ϕ † ( x j ) U ϕ ( x i ) denote the composed unitary operator, and Π 0 : = ∣ 0 ⟩ ⟨ 0 ∣ ⊗ q \Pi_0 := \lvert0\rangle\langle0\rvert^{\otimes q} Π 0 := ∣ 0 ⟩ ⟨ 0 ∣ ⊗ q define the projector onto the all-zero state. Since ρ f i n a l = A Π 0 A † \rho_{\mathrm{final}} = A\Pi_0A^{\dagger} ρ final = A Π 0 A † , by the Born rule, the probability of measuring the all-zero outcome is defined by:
P ( 0 ⊗ q ) = Tr ( Π 0 ρ f i n a l ) = Tr ( Π 0 A Π 0 A † ) . (23) \mathbb{P}(0^{\otimes q}) = \operatorname{Tr}(\Pi_0\rho_{\mathrm{final}}) = \operatorname{Tr}(\Pi_0A\Pi_0A^{\dagger}). \tag*{(23)} P ( 0 ⊗ q ) = Tr ( Π 0 ρ final ) = Tr ( Π 0 A Π 0 A † ) . (23)
Additionally, let ∣ 0 q ⟩ = ∣ 0 ⟩ ⊗ q \lvert0_q\rangle= \lvert0\rangle^{\otimes q} ∣ 0 q ⟩ = ∣ 0 ⟩ ⊗ q , we have:
Tr ( Π 0 A Π 0 A † ) = Tr ( ∣ 0 q ⟩ ⟨ 0 q ∣ A ∣ 0 q ⟩ ⟨ 0 q ∣ A † ) = ⟨ 0 q ∣ A ∣ 0 q ⟩ Tr ( ∣ 0 q ⟩ ⟨ 0 q ∣ A † ) . (24) \operatorname{Tr}(\Pi_0A\Pi_0A^{\dagger}) = \operatorname{Tr}(\lvert0_q\rangle\langle0_q\rvert A\lvert0_q\rangle\langle0_q\rvert A^{\dagger}) = \langle0_q\lvert A\lvert0_q\rangle\operatorname{Tr}(\lvert0_q\rangle\langle0_q\rvert A^{\dagger}). \tag*{(24)} Tr ( Π 0 A Π 0 A † ) = Tr (∣ 0 q ⟩ ⟨ 0 q ∣ A ∣ 0 q ⟩ ⟨ 0 q ∣ A † ) = ⟨ 0 q ∣ A ∣ 0 q ⟩ Tr (∣ 0 q ⟩ ⟨ 0 q ∣ A † ) . (24)
Applying the identity, Tr ( ∣ ψ ⟩ ⟨ ϕ ∣ , X ) = ⟨ ϕ ∣ X ∣ ψ ⟩ \operatorname{Tr}(\lvert\psi\rangle\langle\phi\rvert,X)=\langle\phi\lvert X\lvert\psi\rangle Tr (∣ ψ ⟩ ⟨ ϕ ∣ , X ) = ⟨ ϕ ∣ X ∣ ψ ⟩ , with ∣ ψ ⟩ = ∣ ϕ ⟩ = ∣ 0 q ⟩ \lvert\psi\rangle=\lvert\phi\rangle=\lvert0_q\rangle ∣ ψ ⟩ = ∣ ϕ ⟩ = ∣ 0 q ⟩ and X = A † X=A^{\dagger} X = A † , we have:
Tr ( Π 0 A Π 0 A † ) = ⟨ 0 q ∣ A ∣ 0 q ⟩ ⟨ 0 q ∣ A † ∣ 0 q ⟩ = ⟨ 0 q ∣ A ∣ 0 q ⟩ ⟨ 0 q ∣ A ∣ 0 q ⟩ ‾ = ∣ ⟨ 0 q ∣ A ∣ 0 q ⟩ ∣ 2 . (25) \operatorname{Tr}(\Pi_0A\Pi_0A^{\dagger}) = \langle0_q\lvert A\lvert0_q\rangle\langle0_q\lvert A^{\dagger}\lvert0_q\rangle= \langle0_q\lvert A\lvert0_q\rangle\overline{\langle0_q\lvert A\lvert0_q\rangle} = \left|\langle0_q\lvert A\lvert0_q\rangle\right|^2. \tag*{(25)} Tr ( Π 0 A Π 0 A † ) = ⟨ 0 q ∣ A ∣ 0 q ⟩ ⟨ 0 q ∣ A † ∣ 0 q ⟩ = ⟨ 0 q ∣ A ∣ 0 q ⟩ ⟨ 0 q ∣ A ∣ 0 q ⟩ = ∣ ⟨ 0 q ∣ A ∣ 0 q ⟩ ∣ 2 . (25)
Using Π 0 = ∣ 0 ⟩ ⟨ 0 ∣ ⊗ q \Pi_0 = \lvert0\rangle\langle0\rvert^{\otimes q} Π 0 = ∣ 0 ⟩ ⟨ 0 ∣ ⊗ q , we can obtain:
P ( 0 ⊗ q ) = Tr ( ∣ 0 ⟩ ⟨ 0 ∣ ⊗ q A ∣ 0 ⟩ ⟨ 0 ∣ ⊗ q A † ) = ∣ ⟨ 0 ∣ ⊗ q U ϕ † ( x j ) U ϕ ( x i ) ∣ 0 ⟩ ⊗ q ∣ 2 . (26) \mathbb{P}(0^{\otimes q}) = \operatorname{Tr}(\lvert0\rangle\langle0\rvert^{\otimes q}A\lvert0\rangle\langle0\rvert^{\otimes q}A^{\dagger}) = \left|\langle0\rvert^{\otimes q}U_{\phi}^{\dagger}(x_j)U_{\phi}(x_i)\lvert0\rangle^{\otimes q}\right|^2. \tag*{(26)} P ( 0 ⊗ q ) = Tr (∣ 0 ⟩ ⟨ 0 ∣ ⊗ q A ∣ 0 ⟩ ⟨ 0 ∣ ⊗ q A † ) = ⟨ 0 ∣ ⊗ q U ϕ † ( x j ) U ϕ ( x i ) ∣ 0 ⟩ ⊗ q 2 . (26)
Since the feature map defines ∣ ϕ ( x ) ⟩ = U ϕ ( x ) ∣ 0 ⟩ ⊗ q \lvert\phi(x)\rangle= U_{\phi}(x)\lvert0\rangle^{\otimes q} ∣ ϕ ( x )⟩ = U ϕ ( x ) ∣ 0 ⟩ ⊗ q , their corresponding inner product is
⟨ ϕ ( x j ) ∣ ϕ ( x i ) ⟩ = ⟨ 0 ∣ ⊗ q U ϕ † ( x j ) U ϕ ( x i ) ∣ 0 ⟩ ⊗ q . (27) \langle\phi(x_j)\mid\phi(x_i)\rangle= \langle0\rvert^{\otimes q}U_{\phi}^{\dagger}(x_j)U_{\phi}(x_i)\lvert0\rangle^{\otimes q}. \tag*{(27)} ⟨ ϕ ( x j ) ∣ ϕ ( x i )⟩ = ⟨ 0 ∣ ⊗ q U ϕ † ( x j ) U ϕ ( x i ) ∣ 0 ⟩ ⊗ q . (27)
Therefore, we obtain:
p 0 ( x i , x j ) = ∣ ⟨ ϕ ( x j ) ∣ ϕ ( x i ) ⟩ ∣ 2 = κ Q ( x i , x j ) , (28) p_0(x_i,x_j) = \left|\langle\phi(x_j)\mid\phi(x_i)\rangle\right|^2 = \kappa^{Q}(x_i,x_j), \tag*{(28)} p 0 ( x i , x j ) = ∣ ⟨ ϕ ( x j ) ∣ ϕ ( x i )⟩ ∣ 2 = κ Q ( x i , x j ) , (28)
which proves the proposition.
Finite-shot quantum-kernel oracle. On quantum hardware, the probability in (21) is not available exactly and must be estimated from repeated circuit executions. For a queried pair ( x i , x j ) (x_i, x_j) ( x i , x j ) , let
X s = { 1 , if the s th measurement returns 0 ⊗ q , 0 , otherwise , s = 1 , … , N s . (29) X_s =
\begin{cases}
1, & \text{if the }s\text{th measurement returns }0^{\otimes q},\\
0, & \text{otherwise},
\end{cases}
\qquad s=1,\ldots,N_s. \tag*{(29)} X s = { 1 , 0 , if the s th measurement returns 0 ⊗ q , otherwise , s = 1 , … , N s . (29)
The finite-shot overlap estimator is
κ ^ N s Q ( x i , x j ) : = 1 N s ∑ s = 1 N s X s . (30) \widehat{\kappa}^{Q}_{N_s}(x_i,x_j) := \frac{1}{N_s}\sum_{s=1}^{N_s} X_s. \tag*{(30)} κ N s Q ( x i , x j ) := N s 1 s = 1 ∑ N s X s . (30)
Proposition 3 (Shot-based overlap estimator). For every fixed queried pair x i , x j ∈ X x_i,x_j \in\mathcal{X} x i , x j ∈ X , let κ ^ N s Q ( x i , x j ) \widehat{\kappa}^{Q}_{N_s}(x_i,x_j) κ N s Q ( x i , x j ) denote the empirical estimator obtained from N s N_s N s independent circuit repetitions, defined as the empirical frequency of observing the all-zero outcome. Then,
E [ κ ^ N s Q ( x i , x j ) ] = κ Q ( x i , x j ) , Var [ κ ^ N s Q ( x i , x j ) ] = κ Q ( x i , x j ) [ 1 − κ Q ( x i , x j ) ] N s . (31) \mathbb{E}\left[\widehat{\kappa}^{Q}_{N_s}(x_i,x_j)\right] = \kappa^{Q}(x_i,x_j), \qquad\operatorname{Var}\left[\widehat{\kappa}^{Q}_{N_s}(x_i,x_j)\right] = \frac{\kappa^{Q}(x_i,x_j)\left[1-\kappa^{Q}(x_i,x_j)\right]}{N_s}. \tag*{(31)} E [ κ N s Q ( x i , x j ) ] = κ Q ( x i , x j ) , Var [ κ N s Q ( x i , x j ) ] = N s κ Q ( x i , x j ) [ 1 − κ Q ( x i , x j ) ] . (31)
Proof of Proposition 3. For each circuit execution, by Proposition 2, the success probability is:
P ( X s = 1 ) = κ Q ( x i , x j ) . (32) \mathbb{P}(X_s=1)=\kappa^{Q}(x_i,x_j). \tag*{(32)} P ( X s = 1 ) = κ Q ( x i , x j ) . (32)
Hence, the outcomes across repetitions X 1 , … , X N s X_1,\ldots,X_{N_s} X 1 , … , X N s are i.i.d. Bernoulli random variables with parameter p = κ Q ( x i , x j ) p=\kappa^{Q}(x_i,x_j) p = κ Q ( x i , x j ) , and the empirical estimator is then expressed as κ ^ N s Q ( x i , x j ) = 1 N s ∑ s = 1 N s X s \widehat{\kappa}^{Q}_{N_s}(x_i,x_j)=\frac{1}{N_s}\sum_{s=1}^{N_s}X_s κ N s Q ( x i , x j ) = N s 1 ∑ s = 1 N s X s . Therefore, we can have:
E [ κ ^ N s Q ( x i , x j ) ] = 1 N s ∑ s = 1 N s E [ X s ] = p , (33) \mathbb{E}\left[\widehat{\kappa}^{Q}_{N_s}(x_i,x_j)\right] = \frac{1}{N_s}\sum_{s=1}^{N_s}\mathbb{E}[X_s] = p, \tag*{(33)} E [ κ N s Q ( x i , x j ) ] = N s 1 s = 1 ∑ N s E [ X s ] = p , (33)
which proves (31) . Moreover, since
Var ( X s ) = κ Q ( x i , x j ) ( 1 − κ Q ( x i , x j ) ) , (34) \operatorname{Var}(X_s)=\kappa^{Q}(x_i,x_j)\left(1-\kappa^{Q}(x_i,x_j)\right), \tag*{(34)} Var ( X s ) = κ Q ( x i , x j ) ( 1 − κ Q ( x i , x j ) ) , (34)
independence implies that:
Var [ κ ^ N s Q ( x i , x j ) ] = 1 N s 2 ∑ s = 1 N s Var ( X s ) = κ Q ( x i , x j ) [ 1 − κ Q ( x i , x j ) ] N s , (35) \operatorname{Var}\left[\widehat{\kappa}^{Q}_{N_s}(x_i,x_j)\right] = \frac{1}{N_s^2}\sum_{s=1}^{N_s}\operatorname{Var}(X_s) = \frac{\kappa^{Q}(x_i,x_j)\left[1-\kappa^{Q}(x_i,x_j)\right]}{N_s}, \tag*{(35)} Var [ κ N s Q ( x i , x j ) ] = N s 2 1 s = 1 ∑ N s Var ( X s ) = N s κ Q ( x i , x j ) [ 1 − κ Q ( x i , x j ) ] , (35)
which proves the proposition. □
The estimator is unbiased with standard error scaling as O ( 1 / N s ) O(1/\sqrt{N_s}) O ( 1/ N s ) . Achieving high accuracy may therefore require a large number of shots, especially when many kernel entries are needed. Given n n n training samples, estimating the full kernel matrix requires n ( n + 1 ) / 2 n(n+1)/2 n ( n + 1 ) /2 entries. With N s N_s N s shots per entry, the total number of circuit executions scales as O ( n 2 N s ) O(n^2N_s) O ( n 2 N s ) . Moreover, each evaluation involves both U ϕ ( x i ) U_{\phi}(x_i) U ϕ ( x i ) and U ϕ † ( x j ) U_{\phi}^{\dagger}(x_j) U ϕ † ( x j ) , so the runtime also depends on circuit depth and execution cost of the feature map. This quadratic scaling in n n n is a primary computational bottleneck of QKL.
Analytically known fidelity diagonal: An important special property of the normalized fidelity kernel is that its diagonal is known exactly:
K i i Q = κ Q ( x i , x i ) = ∣ ⟨ ϕ ( x i ) ∣ ϕ ( x i ) ⟩ ∣ 2 = 1. (36) K^{Q}_{ii}=\kappa^{Q}(x_i,x_i)=\left|\langle\phi(x_i)\mid\phi(x_i)\rangle\right|^2=1. \tag*{(36)} K ii Q = κ Q ( x i , x i ) = ∣ ⟨ ϕ ( x i ) ∣ ϕ ( x i )⟩ ∣ 2 = 1. (36)
Equivalently, U ϕ † ( x i ) U ϕ ( x i ) = I U_{\phi}^{\dagger}(x_i)U_{\phi}(x_i)=I U ϕ † ( x i ) U ϕ ( x i ) = I . Thus, under the finite-shot-only model considered in this paper, the diagonal entries require no circuit executions and can be initialized analytically. This property will be used explicitly by the finite-shot ICAQKL recursion.
Ideal quantum Gram matrix. Accordingly, given a full training set { x i } i = 1 n \{x_i\}_{i=1}^{n} { x i } i = 1 n , the corresponding quantum Gram matrix K Q \mathbf{K}^{Q} K Q with [ K i j Q ] i , j = 1 n = [ κ Q ( x i , x j ) ] i , j = 1 n \left[K_{ij}^{Q}\right]_{i,j=1}^{n}=\left[\kappa^{Q}(x_i,x_j)\right]_{i,j=1}^{n} [ K ij Q ] i , j = 1 n = [ κ Q ( x i , x j ) ] i , j = 1 n can be defined by:
K Q = [ κ Q ( x 1 , x 1 ) κ Q ( x 1 , x 2 ) ⋯ κ Q ( x 1 , x n ) κ Q ( x 2 , x 1 ) κ Q ( x 2 , x 2 ) ⋯ κ Q ( x 2 , x n ) ⋮ ⋮ ⋱ ⋮ κ Q ( x n , x 1 ) κ Q ( x n , x 2 ) ⋯ κ Q ( x n , x n ) ] ∈ R n × n . (37) \mathbf{K}^{Q}=
\begin{bmatrix}
\kappa^{Q}(x_1,x_1) & \kappa^{Q}(x_1,x_2) & \cdots& \kappa^{Q}(x_1,x_n)\\
\kappa^{Q}(x_2,x_1) & \kappa^{Q}(x_2,x_2) & \cdots& \kappa^{Q}(x_2,x_n)\\
\vdots& \vdots& \ddots& \vdots\\
\kappa^{Q}(x_n,x_1) & \kappa^{Q}(x_n,x_2) & \cdots& \kappa^{Q}(x_n,x_n)
\end{bmatrix}\in\mathbb{R}^{n\times n}. \tag*{(37)} K Q = κ Q ( x 1 , x 1 ) κ Q ( x 2 , x 1 ) ⋮ κ Q ( x n , x 1 ) κ Q ( x 1 , x 2 ) κ Q ( x 2 , x 2 ) ⋮ κ Q ( x n , x 2 ) ⋯ ⋯ ⋱ ⋯ κ Q ( x 1 , x n ) κ Q ( x 2 , x n ) ⋮ κ Q ( x n , x n ) ∈ R n × n . (37)
A kernel method such as SVM accesses the quantum feature representation only through these pairwise similarities; it does not explicitly construct the exponentially large quantum feature vector. We emphasize, however, that the present work does not require or claim that the chosen quantum kernel is classically intractable. Our focus is the cost of acquiring and approximating a specified quantum kernel under finite-shot access.
Lemma 1 (PSD of the fidelity-based kernel). Let X ⊆ R d \mathcal{X}\subseteq\mathbb{R}^{d} X ⊆ R d denote the input space. For any x i , x j ∈ X x_i,x_j\in\mathcal{X} x i , x j ∈ X , define the corresponding quantum kernel as:
κ Q ( x i , x j ) = ∣ ⟨ ϕ ( x j ) ∣ ϕ ( x i ) ⟩ ∣ 2 , (38) \kappa^{Q}(x_i,x_j)=\left|\langle\phi(x_j)\mid\phi(x_i)\rangle\right|^{2}, \tag*{(38)} κ Q ( x i , x j ) = ∣ ⟨ ϕ ( x j ) ∣ ϕ ( x i )⟩ ∣ 2 , (38) and let K Q \mathbf{K}^{Q} K Q be the associated Gram matrix with entries K i j Q = κ Q ( x i , x j ) K_{ij}^{Q}=\kappa^{Q}(x_i,x_j) K ij Q = κ Q ( x i , x j ) . Then K Q \mathbf{K}^{Q} K Q is Hermitian PSD. That is, K i j Q = K j i Q K_{ij}^{Q}=K_{ji}^{Q} K ij Q = K j i Q , and for every c ∈ C n \mathbf{c}\in\mathbb{C}^{n} c ∈ C n ,
c † K Q c ≥ 0. (39) \mathbf{c}^{\dagger}\mathbf{K}^{Q}\mathbf{c}\geq0. \tag*{(39)} c † K Q c ≥ 0. (39) Proof. We first show that K Q \mathbf{K}^{Q} K Q is Hermitian. For any x i , x j ∈ X x_i,x_j\in\mathcal{X} x i , x j ∈ X , we have:
K j i Q = ∣ ⟨ ϕ ( x i ) ∣ ϕ ( x j ) ⟩ ∣ 2 = ∣ ⟨ ϕ ( x j ) ∣ ϕ ( x i ) ⟩ ‾ ∣ 2 = ∣ ⟨ ϕ ( x j ) ∣ ϕ ( x i ) ⟩ ∣ 2 = K i j Q , (40) K_{ji}^{Q}=\left|\langle\phi(x_i)\mid\phi(x_j)\rangle\right|^{2}=\left|\overline{\langle\phi(x_j)\mid\phi(x_i)\rangle}\right|^{2}=\left|\langle\phi(x_j)\mid\phi(x_i)\rangle\right|^{2}=K_{ij}^{Q}, \tag*{(40)} K j i Q = ∣ ⟨ ϕ ( x i ) ∣ ϕ ( x j )⟩ ∣ 2 = ⟨ ϕ ( x j ) ∣ ϕ ( x i )⟩ 2 = ∣ ⟨ ϕ ( x j ) ∣ ϕ ( x i )⟩ ∣ 2 = K ij Q , (40) implying K Q \mathbf{K}^{Q} K Q is real symmetric, and therefore Hermitian.
For each input x i ∈ X x_i\in\mathcal{X} x i ∈ X , we define the lifted feature map, the feature state ∣ ϕ ( x i ) ⟩ \lvert\phi(x_i)\rangle ∣ ϕ ( x i )⟩ as follows:
Ψ ( x i ) = ∣ ϕ ( x i ) ⟩ ⟨ ϕ ( x i ) ∣ , (41) \Psi(x_i)=\lvert\phi(x_i)\rangle\langle\phi(x_i)\rvert, \tag*{(41)} Ψ ( x i ) = ∣ ϕ ( x i )⟩ ⟨ ϕ ( x i )∣ , (41) which is a rank-one projector on H \mathcal{H} H . Consider the Hilbert space of operators on H \mathcal{H} H equipped with the Hilbert–Schmidt inner product, given by:
⟨ A , B ⟩ H S = Tr ( A † B ) . (42) \langle A,B\rangle_{\mathrm{HS}}=\operatorname{Tr}(A^{\dagger}B). \tag*{(42)} ⟨ A , B ⟩ HS = Tr ( A † B ) . (42) By definition, for any x i , x j ∈ X x_i,x_j\in\mathcal{X} x i , x j ∈ X , we have:
⟨ Ψ ( x i ) , Ψ ( x j ) ⟩ H S = Tr ( Ψ ( x i ) † Ψ ( x j ) ) . (43) \langle\Psi(x_i),\Psi(x_j)\rangle_{\mathrm{HS}}=\operatorname{Tr}\left(\Psi(x_i)^{\dagger}\Psi(x_j)\right). \tag*{(43)} ⟨ Ψ ( x i ) , Ψ ( x j ) ⟩ HS = Tr ( Ψ ( x i ) † Ψ ( x j ) ) . (43) Since Ψ ( x i ) \Psi(x_i) Ψ ( x i ) is Hermitian and rank one, we have Ψ ( x i ) † = Ψ ( x i ) \Psi(x_i)^{\dagger}=\Psi(x_i) Ψ ( x i ) † = Ψ ( x i ) , it follows that:
⟨ Ψ ( x i ) , Ψ ( x j ) ⟩ H S = Tr ( Ψ ( x i ) Ψ ( x j ) ) = Tr ( ∣ ϕ ( x i ) ⟩ ⟨ ϕ ( x i ) ∣ ∣ ϕ ( x j ) ⟩ ⟨ ϕ ( x j ) ∣ ) = ⟨ ϕ ( x i ) ∣ ϕ ( x j ) ⟩ ⟨ ϕ ( x j ) ∣ ϕ ( x i ) ⟩ = ∣ ⟨ ϕ ( x i ) ∣ ϕ ( x j ) ⟩ ∣ 2 = ∣ ⟨ ϕ ( x j ) ∣ ϕ ( x i ) ⟩ ∣ 2 = κ Q ( x i , x j ) , (44) \begin{aligned}
\langle\Psi(x_i),\Psi(x_j)\rangle_{\mathrm{HS}}&=\operatorname{Tr}\left(\Psi(x_i)\Psi(x_j)\right)=\operatorname{Tr}\left(\lvert\phi(x_i)\rangle\langle\phi(x_i)\rvert\lvert\phi(x_j)\rangle\langle\phi(x_j)\rvert\right)\\
&=\langle\phi(x_i)\mid\phi(x_j)\rangle\langle\phi(x_j)\mid\phi(x_i)\rangle\\
&=\left|\langle\phi(x_i)\mid\phi(x_j)\rangle\right|^{2}=\left|\langle\phi(x_j)\mid\phi(x_i)\rangle\right|^{2}\\
&=\kappa^{Q}(x_i,x_j), \tag*{(44)}
\end{aligned} ⟨ Ψ ( x i ) , Ψ ( x j ) ⟩ HS = Tr ( Ψ ( x i ) Ψ ( x j ) ) = Tr ( ∣ ϕ ( x i )⟩ ⟨ ϕ ( x i )∣ ∣ ϕ ( x j )⟩ ⟨ ϕ ( x j )∣ ) = ⟨ ϕ ( x i ) ∣ ϕ ( x j )⟩ ⟨ ϕ ( x j ) ∣ ϕ ( x i )⟩ = ∣ ⟨ ϕ ( x i ) ∣ ϕ ( x j )⟩ ∣ 2 = ∣ ⟨ ϕ ( x j ) ∣ ϕ ( x i )⟩ ∣ 2 = κ Q ( x i , x j ) , (44) implying that κ Q \kappa^{Q} κ Q is the Gram kernel induced by the lifted feature map Ψ \Psi Ψ in the Hilbert–Schmidt space. Let c = ( c 1 , … , c n ) T ∈ C n \mathbf{c}=(c_1,\ldots,c_n)^{\mathsf{T}}\in\mathbb{C}^{n} c = ( c 1 , … , c n ) T ∈ C n be any complex vector. Then we have:
c † K Q c = ∑ i = 1 n ∑ j = 1 n c i ‾ c j κ Q ( x i , x j ) = ∑ i = 1 n ∑ j = 1 n c i ‾ c j ⟨ Ψ ( x i ) , Ψ ( x j ) ⟩ H S (45) \mathbf{c}^{\dagger}\mathbf{K}^{Q}\mathbf{c}=\sum_{i=1}^{n}\sum_{j=1}^{n}\overline{c_i}c_j\kappa^{Q}(x_i,x_j)=\sum_{i=1}^{n}\sum_{j=1}^{n}\overline{c_i}c_j\langle\Psi(x_i),\Psi(x_j)\rangle_{\mathrm{HS}} \tag*{(45)} c † K Q c = i = 1 ∑ n j = 1 ∑ n c i c j κ Q ( x i , x j ) = i = 1 ∑ n j = 1 ∑ n c i c j ⟨ Ψ ( x i ) , Ψ ( x j ) ⟩ HS (45) = ⟨ ∑ i = 1 n c i Ψ ( x i ) , ∑ j = 1 n c j Ψ ( x j ) ⟩ H S (46) =\left\langle\sum_{i=1}^{n}c_i\Psi(x_i),\sum_{j=1}^{n}c_j\Psi(x_j)\right\rangle_{\mathrm{HS}} \tag*{(46)} = ⟨ i = 1 ∑ n c i Ψ ( x i ) , j = 1 ∑ n c j Ψ ( x j ) ⟩ HS (46) = ∥ ∑ i = 1 n c i Ψ ( x i ) ∥ H S 2 ≥ 0. (47) =\left\|\sum_{i=1}^{n}c_i\Psi(x_i)\right\|_{\mathrm{HS}}^{2}\geq0. \tag*{(47)} = i = 1 ∑ n c i Ψ ( x i ) HS 2 ≥ 0. (47) Therefore, K Q \mathbf{K}^{Q} K Q is Hermitian positive semidefinite .
Dense finite-shot kernel acquisition. If one explicitly constructs the complete quantum kernel, symmetry reduces the number of distinct off-diagonal pairs from n ( n − 1 ) n(n-1) n ( n − 1 ) to n ( n − 1 ) / 2 n(n-1)/2 n ( n − 1 ) /2 . Because the fidelity diagonal is analytically equal to one, the number of fresh quantum circuit queries required for dense finite-shot construction is therefore M f u l l = n ( n − 1 ) 2 M_{\mathrm{full}} = \frac{n(n-1)}{2} M full = 2 n ( n − 1 ) rather than n ( n + 1 ) / 2 n(n+1)/2 n ( n + 1 ) /2 . With N s N_s N s shots per off-diagonal query, dense acquisition uses n ( n − 1 ) 2 N s = O ( n 2 N s ) \frac{n(n-1)}{2}N_s = O(n^2N_s) 2 n ( n − 1 ) N s = O ( n 2 N s ) quantum circuit executions. For comparison, if one counts all distinct matrix entries including the analytically known diagonal, the upper-triangular matrix contains n ( n + 1 ) / 2 n(n+1)/2 n ( n + 1 ) /2 entries. We distinguish this matrix-entry count from the actual number of quantum circuit queries.
Dense finite-shot kernel construction. To distinguish the ideal Gram matrix from its finite-shot realization, let K ^ Q , ( N s ) \widehat{\mathbf{K}}^{Q,(N_s)} K Q , ( N s ) denote the dense kernel matrix obtained from finite-shot measurements. Its off-diagonal entries are K ^ i j Q , ( N s ) = κ ^ N s Q ( x i , x j ) \widehat{K}^{Q,(N_s)}_{ij} = \widehat{\kappa}^{Q}_{N_s}(x_i,x_j) K ij Q , ( N s ) = κ N s Q ( x i , x j ) , i ≠ j i \ne j i = j while K ^ i i Q , ( N s ) = K i i Q = 1 \widehat{K}^{Q,(N_s)}_{ii} = K^{Q}_{ii} = 1 K ii Q , ( N s ) = K ii Q = 1 is set analytically under the finite-shot-only model.
Kernel Construction Algorithm. Algorithm 2 summarizes the construction of the quantum kernel matrix via overlap estimation. For each pair of training points, the circuit U ϕ † ( x j ) U ϕ ( x i ) U_\phi^\dagger(x_j)U_\phi(x_i) U ϕ † ( x j ) U ϕ ( x i ) is executed, and the kernel entry is estimated from the empirical probability of the all-zero measurement outcome. By symmetry, only the upper triangular part of the matrix is computed.
Algorithm 2 Dense Quantum Kernel Construction under Finite-Shot Overlap Estimation
Require: Training set { x i } i = 1 n \{x_i\}_{i=1}^{n} { x i } i = 1 n , feature map U ϕ ( ⋅ ) U_\phi(\cdot) U ϕ ( ⋅ ) , shot count N s N_s N s
Ensure: Finite-shot kernel estimate K ^ Q , ( N s ) ∈ R n × n \widehat{\mathbf{K}}^{Q,(N_s)} \in\mathbb{R}^{n \times n} K Q , ( N s ) ∈ R n × n
Initialize K ^ Q , ( N s ) ← I n \widehat{\mathbf{K}}^{Q,(N_s)} \leftarrow\mathbf{I}_n K Q , ( N s ) ← I n
for i = 1 i = 1 i = 1 to n n n do
for j = i + 1 j = i + 1 j = i + 1 to n n n do
Prepare ∣ 0 ⟩ ⊗ q |0\rangle^{\otimes q} ∣0 ⟩ ⊗ q
Apply U ϕ ( x i ) U_\phi(x_i) U ϕ ( x i ) followed by U ϕ † ( x j ) U_\phi^\dagger(x_j) U ϕ † ( x j )
Execute the overlap circuit for N s N_s N s shots
Estimate κ ^ N s Q ( x i , x j ) \widehat{\kappa}^{Q}_{N_s}(x_i,x_j) κ N s Q ( x i , x j ) as the empirical frequency of 0 ⊗ q 0^{\otimes q} 0 ⊗ q
Set K ^ i j Q , ( N s ) ← κ ^ N s Q ( x i , x j ) \widehat{K}^{Q,(N_s)}_{ij} \leftarrow\widehat{\kappa}^{Q}_{N_s}(x_i,x_j) K ij Q , ( N s ) ← κ N s Q ( x i , x j ) and K ^ j i Q , ( N s ) ← K ^ i j Q , ( N s ) \widehat{K}^{Q,(N_s)}_{ji} \leftarrow\widehat{K}^{Q,(N_s)}_{ij} K j i Q , ( N s ) ← K ij Q , ( N s )
end for
end for
Return K ^ Q , ( N s ) \widehat{\mathbf{K}}^{Q,(N_s)} K Q , ( N s )
Hardware and noise model. The kernel-evaluation procedure depends on the execution backend. Statevector simulation permits direct evaluation of the ideal probability in (21) without sampling error. Shot-based simulators and quantum hardware instead return empirical measurement frequencies. The theoretical analysis in this work isolates finite-shot sampling noise : conditional on a queried pair, the measurement outcomes are modeled as independent Bernoulli trials with mean κ Q ( x i , x j ) \kappa^{Q}(x_i,x_j) κ Q ( x i , x j ) . On physical hardware, additional coherent and incoherent effects, including gate errors, decoherence, calibration drift, and readout errors, may bias the observed probability away from the ideal kernel value. Such device-induced bias is distinct from finite-shot sampling variability and is not covered by Proposition 3. Extending ICAQKL to biased or correlated hardware-noise models is therefore an important direction for future work.
THEORETICAL ANALYSIS
This section provides a detail development for the theoretical foundation of ICAQKL under finite-shot quantum-kernel access. The main difficulty is that finite-shot noise enters inside an adaptive matrix-factorization procedure. Consequently, measurement error affects not only the numerical value of an individual queried kernel entry, but potentially also the pivot scores, the subsequent pivot sequence, the recursively constructed Cholesky factor, and ultimately the QSVM solution.
A direct transfer of entrywise kernel-estimation error to the final low-rank surrogate is therefore insufficient. Instead, our analysis tracks how finite-shot estimation error propagates through the adaptive procedure: measurement error first perturbs the residual scores used for pivot selection, which in turn affects the recursively constructed Cholesky factor and the resulting low-rank kernel surrogate. We then propagate this kernel perturbation through the QSVM optimization problem and, finally, to the out-of-sample decision function and classification output.
To make this progression rigorous, we first separate the exact-entry Cholesky recursion from its finite-shot counterpart. We then establish high-probability concentration bounds for adaptively queried quantum-kernel entries and quantify how these estimation errors perturb pivot selection and propagate through the recursive factorization. Building on this analysis, we derive a path-conditioned bound on the resulting kernel approximation error and propagate that perturbation through the QSVM objective and optimizer. We finally extend the analysis to out-of-sample Cholesky evaluation, yielding explicit sufficient conditions for decision-function convergence and classification stability.
Exact and Finite-Shot Low-Rank Approximation
A central distinction in the analysis is between the exact-entry reference recursion and the finite-shot ICAQKL recursion . The former is the standard incomplete-Cholesky construction applied to the ideal quantum Gram matrix and therefore inherits the classical positive-semidefinite residual structure. The latter is driven by stochastic quantum-kernel estimates and is analyzed as a perturbation of an exact Cholesky construction. Maintaining this distinction is essential because finite-shot estimation preserves positive semidefiniteness of the constructed surrogate, but not necessarily of its residual with respect to the ideal kernel.
Exact-entry reference recursion. Let K Q ⪰ 0 \mathbf{K}^{Q} \succeq0 K Q ⪰ 0 denote the ideal quantum Gram matrix. For a pivot sequence P t = ( p 1 , … , p t ) \mathcal{P}_{t}=(p_{1},\ldots,p_{t}) P t = ( p 1 , … , p t ) , let G t = [ g 1 , … , g t ] ∈ R n × t \mathbf{G}_{t}=[\mathbf{g}_{1},\ldots,\mathbf{g}_{t}]\in\mathbb{R}^{n\times t} G t = [ g 1 , … , g t ] ∈ R n × t denote the incomplete-Cholesky factor obtained when the required entries of K Q \mathbf{K}^{Q} K Q are accessed exactly.
The associated rank-t t t surrogate and residual matrix are defined as
K ~ t Q : = G t G t T , R t : = K Q − K ~ t Q , (48) \widetilde{\mathbf{K}}_{t}^{Q}:=\mathbf{G}_{t}\mathbf{G}_{t}^{\mathsf{T}},\qquad\mathbf{R}_{t}:=\mathbf{K}^{Q}-\widetilde{\mathbf{K}}_{t}^{Q}, \tag*{(48)} K t Q := G t G t T , R t := K Q − K t Q , (48)
with residual diagonal
d i , t : = ( R t ) i i , i = 1 , … , n . (49) d_{i,t}:=(\mathbf{R}_{t})_{ii},\quad i=1,\ldots,n. \tag*{(49)} d i , t := ( R t ) ii , i = 1 , … , n . (49)
At iteration t t t , exact greedy pivoting selects an index
p t ∈ arg max 1 ≤ i ≤ n d i , t − 1 . (50) p_{t}\in\underset{1\leq i\leq n}{\operatorname{arg\,max}}\ d_{i,t-1}. \tag*{(50)} p t ∈ 1 ≤ i ≤ n arg max d i , t − 1 . (50)
Whenever d p t , t − 1 > 0 d_{p_{t},t-1}>0 d p t , t − 1 > 0 , the corresponding Cholesky column is given by
G i t = K i p t Q − ∑ ℓ = 1 t − 1 G i ℓ G p t ℓ d p t , t − 1 , i = 1 , … , n . (51) G_{it}=\frac{K_{ip_{t}}^{Q}-\sum_{\ell=1}^{t-1}G_{i\ell}G_{p_{t}\ell}}{\sqrt{d_{p_{t},t-1}}},\quad i=1,\ldots,n. \tag*{(51)} G i t = d p t , t − 1 K i p t Q − ∑ ℓ = 1 t − 1 G i ℓ G p t ℓ , i = 1 , … , n . (51)
Thus, the exact recursion is entirely determined by the residual diagonals and exact kernel entries along the selected pivot columns.
Finite-shot ICAQKL recursion. ICAQKL does not assume direct access to the ideal entries K i j Q K_{ij}^{Q} K ij Q . Instead, whenever a kernel entry is required, the overlap circuit returns the finite-shot estimate κ ^ N s Q ( x i , x j ) \widehat{\kappa}_{N_{\mathrm{s}}}^{Q}(x_{i},x_{j}) κ N s Q ( x i , x j ) . Let G ^ t ( N s ) = [ g ^ 1 ( N s ) , … , g ^ t ( N s ) ] ∈ R n × t \widehat{\mathbf{G}}_{t}^{(N_{\mathrm{s}})}=[\widehat{\mathbf{g}}_{1}^{(N_{\mathrm{s}})},\ldots,\widehat{\mathbf{g}}_{t}^{(N_{\mathrm{s}})}]\in\mathbb{R}^{n\times t} G t ( N s ) = [ g 1 ( N s ) , … , g t ( N s ) ] ∈ R n × t denote the factor constructed from these finite-shot kernel estimates. The resulting low-rank surrogate is
K ~ t Q , ( N s ) : = G ^ t ( N s ) ( G ^ t ( N s ) ) T . (52) \widetilde{\mathbf{K}}_{t}^{Q,(N_{\mathrm{s}})}:=\widehat{\mathbf{G}}_{t}^{(N_{\mathrm{s}})}\left(\widehat{\mathbf{G}}_{t}^{(N_{\mathrm{s}})}\right)^{\mathsf{T}}. \tag*{(52)} K t Q , ( N s ) := G t ( N s ) ( G t ( N s ) ) T . (52)
For the normalized fidelity kernel considered in this work, K i i Q = 1 K_{ii}^{Q}=1 K ii Q = 1 . Hence, the initial diagonal information is known analytically and does not require quantum measurements. We therefore initialize s ^ i , 0 = 1 \widehat{s}_{i,0}=1 s i , 0 = 1 , i = 1 , … , n i=1,\ldots,n i = 1 , … , n . After constructing the t t t -th finite-shot Cholesky column, ICAQKL updates
s ^ i , t = [ s ^ i , t − 1 − ( G ^ i t ( N s ) ) 2 ] + , [ a ] + : = max { a , 0 } . (53) \widehat{s}_{i,t}=\left[\widehat{s}_{i,t-1}-\left(\widehat{G}_{it}^{(N_{\mathrm{s}})}\right)^{2}\right]_{+},\qquad[a]_{+}:=\max\{a,0\}. \tag*{(53)} s i , t = [ s i , t − 1 − ( G i t ( N s ) ) 2 ] + , [ a ] + := max { a , 0 } . (53)
The clipping operation prevents small negative values caused by finite-shot perturbations from being interpreted as admissible pivot scores. We deliberately refer to s ^ i , t \widehat{s}_{i,t} s i , t as a finite-shot pivot score rather than as an exact residual diagonal. In the exact recursion, d i , t = ( K Q − G t G t T ) i i d_{i,t}=(\mathbf{K}^{Q}-\mathbf{G}_{t}\mathbf{G}_{t}^{\mathsf{T}})_{ii} d i , t = ( K Q − G t G t T ) ii is the diagonal of a PSD residual matrix. By contrast, under finite-shot access, K Q − K ~ t Q , ( N s ) \mathbf{K}^{Q}-\widetilde{\mathbf{K}}_{t}^{Q,(N_{\mathrm{s}})} K Q − K t Q , ( N s ) is not generally guaranteed to be PSD. Consequently, s ^ i , t \widehat{s}_{i,t} s i , t should be interpreted as the recursively maintained noisy analogue of the exact residual diagonal rather than identified with it.
Proposition 4 (PSD finite-shot surrogate). Let G ^ t ( N s ) ∈ R n × t \widehat{\mathbf{G}}_{t}^{(N_{\mathrm{s}})} \in\mathbb{R}^{n \times t} G t ( N s ) ∈ R n × t denote the factor produced after t t t iterations of the finite-shot incomplete Cholesky procedure. Then the corresponding surrogate
K ~ t Q , ( N s ) : = G ^ t ( N s ) ( G ^ t ( N s ) ) T (54) \widetilde{\mathbf{K}}_{t}^{Q,(N_{\mathrm{s}})} := \widehat{\mathbf{G}}_{t}^{(N_{\mathrm{s}})}\left(\widehat{\mathbf{G}}_{t}^{(N_{\mathrm{s}})}\right)^{\mathsf{T}} \tag*{(54)} K t Q , ( N s ) := G t ( N s ) ( G t ( N s ) ) T (54) is symmetric positive semidefinite and satisfies
rank ( K ~ t Q , ( N s ) ) ≤ t . (55) \operatorname{rank}\left(\widetilde{\mathbf{K}}_{t}^{Q,(N_{\mathrm{s}})}\right) \leq t. \tag*{(55)} rank ( K t Q , ( N s ) ) ≤ t . (55)
Proof. Let A : = G ^ t ( N s ) \mathbf{A} := \widehat{\mathbf{G}}_{t}^{(N_{\mathrm{s}})} A := G t ( N s ) . For any v ∈ R n \mathbf{v} \in\mathbb{R}^{n} v ∈ R n , it follows
v T A A T v = ∥ A T v ∥ 2 2 ≥ 0. (56) \mathbf{v}^{\mathsf{T}}\mathbf{A}\mathbf{A}^{\mathsf{T}}\mathbf{v} = \left\|\mathbf{A}^{\mathsf{T}}\mathbf{v}\right\|_{2}^{2} \geq0. \tag*{(56)} v T A A T v = A T v 2 2 ≥ 0. (56)
Hence A A T \mathbf{A}\mathbf{A}^{\mathsf{T}} A A T is symmetric PSD. By construction K ~ t Q , ( N s ) = A A T ⪰ 0 \widetilde{\mathbf{K}}_{t}^{Q,(N_{\mathrm{s}})} = \mathbf{A}\mathbf{A}^{\mathsf{T}} \succeq0 K t Q , ( N s ) = A A T ⪰ 0 . Moreover, since G ^ t ( N s ) \widehat{\mathbf{G}}_{t}^{(N_{\mathrm{s}})} G t ( N s ) has t t t columns, its product G ^ t ( N s ) ( G ^ t ( N s ) ) T \widehat{\mathbf{G}}_{t}^{(N_{\mathrm{s}})}\left(\widehat{\mathbf{G}}_{t}^{(N_{\mathrm{s}})}\right)^{\mathsf{T}} G t ( N s ) ( G t ( N s ) ) T has rank at most t t t ,
rank ( G ^ t ( N s ) ( G ^ t ( N s ) ) T ) ≤ rank ( G ^ t ( N s ) ) ≤ t , (57) \operatorname{rank}\left(\widehat{\mathbf{G}}_{t}^{(N_{\mathrm{s}})}\left(\widehat{\mathbf{G}}_{t}^{(N_{\mathrm{s}})}\right)^{\mathsf{T}}\right) \leq\operatorname{rank}\left(\widehat{\mathbf{G}}_{t}^{(N_{\mathrm{s}})}\right) \leq t, \tag*{(57)} rank ( G t ( N s ) ( G t ( N s ) ) T ) ≤ rank ( G t ( N s ) ) ≤ t , (57)
which completes the proof. □
Proposition 4 guarantees that ICAQKL always supplies the downstream QSVM with a valid PSD low-rank kernel surrogate. This property follows directly from the factorized representation and does not require the finite-shot residual to remain PSD. The distinction is important for the subsequent analysis: the classical residual identities, monotonicity properties, and full-rank exactness results are established using the exact-entry recursion, whereas the finite-shot construction is compared with this reference process through explicit perturbation bounds. This separation allows us to retain the deterministic geometry of incomplete Cholesky while accounting rigorously for stochastic quantum-kernel estimation.
Exact Cholesky Residual Invariants
The exact-entry recursion provides the deterministic reference geometry against which the finite-shot ICAQKL recursion will be compared. In particular, when the Cholesky columns are constructed from exact entries of the ideal PSD kernel matrix, the residual remains PSD after every successful pivot. This property yields nonnegative and monotonically decreasing residual diagonals and, ultimately, exact recovery once the number of successful pivots reaches the rank of the kernel matrix. These invariants will later be used to define the path-conditioned exact comparator and to control both finite-shot pivot perturbations and out-of-sample approximation.
Proposition 5 (Exact residual PSD). Suppose that, at iteration t − 1 t-1 t − 1 of the exact-entry Cholesky recursion, R t − 1 ⪰ 0 \mathbf{R}_{t-1} \succeq0 R t − 1 ⪰ 0 and that the selected pivot satisfies d p t , t − 1 > 0 d_{p_t,t-1} > 0 d p t , t − 1 > 0 . Then the updated residual R t = R t − 1 − g t g t T \mathbf{R}_{t} = \mathbf{R}_{t-1} - \mathbf{g}_{t}\mathbf{g}_{t}^{\mathsf{T}} R t = R t − 1 − g t g t T is also PSD, i.e., R t ⪰ 0 \mathbf{R}_{t} \succeq0 R t ⪰ 0 .
Proof. After permuting the pivot p t p_t p t to the first coordinate, write the residual as
R t − 1 = [ d p t , t − 1 r T r B ] . (58) \mathbf{R}_{t-1} =
\begin{bmatrix}
d_{p_t,t-1} & \mathbf{r}^{\mathsf{T}} \\
\mathbf{r} & \mathbf{B}
\end{bmatrix}. \tag*{(58)} R t − 1 = [ d p t , t − 1 r r T B ] . (58)
Since the pivot is strictly positive, the corresponding exact Cholesky column can be written, under the same permutation, as g t = [ d p t , t − 1 r / d p t , t − 1 ] \mathbf{g}_{t} = \begin{bmatrix} \sqrt{d_{p_t,t-1}} \\ \mathbf{r}/\sqrt{d_{p_t,t-1}} \end{bmatrix} g t = [ d p t , t − 1 r / d p t , t − 1 ] . Therefore, we can obtain
R t = R t − 1 − g t g t T = [ 0 0 T 0 B − r r T d p t , t − 1 ] . (59) \mathbf{R}_{t} = \mathbf{R}_{t-1} - \mathbf{g}_{t}\mathbf{g}_{t}^{\mathsf{T}} =
\begin{bmatrix}
0 & \mathbf{0}^{\mathsf{T}} \\
\mathbf{0} & \mathbf{B} - \dfrac{\mathbf{r}\mathbf{r}^{\mathsf{T}}}{d_{p_t,t-1}}
\end{bmatrix}. \tag*{(59)} R t = R t − 1 − g t g t T = 0 0 0 T B − d p t , t − 1 r r T . (59)
Since R t − 1 ⪰ 0 \mathbf{R}_{t-1} \succeq0 R t − 1 ⪰ 0 and d p t , t − 1 > 0 d_{p_t,t-1} > 0 d p t , t − 1 > 0 , the lower-right block B − r r T d p t , t − 1 \mathbf{B} - \dfrac{\mathbf{r}\mathbf{r}^{\mathsf{T}}}{d_{p_t,t-1}} B − d p t , t − 1 r r T is the Schur complement of the pivot and is PSD. Consequently, R t ⪰ 0 \mathbf{R}_{t} \succeq0 R t ⪰ 0 . □
Proposition 6 (Exact residual identity and monotonicity). For every executed iteration t ≥ 1 t \ge1 t ≥ 1 of the exact-entry recursion and every i ∈ { 1 , … , n } i \in\{1,\ldots,n\} i ∈ { 1 , … , n } ,
d i , t = ( R t ) i i = K i i Q − ∑ ℓ = 1 t G i ℓ 2 . (60) d_{i,t}=(\mathbf{R}_t)_{ii}=K^Q_{ii}-\sum_{\ell=1}^{t}G_{i\ell}^{2}. \tag*{(60)} d i , t = ( R t ) ii = K ii Q − ℓ = 1 ∑ t G i ℓ 2 . (60) Moreover, 0 ≤ d i , t ≤ d i , t − 1 0 \le d_{i,t} \le d_{i,t-1} 0 ≤ d i , t ≤ d i , t − 1 .
Proof. From the definition R t = K Q − G t G t T \mathbf{R}_t=\mathbf{K}^Q-\mathbf{G}_t\mathbf{G}_t^{\mathsf{T}} R t = K Q − G t G t T the i i i th diagonal entry satisfies
( R t ) i i = K i i Q − ( G t G t T ) i i = K i i Q − ∑ ℓ = 1 t G i ℓ 2 . (61) (\mathbf{R}_t)_{ii}=K^Q_{ii}-(\mathbf{G}_t\mathbf{G}_t^{\mathsf{T}})_{ii}=K^Q_{ii}-\sum_{\ell=1}^{t}G_{i\ell}^{2}. \tag*{(61)} ( R t ) ii = K ii Q − ( G t G t T ) ii = K ii Q − ℓ = 1 ∑ t G i ℓ 2 . (61)
Therefore, d i , t = d i , t − 1 − G i t 2 d_{i,t}=d_{i,t-1}-G_{it}^{2} d i , t = d i , t − 1 − G i t 2 . Since G i t 2 ≥ 0 G_{it}^{2} \ge0 G i t 2 ≥ 0 , it follows immediately that d i , t ≤ d i , t − 1 d_{i,t} \le d_{i,t-1} d i , t ≤ d i , t − 1 . Furthermore, Proposition 5 gives R t ⪰ 0 \mathbf{R}_t \succeq0 R t ⪰ 0 , and every diagonal entry of a PSD matrix is nonnegative. Thus, d i , t ≥ 0 d_{i,t} \ge0 d i , t ≥ 0 . Combining the two inequalities yields 0 ≤ d i , t ≤ d i , t − 1 0 \le d_{i,t} \le d_{i,t-1} 0 ≤ d i , t ≤ d i , t − 1 , which proves the claim.
For the normalized fidelity kernel, d i , 0 = K i i Q = 1 d_{i,0}=K^Q_{ii}=1 d i , 0 = K ii Q = 1 so all exact residual diagonals are initialized at one and decrease monotonically as successive Cholesky directions are incorporated.
Proposition 7 (Exactness at full rank). Let ρ : = rank ( K Q ) \rho:=\operatorname{rank}(K^Q) ρ := rank ( K Q ) . If the exact-entry Cholesky recursion performs ρ \rho ρ iterations with strictly positive pivots, then R ρ = 0 \mathbf{R}_{\rho}=0 R ρ = 0 and consequently, K Q = G ρ G ρ T \mathbf{K}^Q=\mathbf{G}_{\rho}\mathbf{G}_{\rho}^{\mathsf{T}} K Q = G ρ G ρ T .
Proof. Consider one successful iteration with d p t , t − 1 > 0 d_{p_t,t-1}>0 d p t , t − 1 > 0 . From the Schur-complement representation in the proof of Proposition 5, after permuting the pivot index to the first coordinate, the residual takes the form R t = ( 0 0 T 0 S t ) \mathbf{R}_t=\begin{pmatrix} 0 & \mathbf{0}^{\mathsf{T}} \\ \mathbf{0} & \mathbf{S}_t \end{pmatrix} R t = ( 0 0 0 T S t ) where S t = B − r r T d p t , t − 1 ⪰ 0 \mathbf{S}_t=\mathbf{B}-\frac{\mathbf{r}\mathbf{r}^{\mathsf{T}}}{d_{p_t,t-1}}\succeq0 S t = B − d p t , t − 1 r r T ⪰ 0 . Since the leading pivot d p t , t − 1 d_{p_t,t-1} d p t , t − 1 of R t − 1 \mathbf{R}_{t-1} R t − 1 is strictly positive and therefore invertible, the block-rank identity yields
rank ( R t − 1 ) = 1 + rank ( S t ) . (62) \operatorname{rank}(\mathbf{R}_{t-1})=1+\operatorname{rank}(\mathbf{S}_t). \tag*{(62)} rank ( R t − 1 ) = 1 + rank ( S t ) . (62)
Moreover, rank ( R t ) = rank ( S t ) \operatorname{rank}(\mathbf{R}_t)=\operatorname{rank}(\mathbf{S}_t) rank ( R t ) = rank ( S t ) . Thus every successful pivot reduces residual rank by exactly one
rank ( R t ) = rank ( R t − 1 ) − 1. (63) \operatorname{rank}(\mathbf{R}_t)=\operatorname{rank}(\mathbf{R}_{t-1})-1. \tag*{(63)} rank ( R t ) = rank ( R t − 1 ) − 1. (63)
Initially, R 0 = K Q \mathbf{R}_0=\mathbf{K}^Q R 0 = K Q so rank ( R 0 ) = rank ( K Q ) = ρ \operatorname{rank}(\mathbf{R}_0)=\operatorname{rank}(\mathbf{K}^Q)=\rho rank ( R 0 ) = rank ( K Q ) = ρ . Therefore, after ρ \rho ρ successful pivots,
rank ( R ρ ) = 0. (64) \operatorname{rank}(\mathbf{R}_{\rho})=0. \tag*{(64)} rank ( R ρ ) = 0. (64)
A matrix has rank zero if and only if it is the zero matrix, so R ρ = 0 \mathbf{R}_{\rho}=0 R ρ = 0 . Finally, using
R ρ = K Q − G ρ G ρ T , (65) \mathbf{R}_{\rho}=\mathbf{K}^Q-\mathbf{G}_{\rho}\mathbf{G}_{\rho}^{\mathsf{T}}, \tag*{(65)} R ρ = K Q − G ρ G ρ T , (65)
we obtain K Q = G ρ G ρ T \mathbf{K}^Q=\mathbf{G}_{\rho}\mathbf{G}_{\rho}^{\mathsf{T}} K Q = G ρ G ρ T which proves the proposition.
The exact residual diagonal d i , t d_{i,t} d i , t quantifies the diagonal approximation error remaining at sample i i i after t t t Cholesky directions have been incorporated. Exact greedy pivoting therefore selects the sample with the largest remaining residual diagonal. Proposition 6 shows that these residuals decrease monotonically along the exact-entry recursion, while Proposition 7 establishes that they vanish once the factorization reaches the rank of the kernel matrix.
ICAQKL extends this residual-driven construction to the finite-shot setting by replacing exact quantum-kernel entries with stochastic overlap estimates. The maintained score s ^ i , t \hat{s}_{i,t} s ^ i , t therefore serves as a noisy surrogate for the exact comparator quantity d i , t d_{i,t} d i , t . The central analytical question is then not whether the exact residual remains PSD, which follows from Proposition 5, but how finite-shot estimation errors perturb the pivot scores, alter the resulting pivot decisions, and propagate through the recursively constructed Cholesky factor. We address this question next by first establishing high-probability concentration bounds for the adaptively queried quantum-kernel entries.
Finite-Shot Perturbation Analysis
We now quantify how finite-shot quantum-kernel estimation affects the adaptive Cholesky construction. Two features distinguish this setting from a standard perturbation analysis. First, the queried kernel entries are selected adaptively because each pivot depends on estimates obtained at earlier iterations. Second, the resulting entrywise errors can perturb the residual scores used for pivot selection and thereby alter the subsequent query trajectory. We therefore proceed in stages: we first establish uniform concentration over the adaptively queried entries and then translate score perturbations into guarantees on the quality and stability of the selected pivots.
Adaptive finite-shot concentration. Let q m = ( i m , j m ) q_m=(i_m,j_m) q m = ( i m , j m ) denote the m m m th fresh queried training pair, and let F m − 1 \mathcal{F}_{m-1} F m − 1 denote the sigma-algebra generated by all queried pairs, pivot decisions, and measurement outcomes observed before the m m m th query. Since the next queried pair is selected using only previously available information, q m q_m q m is F m − 1 \mathcal{F}_{m-1} F m − 1 -measurable. Conditional on this history, the N s N_s N s shots used to estimate the corresponding kernel entry are fresh independent Bernoulli measurements with success probability κ Q ( x i m , x j m ) \kappa^Q(\mathbf{x}_{i_m},\mathbf{x}_{j_m}) κ Q ( x i m , x j m ) .
Theorem 4 (Uniform concentration over adaptively queried entries). Suppose that I C A Q K L ICAQKL I C A Q K L performs at most M r M_r M r fresh training-kernel queries through rank r r r . For any δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , define η s : = log ( 2 M r / δ ) 2 N s \eta_s:=\sqrt{\frac{\log(2M_r/\delta)}{2N_s}} η s := 2 N s l o g ( 2 M r / δ ) . Then, with probability at least 1 − δ 1-\delta 1 − δ ,
max 1 ≤ m ≤ M r ∣ κ ^ N s Q ( x i m , x j m ) − κ Q ( x i m , x j m ) ∣ ≤ η s . (66) \max_{1\le m\le M_r}\left|\widehat{\kappa}^{Q}_{N_s}(\mathbf{x}_{i_m},\mathbf{x}_{j_m})-\kappa^Q(\mathbf{x}_{i_m},\mathbf{x}_{j_m})\right|\le\eta_s. \tag*{(66)} 1 ≤ m ≤ M r max κ N s Q ( x i m , x j m ) − κ Q ( x i m , x j m ) ≤ η s . (66)
Proof. For each query index m m m , define the deviation event,
E m ( η ) : = { ∣ κ ^ N s Q ( x i m , x j m ) − κ Q ( x i m , x j m ) ∣ > η } . (67) \mathcal{E}_m(\eta):=\left\{\left|\widehat{\kappa}^{Q}_{N_s}(\mathbf{x}_{i_m},\mathbf{x}_{j_m})-\kappa^Q(\mathbf{x}_{i_m},\mathbf{x}_{j_m})\right|>\eta\right\}. \tag*{(67)} E m ( η ) := { κ N s Q ( x i m , x j m ) − κ Q ( x i m , x j m ) > η } . (67)
Conditional on F m − 1 \mathcal{F}_{m-1} F m − 1 , the queried pair q m q_m q m is fixed. The corresponding estimator κ ^ N s Q ( x i m , x j m ) \widehat{\kappa}^{Q}_{N_s}(\mathbf{x}_{i_m},\mathbf{x}_{j_m}) κ N s Q ( x i m , x j m ) is the empirical mean of N s N_s N s conditionally independent Bernoulli random variables with mean κ Q ( x i m , x j m ) \kappa^Q(\mathbf{x}_{i_m},\mathbf{x}_{j_m}) κ Q ( x i m , x j m ) . Therefore, Hoeffding’s inequality yields, for every η > 0 \eta>0 η > 0 ,
Pr ( E m ( η ) ∣ F m − 1 ) ≤ 2 exp ( − 2 N s η 2 ) . (68) \Pr\left(\mathcal{E}_m(\eta)\mid\mathcal{F}_{m-1}\right)\le2\exp\left(-2N_s\eta^2\right). \tag*{(68)} Pr ( E m ( η ) ∣ F m − 1 ) ≤ 2 exp ( − 2 N s η 2 ) . (68)
Taking expectations with respect to the history and using the tower property,
Pr ( E m ( η ) ) = E [ Pr ( E m ( η ) ∣ F m − 1 ) ] (69) \Pr\left(\mathcal{E}_m(\eta)\right)=\mathbb{E}\left[\Pr\left(\mathcal{E}_m(\eta)\mid\mathcal{F}_{m-1}\right)\right] \tag*{(69)} Pr ( E m ( η ) ) = E [ Pr ( E m ( η ) ∣ F m − 1 ) ] (69)
≤ 2 exp ( − 2 N s η 2 ) . (70) \le2\exp\left(-2N_s\eta^2\right). \tag*{(70)} ≤ 2 exp ( − 2 N s η 2 ) . (70)
Thus, although the identity of the m m m th queried pair depends on the previous finite-shot observations, its estimation error obeys the same Hoeffding bound as a fixed query.
We next control all adaptive queries simultaneously. From (67) , the event that at least one queried entry has estimation error at least η \eta η can then be written as ⋃ m = 1 M r E m ( η ) \bigcup_{m=1}^{M_r}\mathcal{E}_m(\eta) ⋃ m = 1 M r E m ( η ) . Equivalently,
{ max 1 ≤ m ≤ M r ∣ κ ^ N s Q ( x i m , x j m ) − κ Q ( x i m , x j m ) ∣ > η } = ⋃ m = 1 M r E m ( η ) . (71) \left\{\max_{1\le m\le M_r}\left|\widehat{\kappa}^{Q}_{N_s}(\mathbf{x}_{i_m},\mathbf{x}_{j_m})-\kappa^Q(\mathbf{x}_{i_m},\mathbf{x}_{j_m})\right|>\eta\right\}=\bigcup_{m=1}^{M_r}\mathcal{E}_m(\eta). \tag*{(71)} { 1 ≤ m ≤ M r max κ N s Q ( x i m , x j m ) − κ Q ( x i m , x j m ) > η } = m = 1 ⋃ M r E m ( η ) . (71)
Taking probabilities on both sides of (71) and applying the union bound, we obtain:
Pr ( max 1 ≤ m ≤ M r ∣ κ ^ N s Q ( x i m , x j m ) − κ Q ( x i m , x j m ) ∣ > η ) = Pr ( ⋃ m = 1 M r E m ( η ) ) (72) \Pr\left(\max_{1\le m\le M_r}\left|\widehat{\kappa}^{Q}_{N_s}(\mathbf{x}_{i_m},\mathbf{x}_{j_m})-\kappa^Q(\mathbf{x}_{i_m},\mathbf{x}_{j_m})\right|>\eta\right)=\Pr\left(\bigcup_{m=1}^{M_r}\mathcal{E}_m(\eta)\right) \tag*{(72)} Pr ( 1 ≤ m ≤ M r max κ N s Q ( x i m , x j m ) − κ Q ( x i m , x j m ) > η ) = Pr ( m = 1 ⋃ M r E m ( η ) ) (72)
≤ ∑ m = 1 M r Pr ( E m ( η ) ) (73) \le\sum_{m=1}^{M_r}\Pr\left(\mathcal{E}_m(\eta)\right) \tag*{(73)} ≤ m = 1 ∑ M r Pr ( E m ( η ) ) (73)
≤ 2 M r exp ( − 2 N s η 2 ) . (74) \le2M_r\exp\left(-2N_s\eta^2\right). \tag*{(74)} ≤ 2 M r exp ( − 2 N s η 2 ) . (74)
To make the failure probability at most δ \delta δ , it is sufficient that
2 M r exp ( − 2 N s η s 2 ) ≤ δ . (75) 2M_r\exp\left(-2N_s\eta_s^2\right)\le\delta. \tag*{(75)} 2 M r exp ( − 2 N s η s 2 ) ≤ δ . (75)
Equivalently, η ≥ log ( 2 M r / δ ) 2 N s \eta\ge\sqrt{\frac{\log(2M_r/\delta)}{2N_s}} η ≥ 2 N s l o g ( 2 M r / δ ) . Choosing η = η s \eta=\eta_s η = η s therefore yields
Pr ( max 1 ≤ m ≤ M r ∣ κ ^ N s Q ( x i m , x j m ) − κ Q ( x i m , x j m ) ∣ ≤ η s ) ≥ 1 − δ , (76) \Pr\left(\max_{1\le m\le M_r}\left|\widehat{\kappa}^{Q}_{N_s}(x_{i_m},x_{j_m})-\kappa^{Q}(x_{i_m},x_{j_m})\right|\le\eta_s\right)\ge1-\delta, \tag*{(76)} Pr ( 1 ≤ m ≤ M r max κ N s Q ( x i m , x j m ) − κ Q ( x i m , x j m ) ≤ η s ) ≥ 1 − δ , (76)
which proves the theorem.
Theorem 4 provides the first connection between the finite quantum measurement budget and the adaptive factorization. In particular, every queried training entry is simultaneously accurate, with high probability, to η s = O ( log ( M r / δ ) N s ) \eta_s=O\left(\sqrt{\frac{\log(M_r/\delta)}{N_s}}\right) η s = O ( N s l o g ( M r / δ ) ) . This result is, however, only an entrywise oracle guarantee. It does not yet control the final low-rank surrogate because the Cholesky recursion is nonlinear: an estimation error in one queried entry can perturb the current factor, modify the pivot scores, and thereby influence later queries.
To quantify the aggregate finite-shot error over the entries directly queried by ICAQKL, define the sparse queried-entry estimation-error matrix
( e r Q , ( N s ) ) i j = { κ ^ N s Q ( x i , x j ) − κ Q ( x i , x j ) , ( i , j ) ∈ Q r , 0 , otherwise , (77) \left(e_r^{Q,(N_s)}\right)_{ij}=
\begin{cases}
\widehat{\kappa}^{Q}_{N_s}(x_i,x_j)-\kappa^{Q}(x_i,x_j), & (i,j)\in\mathcal{Q}_r,\\
0, & \text{otherwise},
\end{cases} \tag*{(77)} ( e r Q , ( N s ) ) ij = { κ N s Q ( x i , x j ) − κ Q ( x i , x j ) , 0 , ( i , j ) ∈ Q r , otherwise , (77)
where Q r \mathcal{Q}_r Q r denotes the set of matrix coordinates corresponding to the fresh kernel entries queried through rank r r r , with ∣ Q r ∣ ≤ M r |\mathcal{Q}_r|\le M_r ∣ Q r ∣ ≤ M r . Here, each fresh off-diagonal quantum query is counted once. Thus, e r Q , ( N s ) e_r^{Q,(N_s)} e r Q , ( N s ) is an auxiliary sparse error matrix used to summarize the directly observed oracle errors; it need not be interpreted as the symmetric perturbation of a complete Gram matrix.
Lemma 2 (Norm bound for queried-entry estimation error). Under the event in Theorem 4, the queried-entry estimation error satisfies
∥ e r Q , ( N s ) ∥ 2 ≤ ∥ e r Q , ( N s ) ∥ F ≤ M r η s = M r log ( 2 M r / δ ) 2 N s . (78) \left\|e_r^{Q,(N_s)}\right\|_2\le\left\|e_r^{Q,(N_s)}\right\|_F\le\sqrt{M_r}\,\eta_s=\sqrt{\frac{M_r\log(2M_r/\delta)}{2N_s}}. \tag*{(78)} e r Q , ( N s ) 2 ≤ e r Q , ( N s ) F ≤ M r η s = 2 N s M r log ( 2 M r / δ ) . (78) Consequently, the bound holds with probability at least 1 − δ 1-\delta 1 − δ .
Proof. On the concentration event (66) , every nonzero queried entry of e r Q , ( N s ) e_r^{Q,(N_s)} e r Q , ( N s ) satisfies
∣ κ ^ N s Q ( x i , x j ) − κ Q ( x i , x j ) ∣ ≤ η s . (79) \left|\widehat{\kappa}^{Q}_{N_s}(x_i,x_j)-\kappa^{Q}(x_i,x_j)\right|\le\eta_s. \tag*{(79)} κ N s Q ( x i , x j ) − κ Q ( x i , x j ) ≤ η s . (79)
The Frobenius norm of a matrix is defined by:
∥ e r Q , ( N s ) ∥ F 2 = ∑ i = 1 n ∑ j = 1 n ( e r Q , ( N s ) ) i j 2 . (80) \left\|e_r^{Q,(N_s)}\right\|_F^2=\sum_{i=1}^{n}\sum_{j=1}^{n}\left(e_r^{Q,(N_s)}\right)_{ij}^2. \tag*{(80)} e r Q , ( N s ) F 2 = i = 1 ∑ n j = 1 ∑ n ( e r Q , ( N s ) ) ij 2 . (80)
Since all unqueried entries are exactly zero, only the queried entries contribute to this sum. Moreover, under the concentration event, from (79) , each nonzero term is bounded above by ( e r Q , ( N s ) ) i j 2 ≤ η s 2 \left(e_r^{Q,(N_s)}\right)_{ij}^2\le\eta_s^2 ( e r Q , ( N s ) ) ij 2 ≤ η s 2 . Additionally, e r Q , ( N s ) e_r^{Q,(N_s)} e r Q , ( N s ) has support contained in Q r \mathcal{Q}_r Q r . Thus, the matrix has at most M r M_r M r nonzero entries, ∣ Q r ∣ ≤ M r |\mathcal{Q}_r|\le M_r ∣ Q r ∣ ≤ M r , it follows that:
∥ e r Q , ( N s ) ∥ F 2 = ∑ i = 1 n ∑ j = 1 n ( e r Q , ( N s ) ) i j 2 ≤ M r η s 2 . (81) \left\|e_r^{Q,(N_s)}\right\|_F^2=\sum_{i=1}^{n}\sum_{j=1}^{n}\left(e_r^{Q,(N_s)}\right)_{ij}^2\le M_r\eta_s^2. \tag*{(81)} e r Q , ( N s ) F 2 = i = 1 ∑ n j = 1 ∑ n ( e r Q , ( N s ) ) ij 2 ≤ M r η s 2 . (81)
For any real matrix A A A , the spectral norm is bounded by the Frobenius norm ∥ A ∥ 2 ≤ ∥ A ∥ F \|A\|_2\le\|A\|_F ∥ A ∥ 2 ≤ ∥ A ∥ F . Thus, taking the square roots of (81) , we can obtain:
∥ e r Q , ( N s ) ∥ 2 ≤ ∥ e r Q , ( N s ) ∥ F ≤ M r η s . (82) \left\|e_r^{Q,(N_s)}\right\|_2\le\left\|e_r^{Q,(N_s)}\right\|_F\le\sqrt{M_r}\,\eta_s. \tag*{(82)} e r Q , ( N s ) 2 ≤ e r Q , ( N s ) F ≤ M r η s . (82)
This completes the proof.
Lemma 2 bounds the aggregate finite-shot error over the kernel entries directly returned by the quantum oracle. Importantly, it is an auxiliary measurement-error bound rather than a bound on the final low-rank kernel surrogate. The queried estimates enter recursively into both the Cholesky factor and the pivot scores, so their effect on K ~ r Q , ( N s ) \widetilde{K}_r^{Q,(N_s)} K r Q , ( N s ) must be propagated through the adaptive factorization itself. The subsequent analysis performs this propagation by first controlling pivot-score perturbations and then the resulting Cholesky-factor error.
Finite-shot pivot selection. Let P ^ t − 1 = ( p ^ 1 , … , p ^ t − 1 ) \widehat{\mathcal{P}}_{t-1}=(\widehat{p}_1,\ldots,\widehat{p}_{t-1}) P t − 1 = ( p 1 , … , p t − 1 ) denote the pivot history selected by the finite-shot ICAQKL recursion, and let I t − 1 : = { 1 , … , n } ∖ { p ^ 1 , … , p ^ t − 1 } \mathcal{I}_{t-1}:=\{1,\ldots,n\}\setminus\{\widehat{p}_1,\ldots,\widehat{p}_{t-1}\} I t − 1 := { 1 , … , n } ∖ { p 1 , … , p t − 1 } denote the set of indices still eligible for selection at iteration t t t . To separate the effect of the selected pivot path from the numerical error induced by finite-shot kernel estimation, consider an exact-entry Cholesky comparator that follows the same previously selected pivot history P ^ t − 1 \widehat{\mathcal{P}}_{t-1} P t − 1 . Let d i , t − 1 P ^ t − 1 d^{\widehat{\mathcal{P}}_{t-1}}_{i,t-1} d i , t − 1 P t − 1 denote the corresponding exact residual diagonal for i ∈ I t − 1 i\in\mathcal{I}_{t-1} i ∈ I t − 1 . We define the pivot-score discrepancy by
ζ t − 1 : = ∥ s ^ t − 1 − d t − 1 P ^ t − 1 ∥ ∞ , I t − 1 , (83) \zeta_{t-1}:=\left\|\widehat{s}_{t-1}-d^{\widehat{\mathcal{P}}_{t-1}}_{t-1}\right\|_{\infty,\mathcal{I}_{t-1}}, \tag*{(83)} ζ t − 1 := s t − 1 − d t − 1 P t − 1 ∞ , I t − 1 , (83)
where ∣ v ∣ ∞ , I t − 1 : = max i ∈ I t − 1 ∣ v i ∣ |\mathbf{v}|_{\infty,\mathcal{I}_{t-1}}:=\max_{i\in\mathcal{I}_{t-1}}|v_i| ∣ v ∣ ∞ , I t − 1 := max i ∈ I t − 1 ∣ v i ∣ . Thus, ζ t − 1 \zeta_{t-1} ζ t − 1 measures the largest deviation between the finite-shot pivot scores and the exact residual diagonals associated with the same pivot history.
Lemma 3 (Approximate-greedy finite-shot pivot). Let the finite-shot pivot be selected according to p ^ t ∈ arg max i ∈ I t − 1 s ^ i , t − 1 \widehat{p}_t\in\arg\max_{i\in\mathcal{I}_{t-1}}\widehat{s}_{i,t-1} p t ∈ arg max i ∈ I t − 1 s i , t − 1 . Then
d p ^ t , t − 1 P ^ t − 1 ≥ max i ∈ I t − 1 d i , t − 1 P ^ t − 1 − 2 ζ t − 1 . (84) d^{\widehat{\mathcal{P}}_{t-1}}_{\widehat{p}_t,t-1}\geq\max_{i\in\mathcal{I}_{t-1}}d^{\widehat{\mathcal{P}}_{t-1}}_{i,t-1}-2\zeta_{t-1}. \tag*{(84)} d p t , t − 1 P t − 1 ≥ i ∈ I t − 1 max d i , t − 1 P t − 1 − 2 ζ t − 1 . (84)
Proof. Let p t ⋆ ∈ arg max i ∈ I t − 1 d i , t − 1 P ^ t − 1 p_t^\star\in\arg\max_{i\in\mathcal{I}_{t-1}}d^{\widehat{\mathcal{P}}_{t-1}}_{i,t-1} p t ⋆ ∈ arg max i ∈ I t − 1 d i , t − 1 P t − 1 be an exact greedy pivot conditional on the same previous pivot history. By the definition of ζ t − 1 \zeta_{t-1} ζ t − 1 ,
d p ^ t , t − 1 P ^ t − 1 ≥ s ^ p ^ t , t − 1 − ζ t − 1 . (85) d^{\widehat{\mathcal{P}}_{t-1}}_{\widehat{p}_t,t-1}\geq\widehat{s}_{\widehat{p}_t,t-1}-\zeta_{t-1}. \tag*{(85)} d p t , t − 1 P t − 1 ≥ s p t , t − 1 − ζ t − 1 . (85)
Since p ^ t \widehat{p}_t p t maximizes the finite-shot score over I t − 1 \mathcal{I}_{t-1} I t − 1 ,
s ^ p ^ t , t − 1 ≥ s ^ p t ⋆ , t − 1 . (86) \widehat{s}_{\widehat{p}_t,t-1}\geq\widehat{s}_{p_t^\star,t-1}. \tag*{(86)} s p t , t − 1 ≥ s p t ⋆ , t − 1 . (86)
Applying the score-discrepancy bound once more yields
s ^ p t ⋆ , t − 1 ≥ d p t ⋆ , t − 1 P ^ t − 1 − ζ t − 1 . (87) \widehat{s}_{p_t^\star,t-1}\geq d^{\widehat{\mathcal{P}}_{t-1}}_{p_t^\star,t-1}-\zeta_{t-1}. \tag*{(87)} s p t ⋆ , t − 1 ≥ d p t ⋆ , t − 1 P t − 1 − ζ t − 1 . (87)
Combining the three inequalities yields
d p ^ t , t − 1 P ^ t − 1 ≥ d p t ⋆ , t − 1 P ^ t − 1 − 2 ζ t − 1 = max i ∈ I t − 1 d i , t − 1 P ^ t − 1 − 2 ζ t − 1 , (88) d^{\widehat{\mathcal{P}}_{t-1}}_{\widehat{p}_t,t-1}\geq d^{\widehat{\mathcal{P}}_{t-1}}_{p_t^\star,t-1}-2\zeta_{t-1}=\max_{i\in\mathcal{I}_{t-1}}d^{\widehat{\mathcal{P}}_{t-1}}_{i,t-1}-2\zeta_{t-1}, \tag*{(88)} d p t , t − 1 P t − 1 ≥ d p t ⋆ , t − 1 P t − 1 − 2 ζ t − 1 = i ∈ I t − 1 max d i , t − 1 P t − 1 − 2 ζ t − 1 , (88)
which completes the proof.
Lemma 3 does not require finite-shot ICAQKL to reproduce the exact greedy pivot. Instead, it establishes that the selected pivot is approximately greedy with respect to the exact residual geometry associated with the same previously selected path. In particular, the exact residual value of the finite-shot-selected pivot is at most 2 ζ t − 1 2\zeta_{t-1} 2 ζ t − 1 below the best admissible exact residual. This approximate-greedy characterization is preferable to requiring exact pivot agreement when several candidate samples have nearly identical residual diagonals. In such cases, finite-shot noise may alter the ordering of the candidates without materially degrading the quality of the selected pivot. A stronger result is available when the best exact pivot is separated from all competing candidates by a sufficiently large residual gap.
Corollary 1 (Pivot-gap stability). Suppose the exact same-history greedy pivot p t ⋆ p_t^\star p t ⋆ is unique, and define its residual gap over the remaining admissible indices as γ t : = d p t ⋆ , t − 1 P ^ t − 1 − max j ∈ I t − 1 ∖ { p t ⋆ } d j , t − 1 P ^ t − 1 \gamma_t:=d^{\widehat{\mathcal{P}}_{t-1}}_{p_t^\star,t-1}-\max_{j\in\mathcal{I}_{t-1}\setminus\{p_t^\star\}}d^{\widehat{\mathcal{P}}_{t-1}}_{j,t-1} γ t := d p t ⋆ , t − 1 P t − 1 − max j ∈ I t − 1 ∖ { p t ⋆ } d j , t − 1 P t − 1 . If γ t > 2 ζ t − 1 \gamma_t>2\zeta_{t-1} γ t > 2 ζ t − 1 then the finite-shot recursion selects the same pivot as the exact same-history greedy rule p ^ t = p t ⋆ \widehat{p}_t=p_t^\star p t = p t ⋆ .
Proof. Suppose, for contradiction, that p ^ t ≠ p t ⋆ \widehat{p}_t\ne p_t^\star p t = p t ⋆ . Since p ^ t ∈ I t − 1 ∖ { p t ⋆ } \widehat{p}_t\in\mathcal{I}_{t-1}\setminus\{p_t^\star\} p t ∈ I t − 1 ∖ { p t ⋆ } , pivot gap’s definition implies
d p ^ t , t − 1 P ^ t − 1 ≤ d p t ⋆ , t − 1 P ^ t − 1 − γ t . (89) d^{\widehat{\mathcal{P}}_{t-1}}_{\widehat{p}_t,t-1}\leq d^{\widehat{\mathcal{P}}_{t-1}}_{p_t^\star,t-1}-\gamma_t. \tag*{(89)} d p t , t − 1 P t − 1 ≤ d p t ⋆ , t − 1 P t − 1 − γ t . (89) On the other hand, Lemma 3 yields
d p ^ t , t − 1 P ^ t − 1 ≥ max i ∈ I t − 1 d i , t − 1 P ^ t − 1 − 2 ζ t − 1 = d p t ⋆ , t − 1 P ^ t − 1 − 2 ζ t − 1 . (90) d^{\widehat{\mathcal{P}}_{t-1}}_{\widehat{p}_t,t-1}\geq\max_{i\in\mathcal{I}_{t-1}}d^{\widehat{\mathcal{P}}_{t-1}}_{i,t-1}-2\zeta_{t-1}=d^{\widehat{\mathcal{P}}_{t-1}}_{p_t^\star,t-1}-2\zeta_{t-1}. \tag*{(90)} d p t , t − 1 P t − 1 ≥ i ∈ I t − 1 max d i , t − 1 P t − 1 − 2 ζ t − 1 = d p t ⋆ , t − 1 P t − 1 − 2 ζ t − 1 . (90)
Combining (89) and (90) yields
γ t ≤ 2 ζ t − 1 , (91) \gamma_t \le2\zeta_{t-1}, \tag*{(91)} γ t ≤ 2 ζ t − 1 , (91)
which contradicts the stated condition γ t > 2 ζ t − 1 \gamma_t > 2\zeta_{t-1} γ t > 2 ζ t − 1 . Therefore, p ^ t = p t ∗ \hat{p}_t = p_t^* p ^ t = p t ∗ .
Corollary 1. identifies a sufficient condition for exact pivot recovery. When the separation between the largest and second-largest exact residual diagonals exceeds twice the finite-shot score error, measurement noise cannot change their ordering. Thus, pivot-path deviations can occur only when the exact residual gap becomes comparable to the uncertainty in the finite-shot scores.
From pivot stability to factor stability. The preceding concentration and pivot-selection results characterize how finite-shot uncertainty can influence the adaptive query path, but they do not yet quantify the numerical error in the Cholesky factor itself. Even when the finite-shot recursion selects the same pivot as its exact counterpart, the corresponding Cholesky column is still constructed from noisy kernel estimates and therefore differs from the exact column. To isolate this effect, we compare the finite-shot factor with an exact-entry factor constrained to follow the same selected pivot sequence. This path-conditioned comparison separates the structural quality of the chosen pivot path from the recursive numerical perturbation induced by finite-shot kernel estimation, enabling a direct stability analysis of the Cholesky factor.
Path-conditioned factor perturbation. A direct comparison between the finite-shot factor and the ordinary exact greedy Cholesky factor would confound two distinct effects. First, finite-shot estimation may alter the pivot sequence itself. Second, even when the pivot sequence is fixed, the queried kernel values used to construct each Cholesky column remain noisy. To separate these effects, we introduce an exact-entry comparator that follows the same pivot sequence selected by the finite-shot recursion. Specifically, for the finite-shot pivot sequence through iteration t t t , P ^ t = ( p ^ 1 , … , p ^ t ) \widehat{P}_t = (\hat{p}_1,\ldots,\hat{p}_t) P t = ( p ^ 1 , … , p ^ t ) , let G ^ t P ^ t \widehat{G}_t^{\widehat{P}_t} G t P t be the exact-entry Cholesky factor obtained by following this same sequence while evaluating every required kernel entry exactly. This path-conditioned comparator isolates the numerical perturbation induced by finite-shot estimation from the structural approximation quality of the selected pivot path.
Assumption 2 (Stable executed path). For every executed iteration t ≤ r t \le r t ≤ r , there exist constants τ > 0 \tau> 0 τ > 0 , B < ∞ B < \infty B < ∞ , κ < ∞ \kappa< \infty κ < ∞ such that the exact and finite-shot pivot quantities satisfy d p ^ t , t − 1 P ^ t − 1 ≥ τ d^{\widehat{P}_{t-1}}_{\hat{p}_t,t-1} \ge\tau d p ^ t , t − 1 P t − 1 ≥ τ , s ^ p ^ t , t − 1 ≥ τ \hat{s}_{\hat{p}_t,t-1} \ge\tau s ^ p ^ t , t − 1 ≥ τ and the exact and finite-shot factor rows satisfy
max i ∥ G ^ i , 1 : t P ^ t ∥ 2 ≤ B , max i ∥ G ^ i , 1 : t ( N s ) ∥ 2 ≤ B . (92) \max_i \left\|\widehat{G}^{\widehat{P}_t}_{i,1:t}\right\|_2 \le B,\qquad\max_i \left\|\widehat{G}^{(N_s)}_{i,1:t}\right\|_2 \le B. \tag*{(92)} i max G i , 1 : t P t 2 ≤ B , i max G i , 1 : t ( N s ) 2 ≤ B . (92) Moreover, K i i Q ≤ κ K^Q_{ii} \le\kappa K ii Q ≤ κ , i = 1 , … , n i=1,\ldots,n i = 1 , … , n . For the normalized fidelity kernel considered in this work, κ = 1 \kappa= 1 κ = 1 .
The constant τ \tau τ is an analysis condition on the executed pivot path rather than a modification of the ICAQKL algorithm. It prevents the reciprocal square-root normalization in the Cholesky update from becoming arbitrarily ill-conditioned. Define the rowwise factor perturbation
E t : = max i ∥ G ^ i , 1 : t ( N s ) − G ^ i , 1 : t P ^ t ∥ 2 , (93) E_t := \max_i \left\|\widehat{G}^{(N_s)}_{i,1:t} - \widehat{G}^{\widehat{P}_t}_{i,1:t}\right\|_2, \tag*{(93)} E t := i max G i , 1 : t ( N s ) − G i , 1 : t P t 2 , (93)
the maximum error in the newly constructed column
a t : = max i ∣ G ^ i t ( N s ) − G ^ i t P ^ t ∣ , (94) a_t := \max_i \left|\widehat{G}^{(N_s)}_{it} - \widehat{G}^{\widehat{P}_t}_{it}\right|, \tag*{(94)} a t := i max G i t ( N s ) − G i t P t , (94)
and the pivot-score discrepancy
ζ t : = ∥ s ^ t − d t P ^ t ∥ ∞ , I t , (95) \zeta_t := \left\|\widehat{s}_t - d^{\widehat{P}_t}_t\right\|_{\infty,\mathcal{I}_t}, \tag*{(95)} ζ t := s t − d t P t ∞ , I t , (95)
where I t \mathcal{I}_t I t denotes the indices still admissible after iteration t t t . Because the fidelity-kernel diagonal is known exactly and both recursions are initialized from K i i Q = s ^ i , 0 = 1 K^Q_{ii} = \hat{s}_{i,0} = 1 K ii Q = s ^ i , 0 = 1 , we have E 0 = ζ 0 = 0 E_0 = \zeta_0 = 0 E 0 = ζ 0 = 0 .
Theorem 5 (Recursive finite-shot factor perturbation). Under Assumption 2 and the concentration event 64, the finite-shot perturbations satisfy, for every t ≤ r t \le r t ≤ r ,
a t ≤ η s + 2 B E t − 1 τ + κ ζ t − 1 2 τ 3 / 2 , E t ≤ E t − 1 2 + a t 2 , ζ t ≤ ζ t − 1 + 2 B a t . (96) a_t \le\frac{\eta_s + 2BE_{t-1}}{\sqrt{\tau}} + \frac{\kappa\zeta_{t-1}}{2\tau^{3/2}},\qquad E_t \le\sqrt{E_{t-1}^2+a_t^2},\qquad\zeta_t \le\zeta_{t-1}+2Ba_t. \tag*{(96)} a t ≤ τ η s + 2 B E t − 1 + 2 τ 3/2 κ ζ t − 1 , E t ≤ E t − 1 2 + a t 2 , ζ t ≤ ζ t − 1 + 2 B a t . (96)
Consequently, for fixed r r r , τ \tau τ , B B B , and κ \kappa κ , there exists a finite constant C r , τ , B , κ > 0 C_{r,\tau,B,\kappa} > 0 C r , τ , B , κ > 0 such that
E r ≤ C r , τ , B , κ η s . (97) E_r \le C_{r,\tau,B,\kappa}\eta_s. \tag*{(97)} E r ≤ C r , τ , B , κ η s . (97)
Proof. Fix an iteration t t t and the common pivot p ^ t \hat{p}_t p ^ t . For each row i i i , define the exact and finite-shot Cholesky numerators by
u i , t = K i p ^ t Q − ∑ ℓ = 1 t − 1 G i ℓ P ^ t − 1 G p ^ t ℓ P ^ t − 1 , u ^ i , t = K ^ i p ^ t Q − ∑ ℓ = 1 t − 1 G ^ i ℓ ( N s ) G ^ p ^ t ℓ ( N s ) . (98) u_{i,t}=K^Q_{i\hat{p}_t}-\sum_{\ell=1}^{t-1}G^{\hat{P}_{t-1}}_{i\ell}G^{\hat{P}_{t-1}}_{\hat{p}_t\ell},\qquad\hat{u}_{i,t}=\hat{K}^Q_{i\hat{p}_t}-\sum_{\ell=1}^{t-1}\hat{G}^{(N_s)}_{i\ell}\hat{G}^{(N_s)}_{\hat{p}_t\ell}. \tag*{(98)} u i , t = K i p ^ t Q − ℓ = 1 ∑ t − 1 G i ℓ P ^ t − 1 G p ^ t ℓ P ^ t − 1 , u ^ i , t = K ^ i p ^ t Q − ℓ = 1 ∑ t − 1 G ^ i ℓ ( N s ) G ^ p ^ t ℓ ( N s ) . (98)
On the concentration event, ∣ K ^ i p ^ t Q − K i p ^ t Q ∣ ≤ η s \left|\hat{K}^Q_{i\hat{p}_t}-K^Q_{i\hat{p}_t}\right|\le\eta_s K ^ i p ^ t Q − K i p ^ t Q ≤ η s for every queried entry. For the recursive inner-product term, by the triangle inequality and Cauchy–Schwarz inequality,
∣ ( G ^ i , 1 : t − 1 ( N s ) ) ⊤ G ^ p ^ t , 1 : t − 1 ( N s ) − ( G i , 1 : t − 1 P ^ t − 1 ) ⊤ G p ^ t , 1 : t − 1 P ^ t − 1 ∣ ≤ ∥ G ^ i , 1 : t − 1 ( N s ) − G i , 1 : t − 1 P ^ t − 1 ∥ 2 ∥ G ^ p ^ t , 1 : t − 1 ( N s ) ∥ 2 + ∥ G i , 1 : t − 1 P ^ t − 1 ∥ 2 ∥ G ^ p ^ t , 1 : t − 1 ( N s ) − G p ^ t , 1 : t − 1 P ^ t − 1 ∥ 2 ≤ 2 B E t − 1 . (99) \begin{aligned}
\left|(\hat{G}^{(N_s)}_{i,1:t-1})^\top\hat{G}^{(N_s)}_{\hat{p}_t,1:t-1}-(G^{\hat{P}_{t-1}}_{i,1:t-1})^\top G^{\hat{P}_{t-1}}_{\hat{p}_t,1:t-1}\right|
&\le\left\|\hat{G}^{(N_s)}_{i,1:t-1}-G^{\hat{P}_{t-1}}_{i,1:t-1}\right\|_2\left\|\hat{G}^{(N_s)}_{\hat{p}_t,1:t-1}\right\|_2\\
&\quad+\left\|G^{\hat{P}_{t-1}}_{i,1:t-1}\right\|_2\left\|\hat{G}^{(N_s)}_{\hat{p}_t,1:t-1}-G^{\hat{P}_{t-1}}_{\hat{p}_t,1:t-1}\right\|_2\\
&\le2BE_{t-1}. \tag*{(99)}
\end{aligned} ( G ^ i , 1 : t − 1 ( N s ) ) ⊤ G ^ p ^ t , 1 : t − 1 ( N s ) − ( G i , 1 : t − 1 P ^ t − 1 ) ⊤ G p ^ t , 1 : t − 1 P ^ t − 1 ≤ G ^ i , 1 : t − 1 ( N s ) − G i , 1 : t − 1 P ^ t − 1 2 G ^ p ^ t , 1 : t − 1 ( N s ) 2 + G i , 1 : t − 1 P ^ t − 1 2 G ^ p ^ t , 1 : t − 1 ( N s ) − G p ^ t , 1 : t − 1 P ^ t − 1 2 ≤ 2 B E t − 1 . (99)
Therefore, we can obtain
∣ u ^ i , t − u i , t ∣ ≤ η s + 2 B E t − 1 . (100) |\hat{u}_{i,t}-u_{i,t}|\le\eta_s+2BE_{t-1}. \tag*{(100)} ∣ u ^ i , t − u i , t ∣ ≤ η s + 2 B E t − 1 . (100)
Next, the map h ( x ) = x − 1 / 2 h(x)=x^{-1/2} h ( x ) = x − 1/2 has derivative ∣ h ′ ( x ) ∣ = 1 2 x 3 / 2 ≤ 1 2 τ 3 / 2 |h'(x)|=\frac{1}{2x^{3/2}}\le\frac{1}{2\tau^{3/2}} ∣ h ′ ( x ) ∣ = 2 x 3/2 1 ≤ 2 τ 3/2 1 on [ τ , ∞ ) [\tau,\infty) [ τ , ∞ ) . Therefore,
∣ 1 s ^ p ^ t , t − 1 − 1 d p ^ t , t − 1 P ^ t − 1 ∣ ≤ ∣ s ^ p ^ t , t − 1 − d p ^ t , t − 1 P ^ t − 1 ∣ 2 τ 3 / 2 ≤ ζ t − 1 2 τ 3 / 2 . (101) \left|\frac{1}{\sqrt{\hat{s}_{\hat{p}_t,t-1}}}-\frac{1}{\sqrt{d^{\hat{P}_{t-1}}_{\hat{p}_t,t-1}}}\right|\le\frac{\left|\hat{s}_{\hat{p}_t,t-1}-d^{\hat{P}_{t-1}}_{\hat{p}_t,t-1}\right|}{2\tau^{3/2}}\le\frac{\zeta_{t-1}}{2\tau^{3/2}}. \tag*{(101)} s ^ p ^ t , t − 1 1 − d p ^ t , t − 1 P ^ t − 1 1 ≤ 2 τ 3/2 s ^ p ^ t , t − 1 − d p ^ t , t − 1 P ^ t − 1 ≤ 2 τ 3/2 ζ t − 1 . (101)
The exact numerator is an entry of the exact residual, i.e., u i , t = ( R t − 1 P ^ t − 1 ) i , p ^ t u_{i,t}=(R^{\hat{P}_{t-1}}_{t-1})_{i,\hat{p}_t} u i , t = ( R t − 1 P ^ t − 1 ) i , p ^ t . Since this residual is PSD, Cauchy–Schwarz for PSD matrices yields
∣ u i , t ∣ ≤ d i , t − 1 P ^ t − 1 d p ^ t , t − 1 P ^ t − 1 . (102) |u_{i,t}|\le\sqrt{d^{\hat{P}_{t-1}}_{i,t-1}d^{\hat{P}_{t-1}}_{\hat{p}_t,t-1}}. \tag*{(102)} ∣ u i , t ∣ ≤ d i , t − 1 P ^ t − 1 d p ^ t , t − 1 P ^ t − 1 . (102)
By residual monotonicity and K i i Q ≤ κ K^Q_{ii}\le\kappa K ii Q ≤ κ , we have
d i , t − 1 P ^ t − 1 ≤ K i i Q ≤ κ , (103) d^{\hat{P}_{t-1}}_{i,t-1}\le K^Q_{ii}\le\kappa, \tag*{(103)} d i , t − 1 P ^ t − 1 ≤ K ii Q ≤ κ , (103)
and similarly for the pivot diagonal. Hence, ∣ u i , t ∣ ≤ κ |u_{i,t}|\le\kappa ∣ u i , t ∣ ≤ κ . By using
G ^ i t ( N s ) = u ^ i , t s ^ p ^ t , t − 1 , G i t P ^ t = u i , t d p ^ t , t − 1 P ^ t − 1 , (104) \hat{G}^{(N_s)}_{it}=\frac{\hat{u}_{i,t}}{\sqrt{\hat{s}_{\hat{p}_t,t-1}}},\qquad G^{\hat{P}_t}_{it}=\frac{u_{i,t}}{\sqrt{d^{\hat{P}_{t-1}}_{\hat{p}_t,t-1}}}, \tag*{(104)} G ^ i t ( N s ) = s ^ p ^ t , t − 1 u ^ i , t , G i t P ^ t = d p ^ t , t − 1 P ^ t − 1 u i , t , (104)
we obtain
∣ G ^ i t ( N s ) − G i t P ^ t ∣ ≤ ∣ u ^ i , t − u i , t ∣ s ^ p ^ t , t − 1 + ∣ u i , t ∣ ∣ 1 s ^ p ^ t , t − 1 − 1 d p ^ t , t − 1 P ^ t − 1 ∣ ≤ η s + 2 B E t − 1 τ + κ ζ t − 1 2 τ 3 / 2 . (105) \left|\hat{G}^{(N_s)}_{it}-G^{\hat{P}_t}_{it}\right|\le\frac{|\hat{u}_{i,t}-u_{i,t}|}{\sqrt{\hat{s}_{\hat{p}_t,t-1}}}+|u_{i,t}|\left|\frac{1}{\sqrt{\hat{s}_{\hat{p}_t,t-1}}}-\frac{1}{\sqrt{d^{\hat{P}_{t-1}}_{\hat{p}_t,t-1}}}\right|\le\frac{\eta_s+2BE_{t-1}}{\sqrt{\tau}}+\frac{\kappa\zeta_{t-1}}{2\tau^{3/2}}. \tag*{(105)} G ^ i t ( N s ) − G i t P ^ t ≤ s ^ p ^ t , t − 1 ∣ u ^ i , t − u i , t ∣ + ∣ u i , t ∣ s ^ p ^ t , t − 1 1 − d p ^ t , t − 1 P ^ t − 1 1 ≤ τ η s + 2 B E t − 1 + 2 τ 3/2 κ ζ t − 1 . (105)
Taking the maximum over i i i proves for a t a_t a t in (96) . For each row,
∥ G ^ i , 1 : t ( N s ) − G i , 1 : t P ^ t ∥ 2 2 = ∥ G ^ i , 1 : t − 1 ( N s ) − G i , 1 : t − 1 P ^ t − 1 ∥ 2 2 + ∥ G ^ i t ( N s ) − G i t P ^ t ∥ 2 . (106) \left\|\hat{G}^{(N_s)}_{i,1:t}-G^{\hat{P}_t}_{i,1:t}\right\|_2^2=\left\|\hat{G}^{(N_s)}_{i,1:t-1}-G^{\hat{P}_{t-1}}_{i,1:t-1}\right\|_2^2+\left\|\hat{G}^{(N_s)}_{it}-G^{\hat{P}_t}_{it}\right\|^2. \tag*{(106)} G ^ i , 1 : t ( N s ) − G i , 1 : t P ^ t 2 2 = G ^ i , 1 : t − 1 ( N s ) − G i , 1 : t − 1 P ^ t − 1 2 2 + G ^ i t ( N s ) − G i t P ^ t 2 . (106)
Taking the maximum over i i i yields
E t ≤ E t − 1 2 + a t 2 . (107) E_t\le\sqrt{E_{t-1}^2+a_t^2}. \tag*{(107)} E t ≤ E t − 1 2 + a t 2 . (107)
which proves for E t E_t E t in (96) . For the score recursion, let P + ( x ) : = [ x ] + P_+(x):=[x]_+ P + ( x ) := [ x ] + . Since projection onto [ 0 , ∞ ) [0,\infty) [ 0 , ∞ ) is nonexpansive and the exact residual diagonal is nonnegative,
d ^ i , t P ^ t = P + ( d ^ i , t − 1 P ^ t − 1 − ( G ^ i t P ) 2 ) . (108) \hat{d}_{i,t}^{\hat{P}_t}=P_+\left(\hat{d}_{i,t-1}^{\hat{P}_{t-1}}-\left(\hat{G}_{it}^{P}\right)^2\right). \tag*{(108)} d ^ i , t P ^ t = P + ( d ^ i , t − 1 P ^ t − 1 − ( G ^ i t P ) 2 ) . (108)
Therefore, we can obtain
∣ s ^ i , t − d ^ i , t P ^ t ∣ ≤ ∣ s ^ i , t − 1 − d ^ i , t − 1 P ^ t − 1 ∣ + ∣ ( G ^ i t ( N s ) ) 2 − ( G ^ i t P ^ t ) 2 ∣ . (109) \left|\hat{s}_{i,t}-\hat{d}_{i,t}^{\hat{P}_t}\right|\leq\left|\hat{s}_{i,t-1}-\hat{d}_{i,t-1}^{\hat{P}_{t-1}}\right|+\left|\left(\hat{G}_{it}^{(N_s)}\right)^2-\left(\hat{G}_{it}^{\hat{P}_t}\right)^2\right|. \tag*{(109)} s ^ i , t − d ^ i , t P ^ t ≤ s ^ i , t − 1 − d ^ i , t − 1 P ^ t − 1 + ( G ^ i t ( N s ) ) 2 − ( G ^ i t P ^ t ) 2 . (109)
Using ∣ a 2 − b 2 ∣ = ∣ a − b ∣ ∣ a + b ∣ |a^2-b^2|=|a-b||a+b| ∣ a 2 − b 2 ∣ = ∣ a − b ∣∣ a + b ∣ and the row bounds in Assumption 2,
∣ ( G ^ i t ( N s ) ) 2 − ( G ^ i t P ^ t ) 2 ∣ ≤ 2 B a t . (110) \left|\left(\hat{G}_{it}^{(N_s)}\right)^2-\left(\hat{G}_{it}^{\hat{P}_t}\right)^2\right|\leq2B a_t. \tag*{(110)} ( G ^ i t ( N s ) ) 2 − ( G ^ i t P ^ t ) 2 ≤ 2 B a t . (110)
Taking the maximum over admissible indices yields ζ t ≤ ζ t − 1 + 2 B a t \zeta_t\leq\zeta_{t-1}+2B a_t ζ t ≤ ζ t − 1 + 2 B a t , which proves ζ t \zeta_t ζ t in (96) .
It remains to establish the final proportionality to η s \eta_s η s . Define deterministic constants recursively by C E ( 0 ) = C ζ ( 0 ) = 0 C_E^{(0)}=C_\zeta^{(0)}=0 C E ( 0 ) = C ζ ( 0 ) = 0 and, for t ≥ 1 t\geq1 t ≥ 1 ,
C a ( t ) : = 1 + 2 B C E ( t − 1 ) τ + κ C ζ ( t − 1 ) 2 τ 3 / 2 , C E ( t ) : = ( C E ( t − 1 ) ) 2 + ( C a ( t ) ) 2 , C ζ ( t ) : = C ζ ( t − 1 ) + 2 B C a ( t ) . (111) C_a^{(t)}:=\frac{1+2B C_E^{(t-1)}}{\sqrt{\tau}}+\frac{\kappa C_\zeta^{(t-1)}}{2\tau^{3/2}},\quad C_E^{(t)}:=\sqrt{\left(C_E^{(t-1)}\right)^2+\left(C_a^{(t)}\right)^2},\quad C_\zeta^{(t)}:=C_\zeta^{(t-1)}+2B C_a^{(t)}. \tag*{(111)} C a ( t ) := τ 1 + 2 B C E ( t − 1 ) + 2 τ 3/2 κ C ζ ( t − 1 ) , C E ( t ) := ( C E ( t − 1 ) ) 2 + ( C a ( t ) ) 2 , C ζ ( t ) := C ζ ( t − 1 ) + 2 B C a ( t ) . (111)
An induction using (96) shows that
a t ≤ C a ( t ) η s , E t ≤ C E ( t ) η s , ζ t ≤ C ζ ( t ) η s . (112) a_t\leq C_a^{(t)}\eta_s,\quad E_t\leq C_E^{(t)}\eta_s,\quad\zeta_t\leq C_\zeta^{(t)}\eta_s. \tag*{(112)} a t ≤ C a ( t ) η s , E t ≤ C E ( t ) η s , ζ t ≤ C ζ ( t ) η s . (112)
For fixed r r r , τ \tau τ , B B B , κ \kappa κ , all of these constants are finite. Taking C r , τ , B , κ : = C E ( r ) C_{r,\tau,B,\kappa}:=C_E^{(r)} C r , τ , B , κ := C E ( r ) establishes (97) .
Theorem 5 identifies the recursive mechanism through which finite-shot quantum-kernel error propagates through ICAQKL. The oracle error η s \eta_s η s directly perturbs the numerator of each Cholesky update, while the accumulated factor error E t − 1 E_{t-1} E t − 1 feeds back into subsequent inner products and the score discrepancy ζ t − 1 \zeta_{t-1} ζ t − 1 perturbs the pivot normalization. Thus, finite-shot error is propagated recursively rather than added only once at the matrix level. The lower pivot bound τ \tau τ quantifies the conditioning of this recursion. As a selected residual approaches zero, the normalization by its square root becomes increasingly sensitive to perturbations. Assumption 2 therefore characterizes the regime in which the executed finite-shot factorization remains stable. To convert the rowwise perturbation into a matrix-level factor error, define
Δ r : = ∥ G ^ r ( N s ) − G r P ^ r ∥ 2 . (113) \Delta_r:=\left\|\hat{G}_r^{(N_s)}-G_r^{\hat{P}_r}\right\|_2. \tag*{(113)} Δ r := G ^ r ( N s ) − G r P ^ r 2 . (113)
Using Frobenius norm property, ∣ A ∣ 2 ≤ ∣ A ∣ F \lvert A\rvert_2\leq\lvert A\rvert_F ∣ A ∣ 2 ≤ ∣ A ∣ F ,
Δ r ≤ ∥ G ^ r ( N s ) − G r P ^ r ∥ F ≤ n E r . (114) \Delta_r\leq\left\|\hat{G}_r^{(N_s)}-G_r^{\hat{P}_r}\right\|_F\leq\sqrt{n}E_r. \tag*{(114)} Δ r ≤ G ^ r ( N s ) − G r P ^ r F ≤ n E r . (114)
Consequently, for fixed stable rank and fixed τ \tau τ , B B B , κ \kappa κ ,
Δ r = O ( η s ) = O ( log ( M r / δ ) N s ) . (115) \Delta_r=O(\eta_s)=O\left(\sqrt{\frac{\log(M_r/\delta)}{N_s}}\right). \tag*{(115)} Δ r = O ( η s ) = O N s log ( M r / δ ) . (115)
This result establishes the required bridge from finite-shot quantum-kernel estimation error to perturbation of the recursively constructed Cholesky factor. The remaining step is to combine this numerical factor error with the structural approximation error of the selected pivot path to obtain a bound on the final low-rank kernel surrogate.
Total finite-shot kernel approximation error. The preceding analysis allows us to separate two conceptually distinct sources of error in the finite-shot ICAQKL surrogate. The first is the structural rank/path error . Even if every kernel entry required along the selected pivot sequence were evaluated exactly, a rank-r r r Cholesky factor generally does not recover the complete kernel unless the selected rank is sufficiently large. The second is the finite-shot factorization error . Conditional on the same pivot sequence, the factor constructed from finite-shot kernel estimates differs from the corresponding exact-entry factor. The following result separates these two effects.
Theorem 6 (Path-conditioned total kernel error). Define the exact-path rank-r r r approximation error by ε r ( P ^ r ) : = ∥ K Q − G r P ^ r ( G ^ r P ^ r ) T ∥ 2 \varepsilon_r(\widehat{P}_r):=\left\|K^Q-G_r^{\widehat{P}_r}(\widehat{G}_r^{\widehat{P}_r})^{\mathsf{T}}\right\|_2 ε r ( P r ) := K Q − G r P r ( G r P r ) T 2 , and let β r : = ∥ G r P ^ r ∥ 2 \beta_r:=\left\|G_r^{\widehat{P}_r}\right\|_2 β r := G r P r 2 . Then the finite-shot kernel-surrogate error E r ( N s ) : = ∥ K Q − K ~ r Q , ( N s ) ∥ 2 \mathcal{E}_r^{(N_s)}:=\left\|K^Q-\widetilde{K}_r^{Q,(N_s)}\right\|_2 E r ( N s ) := K Q − K r Q , ( N s ) 2 satisfies
E r ( N s ) ≤ ε r ( P ^ r ) + ( 2 β r + Δ r ) Δ r . (116) \mathcal{E}_r^{(N_s)} \le\varepsilon_r(\widehat{P}_r)+(2\beta_r+\Delta_r)\Delta_r. \tag*{(116)} E r ( N s ) ≤ ε r ( P r ) + ( 2 β r + Δ r ) Δ r . (116)
Proof. Recall that
K ~ r Q , ( N s ) = G ^ r ( N s ) ( G ^ r ( N s ) ) T . (117) \widetilde{K}_r^{Q,(N_s)}=\widehat{G}_r^{(N_s)}\left(\widehat{G}_r^{(N_s)}\right)^{\mathsf{T}}. \tag*{(117)} K r Q , ( N s ) = G r ( N s ) ( G r ( N s ) ) T . (117)
Add and subtract the exact-entry surrogate following the same selected pivot path:
∥ K Q − K ~ r Q , ( N s ) ∥ 2 ≤ ∥ K Q − G r P ^ r ( G ^ r P ^ r ) T ∥ 2 + ∥ G r P ^ r ( G ^ r P ^ r ) T − G ^ r ( N s ) ( G ^ r ( N s ) ) T ∥ 2 (118) \left\|K^Q-\widetilde{K}_r^{Q,(N_s)}\right\|_2\leq\left\|K^Q-G_r^{\widehat{P}_r}(\widehat{G}_r^{\widehat{P}_r})^{\mathsf{T}}\right\|_2+\left\|G_r^{\widehat{P}_r}(\widehat{G}_r^{\widehat{P}_r})^{\mathsf{T}}-\widehat{G}_r^{(N_s)}\left(\widehat{G}_r^{(N_s)}\right)^{\mathsf{T}}\right\|_2 \tag*{(118)} K Q − K r Q , ( N s ) 2 ≤ K Q − G r P r ( G r P r ) T 2 + G r P r ( G r P r ) T − G r ( N s ) ( G r ( N s ) ) T 2 (118)
= ε r ( P ^ r ) + ∥ G r P ^ r ( G ^ r P ^ r ) T − G ^ r ( N s ) ( G ^ r ( N s ) ) T ∥ 2 . (119) =\varepsilon_r(\widehat{P}_r)+\left\|G_r^{\widehat{P}_r}(\widehat{G}_r^{\widehat{P}_r})^{\mathsf{T}}-\widehat{G}_r^{(N_s)}\left(\widehat{G}_r^{(N_s)}\right)^{\mathsf{T}}\right\|_2. \tag*{(119)} = ε r ( P r ) + G r P r ( G r P r ) T − G r ( N s ) ( G r ( N s ) ) T 2 . (119)
Define the factor perturbation matrix D r : = G ^ r ( N s ) − G r P ^ r D_r:=\widehat{G}_r^{(N_s)}-G_r^{\widehat{P}_r} D r := G r ( N s ) − G r P r so that, by definition, ∥ D r ∥ 2 = Δ r \left\|D_r\right\|_2=\Delta_r ∥ D r ∥ 2 = Δ r . Since
G ^ r ( N s ) = G r P ^ r + D r , (120) \widehat{G}_r^{(N_s)}=G_r^{\widehat{P}_r}+D_r, \tag*{(120)} G r ( N s ) = G r P r + D r , (120)
it follows that
G ^ r ( N s ) ( G ^ r ( N s ) ) T − G r P ^ r ( G r P ^ r ) T = D r ( G r P ^ r ) T + G r P ^ r D r T + D r D r T . (121) \widehat{G}_r^{(N_s)}\left(\widehat{G}_r^{(N_s)}\right)^{\mathsf{T}}-G_r^{\widehat{P}_r}\left(G_r^{\widehat{P}_r}\right)^{\mathsf{T}}=D_r\left(G_r^{\widehat{P}_r}\right)^{\mathsf{T}}+G_r^{\widehat{P}_r}D_r^{\mathsf{T}}+D_rD_r^{\mathsf{T}}. \tag*{(121)} G r ( N s ) ( G r ( N s ) ) T − G r P r ( G r P r ) T = D r ( G r P r ) T + G r P r D r T + D r D r T . (121)
Therefore, by the triangle inequality and submultiplicativity of the spectral norm,
∥ G r P ^ r ( G r P ^ r ) T − G ^ r ( N s ) ( G ^ r ( N s ) ) T ∥ 2 ≤ ∥ D r ( G r P ^ r ) T ∥ 2 + ∥ G r P ^ r D r T ∥ 2 + ∥ D r D r T ∥ 2 (122) \left\|G_r^{\widehat{P}_r}\left(G_r^{\widehat{P}_r}\right)^{\mathsf{T}}-\widehat{G}_r^{(N_s)}\left(\widehat{G}_r^{(N_s)}\right)^{\mathsf{T}}\right\|_2\leq\left\|D_r\left(G_r^{\widehat{P}_r}\right)^{\mathsf{T}}\right\|_2+\left\|G_r^{\widehat{P}_r}D_r^{\mathsf{T}}\right\|_2+\left\|D_rD_r^{\mathsf{T}}\right\|_2 \tag*{(122)} G r P r ( G r P r ) T − G r ( N s ) ( G r ( N s ) ) T 2 ≤ D r ( G r P r ) T 2 + G r P r D r T 2 + D r D r T 2 (122)
≤ ∥ D r ∥ 2 ∥ G r P ^ r ∥ 2 + ∥ G r P ^ r ∥ 2 ∥ D r ∥ 2 + ∥ D r ∥ 2 2 (123) \leq\left\|D_r\right\|_2\left\|G_r^{\widehat{P}_r}\right\|_2+\left\|G_r^{\widehat{P}_r}\right\|_2\left\|D_r\right\|_2+\left\|D_r\right\|_2^2 \tag*{(123)} ≤ ∥ D r ∥ 2 G r P r 2 + G r P r 2 ∥ D r ∥ 2 + ∥ D r ∥ 2 2 (123)
= 2 β r Δ r + Δ r 2 = ( 2 β r + Δ r ) Δ r . (124) =2\beta_r\Delta_r+\Delta_r^2=(2\beta_r+\Delta_r)\Delta_r. \tag*{(124)} = 2 β r Δ r + Δ r 2 = ( 2 β r + Δ r ) Δ r . (124)
Substituting (124) into (119) proves (116) . □
Remark 1. Suppose the pivot-gap condition in Corollary 1 holds at every executed iteration t = 1 , … , r t=1,\ldots,r t = 1 , … , r . Then, inductively, the finite-shot pivot sequence coincides with the exact greedy sequence, P ^ r = P r ∗ \widehat{P}_r=P_r^* P r = P r ∗ . Consequently, ε r ( P ^ r ) = ∥ K Q − G r P r ∗ ( G r P r ∗ ) T ∥ 2 \varepsilon_r(\widehat{P}_r)=\left\|K^Q-G_r^{P_r^*}(G_r^{P_r^*})^{\mathsf{T}}\right\|_2 ε r ( P r ) = K Q − G r P r ∗ ( G r P r ∗ ) T 2 , which is precisely the rank-r r r approximation error generated by the exact greedy Cholesky recursion.
Theorem 6 is deterministic once the selected path and the two factors are fixed. Combining it with Theorem 5, however, yields the finite-shot consequence Δ r = O ( η s ) \Delta_r=O(\eta_s) Δ r = O ( η s ) for fixed stable r r r , τ \tau τ , B B B , κ \kappa κ . Therefore, E r ( N s ) ≤ ε r ( P ^ r ) + O ( η s ) \mathcal{E}_r^{(N_s)}\leq\varepsilon_r(\widehat{P}_r)+O(\eta_s) E r ( N s ) ≤ ε r ( P r ) + O ( η s ) . Thus, at a fixed stable rank, increasing the shot budget suppresses the numerical finite-shot contribution, while the remaining error is determined by the approximation quality of the selected rank-r r r pivot path.
Additionally, Theorem 6 provides the interface between quantum-kernel acquisition and the subsequent QSVM analysis. The overall kernel error separates into the structural approximation error associated with the selected rank-r r r path and the numerical factorization error induced by finite-shot measurements, E r ( N s ) ≤ ε r ( P ^ r ) + ( 2 β r + Δ r ) Δ r \mathcal{E}_r^{(N_s)}\leq\varepsilon_r(\widehat{P}_r)+(2\beta_r+\Delta_r)\Delta_r E r ( N s ) ≤ ε r ( P r ) + ( 2 β r + Δ r ) Δ r . The downstream learning analysis, therefore, need not track individual measurement outcomes, pivot-score errors, or Cholesky-column perturbations separately. Once E r ( N s ) \mathcal{E}_r^{(N_s)} E r ( N s ) is controlled, this matrix-level error can be propagated through the QSVM objective and ultimately to the learned classifier.
QSVM Objective and Optimizer Stability
Having controlled the finite-shot kernel-surrogate error, we now propagate this perturbation through the QSVM training problem. The key observation is that the kernel matrix enters the dual objective only through a quadratic form. Consequently, spectral-norm control of the kernel perturbation yields a uniform perturbation bound over the entire feasible set, which in turn allows us to compare the exact and approximate optimizers. Let
A : = { α ∈ R n : 0 ≤ α i ≤ C , y T α = 0 } . (125) \mathcal{A}:=\left\{\alpha\in\mathbb{R}^n:0\leq\alpha_i\leq C,\mathbf{y}^{\mathsf{T}}\alpha=0\right\}. \tag*{(125)} A := { α ∈ R n : 0 ≤ α i ≤ C , y T α = 0 } . (125)
denote the feasible set of the soft-margin SVM dual, and define Y : = diag ( y 1 , … , y n ) \mathbf{Y}:=\operatorname{diag}(y_1,\ldots,y_n) Y := diag ( y 1 , … , y n ) . Since y i ∈ { − 1 , + 1 } y_i \in\{-1,+1\} y i ∈ { − 1 , + 1 } , we have
Y T Y = I . (126) \mathbf{Y}^{\mathsf{T}}\mathbf{Y}=\mathbf{I}. \tag*{(126)} Y T Y = I . (126)
For a kernel matrix K \mathbf{K} K , write the SVM dual in minimization form as
J K ( α ) : = 1 2 α T Y K Y α − 1 T α . (127) J_{\mathbf{K}}(\boldsymbol{\alpha}) := \frac{1}{2}\boldsymbol{\alpha}^{\mathsf{T}}\mathbf{Y}\mathbf{K}\mathbf{Y}\boldsymbol{\alpha}-\mathbf{1}^{\mathsf{T}}\boldsymbol{\alpha}. \tag*{(127)} J K ( α ) := 2 1 α T YKY α − 1 T α . (127)
Lemma 4 (Uniform perturbation of the QSVM dual). For every α ∈ A \boldsymbol{\alpha} \in\mathcal{A} α ∈ A ,
∣ J K Q ( α ) − J K ~ r Q , ( N s ) ( α ) ∣ ≤ 1 2 ∥ α ∥ 2 2 E r ( N s ) . (128) \left|J_{\mathbf{K}^{Q}}(\boldsymbol{\alpha})-J_{\widetilde{\mathbf{K}}_{r}^{Q,(N_s)}}(\boldsymbol{\alpha})\right|\leq\frac{1}{2}\|\boldsymbol{\alpha}\|_{2}^{2}\mathcal{E}_{r}^{(N_s)}. \tag*{(128)} J K Q ( α ) − J K r Q , ( N s ) ( α ) ≤ 2 1 ∥ α ∥ 2 2 E r ( N s ) . (128)
Consequently,
sup α ∈ A ∣ J K Q ( α ) − J K ~ r Q , ( N s ) ( α ) ∣ ≤ n C 2 2 E r ( N s ) . (129) \sup_{\boldsymbol{\alpha}\in\mathcal{A}}\left|J_{\mathbf{K}^{Q}}(\boldsymbol{\alpha})-J_{\widetilde{\mathbf{K}}_{r}^{Q,(N_s)}}(\boldsymbol{\alpha})\right|\leq\frac{nC^{2}}{2}\mathcal{E}_{r}^{(N_s)}. \tag*{(129)} α ∈ A sup J K Q ( α ) − J K r Q , ( N s ) ( α ) ≤ 2 n C 2 E r ( N s ) . (129)
Proof. Subtracting the two objectives gives
J K Q ( α ) − J K ~ r Q , ( N s ) ( α ) = 1 2 α T Y ( K Q − K ~ r Q , ( N s ) ) Y α . (130) J_{\mathbf{K}^{Q}}(\boldsymbol{\alpha})-J_{\widetilde{\mathbf{K}}_{r}^{Q,(N_s)}}(\boldsymbol{\alpha})=\frac{1}{2}\boldsymbol{\alpha}^{\mathsf{T}}\mathbf{Y}\left(\mathbf{K}^{Q}-\widetilde{\mathbf{K}}_{r}^{Q,(N_s)}\right)\mathbf{Y}\boldsymbol{\alpha}. \tag*{(130)} J K Q ( α ) − J K r Q , ( N s ) ( α ) = 2 1 α T Y ( K Q − K r Q , ( N s ) ) Y α . (130)
Let v : = Y α \mathbf{v}:=\mathbf{Y}\boldsymbol{\alpha} v := Y α . Since Y T Y = I \mathbf{Y}^{\mathsf{T}}\mathbf{Y}=\mathbf{I} Y T Y = I , then ∥ v ∥ 2 = ∥ α ∥ 2 \|\mathbf{v}\|_{2}=\|\boldsymbol{\alpha}\|_{2} ∥ v ∥ 2 = ∥ α ∥ 2 . Using the standard quadratic-form bound
∣ v T A v ∣ ≤ ∥ A ∥ 2 ∥ v ∥ 2 2 (131) \left|\mathbf{v}^{\mathsf{T}}\mathbf{A}\mathbf{v}\right|\leq\|\mathbf{A}\|_{2}\|\mathbf{v}\|_{2}^{2} \tag*{(131)} v T Av ≤ ∥ A ∥ 2 ∥ v ∥ 2 2 (131)
for symmetric A \mathbf{A} A , we obtain
∣ J K Q ( α ) − J K ~ r Q , ( N s ) ( α ) ∣ ≤ 1 2 ∥ α ∥ 2 2 ∥ K Q − K ~ r Q , ( N s ) ∥ 2 = 1 2 ∥ α ∥ 2 2 E r ( N s ) , (132) \left|J_{\mathbf{K}^{Q}}(\boldsymbol{\alpha})-J_{\widetilde{\mathbf{K}}_{r}^{Q,(N_s)}}(\boldsymbol{\alpha})\right|\leq\frac{1}{2}\|\boldsymbol{\alpha}\|_{2}^{2}\left\|\mathbf{K}^{Q}-\widetilde{\mathbf{K}}_{r}^{Q,(N_s)}\right\|_{2}=\frac{1}{2}\|\boldsymbol{\alpha}\|_{2}^{2}\mathcal{E}_{r}^{(N_s)}, \tag*{(132)} J K Q ( α ) − J K r Q , ( N s ) ( α ) ≤ 2 1 ∥ α ∥ 2 2 K Q − K r Q , ( N s ) 2 = 2 1 ∥ α ∥ 2 2 E r ( N s ) , (132)
which proves (128) . Moreover, the box constraints imply
∥ α ∥ 2 2 = ∑ i = 1 n α i 2 ≤ n C 2 . (133) \|\boldsymbol{\alpha}\|_{2}^{2}=\sum_{i=1}^{n}\alpha_i^{2}\leq nC^{2}. \tag*{(133)} ∥ α ∥ 2 2 = i = 1 ∑ n α i 2 ≤ n C 2 . (133)
Taking the supremum over A \mathcal{A} A therefore yields (129) .
Lemma 4 is uniform over the feasible set rather than being evaluated at a particular optimizer. This distinction is important because the exact and finite-shot QSVM problems generally have different minimizers. Uniform control allows the two optimization problems to be compared without assuming that their solutions coincide.
Define the exact optimal set by
A Q , ⋆ : = arg min α ∈ A J K Q ( α ) , (134) \mathcal{A}^{Q,\star}:=\underset{\boldsymbol{\alpha}\in\mathcal{A}}{\arg\min}\ J_{\mathbf{K}^{Q}}(\boldsymbol{\alpha}), \tag*{(134)} A Q , ⋆ := α ∈ A arg min J K Q ( α ) , (134)
and let
α ~ r ( N s ) ∈ arg min α ∈ A J K ~ r Q , ( N s ) ( α ) (135) \widetilde{\boldsymbol{\alpha}}_{r}^{(N_s)}\in\underset{\boldsymbol{\alpha}\in\mathcal{A}}{\arg\min}\ J_{\widetilde{\mathbf{K}}_{r}^{Q,(N_s)}}(\boldsymbol{\alpha}) \tag*{(135)} α r ( N s ) ∈ α ∈ A arg min J K r Q , ( N s ) ( α ) (135)
be any optimizer of the finite-shot low-rank QSVM.
Theorem 7 (Exact-objective suboptimality). For every α ⋆ ∈ A Q , ⋆ \boldsymbol{\alpha}^{\star}\in\mathcal{A}^{Q,\star} α ⋆ ∈ A Q , ⋆ ,
0 ≤ J K Q ( α ~ r ( N s ) ) − J K Q ( α ⋆ ) ≤ n C 2 E r ( N s ) . (136) 0\leq J_{\mathbf{K}^{Q}}\left(\widetilde{\boldsymbol{\alpha}}_{r}^{(N_s)}\right)-J_{\mathbf{K}^{Q}}\left(\boldsymbol{\alpha}^{\star}\right)\leq nC^{2}\mathcal{E}_{r}^{(N_s)}. \tag*{(136)} 0 ≤ J K Q ( α r ( N s ) ) − J K Q ( α ⋆ ) ≤ n C 2 E r ( N s ) . (136) :::`
Proof. The lower bound follows immediately from the optimality of α ⋆ \alpha^\star α ⋆ for the exact objective. For the upper bound, insert the approximate objective:
J K Q ( α ~ r ( N s ) ) − J K Q ( α ⋆ ) = [ J K Q ( α ~ r ( N s ) ) − J ~ K ~ r Q , ( N s ) ( α ~ r ( N s ) ) ] + [ J ~ K ~ r Q , ( N s ) ( α ~ r ( N s ) ) − J ~ K ~ r Q , ( N s ) ( α ⋆ ) ] + [ J ~ K ~ r Q , ( N s ) ( α ⋆ ) − J K Q ( α ⋆ ) ] . (137) J_{K_Q}(\widetilde{\alpha}_{r}^{(N_s)})-J_{K_Q}(\alpha^\star)
=
\left[J_{K_Q}(\widetilde{\alpha}_{r}^{(N_s)})-\widetilde{J}_{\widetilde{K}_{r}^{Q,(N_s)}}(\widetilde{\alpha}_{r}^{(N_s)})\right]
+
\left[\widetilde{J}_{\widetilde{K}_{r}^{Q,(N_s)}}(\widetilde{\alpha}_{r}^{(N_s)})-\widetilde{J}_{\widetilde{K}_{r}^{Q,(N_s)}}(\alpha^\star)\right]
+
\left[\widetilde{J}_{\widetilde{K}_{r}^{Q,(N_s)}}(\alpha^\star)-J_{K_Q}(\alpha^\star)\right]. \tag*{(137)} J K Q ( α r ( N s ) ) − J K Q ( α ⋆ ) = [ J K Q ( α r ( N s ) ) − J K r Q , ( N s ) ( α r ( N s ) ) ] + [ J K r Q , ( N s ) ( α r ( N s ) ) − J K r Q , ( N s ) ( α ⋆ ) ] + [ J K r Q , ( N s ) ( α ⋆ ) − J K Q ( α ⋆ ) ] . (137)
The middle term is nonpositive by the optimality of α ~ r ( N s ) \widetilde{\alpha}_{r}^{(N_s)} α r ( N s ) for the approximate problem. Lemma 4 bounds the magnitude of each of the remaining terms by n C 2 2 E r ( N s ) \frac{nC^2}{2}\mathcal{E}_{r}^{(N_s)} 2 n C 2 E r ( N s ) . Therefore,
J K Q ( α ~ r ( N s ) ) − J K Q ( α ⋆ ) ≤ n C 2 E r ( N s ) , (138) J_{K_Q}(\widetilde{\alpha}_{r}^{(N_s)})-J_{K_Q}(\alpha^\star)\le nC^2\mathcal{E}_{r}^{(N_s)}, \tag*{(138)} J K Q ( α r ( N s ) ) − J K Q ( α ⋆ ) ≤ n C 2 E r ( N s ) , (138)
which proves (136) .
Theorem 7 shows that optimization with the finite-shot low-rank kernel produces a solution that remains approximately optimal for the exact QSVM objective whenever the kernel-surrogate error is small. This is an objective-value guarantee; controlling the optimizer itself requires an additional regularity condition.
Assumption 3 (Quadratic growth). There exists μ > 0 \mu>0 μ > 0 such that, for every α ∈ A \alpha\in\mathcal{A} α ∈ A ,
J K Q ( α ) − J K Q ⋆ ≥ μ 2 dist ( α , A Q , ⋆ ) 2 , (139) J_{K_Q}(\alpha)-J_{K_Q}^\star\ge\frac{\mu}{2}\operatorname{dist}(\alpha,\mathcal{A}^{Q,\star})^2, \tag*{(139)} J K Q ( α ) − J K Q ⋆ ≥ 2 μ dist ( α , A Q , ⋆ ) 2 , (139) where J K Q ⋆ : = min α ∈ A J K Q ( α ) J_{K_Q}^\star:=\min_{\alpha\in\mathcal{A}}J_{K_Q}(\alpha) J K Q ⋆ := min α ∈ A J K Q ( α ) .
Theorem 8 (Distance to the exact optimal set). Under Assumption 3,
dist ( α ~ r ( N s ) , A Q , ⋆ ) ≤ 2 n C 2 μ E r ( N s ) . (140) \operatorname{dist}(\widetilde{\alpha}_{r}^{(N_s)},\mathcal{A}^{Q,\star})\le\sqrt{\frac{2nC^2}{\mu}\mathcal{E}_{r}^{(N_s)}}. \tag*{(140)} dist ( α r ( N s ) , A Q , ⋆ ) ≤ μ 2 n C 2 E r ( N s ) . (140)
Proof. Since every α ⋆ ∈ A Q , ⋆ \alpha^\star\in\mathcal{A}^{Q,\star} α ⋆ ∈ A Q , ⋆ attains J K Q ⋆ J_{K_Q}^\star J K Q ⋆ , Theorem 7 yields
J K Q ( α ~ r ( N s ) ) − J K Q ⋆ ≤ n C 2 E r ( N s ) . (141) J_{K_Q}(\widetilde{\alpha}_{r}^{(N_s)})-J_{K_Q}^\star\le nC^2\mathcal{E}_{r}^{(N_s)}. \tag*{(141)} J K Q ( α r ( N s ) ) − J K Q ⋆ ≤ n C 2 E r ( N s ) . (141)
On the other hand, applying Assumption 3 at α ~ r ( N s ) \widetilde{\alpha}_{r}^{(N_s)} α r ( N s ) yields
μ 2 dist ( α ~ r ( N s ) , A Q , ⋆ ) 2 ≤ J K Q ( α ~ r ( N s ) ) − J K Q ⋆ . (142) \frac{\mu}{2}\operatorname{dist}(\widetilde{\alpha}_{r}^{(N_s)},\mathcal{A}^{Q,\star})^2\le J_{K_Q}(\widetilde{\alpha}_{r}^{(N_s)})-J_{K_Q}^\star. \tag*{(142)} 2 μ dist ( α r ( N s ) , A Q , ⋆ ) 2 ≤ J K Q ( α r ( N s ) ) − J K Q ⋆ . (142)
Combining the two inequalities, we obtain
μ 2 dist ( α ~ r ( N s ) , A Q , ⋆ ) 2 ≤ n C 2 E r ( N s ) . (143) \frac{\mu}{2}\operatorname{dist}(\widetilde{\alpha}_{r}^{(N_s)},\mathcal{A}^{Q,\star})^2\le nC^2\mathcal{E}_{r}^{(N_s)}. \tag*{(143)} 2 μ dist ( α r ( N s ) , A Q , ⋆ ) 2 ≤ n C 2 E r ( N s ) . (143)
Taking square roots completes the proof.
The exact QSVM dual optimizer need not be unique. Theorem 8 therefore controls the distance from the finite-shot optimizer to the complete exact optimal set A Q , ⋆ \mathcal{A}^{Q,\star} A Q , ⋆ , rather than to an arbitrarily selected exact optimizer. This formulation avoids an unnecessary uniqueness assumption. Combining the preceding results yields the training-side perturbation chain
E r ( N s ) ⟶ QSVM objective stability ⟶ optimizer-set stability . (144) \mathcal{E}_{r}^{(N_s)}\longrightarrow\text{QSVM objective stability}\longrightarrow\text{optimizer-set stability}. \tag*{(144)} E r ( N s ) ⟶ QSVM objective stability ⟶ optimizer-set stability . (144)
Particularly, if E r ( N s ) → 0 \mathcal{E}_{r}^{(N_s)}\to0 E r ( N s ) → 0 then J K Q ( α ~ r ( N s ) ) − J K Q ⋆ → 0 J_{K_Q}(\widetilde{\alpha}_{r}^{(N_s)})-J_{K_Q}^\star\to0 J K Q ( α r ( N s ) ) − J K Q ⋆ → 0 , under quadratic growth dist ( α ~ r ( N s ) , A Q , ⋆ ) → 0 \operatorname{dist}(\widetilde{\alpha}_{r}^{(N_s)},\mathcal{A}^{Q,\star})\to0 dist ( α r ( N s ) , A Q , ⋆ ) → 0 . Prediction requires one additional ingredient, however: control of the kernel similarities between the training samples and a previously unseen test point. We address this out-of-sample extension next.
Out-of-Sample and Prediction Stability
The preceding analysis controls the error of the finite-shot ICAQKL surrogate on the training Gram matrix and establishes stability of the corresponding QSVM optimizer. Prediction on a previously unseen point requires an additional step. In particular, the learned low-rank representation must be extended from the training samples to a new test point using fresh quantum-kernel evaluations. We therefore distinguish two sources of out-of-sample error: the structural error of the exact rank-r r r Cholesky extension along the selected training path and the additional finite-shot error introduced by noisy training factors and fresh test-time measurements. Throughout this subsection, let z ∈ X \mathbf{z} \in\mathcal{X} z ∈ X be a fixed test point and define the exact train–test quantum-kernel vector
k z Q : = ( κ Q ( x 1 , z ) , … , κ Q ( x n , z ) ) T . (145) \mathbf{k}^{Q}_{z} := \left(\kappa^{Q}(\mathbf{x}_{1},\mathbf{z}),\ldots,\kappa^{Q}(\mathbf{x}_{n},\mathbf{z})\right)^{\mathsf{T}}. \tag*{(145)} k z Q := ( κ Q ( x 1 , z ) , … , κ Q ( x n , z ) ) T . (145)
Let P ^ r = ( p ^ 1 , … , p ^ r ) \widehat{P}_{r}=(\widehat{p}_{1},\ldots,\widehat{p}_{r}) P r = ( p 1 , … , p r ) denote the pivot path selected during finite-shot ICAQKL training.
Exact out-of-sample Cholesky extension. Consider first an exact-entry extension that follows the same selected training path P ^ r \widehat{P}_{r} P r . Let g r ( z ) = ( g 1 ( z ) , … , g r ( z ) ) T \mathbf{g}_{r}(\mathbf{z})=(g_{1}(\mathbf{z}),\ldots,g_{r}(\mathbf{z}))^{\mathsf{T}} g r ( z ) = ( g 1 ( z ) , … , g r ( z ) ) T denote the resulting exact Cholesky feature for z \mathbf{z} z . Its components are generated recursively according to
g ℓ ( z ) = κ Q ( x p ^ ℓ , z ) − ∑ m = 1 ℓ − 1 g m ( z ) G p ^ ℓ m P ^ r G p ^ ℓ p ^ ℓ P ^ r , ℓ = 1 , … , r . (146) g_{\ell}(\mathbf{z})=
\frac{\kappa^{Q}(\mathbf{x}_{\widehat{p}_{\ell}},\mathbf{z})-\sum_{m=1}^{\ell-1}g_{m}(\mathbf{z})G^{\widehat{P}_{r}}_{\widehat{p}_{\ell}m}}{G^{\widehat{P}_{r}}_{\widehat{p}_{\ell}\widehat{p}_{\ell}}},
\qquad\ell=1,\ldots,r. \tag*{(146)} g ℓ ( z ) = G p ℓ p ℓ P r κ Q ( x p ℓ , z ) − ∑ m = 1 ℓ − 1 g m ( z ) G p ℓ m P r , ℓ = 1 , … , r . (146)
The corresponding exact-entry rank-r r r train–test approximation is
k ~ r , z Q , P ^ r : = G r P ^ r g r ( z ) . (147) \widetilde{\mathbf{k}}^{Q,\widehat{P}_{r}}_{r,z}:=G^{\widehat{P}_{r}}_{r}\mathbf{g}_{r}(\mathbf{z}). \tag*{(147)} k r , z Q , P r := G r P r g r ( z ) . (147)
The following result relates the accuracy of this extension directly to the training residual.
Lemma 5 (Exact out-of-sample residual bound). Suppose κ Q ( z , z ) ≤ κ \kappa^{Q}(\mathbf{z},\mathbf{z})\leq\kappa κ Q ( z , z ) ≤ κ . Then
∥ k z Q − k ~ r , z Q , P ^ r ∥ 2 2 ≤ κ tr ( R r P ^ r ) ≤ n κ ∥ R r P ^ r ∥ 2 . (148) \left\|\mathbf{k}^{Q}_{z}-\widetilde{\mathbf{k}}^{Q,\widehat{P}_{r}}_{r,z}\right\|_{2}^{2}
\leq\kappa\operatorname{tr}\left(R^{\widehat{P}_{r}}_{r}\right)
\leq n\kappa\left\|R^{\widehat{P}_{r}}_{r}\right\|_{2}. \tag*{(148)} k z Q − k r , z Q , P r 2 2 ≤ κ tr ( R r P r ) ≤ nκ R r P r 2 . (148) Moreover,
∥ k z Q − k ~ r , z Q , P ^ r ∥ 2 ≤ n κ max i d ^ i , r P r . (149) \left\|\mathbf{k}^{Q}_{z}-\widetilde{\mathbf{k}}^{Q,\widehat{P}_{r}}_{r,z}\right\|_{2}
\leq\sqrt{n\kappa\max_{i}\widehat{d}^{P_{r}}_{i,r}}. \tag*{(149)} k z Q − k r , z Q , P r 2 ≤ nκ i max d i , r P r . (149) Proof. Consider the augmented Gram matrix containing the n n n training samples and the test point z \mathbf{z} z :
K a u g Q ( z ) = [ K Q k z Q ( k z Q ) T κ Q ( z , z ) ] . (150) \mathbf{K}^{Q}_{\mathrm{aug}}(\mathbf{z})=
\begin{bmatrix}
\mathbf{K}^{Q} & \mathbf{k}^{Q}_{z}\\
(\mathbf{k}^{Q}_{z})^{\mathsf{T}} & \kappa^{Q}(\mathbf{z},\mathbf{z})
\end{bmatrix}. \tag*{(150)} K aug Q ( z ) = [ K Q ( k z Q ) T k z Q κ Q ( z , z ) ] . (150) Since κ Q \kappa^{Q} κ Q is a positive-semidefinite kernel, K a u g Q ( z ) ⪰ 0 \mathbf{K}^{Q}_{\mathrm{aug}}(\mathbf{z})\succeq0 K aug Q ( z ) ⪰ 0 . Apply the same r r r exact Cholesky pivots P ^ r \widehat{P}_{r} P r , restricted to the training indices. The corresponding augmented residual takes the form
\begin{bmatrix}
R^{\widehat{P}_{r}}_{r} & \mathbf{e}_{r,z}\\
\mathbf{e}_{r,z}^{\mathsf{T}} & \rho_{r,z}
\end{bmatrix}\succeq0, \tag*{(151)}\end{bmatrix}
where e r , z : = k z Q − k ~ r , z Q , P ^ r \mathbf{e}_{r,z}:=\mathbf{k}^{Q}_{z}-\widetilde{\mathbf{k}}^{Q,\widehat{P}_{r}}_{r,z} e r , z := k z Q − k r , z Q , P r . For every training index i i i , positive semidefiniteness of the corresponding 2 × 2 2\times2 2 × 2 principal minor implies ∣ e r , z , i ∣ 2 ≤ ( R r P ^ r ) i i ρ r , z \lvert e_{r,z,i}\rvert^{2}\leq\left(R^{\widehat{P}_{r}}_{r}\right)_{ii}\rho_{r,z} ∣ e r , z , i ∣ 2 ≤ ( R r P r ) ii ρ r , z . The test-point residual diagonal satisfies
0 ≤ ρ r , z ≤ κ Q ( z , z ) ≤ κ . (152) 0\leq\rho_{r,z}\leq\kappa^{Q}(\mathbf{z},\mathbf{z})\leq\kappa. \tag*{(152)} 0 ≤ ρ r , z ≤ κ Q ( z , z ) ≤ κ . (152) Therefore, we obtain
∥ e r , z ∥ 2 2 = ∑ i = 1 n ∣ e r , z , i ∣ 2 ≤ κ ∑ i = 1 n ( R r P ^ r ) i i = κ tr ( R r P ^ r ) . (153) \left\|\mathbf{e}_{r,z}\right\|_{2}^{2}
=\sum_{i=1}^{n}\lvert e_{r,z,i}\rvert^{2}
\leq\kappa\sum_{i=1}^{n}\left(R^{\widehat{P}_{r}}_{r}\right)_{ii}
=\kappa\operatorname{tr}\left(R^{\widehat{P}_{r}}_{r}\right). \tag*{(153)} ∥ e r , z ∥ 2 2 = i = 1 ∑ n ∣ e r , z , i ∣ 2 ≤ κ i = 1 ∑ n ( R r P r ) ii = κ tr ( R r P r ) . (153)
Since the exact residual is PSD,
tr ( R r P ^ r ) ≤ n ∥ R r P ^ r ∥ 2 , (154) \operatorname{tr}\left(\mathbf{R}_{r}^{\widehat{P}_{r}}\right) \le n\left\|\mathbf{R}_{r}^{\widehat{P}_{r}}\right\|_{2}, \tag*{(154)} tr ( R r P r ) ≤ n R r P r 2 , (154)
which proves (148) . Similarly,
tr ( R r P ^ r ) = ∑ i = 1 n d ^ i , r P ^ r ≤ n max i d ^ i , r P ^ r . (155) \operatorname{tr}\left(\mathbf{R}_{r}^{\widehat{P}_{r}}\right) = \sum_{i=1}^{n}\widehat{d}_{i,r}^{\widehat{P}_{r}} \le n\max_i \widehat{d}_{i,r}^{\widehat{P}_{r}}. \tag*{(155)} tr ( R r P r ) = i = 1 ∑ n d i , r P r ≤ n i max d i , r P r . (155)
Substitution and taking square roots yield (149) .
Lemma 5 provides a direct link between the training Cholesky residual and the accuracy of the exact out-of-sample extension. In particular, if the training recursion terminates when max i s ^ i , r ≤ ϵ \max_i \widehat{s}_{i,r} \le\epsilon max i s i , r ≤ ϵ and the score discrepancy satisfies ∥ s ^ r − d ^ r P ^ r ∥ ∞ ≤ ζ r \left\|\widehat{\mathbf{s}}_r-\widehat{\mathbf{d}}_r^{\widehat{P}_r}\right\|_\infty\le\zeta_r s r − d r P r ∞ ≤ ζ r then max i d ^ i , r P ^ r ≤ ϵ + ζ r \max_i \widehat{d}_{i,r}^{\widehat{P}_r} \le\epsilon+\zeta_r max i d i , r P r ≤ ϵ + ζ r . Hence,
∥ k z Q − k r , z Q , P ^ r ∥ 2 ≤ n κ ( ϵ + ζ r ) . (156) \left\|\mathbf{k}_{z}^{Q}-\mathbf{k}_{r,z}^{Q,\widehat{P}_r}\right\|_2 \le\sqrt{n\kappa(\epsilon+\zeta_r)}. \tag*{(156)} k z Q − k r , z Q , P r 2 ≤ nκ ( ϵ + ζ r ) . (156)
Thus, the same residual scores used to terminate the training factorization also provide a sufficient criterion for controlling the exact-entry out-of-sample approximation error.
Finite-shot pivot–test measurements. Training and prediction incur different quantum-query costs. Constructing the rank-r r r training factor requires at most
M r = n r − r ( r + 1 ) 2 = O ( n r ) (157) M_r=nr-\frac{r(r+1)}{2}=O(nr) \tag*{(157)} M r = n r − 2 r ( r + 1 ) = O ( n r ) (157)
fresh off-diagonal training-kernel evaluations under symmetry, caching, and analytic fidelity diagonals. Once the factor has been constructed, however, evaluating a single test point requires only the r r r pivot–test similarities κ ^ N s Q ( x p ^ ℓ , z ) \widehat{\kappa}_{N_s}^{Q}(\mathbf{x}_{\widehat{p}_\ell},\mathbf{z}) κ N s Q ( x p ℓ , z ) , ℓ = 1 , … , r \ell=1,\ldots,r ℓ = 1 , … , r . Conditioned on the completed training phase, these are fresh quantum measurements. Define η z : = log ( 2 r / δ z ) 2 N s \eta_z:=\sqrt{\frac{\log(2r/\delta_z)}{2N_s}} η z := 2 N s l o g ( 2 r / δ z ) . Applying Hoeffding’s inequality and a union bound over the r r r pivot–test queries gives, with conditional probability at least 1 − δ z 1-\delta_z 1 − δ z ,
( ∑ ℓ = 1 r ∣ κ ^ N s Q ( x p ^ ℓ , z ) − κ Q ( x p ^ ℓ , z ) ∣ 2 ) 1 / 2 ≤ r η z = r log ( 2 r / δ z ) 2 N s . (158) \left(\sum_{\ell=1}^{r}\left|\widehat{\kappa}_{N_s}^{Q}(\mathbf{x}_{\widehat{p}_\ell},\mathbf{z})-\kappa^{Q}(\mathbf{x}_{\widehat{p}_\ell},\mathbf{z})\right|^2\right)^{1/2}
\le\sqrt{r}\eta_z=\sqrt{\frac{r\log(2r/\delta_z)}{2N_s}}. \tag*{(158)} ( ℓ = 1 ∑ r κ N s Q ( x p ℓ , z ) − κ Q ( x p ℓ , z ) 2 ) 1/2 ≤ r η z = 2 N s r log ( 2 r / δ z ) . (158)
The appearance of r r r , rather than M r M_r M r , reflects the different roles of training and prediction: M r M_r M r counts the distinct quantum-kernel evaluations needed to construct the training factor, whereas only r r r fresh pivot–test evaluations are required for each new test point.
Finite-shot out-of-sample perturbation. Finite-shot out-of-sample feature is computed recursively
g ~ ℓ ( N s ) ( z ) = κ ^ N s Q ( x p ^ ℓ , z ) − ∑ m = 1 ℓ − 1 g ~ m ( N s ) ( z ) G ^ p ^ ℓ p ^ m ( N s ) G ^ p ^ ℓ p ^ ℓ ( N s ) , ℓ = 1 , … , r . (159) \widetilde{g}_{\ell}^{(N_s)}(\mathbf{z})=
\frac{\widehat{\kappa}_{N_s}^{Q}(\mathbf{x}_{\widehat{p}_\ell},\mathbf{z})-\sum_{m=1}^{\ell-1}\widetilde{g}_{m}^{(N_s)}(\mathbf{z})\widehat{G}_{\widehat{p}_\ell\widehat{p}_m}^{(N_s)}}{\widehat{G}_{\widehat{p}_\ell\widehat{p}_\ell}^{(N_s)}},
\qquad\ell=1,\ldots,r. \tag*{(159)} g ℓ ( N s ) ( z ) = G p ℓ p ℓ ( N s ) κ N s Q ( x p ℓ , z ) − ∑ m = 1 ℓ − 1 g m ( N s ) ( z ) G p ℓ p m ( N s ) , ℓ = 1 , … , r . (159)
Let g ^ r ( z ) : = g ~ ( N s ) ( z ) \widehat{\mathbf{g}}_r(\mathbf{z}):=\widetilde{\mathbf{g}}^{(N_s)}(\mathbf{z}) g r ( z ) := g ( N s ) ( z ) and define the finite-shot approximate train–test vector by k ~ r , z Q , ( N s ) : = G ^ r ( N s ) g ^ r ( z ) \widetilde{\mathbf{k}}_{r,z}^{Q,(N_s)}:=\widehat{\mathbf{G}}_{r}^{(N_s)}\widehat{\mathbf{g}}_r(\mathbf{z}) k r , z Q , ( N s ) := G r ( N s ) g r ( z ) . Let S P ^ r \mathbf{S}_{\widehat{P}_r} S P r denote the row-selection operator extracting the selected pivots in their order of selection, and define T r : = S P ^ r G r P ^ r \mathbf{T}_r:=\mathbf{S}_{\widehat{P}_r}\mathbf{G}_{r}^{\widehat{P}_r} T r := S P r G r P r , and T ^ r : = S P ^ r G ^ r ( N s ) \widehat{\mathbf{T}}_r:=\mathbf{S}_{\widehat{P}_r}\widehat{\mathbf{G}}_{r}^{(N_s)} T r := S P r G r ( N s ) . Along a successful Cholesky path, T r \mathbf{T}_r T r is lower triangular with positive diagonal entries. Define ν r : = σ min ( T r ) \nu_r:=\sigma_{\min}(\mathbf{T}_r) ν r := σ m i n ( T r ) and recall β r : = ∥ G r P ^ r ∥ 2 \beta_r:=\left\|\mathbf{G}_{r}^{\widehat{P}_r}\right\|_2 β r := G r P r 2 .
Theorem 9 (Finite-shot out-of-sample perturbation). Suppose ν r > 0 \nu_r>0 ν r > 0 , Δ r < ν r \Delta_r<\nu_r Δ r < ν r . Conditioned on the completed training phase, on the event (158) ,
∥ k ~ r , z Q , P ^ r − k ~ r , z Q , ( N s ) ∥ 2 ≤ κ Δ r + ( β r + Δ r ) r η z + κ Δ r ν r − Δ r . (160) \left\|\widetilde{\mathbf{k}}_{r,z}^{Q,\widehat{P}_r}-\widetilde{\mathbf{k}}_{r,z}^{Q,(N_s)}\right\|_2
\le\sqrt{\kappa}\Delta_r+(\beta_r+\Delta_r)\frac{\sqrt{r}\eta_z+\sqrt{\kappa}\Delta_r}{\nu_r-\Delta_r}. \tag*{(160)} k r , z Q , P r − k r , z Q , ( N s ) 2 ≤ κ Δ r + ( β r + Δ r ) ν r − Δ r r η z + κ Δ r . (160) Consequently,
∥ k z Q − k ~ r , z Q , ( N s ) ∥ 2 ≤ κ tr ( R r P ^ r ) + κ Δ r + ( β r + Δ r ) r η z + κ Δ r ν r − Δ r . (161) \left\|\mathbf{k}_{z}^{Q}-\widetilde{\mathbf{k}}_{r,z}^{Q,(N_s)}\right\|_2
\le\sqrt{\kappa\operatorname{tr}\left(\mathbf{R}_{r}^{\widehat{P}_r}\right)}
+\sqrt{\kappa}\Delta_r
+(\beta_r+\Delta_r)\frac{\sqrt{r}\eta_z+\sqrt{\kappa}\Delta_r}{\nu_r-\Delta_r}. \tag*{(161)} k z Q − k r , z Q , ( N s ) 2 ≤ κ tr ( R r P r ) + κ Δ r + ( β r + Δ r ) ν r − Δ r r η z + κ Δ r . (161)
Proof. Define the exact and finite-shot vectors of pivot–test kernel values by
v r ( z ) : = ( κ Q ( x p 1 , z ) , … , κ Q ( x p r , z ) ) T , (162) \mathbf{v}_r(z) := \left(\kappa^Q(x_{p_1},z),\ldots,\kappa^Q(x_{p_r},z)\right)^{\mathsf T}, \tag*{(162)} v r ( z ) := ( κ Q ( x p 1 , z ) , … , κ Q ( x p r , z ) ) T , (162)
v ^ r ( z ) : = ( κ ^ N s Q ( x p ^ 1 , z ) , … , κ ^ N s Q ( x p ^ r , z ) ) T . (163) \widehat{\mathbf{v}}_r(z) := \left(\widehat{\kappa}_{N_s}^Q(x_{\widehat{p}_1},z),\ldots,\widehat{\kappa}_{N_s}^Q(x_{\widehat{p}_r},z)\right)^{\mathsf T}. \tag*{(163)} v r ( z ) := ( κ N s Q ( x p 1 , z ) , … , κ N s Q ( x p r , z ) ) T . (163)
The exact and finite-shot recursive extensions can be written as lower-triangular systems:
T r g r ( z ) = v r ( z ) , (164) \mathbf{T}_r\mathbf{g}_r(z)=\mathbf{v}_r(z), \tag*{(164)} T r g r ( z ) = v r ( z ) , (164)
T ^ r g ^ r ( z ) = v ^ r ( z ) . (165) \widehat{\mathbf{T}}_r\widehat{\mathbf{g}}_r(z)=\widehat{\mathbf{v}}_r(z). \tag*{(165)} T r g r ( z ) = v r ( z ) . (165)
Since row selection is a contraction,
∥ T ^ r − T r ∥ 2 ≤ Δ r . (166) \left\|\widehat{\mathbf{T}}_r-\mathbf{T}_r\right\|_2\leq\Delta_r. \tag*{(166)} T r − T r 2 ≤ Δ r . (166)
Weyl’s singular-value perturbation inequality therefore gives σ min ( T ^ r ) ≥ ν r − Δ r > 0 \sigma_{\min}(\widehat{\mathbf{T}}_r)\geq\nu_r-\Delta_r>0 σ m i n ( T r ) ≥ ν r − Δ r > 0 . Hence,
∥ T ^ r − 1 ∥ 2 ≤ 1 ν r − Δ r . (167) \left\|\widehat{\mathbf{T}}_r^{-1}\right\|_2\leq\frac{1}{\nu_r-\Delta_r}. \tag*{(167)} T r − 1 2 ≤ ν r − Δ r 1 . (167)
From (158) , we have
∥ v ^ r ( z ) − v r ( z ) ∥ 2 ≤ r η z . (168) \left\|\widehat{\mathbf{v}}_r(z)-\mathbf{v}_r(z)\right\|_2\leq\sqrt{r}\eta_z. \tag*{(168)} ∥ v r ( z ) − v r ( z ) ∥ 2 ≤ r η z . (168)
Moreover, the exact augmented Cholesky residual implies ρ r , z = κ Q ( z , z ) − ∥ g r ( z ) ∥ 2 2 ≥ 0 \rho_{r,z}=\kappa^Q(z,z)-\|\mathbf{g}_r(z)\|_2^2\geq0 ρ r , z = κ Q ( z , z ) − ∥ g r ( z ) ∥ 2 2 ≥ 0 , it follows that ∥ g r ( z ) ∥ 2 2 ≤ κ Q ( z , z ) ≤ κ \|\mathbf{g}_r(z)\|_2^2\leq\kappa^Q(z,z)\leq\kappa ∥ g r ( z ) ∥ 2 2 ≤ κ Q ( z , z ) ≤ κ so
∥ g r ( z ) ∥ 2 ≤ κ . (169) \left\|\mathbf{g}_r(z)\right\|_2\leq\sqrt{\kappa}. \tag*{(169)} ∥ g r ( z ) ∥ 2 ≤ κ . (169)
Subtracting (164) from (165) yields
g ^ r ( z ) − g r ( z ) = T ^ r − 1 [ v ^ r ( z ) − v r ( z ) − ( T ^ r − T r ) g r ( z ) ] . (170) \widehat{\mathbf{g}}_r(z)-\mathbf{g}_r(z)=\widehat{\mathbf{T}}_r^{-1}\left[\widehat{\mathbf{v}}_r(z)-\mathbf{v}_r(z)-\left(\widehat{\mathbf{T}}_r-\mathbf{T}_r\right)\mathbf{g}_r(z)\right]. \tag*{(170)} g r ( z ) − g r ( z ) = T r − 1 [ v r ( z ) − v r ( z ) − ( T r − T r ) g r ( z ) ] . (170)
By using (167) , (168) , (166) , and (169) , we obtain
∥ g ^ r ( z ) − g r ( z ) ∥ 2 ≤ r η z + κ Δ r ν r − Δ r . (171) \left\|\widehat{\mathbf{g}}_r(z)-\mathbf{g}_r(z)\right\|_2\leq\frac{\sqrt{r}\eta_z+\sqrt{\kappa}\Delta_r}{\nu_r-\Delta_r}. \tag*{(171)} ∥ g r ( z ) − g r ( z ) ∥ 2 ≤ ν r − Δ r r η z + κ Δ r . (171)
Finally, we have
∥ G ^ r ( N s ) g ^ r ( z ) − G r P ^ r g r ( z ) ∥ 2 ≤ ∥ G ^ r ( N s ) − G r P ^ r ∥ 2 ∥ g r ( z ) ∥ 2 + ∥ G ^ r ( N s ) ∥ 2 ∥ g ^ r ( z ) − g r ( z ) ∥ 2 . (172) \left\|\widehat{\mathbf{G}}_r^{(N_s)}\widehat{\mathbf{g}}_r(z)-\mathbf{G}_r^{\widehat{P}_r}\mathbf{g}_r(z)\right\|_2\leq\left\|\widehat{\mathbf{G}}_r^{(N_s)}-\mathbf{G}_r^{\widehat{P}_r}\right\|_2\left\|\mathbf{g}_r(z)\right\|_2+\left\|\widehat{\mathbf{G}}_r^{(N_s)}\right\|_2\left\|\widehat{\mathbf{g}}_r(z)-\mathbf{g}_r(z)\right\|_2. \tag*{(172)} G r ( N s ) g r ( z ) − G r P r g r ( z ) 2 ≤ G r ( N s ) − G r P r 2 ∥ g r ( z ) ∥ 2 + G r ( N s ) 2 ∥ g r ( z ) − g r ( z ) ∥ 2 . (172)
Since
∥ G ^ r ( N s ) ∥ 2 ≤ ∥ G r P ^ r ∥ 2 + Δ r = β r + Δ r , (173) \left\|\widehat{\mathbf{G}}_r^{(N_s)}\right\|_2\leq\left\|\mathbf{G}_r^{\widehat{P}_r}\right\|_2+\Delta_r=\beta_r+\Delta_r, \tag*{(173)} G r ( N s ) 2 ≤ G r P r 2 + Δ r = β r + Δ r , (173)
substituting (169) and (171) proves (160) . The total bound (161) then follows by the triangle inequality together with Lemma 5.
The conditioning factor ν r \nu_r ν r is essential. Although positive pivot diagonals ensure that the triangular system is nonsingular, they do not by themselves provide a uniform lower bound on its smallest singular value. If ν r \nu_r ν r is small, perturbations in either the learned factor or the fresh test-time kernel estimates can be strongly amplified. We therefore retain the conditioning requirement explicitly rather than attempting to infer it from the pivot floor alone.
Bias-aware decision-function stability. The equality y ⊤ α = 0 \mathbf{y}^{\top}\boldsymbol{\alpha}=0 y ⊤ α = 0 in the QSVM dual corresponds to an unregularized intercept. Consequently, prediction stability requires explicit control of the bias term in addition to the dual variables and train–test kernel vector. Choose α ∘ ∈ A Q , ⋆ \boldsymbol{\alpha}^{\circ}\in\mathcal{A}^{Q,\star} α ∘ ∈ A Q , ⋆ such that
∥ α ~ r ( N s ) − α ∘ ∥ 2 = dist ( α ~ r ( N s ) , A Q , ⋆ ) . (174) \left\|\widetilde{\boldsymbol{\alpha}}_{r}^{(N_{\mathrm{s}})}-\boldsymbol{\alpha}^{\circ}\right\|_{2}=\operatorname{dist}\left(\widetilde{\boldsymbol{\alpha}}_{r}^{(N_{\mathrm{s}})},\mathcal{A}^{Q,\star}\right). \tag*{(174)} α r ( N s ) − α ∘ 2 = dist ( α r ( N s ) , A Q , ⋆ ) . (174)
The corresponding exact predictor is
f K Q ( z ) = ∑ i = 1 n α i ∘ y i κ Q ( x i , z ) + b ∘ , (175) f_{K_Q}(\mathbf{z})=\sum_{i=1}^{n}\alpha_i^{\circ}y_i\kappa^{Q}(\mathbf{x}_i,\mathbf{z})+b^{\circ}, \tag*{(175)} f K Q ( z ) = i = 1 ∑ n α i ∘ y i κ Q ( x i , z ) + b ∘ , (175)
whereas the finite-shot ICAQKL predictor is
f r Q , ( N s ) ( z ) = ∑ i = 1 n α ~ r , i ( N s ) y i κ ~ r Q , ( N s ) ( x i , z ) + b ~ r ( N s ) . (176) f_{r}^{Q,(N_{\mathrm{s}})}(\mathbf{z})=\sum_{i=1}^{n}\widetilde{\alpha}_{r,i}^{(N_{\mathrm{s}})}y_i\widetilde{\kappa}_{r}^{Q,(N_{\mathrm{s}})}(\mathbf{x}_i,\mathbf{z})+\widetilde{b}_{r}^{(N_{\mathrm{s}})}. \tag*{(176)} f r Q , ( N s ) ( z ) = i = 1 ∑ n α r , i ( N s ) y i κ r Q , ( N s ) ( x i , z ) + b r ( N s ) . (176)
We first record a simple norm bound for the exact train–test vector.
Lemma 6 (Exact train–test norm). Suppose κ Q ( x , x ) ≤ κ \kappa^{Q}(\mathbf{x},\mathbf{x})\le\kappa κ Q ( x , x ) ≤ κ for every x ∈ X \mathbf{x}\in\mathcal{X} x ∈ X . Then ∥ k z Q ∥ 2 ≤ κ n \left\|\mathbf{k}_{\mathbf{z}}^{Q}\right\|_{2}\le\kappa\sqrt{n} k z Q 2 ≤ κ n .
Proof. Kernel Cauchy–Schwarz yields
∣ κ Q ( x i , z ) ∣ ≤ κ Q ( x i , x i ) κ Q ( z , z ) ≤ κ . (177) \left|\kappa^{Q}(\mathbf{x}_i,\mathbf{z})\right|\le\sqrt{\kappa^{Q}(\mathbf{x}_i,\mathbf{x}_i)\kappa^{Q}(\mathbf{z},\mathbf{z})}\le\kappa. \tag*{(177)} κ Q ( x i , z ) ≤ κ Q ( x i , x i ) κ Q ( z , z ) ≤ κ . (177)
Therefore, ∥ k z Q ∥ 2 2 ≤ n κ 2 \left\|\mathbf{k}_{\mathbf{z}}^{Q}\right\|_{2}^{2}\le n\kappa^{2} k z Q 2 2 ≤ n κ 2 which proves the claim.
Theorem 10 (Decision-function stability). The exact and finite-shot predictors satisfy
∣ f K Q ( z ) − f r Q , ( N s ) ( z ) ∣ ≤ κ n dist ( α ~ r ( N s ) , A Q , ⋆ ) + C n ∥ k z Q − k ~ r , z Q , ( N s ) ∥ 2 + ∣ b ∘ − b ~ r ( N s ) ∣ . (178) \left|f_{K_Q}(\mathbf{z})-f_{r}^{Q,(N_{\mathrm{s}})}(\mathbf{z})\right|\le\kappa\sqrt{n}\operatorname{dist}\left(\widetilde{\boldsymbol{\alpha}}_{r}^{(N_{\mathrm{s}})},\mathcal{A}^{Q,\star}\right)+C\sqrt{n}\left\|\mathbf{k}_{\mathbf{z}}^{Q}-\widetilde{\mathbf{k}}_{r,\mathbf{z}}^{Q,(N_{\mathrm{s}})}\right\|_{2}+\left|b^{\circ}-\widetilde{b}_{r}^{(N_{\mathrm{s}})}\right|. \tag*{(178)} f K Q ( z ) − f r Q , ( N s ) ( z ) ≤ κ n dist ( α r ( N s ) , A Q , ⋆ ) + C n k z Q − k r , z Q , ( N s ) 2 + b ∘ − b r ( N s ) . (178)
Proof. Using vector notation, we write
f K Q ( z ) = ( α ∘ ) ⊤ Y k z Q + b ∘ , (179) f_{K_Q}(\mathbf{z})=(\boldsymbol{\alpha}^{\circ})^{\top}\mathbf{Y}\mathbf{k}_{\mathbf{z}}^{Q}+b^{\circ}, \tag*{(179)} f K Q ( z ) = ( α ∘ ) ⊤ Y k z Q + b ∘ , (179)
f r Q , ( N s ) ( z ) = ( α ~ r ( N s ) ) ⊤ Y k ~ r , z Q , ( N s ) + b ~ r ( N s ) . (180) f_{r}^{Q,(N_{\mathrm{s}})}(\mathbf{z})=\left(\widetilde{\boldsymbol{\alpha}}_{r}^{(N_{\mathrm{s}})}\right)^{\top}\mathbf{Y}\widetilde{\mathbf{k}}_{r,\mathbf{z}}^{Q,(N_{\mathrm{s}})}+\widetilde{b}_{r}^{(N_{\mathrm{s}})}. \tag*{(180)} f r Q , ( N s ) ( z ) = ( α r ( N s ) ) ⊤ Y k r , z Q , ( N s ) + b r ( N s ) . (180)
Adding and subtracting ( α ~ r ( N s ) ) ⊤ Y k z Q \left(\widetilde{\boldsymbol{\alpha}}_{r}^{(N_{\mathrm{s}})}\right)^{\top}\mathbf{Y}\mathbf{k}_{\mathbf{z}}^{Q} ( α r ( N s ) ) ⊤ Y k z Q , we then obtain
f K Q ( z ) − f r Q , ( N s ) ( z ) = ( α ∘ − α ~ r ( N s ) ) ⊤ Y k z Q + ( α ~ r ( N s ) ) ⊤ Y ( k z Q − k ~ r , z Q , ( N s ) ) + b ∘ − b ~ r ( N s ) . (181) f_{K_Q}(\mathbf{z})-f_{r}^{Q,(N_{\mathrm{s}})}(\mathbf{z})=(\boldsymbol{\alpha}^{\circ}-\widetilde{\boldsymbol{\alpha}}_{r}^{(N_{\mathrm{s}})})^{\top}\mathbf{Y}\mathbf{k}_{\mathbf{z}}^{Q}+\left(\widetilde{\boldsymbol{\alpha}}_{r}^{(N_{\mathrm{s}})}\right)^{\top}\mathbf{Y}\left(\mathbf{k}_{\mathbf{z}}^{Q}-\widetilde{\mathbf{k}}_{r,\mathbf{z}}^{Q,(N_{\mathrm{s}})}\right)+b^{\circ}-\widetilde{b}_{r}^{(N_{\mathrm{s}})}. \tag*{(181)} f K Q ( z ) − f r Q , ( N s ) ( z ) = ( α ∘ − α r ( N s ) ) ⊤ Y k z Q + ( α r ( N s ) ) ⊤ Y ( k z Q − k r , z Q , ( N s ) ) + b ∘ − b r ( N s ) . (181)
Since Y ⊤ Y = I \mathbf{Y}^{\top}\mathbf{Y}=\mathbf{I} Y ⊤ Y = I , Cauchy–Schwarz yields
∣ ( α ∘ − α ~ r ( N s ) ) ⊤ Y k z Q ∣ ≤ ∥ α ∘ − α ~ r ( N s ) ∥ 2 ∥ k z Q ∥ 2 (182) \left|(\boldsymbol{\alpha}^{\circ}-\widetilde{\boldsymbol{\alpha}}_{r}^{(N_{\mathrm{s}})})^{\top}\mathbf{Y}\mathbf{k}_{\mathbf{z}}^{Q}\right|\le\left\|\boldsymbol{\alpha}^{\circ}-\widetilde{\boldsymbol{\alpha}}_{r}^{(N_{\mathrm{s}})}\right\|_{2}\left\|\mathbf{k}_{\mathbf{z}}^{Q}\right\|_{2} \tag*{(182)} ( α ∘ − α r ( N s ) ) ⊤ Y k z Q ≤ α ∘ − α r ( N s ) 2 k z Q 2 (182)
≤ κ n dist ( α ~ r ( N s ) , A Q , ⋆ ) . (183) \le\kappa\sqrt{n}\operatorname{dist}\left(\widetilde{\boldsymbol{\alpha}}_{r}^{(N_{\mathrm{s}})},\mathcal{A}^{Q,\star}\right). \tag*{(183)} ≤ κ n dist ( α r ( N s ) , A Q , ⋆ ) . (183)
Moreover, the box constraints imply ∥ α ~ r ( N s ) ∥ 2 ≤ C n \left\|\widetilde{\boldsymbol{\alpha}}_{r}^{(N_{\mathrm{s}})}\right\|_{2}\le C\sqrt{n} α r ( N s ) 2 ≤ C n . Applying Cauchy–Schwarz to the second term and then the triangle inequality completes the proof.
Theorem 10 separates prediction perturbation into three distinct channels: perturbation of the learned dual variables, approximation of the train–test kernel vector, and perturbation of the SVM intercept. The first two are controlled by the preceding kernel and optimization analysis. The remaining intercept term can also be controlled under a standard support-vector stability condition.
Corollary 2 (Bias perturbation). Suppose there exists an index j j j satisfying 0 < α j ∘ < C 0<\alpha_j^{\circ}<C 0 < α j ∘ < C and 0 < α ~ r , j ( N s ) < C 0<\widetilde{\alpha}_{r,j}^{(N_{\mathrm{s}})}<C 0 < α r , j ( N s ) < C . Then the following bound holds
∣ b ∘ − b ~ r ( N s ) ∣ ≤ κ n dist ( α ~ r ( N s ) , A Q , ⋆ ) + C n ∥ k x j Q − k ~ r , x j Q , ( N s ) ∥ 2 . (184) \left|b^{\circ}-\widetilde{b}_{r}^{(N_{\mathrm{s}})}\right|\le\kappa\sqrt{n}\operatorname{dist}\left(\widetilde{\boldsymbol{\alpha}}_{r}^{(N_{\mathrm{s}})},\mathcal{A}^{Q,\star}\right)+C\sqrt{n}\left\|\mathbf{k}_{\mathbf{x}_j}^{Q}-\widetilde{\mathbf{k}}_{r,\mathbf{x}_j}^{Q,(N_{\mathrm{s}})}\right\|_{2}. \tag*{(184)} b ∘ − b r ( N s ) ≤ κ n dist ( α r ( N s ) , A Q , ⋆ ) + C n k x j Q − k r , x j Q , ( N s ) 2 . (184)
Proof. Since j j j is a non-bound support vector for both solutions, the KKT conditions imply
b ∘ = y j − ∑ i = 1 n α i ∘ y i κ Q ( x i , x j ) , (185) b^\circ= y_j-\sum_{i=1}^{n}\alpha_i^\circ y_i\kappa^{Q}(x_i,x_j), \tag*{(185)} b ∘ = y j − i = 1 ∑ n α i ∘ y i κ Q ( x i , x j ) , (185)
b ~ r ( N s ) = y j − ∑ i = 1 n α ~ r , i ( N s ) y i κ ~ Q , ( N s ) ( x i , x j ) . (186) \widetilde{b}_{r}^{(N_s)} = y_j-\sum_{i=1}^{n}\widetilde{\alpha}_{r,i}^{(N_s)}y_i\widetilde{\kappa}^{Q,(N_s)}(x_i,x_j). \tag*{(186)} b r ( N s ) = y j − i = 1 ∑ n α r , i ( N s ) y i κ Q , ( N s ) ( x i , x j ) . (186)
Adding and subtracting ∑ i = 1 n α ~ r , i ( N s ) y i κ Q ( x i , x j ) \sum_{i=1}^{n}\widetilde{\alpha}_{r,i}^{(N_s)}y_i\kappa^{Q}(x_i,x_j) ∑ i = 1 n α r , i ( N s ) y i κ Q ( x i , x j ) and then applying the same Cauchy–Schwarz argument used in Theorem 10 yields (184) .
Margin preservation and classification stability. Exact recovery of the decision value is stronger than what is required for classification. A prediction remains unchanged whenever the perturbation is smaller than the exact classification margin.
Corollary 3 (Margin preservation). Fix z ∈ X z\in\mathcal{X} z ∈ X with label y ∈ − 1 , + 1 y\in-1,+1 y ∈ − 1 , + 1 . Suppose the exact classifier satisfies y f K Q ( z ) ≥ γ > 0 yf_{K^Q}(z)\ge\gamma>0 y f K Q ( z ) ≥ γ > 0 . If
κ n dist ( α ~ r ( N s ) , A Q ) + C n ∥ k z Q − k ~ r , z Q , ( N s ) ∥ 2 + ∣ b ∘ − b ~ r ( N s ) ∣ < γ , (187) \kappa\sqrt{n}\operatorname{dist}\left(\widetilde{\alpha}_{r}^{(N_s)},\mathcal{A}^{Q}\right)+C\sqrt{n}\left\|\mathbf{k}_{z}^{Q}-\widetilde{\mathbf{k}}_{r,z}^{Q,(N_s)}\right\|_{2}+\left|b^\circ-\widetilde{b}_{r}^{(N_s)}\right|<\gamma, \tag*{(187)} κ n dist ( α r ( N s ) , A Q ) + C n k z Q − k r , z Q , ( N s ) 2 + b ∘ − b r ( N s ) < γ , (187) then sign ( f r Q , ( N s ) ( z ) ) = sign ( f K Q ( z ) ) = y \operatorname{sign}\left(f_{r}^{Q,(N_s)}(z)\right)=\operatorname{sign}\left(f_{K^Q}(z)\right)=y sign ( f r Q , ( N s ) ( z ) ) = sign ( f K Q ( z ) ) = y .
Proof. By Theorem 10 and condition (187) imply
∣ f K Q ( z ) − f r Q , ( N s ) ( z ) ∣ < γ . (188) \left|f_{K^Q}(z)-f_{r}^{Q,(N_s)}(z)\right|<\gamma. \tag*{(188)} f K Q ( z ) − f r Q , ( N s ) ( z ) < γ . (188)
Therefore, we can obtain
y f r Q , ( N s ) ( z ) ≥ y f K Q ( z ) − ∣ f K Q ( z ) − f r Q , ( N s ) ( z ) ∣ > 0. (189) yf_{r}^{Q,(N_s)}(z)\ge yf_{K^Q}(z)-\left|f_{K^Q}(z)-f_{r}^{Q,(N_s)}(z)\right|>0. \tag*{(189)} y f r Q , ( N s ) ( z ) ≥ y f K Q ( z ) − f K Q ( z ) − f r Q , ( N s ) ( z ) > 0. (189)
Consequently, the two classifiers assign the same label.
Corollary 3 explains why sizeable kernel-reconstruction errors need not translate directly into comparable losses in classification accuracy. Exact reproduction of every kernel value is unnecessary; only perturbations sufficiently large to cross the decision boundary can change the predicted label.
Joint shot–rank convergence. We now combine the training-side and out-of-sample perturbation results into an end-to-end convergence statement. We first state the result for a fixed finite training set of size n n n . If the training sample size is also allowed to increase, the explicit n n n -dependent factors appearing in the preceding bounds must additionally be controlled. Let { ( r ℓ , N s , ℓ ) } ℓ ≥ 1 \{(r_\ell,N_{s,\ell})\}_{\ell\ge1} {( r ℓ , N s , ℓ ) } ℓ ≥ 1 denote a sequence of rank and shot-budget configurations with r ℓ ≤ ρ : = rank ( K Q ) r_\ell\le\rho:=\operatorname{rank}(\mathbf{K}^{Q}) r ℓ ≤ ρ := rank ( K Q ) .
Corollary 4 (Joint shot–rank convergence). Suppose, along this sequence,
ε r ℓ ( P ^ r ℓ ) → 0 , Δ r ℓ → 0 , r ℓ log ( 2 r ℓ / δ z , ℓ ) N s , ℓ → 0. (190) \varepsilon_{r_\ell}(\widehat{\mathcal{P}}_{r_\ell})\to0,\qquad\Delta_{r_\ell}\to0,\qquad\frac{r_\ell\log(2r_\ell/\delta_{z,\ell})}{N_{s,\ell}}\to0. \tag*{(190)} ε r ℓ ( P r ℓ ) → 0 , Δ r ℓ → 0 , N s , ℓ r ℓ log ( 2 r ℓ / δ z , ℓ ) → 0. (190) Assume furthermore that the out-of-sample pivot blocks and exact path-conditioned factors remain uniformly controlled:
inf ℓ ν r ℓ ≥ ν 0 > 0 , sup ℓ β r ℓ ≤ β 0 < ∞ . (191) \inf_{\ell}\nu_{r_\ell}\ge\nu_0>0,\qquad\sup_{\ell}\beta_{r_\ell}\le\beta_0<\infty. \tag*{(191)} ℓ inf ν r ℓ ≥ ν 0 > 0 , ℓ sup β r ℓ ≤ β 0 < ∞. (191) Assume additionally either ∣ b ∘ − b ~ r ℓ ( N s , ℓ ) ∣ → 0 \left|b^\circ-\widetilde{b}_{r_\ell}^{(N_{s,\ell})}\right|\to0 b ∘ − b r ℓ ( N s , ℓ ) → 0 or that the shared non-bound support-vector condition of Corollary 2 holds and the corresponding train–test kernel-vector error vanishes. Then, for every fixed z ∈ X z\in\mathcal{X} z ∈ X ,
f r ℓ Q , ( N s , ℓ ) ( z ) ⟶ f K Q ( z ) (192) f_{r_\ell}^{Q,(N_{s,\ell})}(z)\longrightarrow f_{K^Q}(z) \tag*{(192)} f r ℓ Q , ( N s , ℓ ) ( z ) ⟶ f K Q ( z ) (192)
on the joint training and test-time concentration events. If, in addition,
y f K Q ( z ) ≥ γ > 0 , (193) y f_{\mathsf{K}_Q}(\mathbf{z}) \ge\gamma> 0, \tag*{(193)} y f K Q ( z ) ≥ γ > 0 , (193)
then for all sufficiently large ℓ \ell ℓ , sign ( f r ℓ Q , ( N s , ℓ ) ( z ) ) = y \operatorname{sign}\left(f_{r_\ell}^{Q,(N_s,\ell)}(\mathbf{z})\right)=y sign ( f r ℓ Q , ( N s , ℓ ) ( z ) ) = y . If the training concentration event has probability at least 1 − δ ℓ 1-\delta_\ell 1 − δ ℓ and the conditional test-time event has probability at least 1 − δ z , ℓ 1-\delta_{z,\ell} 1 − δ z , ℓ , then the corresponding joint event has probability at least 1 − δ ℓ − δ z , ℓ 1-\delta_\ell-\delta_{z,\ell} 1 − δ ℓ − δ z , ℓ . In particular, if δ ℓ + δ z , ℓ → 0 \delta_\ell+\delta_{z,\ell}\to0 δ ℓ + δ z , ℓ → 0 then (192) holds in probability.
Proof. By Theorem 6, we have
E r ℓ ( N s , ℓ ) ≤ ε r ℓ ( P ^ r ℓ ) + ( 2 β r ℓ + Δ r ℓ ) Δ r ℓ . (194) \mathcal{E}_{r_\ell}^{(N_s,\ell)} \le\varepsilon_{r_\ell}\left(\widehat{P}_{r_\ell}\right)+\left(2\beta_{r_\ell}+\Delta_{r_\ell}\right)\Delta_{r_\ell}. \tag*{(194)} E r ℓ ( N s , ℓ ) ≤ ε r ℓ ( P r ℓ ) + ( 2 β r ℓ + Δ r ℓ ) Δ r ℓ . (194)
Conditions (190) therefore imply E r ℓ ( N s , ℓ ) → 0 \mathcal{E}_{r_\ell}^{(N_s,\ell)}\to0 E r ℓ ( N s , ℓ ) → 0 . Under Assumption 3, Theorem 8 then yields
dist ( α ~ r ℓ ( N s , ℓ ) , A Q , ∗ ) → 0. (195) \operatorname{dist}\left(\widetilde{\alpha}_{r_\ell}^{(N_s,\ell)},\mathcal{A}^{Q,*}\right)\to0. \tag*{(195)} dist ( α r ℓ ( N s , ℓ ) , A Q , ∗ ) → 0. (195)
For the exact out-of-sample term, Lemma 5 and ε r ℓ ( P ^ r ℓ ) = ∥ R r ℓ P ^ r ℓ ∥ 2 \varepsilon_{r_\ell}\left(\widehat{P}_{r_\ell}\right)=\left\|\mathbf{R}_{r_\ell}^{\widehat{P}_{r_\ell}}\right\|_2 ε r ℓ ( P r ℓ ) = R r ℓ P r ℓ 2 yields, because n n n is fixed,
∥ k z Q − k r ℓ , z Q , P ^ r ℓ ∥ 2 ≤ n κ ε r ℓ ( P ^ r ℓ ) → 0. (196) \left\|\mathbf{k}_{\mathbf{z}}^Q-\mathbf{k}_{r_\ell,\mathbf{z}}^{Q,\widehat{P}_{r_\ell}}\right\|_2\le\sqrt{n\kappa\varepsilon_{r_\ell}\left(\widehat{P}_{r_\ell}\right)}\to0. \tag*{(196)} k z Q − k r ℓ , z Q , P r ℓ 2 ≤ nκ ε r ℓ ( P r ℓ ) → 0. (196)
Condition (190) implies
r ℓ η z , ℓ = r ℓ log ( 2 r ℓ / δ z , ℓ ) 2 N s , ℓ → 0. (197) \sqrt{r_\ell}\eta_{z,\ell}=\sqrt{\frac{r_\ell\log\left(2r_\ell/\delta_{z,\ell}\right)}{2N_{s,\ell}}}\to0. \tag*{(197)} r ℓ η z , ℓ = 2 N s , ℓ r ℓ log ( 2 r ℓ / δ z , ℓ ) → 0. (197)
Together with Δ r ℓ → 0 \Delta_{r_\ell}\to0 Δ r ℓ → 0 , ν r ℓ ≥ ν 0 > 0 \nu_{r_\ell}\ge\nu_0>0 ν r ℓ ≥ ν 0 > 0 , β r ℓ ≤ β 0 \beta_{r_\ell}\le\beta_0 β r ℓ ≤ β 0 Theorem 9 therefore yields
∥ k ~ r ℓ , z Q , P ^ r ℓ − k ~ r ℓ , z Q , ( N s , ℓ ) ∥ 2 → 0. (198) \left\|\widetilde{\mathbf{k}}_{r_\ell,\mathbf{z}}^{Q,\widehat{P}_{r_\ell}}-\widetilde{\mathbf{k}}_{r_\ell,\mathbf{z}}^{Q,(N_s,\ell)}\right\|_2\to0. \tag*{(198)} k r ℓ , z Q , P r ℓ − k r ℓ , z Q , ( N s , ℓ ) 2 → 0. (198)
Combining this with (196) we can obtain
∥ k z Q − k ~ r ℓ , z Q , ( N s , ℓ ) ∥ 2 → 0. (199) \left\|\mathbf{k}_{\mathbf{z}}^Q-\widetilde{\mathbf{k}}_{r_\ell,\mathbf{z}}^{Q,(N_s,\ell)}\right\|_2\to0. \tag*{(199)} k z Q − k r ℓ , z Q , ( N s , ℓ ) 2 → 0. (199)
The optimizer term (195) , the kernel-vector term (199) , and the assumed intercept convergence together imply through Theorem 10 that
∣ f K Q ( z ) − f r ℓ Q , ( N s , ℓ ) ( z ) ∣ → 0. (200) \left|f_{\mathsf{K}_Q}(\mathbf{z})-f_{r_\ell}^{Q,(N_s,\ell)}(\mathbf{z})\right|\to0. \tag*{(200)} f K Q ( z ) − f r ℓ Q , ( N s , ℓ ) ( z ) → 0. (200)
This proves (192) . If the exact decision value has margin γ > 0 \gamma>0 γ > 0 , the classification statement follows from Corollary 3. Finally, the training concentration event fails with probability at most δ ℓ \delta_\ell δ ℓ , while the test-time event fails conditionally with probability at most δ z , ℓ \delta_{z,\ell} δ z , ℓ . A union bound gives a joint success probability of at least 1 − δ ℓ − δ z , ℓ 1-\delta_\ell-\delta_{z,\ell} 1 − δ ℓ − δ z , ℓ .
Relation to the training shot requirement. Under the stable-path conditions of Theorem 5, Δ r ≤ n C r , τ , B , κ η s \Delta_r\le\sqrt{n}C_{r,\tau,B,\kappa}\eta_s Δ r ≤ n C r , τ , B , κ η s . For a fixed finite training set and a fixed stable rank, therefore, N s → ∞ N_s\to\infty N s → ∞ implies η s → 0 \eta_s\to0 η s → 0 and hence Δ r → 0 \Delta_r\to0 Δ r → 0 . If the approximation rank or training-set size is also allowed to vary, it is not sufficient to control only η s \eta_s η s . The rank-dependent perturbation constant C r , τ , B , κ C_{r,\tau,B,\kappa} C r , τ , B , κ and the explicit n n n -dependent factors in the preceding bounds must remain controlled as well. A sufficient training-measurement requirement is therefore
C r , τ , B , κ n log ( 2 M r / δ ) N s → 0. (201) C_{r,\tau,B,\kappa}\sqrt{\frac{n\log\left(2M_r/\delta\right)}{N_s}}\to0. \tag*{(201)} C r , τ , B , κ N s n log ( 2 M r / δ ) → 0. (201)
For the fixed-data regime emphasized here, r ≤ ρ ≤ n r\le\rho\le n r ≤ ρ ≤ n and M r M_r M r remain finite. Consequently, increasing the shot budget removes the finite-shot contribution at every fixed executed rank.
Full-rank special case. Let ρ = rank ( K Q ) \rho=\operatorname{rank}(\mathbf{K}^{Q}) ρ = rank ( K Q ) . If an exact comparator path executes ρ \rho ρ strictly positive pivots, then Proposition 7 gives R ρ = 0 \mathbf{R}_{\rho}=0 R ρ = 0 and hence ε ρ ( P ^ ρ ) = 0 \varepsilon_{\rho}(\widehat{\mathcal{P}}_{\rho})=0 ε ρ ( P ρ ) = 0 . Lemma 5 then implies k z Q = k ~ z , P ^ ρ Q , P ^ ρ k_{z}^{Q}=\widetilde{k}_{z,\widehat{\mathcal{P}}_{\rho}}^{Q,\widehat{\mathcal{P}}_{\rho}} k z Q = k z , P ρ Q , P ρ for every fixed test point satisfying the kernel-diagonal bound. Thus, at full exact rank, the structural training and out-of-sample errors vanish completely. Under the stability and conditioning assumptions, increasing N s N_{s} N s then removes the remaining finite-shot factor and pivot–test measurement errors.
The preceding results complete the error-propagation analysis of ICAQKL. Finite-shot quantum measurements first perturb the adaptively queried training-kernel entries. These perturbations affect the residual scores and recursively constructed Cholesky factor, which determine the spectral error of the low-rank training kernel. The resulting kernel error controls both the QSVM objective and the distance of the finite-shot optimizer to the exact optimal set. Prediction introduces two additional ingredients: fresh pivot–test quantum measurements and the conditioning of the triangular Cholesky extension. Once these terms and the SVM intercept are controlled, the finite-shot decision function converges to its exact-kernel counterpart, and any test point separated from the decision boundary by a nonzero margin eventually retains the same classification. This decomposition exposes the two principal resources controlled by ICAQKL. The approximation rank determines which quantum-kernel similarities are acquired, whereas the shot budget determines how accurately those selected similarities are measured. The theory therefore connects adaptive kernel acquisition and quantum measurement precision directly to the stability of the final QSVM classifier.
Reproducibility Details
Datasets and binary tasks. We evaluate the proposed ICD-based quantum kernel SVM on tabular, handwritten-digit, fashion-image, and biomedical-image classification benchmarks. The standard benchmarks include the Wisconsin Diagnostic Breast Cancer (WDBC) dataset Wolberg et al. [27 ] , MNIST/Digits, and FashionMNIST Xiao et al. [28 ] . Biomedical experiments use MedMNIST v2 Yang et al. [29 ] , including BreastMNIST, PneumoniaMNIST, PathMNIST, and OrganAMNIST. To keep a consistent binary-classification setting, multiclass datasets are restricted to specified class pairs in the main benchmark. For example, PathMNIST and OrganAMNIST are evaluated on classes 0 and 1. The selected labels are then remapped to { 0 , 1 } \{0,1\} { 0 , 1 } . For datasets without predefined validation partitions, we use train/validation/test splits that preserve class proportions. MedMNIST experiments retain the official train/validation/test partitions before any optional computational subsampling. When dataset caps are needed because of the cost of quantum-kernel evaluation, samples are selected without replacement using the experiment seed, and the same partition is used by all methods compared in that run.
PCA-Based Quantum Input Construction The original datasets generally have substantially more input dimensions than the number of qubits available to the quantum feature map. For example, image datasets contain hundreds or thousands of pixel features after flattening, whereas our quantum circuits use only a small number of qubits. We therefore employ principal component analysis (PCA) as a deterministic, unsupervised dimensionality-reduction step that maps each input to a q q q -dimensional representation, where q q q is the number of qubits used by the quantum kernel circuit.
Training-only preprocessing. To prevent information leakage, all preprocessing transformations are estimated exclusively from the training partition. Let
X t r = [ x 1 T , … , x n T ] T ∈ R n × d (202) X_{\mathrm{tr}}=\left[x_{1}^{\mathsf{T}},\ldots,x_{n}^{\mathsf{T}}\right]^{\mathsf{T}}\in\mathbb{R}^{n\times d} \tag*{(202)} X tr = [ x 1 T , … , x n T ] T ∈ R n × d (202)
denote the training data, where d d d is the original input dimension. We first standardize every feature using the training-set mean and standard deviation,
x ^ i j = x i j − μ j σ j , (203) \widehat{x}_{ij}=\frac{x_{ij}-\mu_{j}}{\sigma_{j}}, \tag*{(203)} x ij = σ j x ij − μ j , (203)
where
μ j = 1 n ∑ i = 1 n x i j , σ j 2 = 1 n ∑ i = 1 n ( x i j − μ j ) 2 . (204) \mu_{j}=\frac{1}{n}\sum_{i=1}^{n}x_{ij},\qquad\sigma_{j}^{2}=\frac{1}{n}\sum_{i=1}^{n}(x_{ij}-\mu_{j})^{2}. \tag*{(204)} μ j = n 1 i = 1 ∑ n x ij , σ j 2 = n 1 i = 1 ∑ n ( x ij − μ j ) 2 . (204)
The same ( μ j , σ j ) (\mu_{j},\sigma_{j}) ( μ j , σ j ) estimated from the training partition are subsequently applied to validation and test examples.
Principal-component projection. PCA is then fitted to the standardized training matrix. Let X ^ t r ∈ R n × d \widehat{X}_{\mathrm{tr}} \in\mathbb{R}^{n \times d} X tr ∈ R n × d denote the standardized data and consider the empirical covariance matrix
Σ = 1 n − 1 X ^ t r T X ^ t r . (205) \Sigma= \frac{1}{n-1}\widehat{X}_{\mathrm{tr}}^{\mathsf{T}}\widehat{X}_{\mathrm{tr}}. \tag*{(205)} Σ = n − 1 1 X tr T X tr . (205)
Let λ 1 ≥ λ 2 ≥ ⋯ ≥ λ d ≥ 0 \lambda_1 \ge\lambda_2 \ge\cdots\ge\lambda_d \ge0 λ 1 ≥ λ 2 ≥ ⋯ ≥ λ d ≥ 0 be the eigenvalues of Σ \Sigma Σ with corresponding orthonormal eigenvectors v 1 , … , v d v_1,\ldots,v_d v 1 , … , v d . PCA retains the first q q q eigenvectors,
V q = [ v 1 , … , v q ] ∈ R d × q , (206) V_q = [v_1,\ldots,v_q] \in\mathbb{R}^{d \times q}, \tag*{(206)} V q = [ v 1 , … , v q ] ∈ R d × q , (206)
and maps each standardized input x ^ \widehat{x} x to
z = V q T x ^ ∈ R q . (207) z = V_q^{\mathsf{T}}\widehat{x} \in\mathbb{R}^{q}. \tag*{(207)} z = V q T x ∈ R q . (207)
Thus, the PCA dimension is chosen to equal the number of qubits: d P C A = q d_{\mathrm{PCA}} = q d PCA = q . Unless otherwise stated, we use q = 6 q = 6 q = 6 . Experiments employing a different circuit width use the corresponding PCA dimension; for example, a four-qubit configuration uses four principal components.
Explained variance. The fraction of training-set variance retained by the q q q -dimensional representation is
EVR ( q ) = ∑ j = 1 q λ j ∑ j = 1 d λ j . (208) \operatorname{EVR}(q) = \frac{\sum_{j=1}^{q}\lambda_j}{\sum_{j=1}^{d}\lambda_j}. \tag*{(208)} EVR ( q ) = ∑ j = 1 d λ j ∑ j = 1 q λ j . (208)
We regard this quantity as a preprocessing diagnostic rather than an optimization objective: the number of retained components is determined by the quantum circuit width, not by selecting a variance threshold. Reporting EVR ( q ) \operatorname{EVR}(q) EVR ( q ) for each dataset provides a direct measure of how much information is compressed before the quantum kernel is evaluated.
Angle rescaling. The PCA coordinates generally take values on an unbounded real scale, whereas the quantum feature map encodes them as rotation angles. We therefore fit a component-wise affine rescaling on the PCA-transformed training set. For the j j j th retained principal component, let
a j = min i ∈ t r a i n z i j , b j = max i ∈ t r a i n z i j . (209) a_j = \min_{i \in\mathrm{train}} z_{ij}, \qquad b_j = \max_{i \in\mathrm{train}} z_{ij}. \tag*{(209)} a j = i ∈ train min z ij , b j = i ∈ train max z ij . (209)
The corresponding quantum input coordinate is
θ j = π z j − a j b j − a j , (210) \theta_j = \pi\frac{z_j-a_j}{b_j-a_j}, \tag*{(210)} θ j = π b j − a j z j − a j , (210)
so that training examples are mapped into θ ∈ [ 0 , π ] q \theta\in[0,\pi]^q θ ∈ [ 0 , π ] q . The same training-derived values ( a j , b j ) (a_j,b_j) ( a j , b j ) are used to transform validation and test data. The complete preprocessing map is therefore
x ⟼ x ^ ⟼ V q T x ^ ⟼ θ . (211) x \longmapsto\widehat{x} \longmapsto V_q^{\mathsf{T}}\widehat{x} \longmapsto\theta. \tag*{(211)} x ⟼ x ⟼ V q T x ⟼ θ . (211)
Connection to the quantum kernel. The resulting angle vector
θ ( x ) = [ θ 1 ( x ) , … , θ q ( x ) ] T (212) \theta(x) = [\theta_1(x),\ldots,\theta_q(x)]^{\mathsf{T}} \tag*{(212)} θ ( x ) = [ θ 1 ( x ) , … , θ q ( x ) ] T (212)
is supplied to the q q q -qubit quantum feature map. In our implementation, the PCA coordinates are encoded through single-qubit Y Y Y rotations followed by entangling layers. The fidelity kernel is then
k ( x , x ′ ) = ∣ ⟨ ϕ ( θ ( x ) ) ∣ ϕ ( θ ( x ′ ) ) ⟩ ∣ 2 . (213) k(x,x') = \left|\langle\phi(\theta(x)) \mid\phi(\theta(x')) \rangle\right|^2. \tag*{(213)} k ( x , x ′ ) = ∣ ⟨ ϕ ( θ ( x )) ∣ ϕ ( θ ( x ′ ))⟩ ∣ 2 . (213)
Consequently, PCA is not used as a classifier and does not access class labels. Its role is solely to construct a low-dimensional, training-derived representation compatible with the available number of qubits.
Pivoted incomplete Cholesky training. Given the exact training kernel K ∈ R n × n K \in\mathbb{R}^{n \times n} K ∈ R n × n , ICD constructs
K ≈ K ~ r = G r G r T , G r ∈ R n × r , (214) K \approx\widetilde{K}_r = G_r G_r^{\mathsf{T}}, \qquad G_r \in\mathbb{R}^{n \times r}, \tag*{(214)} K ≈ K r = G r G r T , G r ∈ R n × r , (214)
using greedy residual-diagonal pivoting. At iteration t t t , the pivot is selected as
p t = arg max i ( R t ) i i , R t = K − G t G t T , (215) p_t = \underset{i}{\operatorname{arg\,max}} \, (R_t)_{ii}, \qquad R_t = K - G_t G_t^{\mathsf{T}}, \tag*{(215)} p t = i arg max ( R t ) ii , R t = K − G t G t T , (215)
and the procedure terminates either after the prescribed maximum rank r r r or when the maximum residual diagonal falls below the numerical tolerance. Unless otherwise stated, we use r = 30 r = 30 r = 30 and tolerance 10 − 8 10^{-8} 1 0 − 8 . Rank-ablation experiments evaluate r ∈ { 5 , 10 , 15 , 20 , 25 , 30 , 40 } r \in\{5, 10, 15, 20, 25, 30, 40\} r ∈ { 5 , 10 , 15 , 20 , 25 , 30 , 40 } . The resulting rows of G r G_r G r serve as explicit low-dimensional kernel features, on which a linear SVM is trained. Unless stated otherwise, the SVM regularization parameter is C = 1 C = 1 C = 1 .
Exact-kernel comparison protocol. Because construction of the exact quantum kernel requires O ( n 2 ) O(n^2) O ( n 2 ) fidelity evaluations, Full-QSVM is additionally evaluated on a common capped training subset when a full dense quantum kernel is computationally prohibitive. We refer to this setting as Full-QSVM (subset) . ICD-QSVM and Nyström-QSVM are also rerun on the same samples when evaluating approximation error against the exact kernel. Consequently, quantities such as
∥ K − K ~ r ∥ F ∥ K ∥ F (216) \frac{\lVert K - \widetilde{K}_r \rVert_F}{\lVert K \rVert_F} \tag*{(216)} ∥ K ∥ F ∥ K − K r ∥ F (216)
are computed on identical matrices and identical training samples. In contrast, the “ICD-full” result denotes ICD-QSVM trained on the complete available training partition and is intended to measure the practical scalable performance of the proposed method rather than to provide a sample-size-matched comparison with the exact dense kernel.
Kernel-evaluation accounting. We distinguish kernel-evaluation cost from classical SVM optimization cost. For the exact Full-QSVM on n n n training examples, direct dense construction requires n 2 n^2 n 2 kernel evaluations in our implementation. For rank-r r r pivoted Cholesky, kernel entries are evaluated lazily and cached. Kernel symmetry is exploited, and diagonal entries are not queried because fidelity kernels satisfy k ( x i , x i ) = 1 k(x_i, x_i) = 1 k ( x i , x i ) = 1 . Therefore, the number of new training-kernel evaluations is
N I C D = n r − r ( r + 1 ) 2 . (217) N_{\mathrm{ICD}} = nr - \frac{r(r+1)}{2}. \tag*{(217)} N ICD = n r − 2 r ( r + 1 ) . (217)
For example, with n = 603 n = 603 n = 603 and r = 30 r = 30 r = 30 ,
N I C D = 603 × 30 − 30 × 31 2 = 17,625. (218) N_{\mathrm{ICD}} = 603 \times30 - \frac{30 \times31}{2} = 17{,}625. \tag*{(218)} N ICD = 603 × 30 − 2 30 × 31 = 17 , 625. (218)
For a capped subset with n = 120 n = 120 n = 120 and r = 30 r = 30 r = 30 , the corresponding count is 3,135, compared with 14,400 entries for direct dense construction. We report wall-clock fit time separately because simulator runtime also depends on the quantum-circuit backend and software overhead.
Finite-shot experiments. To assess sensitivity to measurement noise, we additionally replace analytic fidelity probabilities with finite-shot estimates. For a shot budget S S S , every required kernel value is estimated from S S S circuit measurements. We study several shot budgets, e.g., S ∈ { 64 , 128 , 256 , 512 } S \in\{64, 128, 256, 512\} S ∈ { 64 , 128 , 256 , 512 } , together with the analytic-kernel reference. Because finite-shot estimation introduces stochastic perturbations into the kernel matrix, these experiments report both predictive accuracy and approximation quality as functions of S S S . Analytic and finite-shot results are kept distinct in all tables and figures.
Reproducibility and randomness control. Randomness arises from dataset splitting or computational subsampling, capped-subset selection, and, where applicable, finite-shot measurement. Every experiment is indexed by an explicit random seed. For multi-seed experiments, the complete data-splitting and sampling procedure is repeated independently for each seed rather than changing only the downstream classifier initialization. We report the mean and standard deviation across seeds,
m ˉ = 1 S s e e d ∑ s = 1 S s e e d m s , σ m = 1 S s e e d − 1 ∑ s = 1 S s e e d ( m s − m ˉ ) 2 , (219) \bar{m} = \frac{1}{S_{\mathrm{seed}}} \sum_{s=1}^{S_{\mathrm{seed}}} m_s,\quad\sigma_m = \sqrt{\frac{1}{S_{\mathrm{seed}} - 1} \sum_{s=1}^{S_{\mathrm{seed}}} (m_s - \bar{m})^2}, \tag*{(219)} m ˉ = S seed 1 s = 1 ∑ S seed m s , σ m = S seed − 1 1 s = 1 ∑ S seed ( m s − m ˉ ) 2 , (219)
for accuracy, balanced accuracy, approximation error, and runtime where appropriate. All competing methods within a seed use the same training, validation, and test samples. The PCA transformation is refit independently on the corresponding training partition for each seed, thereby reproducing the complete learning pipeline rather than reusing preprocessing statistics across repeated trials.
Table 7. Default experimental and reproducibility settings. Dataset-specific deviations are stated with the corresponding experiment.