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

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2611.03777

Adaptive Low-Rank Quantum Kernel Acquisition under Finite-Shot Measurements: Perturbation Guarantees for QSVMs

Duong Do, Duong Tung Nguyen

Published Nov 2, 2026• 0 citations
arXivHTMLPDF

Abstract

Quantum kernel methods require estimating entries of a dense Gram matrix through repeated circuit measurements, making kernel construction expensive and statistically noisy. For a dataset of size $n$, dense construction requires $O(n^2)$ kernel queries, while existing approximation methods typically assume inexpensive access to kernel entries or use non-adaptive sampling. We study adaptive low-rank quantum kernel acquisition when the kernel is accessible only through a finite-shot quantum overlap oracle. Our framework, ICAQKL, uses residual-driven incomplete Cholesky construction to acquire informative kernel columns sequentially and form a positive-semidefinite rank-$r$ surrogate, reducing the training-kernel acquisition cost to $O(nrN_s)$ circuit executions for $r\ll n$, where $N_s$ is the number of shots per queried entry. The central difficulty is that finite-shot errors perturb both the queried kernel values and the adaptive pivot sequence that determines the low-rank factor. We develop a non-asymptotic perturbation framework for this stochastic adaptive process, establishing concentration over the realized queries, stability of noisy pivot selection and factor construction, and propagation of the coupled sampling and approximation errors to the QSVM objective, optimizer, prediction function, and classification margin. The resulting rank--shot conditions characterize when ICAQKL approaches the full QSVM induced by the same quantum feature map. Experiments on benchmark and biomedical datasets show favorable accuracy--query-cost tradeoffs, competitive performance with the full QSVM, and competitive or improved performance relative to the evaluated Nyström baselines under comparable settings. ICAQKL is intended to enable measurement-efficient and theoretically controlled use of a selected quantum kernel, rather than to establish quantum advantage over classical kernels.

DOI
10.48550/arxiv.2611.03777

Related papers

Active Quantum Kernel Acquisition for Gaussian Process Regression

Jian Xu, Artur Miroszewski, John William Paisley +2 more

Quantum kernel estimation on near-term hardware is shot-budgeted: every entry of the kernel Gram matrix is a Bernoulli expectation that must be sampled with a finite number of circuit executions. Recent work on quantum kernel classification has shown that allocating shots non-uniformly across kernel entries, weighted by their downstream task sensitivity, can reduce the shot budget required to reach a target accuracy. We extend this idea to Gaussian process (GP) regression, a setting whose downstream quantities (full-spectrum posterior variance, log-determinant, marginal likelihood) couple to kernel error more tightly than the sign-only outputs of classification. We derive three closed-form pair-level sensitivities predictive coupling $|α_iα_j|$, leave-one-out residual, and marginal-likelihood gradient and plug them into a Neyman-style minimum-variance allocation rule. To prevent catastrophic over-concentration when the warm-up sensitivity estimate is itself noisy, we add a high uniform coverage floor justified by a Frobenius lower bound on the missing-entry perturbation. On four UCI benchmarks and two synthetic RBF + Bernoulli controlled studies, the resulting allocator delivers $10$--$21\%$ test-RMSE improvement over uniform allocation across the moderate-budget regime. The gain transfers (i) to genuine ZZ and Pauli-Z quantum kernels on quantum-natural data ($-13$--$15\%$ at low budget, $p<0.05$ paired) and (ii) to four downstream tasks (Bayesian quadrature, heteroscedastic regression, hyperparameter learning, multi-output Cokriging). On UCI features embedded into a ZZ kernel the gain disappears, consistent with the exponential-concentration regime where shot allocation has nothing to exploit.

arXiv:2606.28833•Jun 27, 2026•1 citation

AQKA: Active Quantum Kernel Acquisition Under a Shot Budget

Jian Xu, Chao Li, Delu Zeng +2 more

Estimating an $N \times N$ quantum kernel from circuit fidelities requires $Θ(N^2 S)$ measurement shots, the dominant bottleneck for deployment on near-term hardware. Existing budget-saving methods (Nyström-QKE, ShoFaR, kernel-target alignment) sub-sample \emph{which} entries to measure but allocate shots \emph{uniformly} within their chosen subset, ignoring how much each entry drives the downstream classifier. We close this gap with two contributions. \textbf{First, a complete regime decomposition} for shot-budgeted quantum kernel learning: a principled menu of when each allocator wins. Our method, \emph{AQKA}, dominates the budget-limited regime ($B \lesssim 16 n_{\mathrm{pairs}}$) on sparse-sensitivity KRR, with the gap \emph{growing} from $+8$ to $+25$ pts over uniform as $N$ scales $225{\to}1000$ and reaching $+26$--$32$ pts on an \texttt{ibm\_pittsburgh} (156-qubit Heron) hardware kernel; Nyström-QKE wins at saturating budgets on planted-sparse via low-rank reconstruction; ShoFaR is competitive only at extreme low budgets. \textbf{Second, a closed-form pair-level acquisition theory}: $s_{ij}^{\star} \propto |g_{ij}|\sqrt{K_{ij}(1-K_{ij})}$ with explicit gradient $g_{ij}$ for KRR (Lemma~1, $|β_iα_j+β_jα_i|\sqrt{K_{ij}(1-K_{ij})}$) and SVM via the envelope theorem ($|η_i^*η_j^*|\sqrt{K_{ij}(1-K_{ij})}$); a \emph{corrected} sparsity-aware Cauchy--Schwarz rate $ρ\le 2m/N$ matching empirics (vs.\ the naive $m^2/N^2$); an explicit-constant plug-in regret bound (Theorem~2); and a tighter SVM ceiling $ρ^{\mathrm{SVM}} \le m_{\mathrm{sv}}^2/N^2$. We close with the first multi-seed live online adaptive shot allocation on quantum hardware: $+17.0 \pm 4.8$ pts at $N{=}20$ on \texttt{ibm\_aachen} ($3.5σ$, 5 seeds), with the advantage holding at $N{=}30$ at higher budget on \texttt{ibm\_berlin} ($+14.0 \pm 8.5$ pts, 5 seeds).

arXiv:2605.14672•May 14, 2026•2 citations

Reduced Cost Quantum Kernel Training

Daniel R. Germain, Benjamin Goldweber, Kayla J. Rodriguez +1 more

Quantum kernel methods are promising for near-term quantum machine learning, but their training costs are driven by the quadratic scaling of Gram-matrix construction and the measurement cost of estimating individual kernel values. In this work, we investigate one-class anomaly detection as a resource-efficient operating regime for training non-variational quantum kernel models. Using the ULB Credit Card Fraud Detection dataset, we evaluate three quantum feature maps across training-set sizes and qubit counts. Power-law saturation models reveal strong diminishing returns with increasing training data, with 500-sample models retaining approximately 90--93\% of their fitted asymptotic average precision (AP). We further observe no severe exponential concentration among the evaluated feature maps over the investigated qubit range, thereby avoiding the exponentially increasing measurement requirements associated with that regime. Finally, Nyström approximation reduces kernel construction from $\mathcal{O}(N^2)$ to $\mathcal{O}(Nm)$ evaluations, with QSVR retaining 94--97\% of its exact-kernel AP using only five landmarks. For ZZ-QSVR, downsampling from 4,000 to 500 training samples and applying a five-landmark approximation decreases the number of required kernel evaluations from approximately $8.0$ million to $2,485$, a reduction of more than 3,200-fold, while AP decreases from $0.812$ to $0.737$. Under the minimum IonQ pricing assumption considered here, this corresponds to an illustrative reduction in quantum kernel training cost from approximately \$1.34 billion to \$417{,}480. These results demonstrate that training-set reduction and low-rank approximation can substantially reduce the resources required to train non-variational quantum kernel anomaly detectors while retaining meaningful anomaly-discrimination performance.

quant-pharXiv:2610.04190•Oct 6, 2026•0 citations

Quantum-Efficient Kernel Target Alignment

Rodrigo Coelho, Georg Kruse, Andreas Roßkopf

In recent years, quantum computers have emerged as promising candidates for implementing kernels. Quantum Embedding Kernels embed data points into quantum states and calculate their inner product in a high-dimensional Hilbert Space by computing the overlap between the resulting quantum states. Variational Quantum Circuits (VQCs) are typically used for this end, with Kernel Target Alignment (KTA) as cost function. The optimized kernels can then be deployed in Support Vector Machines (SVMs) for classification tasks. However, both classical and quantum SVMs scale poorly with increasing dataset sizes. This issue is exacerbated in quantum kernel methods, as each inner product requires a quantum circuit execution. In this paper, we investigate KTA-trained quantum embedding kernels and employ a low-rank matrix approximation, the Nyström method, to reduce the quantum circuit executions needed to construct the Kernel Matrix. We empirically evaluate the performance of our approach across various datasets, focusing on the accuracy of the resulting SVM and the reduction in quantum circuit executions. Additionally, we examine and compare the robustness of our model under different noise types, particularly coherent and depolarizing noise.

arXiv:2502.08225•International Conference on Agents and Artificial Intelligence (ICAART)•Jan 1, 2025•9 citations

A Hybrid Quantum Machine Learning Framework Based on Nyström Approximation for Scalability Enhancement of Quantum Kernels

Mohammad Hossein Rezvannia

Abstract Quantum Machine Learning (QML) is an emerging field at the intersection of quantum computing and artificial intelligence, offering high potential for extracting complex nonlinear patterns from high-dimensional data. However, many quantum kernel-based methods suffer from high computational costs, the requirement for numerous quantum circuit executions, and the limitations of current Noisy Intermediate-Scale Quantum (NISQ) hardware. These challenges, particularly when dealing with large datasets, represent a major barrier to the widespread adoption of these methods in practical applications. In this paper, a hybrid quantum machine learning framework based on Nyström approximation is proposed to effectively reduce the computational complexity of quantum kernels and enhance their scalability. In the proposed framework, classical data is first mapped to the quantum Hilbert space via parameterized quantum circuits, and the quantum kernel is defined based on the overlap of quantum states. Then, utilizing the Nyström approximation technique, the full kernel calculation is restricted to a representative subset of data, and the final learning process is conducted in the classical space. This approach reduces computational complexity from \(\:O\left({N}^{2}\right)\) to \(\:O\left(Nm\right)\), where N is the number of samples and m is the size of the selected subset. Analytical results and simulations on the Breast Cancer Wisconsin dataset demonstrate that the proposed framework reduces computational costs by over 60% while maintaining the geometric structure of the quantum feature space, with a classification accuracy loss of less than 3%. These results suggest that the proposed method can serve as a practical, scalable, and noise-resilient solution for applying quantum machine learning to real-world data-driven problems.

•Feb 18, 2026•0 citations

Who can sample forever? Shot noise effects in quantum linear regression

Gabriele Lo Monaco, Salvatore Lorenzo, Alessandro Ferraro +3 more

Quantum fidelity kernels and quantum extreme learning machines share the same basic architecture: a fixed quantum device generates features that are combined through a classically trained linear model. We refer to this broad non-variational setting as quantum linear regression. A defining aspect of these models is that the quantum features are not directly available, but must be estimated from a finite number of shots. We show that finite statistics makes quantum linear regression unavoidably ill-conditioned. Ideal feature vectors are confined to a subspace determined by the dimension of the Hilbert space, whereas finite-shot estimates generically acquire components outside this subspace. Training then attempts to fit directions that disappear in the infinite-statistics limit, making the learned model increasingly sensitive to sampling noise. We analyze this mechanism for quantum extreme learning machines trained on $n_{\rm tr}$ states with $N$ shots per state. Despite the ill-conditioning, predictions remain controlled when the training targets are exact. Finite sampling produces a systematic prediction error that decreases quadratically with $N$, while fluctuations induced by the random training measurements decrease inversely with the total training budget. Thus, unlike in standard linear regression with exactly known features, increasing the dataset size alone cannot remove the error caused by sampling noise. If the training targets are also noisy, due for instance to state-preparation errors, the otherwise hidden directions become active. The test error can then increase with $N$, a behavior that we ascribe to a form of quantum overfitting. Our results expose a fundamental tradeoff between dataset size and per-state statistics in non-variational quantum learning and provide a baseline for resource-aware training and regularization strategies.

quant-pharXiv:2610.12015•Oct 9, 2026•1 citation
Quantum kernel methods require estimating entries of a dense Gram matrix through repeated circuit measurements, making kernel construction expensive and statistically noisy. For a dataset of size nnn, dense construction requires O(n2)O(n^2)O(n2) kernel queries, while existing approximation methods typically assume inexpensive access to kernel entries or use non-adaptive sampling. We study adaptive low-rank quantum kernel acquisition when the kernel is accessible only through a finite-shot quantum overlap oracle. Our framework, ICAQKL, uses residual-driven incomplete Cholesky construction to acquire informative kernel columns sequentially and form a positive-semidefinite rank-rrr surrogate, reducing the training-kernel acquisition cost to O(nrNs)O(nrN_s)O(nrNs​) circuit executions for r≪nr\ll nr≪n, where NsN_sNs​ is the number of shots per queried entry. The central difficulty is that finite-shot errors perturb both the queried kernel values and the adaptive pivot sequence that determines the low-rank factor. We develop a non-asymptotic perturbation framework for this stochastic adaptive process, establishing concentration over the realized queries, stability of noisy pivot selection and factor construction, and propagation of the coupled sampling and approximation errors to the QSVM objective, optimizer, prediction function, and classification margin. The resulting rank--shot conditions characterize when ICAQKL approaches the full QSVM induced by the same quantum feature map. Experiments on benchmark and biomedical datasets show favorable accuracy--query-cost tradeoffs, competitive performance with the full QSVM, and competitive or improved performance relative to the evaluated Nyström baselines under comparable settings. ICAQKL is intended to enable measurement-efficient and theoretically controlled use of a selected quantum kernel, rather than to establish quantum advantage over classical kernels.
Quantum kernel estimation on near-term hardware is shot-budgeted: every entry of the kernel Gram matrix is a Bernoulli expectation that must be sampled with a finite number of circuit executions. Recent work on quantum kernel classification has shown that allocating shots non-uniformly across kernel entries, weighted by their downstream task sensitivity, can reduce the shot budget required to reach a target accuracy. We extend this idea to Gaussian process (GP) regression, a setting whose downstream quantities (full-spectrum posterior variance, log-determinant, marginal likelihood) couple to kernel error more tightly than the sign-only outputs of classification. We derive three closed-form pair-level sensitivities predictive coupling ∣αiαj∣|α_iα_j|∣αi​αj​∣, leave-one-out residual, and marginal-likelihood gradient and plug them into a Neyman-style minimum-variance allocation rule. To prevent catastrophic over-concentration when the warm-up sensitivity estimate is itself noisy, we add a high uniform coverage floor justified by a Frobenius lower bound on the missing-entry perturbation. On four UCI benchmarks and two synthetic RBF + Bernoulli controlled studies, the resulting allocator delivers 101010--21%21\%21% test-RMSE improvement over uniform allocation across the moderate-budget regime. The gain transfers (i) to genuine ZZ and Pauli-Z quantum kernels on quantum-natural data (−13-13−13--15%15\%15% at low budget, p<0.05p<0.05p<0.05 paired) and (ii) to four downstream tasks (Bayesian quadrature, heteroscedastic regression, hyperparameter learning, multi-output Cokriging). On UCI features embedded into a ZZ kernel the gain disappears, consistent with the exponential-concentration regime where shot allocation has nothing to exploit.
Estimating an N×NN \times NN×N quantum kernel from circuit fidelities requires Θ(N2S)Θ(N^2 S)Θ(N2S) measurement shots, the dominant bottleneck for deployment on near-term hardware. Existing budget-saving methods (Nyström-QKE, ShoFaR, kernel-target alignment) sub-sample \emph{which} entries to measure but allocate shots \emph{uniformly} within their chosen subset, ignoring how much each entry drives the downstream classifier. We close this gap with two contributions. \textbf{First, a complete regime decomposition} for shot-budgeted quantum kernel learning: a principled menu of when each allocator wins. Our method, \emph{AQKA}, dominates the budget-limited regime (B≲16npairsB \lesssim 16 n_{\mathrm{pairs}}B≲16npairs​) on sparse-sensitivity KRR, with the gap \emph{growing} from +8+8+8 to +25+25+25 pts over uniform as NNN scales 225→1000225{\to}1000225→1000 and reaching +26+26+26--323232 pts on an \texttt{ibm\_pittsburgh} (156-qubit Heron) hardware kernel; Nyström-QKE wins at saturating budgets on planted-sparse via low-rank reconstruction; ShoFaR is competitive only at extreme low budgets. \textbf{Second, a closed-form pair-level acquisition theory}: sij⋆∝∣gij∣Kij(1−Kij)s_{ij}^{\star} \propto |g_{ij}|\sqrt{K_{ij}(1-K_{ij})}sij⋆​∝∣gij​∣Kij​(1−Kij​)​ with explicit gradient gijg_{ij}gij​ for KRR (Lemma~1, ∣βiαj+βjαi∣Kij(1−Kij)|β_iα_j+β_jα_i|\sqrt{K_{ij}(1-K_{ij})}∣βi​αj​+βj​αi​∣Kij​(1−Kij​)​) and SVM via the envelope theorem (∣ηi∗ηj∗∣Kij(1−Kij)|η_i^*η_j^*|\sqrt{K_{ij}(1-K_{ij})}∣ηi∗​ηj∗​∣Kij​(1−Kij​)​); a \emph{corrected} sparsity-aware Cauchy--Schwarz rate ρ≤2m/Nρ\le 2m/Nρ≤2m/N matching empirics (vs.\ the naive m2/N2m^2/N^2m2/N2); an explicit-constant plug-in regret bound (Theorem~2); and a tighter SVM ceiling ρSVM≤msv2/N2ρ^{\mathrm{SVM}} \le m_{\mathrm{sv}}^2/N^2ρSVM≤msv2​/N2. We close with the first multi-seed live online adaptive shot allocation on quantum hardware: +17.0±4.8+17.0 \pm 4.8+17.0±4.8 pts at N=20N{=}20N=20 on \texttt{ibm\_aachen} (3.5σ3.5σ3.5σ, 5 seeds), with the advantage holding at N=30N{=}30N=30 at higher budget on \texttt{ibm\_berlin} (+14.0±8.5+14.0 \pm 8.5+14.0±8.5 pts, 5 seeds).
Quantum kernel methods are promising for near-term quantum machine learning, but their training costs are driven by the quadratic scaling of Gram-matrix construction and the measurement cost of estimating individual kernel values. In this work, we investigate one-class anomaly detection as a resource-efficient operating regime for training non-variational quantum kernel models. Using the ULB Credit Card Fraud Detection dataset, we evaluate three quantum feature maps across training-set sizes and qubit counts. Power-law saturation models reveal strong diminishing returns with increasing training data, with 500-sample models retaining approximately 90--93\% of their fitted asymptotic average precision (AP). We further observe no severe exponential concentration among the evaluated feature maps over the investigated qubit range, thereby avoiding the exponentially increasing measurement requirements associated with that regime. Finally, Nyström approximation reduces kernel construction from O(N2)\mathcal{O}(N^2)O(N2) to O(Nm)\mathcal{O}(Nm)O(Nm) evaluations, with QSVR retaining 94--97\% of its exact-kernel AP using only five landmarks. For ZZ-QSVR, downsampling from 4,000 to 500 training samples and applying a five-landmark approximation decreases the number of required kernel evaluations from approximately 8.08.08.0 million to 2,4852,4852,485, a reduction of more than 3,200-fold, while AP decreases from 0.8120.8120.812 to 0.7370.7370.737. Under the minimum IonQ pricing assumption considered here, this corresponds to an illustrative reduction in quantum kernel training cost from approximately $1.34 billion to $417{,}480. These results demonstrate that training-set reduction and low-rank approximation can substantially reduce the resources required to train non-variational quantum kernel anomaly detectors while retaining meaningful anomaly-discrimination performance.
In recent years, quantum computers have emerged as promising candidates for implementing kernels. Quantum Embedding Kernels embed data points into quantum states and calculate their inner product in a high-dimensional Hilbert Space by computing the overlap between the resulting quantum states. Variational Quantum Circuits (VQCs) are typically used for this end, with Kernel Target Alignment (KTA) as cost function. The optimized kernels can then be deployed in Support Vector Machines (SVMs) for classification tasks. However, both classical and quantum SVMs scale poorly with increasing dataset sizes. This issue is exacerbated in quantum kernel methods, as each inner product requires a quantum circuit execution. In this paper, we investigate KTA-trained quantum embedding kernels and employ a low-rank matrix approximation, the Nyström method, to reduce the quantum circuit executions needed to construct the Kernel Matrix. We empirically evaluate the performance of our approach across various datasets, focusing on the accuracy of the resulting SVM and the reduction in quantum circuit executions. Additionally, we examine and compare the robustness of our model under different noise types, particularly coherent and depolarizing noise.
Abstract Quantum Machine Learning (QML) is an emerging field at the intersection of quantum computing and artificial intelligence, offering high potential for extracting complex nonlinear patterns from high-dimensional data. However, many quantum kernel-based methods suffer from high computational costs, the requirement for numerous quantum circuit executions, and the limitations of current Noisy Intermediate-Scale Quantum (NISQ) hardware. These challenges, particularly when dealing with large datasets, represent a major barrier to the widespread adoption of these methods in practical applications. In this paper, a hybrid quantum machine learning framework based on Nyström approximation is proposed to effectively reduce the computational complexity of quantum kernels and enhance their scalability. In the proposed framework, classical data is first mapped to the quantum Hilbert space via parameterized quantum circuits, and the quantum kernel is defined based on the overlap of quantum states. Then, utilizing the Nyström approximation technique, the full kernel calculation is restricted to a representative subset of data, and the final learning process is conducted in the classical space. This approach reduces computational complexity from  O(N2)\:O\left({N}^{2}\right)O(N2) to  O(Nm)\:O\left(Nm\right)O(Nm), where N is the number of samples and m is the size of the selected subset. Analytical results and simulations on the Breast Cancer Wisconsin dataset demonstrate that the proposed framework reduces computational costs by over 60% while maintaining the geometric structure of the quantum feature space, with a classification accuracy loss of less than 3%. These results suggest that the proposed method can serve as a practical, scalable, and noise-resilient solution for applying quantum machine learning to real-world data-driven problems.
Quantum fidelity kernels and quantum extreme learning machines share the same basic architecture: a fixed quantum device generates features that are combined through a classically trained linear model. We refer to this broad non-variational setting as quantum linear regression. A defining aspect of these models is that the quantum features are not directly available, but must be estimated from a finite number of shots. We show that finite statistics makes quantum linear regression unavoidably ill-conditioned. Ideal feature vectors are confined to a subspace determined by the dimension of the Hilbert space, whereas finite-shot estimates generically acquire components outside this subspace. Training then attempts to fit directions that disappear in the infinite-statistics limit, making the learned model increasingly sensitive to sampling noise. We analyze this mechanism for quantum extreme learning machines trained on ntrn_{\rm tr}ntr​ states with NNN shots per state. Despite the ill-conditioning, predictions remain controlled when the training targets are exact. Finite sampling produces a systematic prediction error that decreases quadratically with NNN, while fluctuations induced by the random training measurements decrease inversely with the total training budget. Thus, unlike in standard linear regression with exactly known features, increasing the dataset size alone cannot remove the error caused by sampling noise. If the training targets are also noisy, due for instance to state-preparation errors, the otherwise hidden directions become active. The test error can then increase with NNN, a behavior that we ascribe to a form of quantum overfitting. Our results expose a fundamental tradeoff between dataset size and per-state statistics in non-variational quantum learning and provide a baseline for resource-aware training and regularization strategies.