Optimal algorithmic complexity of inference in quantum kernel methods
Authors: Elies Gil-Fuster, Seongwook Shin, Sofiene Jerbi, Jens Eisert, Maximilian J. Kramer
Organizations: Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany · Fraunhofer Heinrich Hertz Institute, 10587 Berlin, Germany · Department of Quantum Information Science and Engineering, Sejong University, 209 Neungdong-ro, Gwangjin-gu, 05006, Seoul, Republic of Korea · Helmholtz-Zentrum Berlin für Materialien und Energie, 14109 Berlin, Germany
Abstract
Quantum kernel methods are among the leading candidates for achieving quantum advantage in supervised learning. A key bottleneck is the cost of inference: evaluating a trained model on new data requires estimating a weighted sum ∑i=1Nαik(x,xi) of N kernel values to additive precision ε, where α is the vector of trained coefficients. The standard approach estimates each term independently via sampling, yielding a query complexity of O(N∥α∥22/ε2). In this work, we identify two independent axes for improvement: (1) How individual kernel values are estimated (sampling versus quantum amplitude estimation), and (2) how the sum is approximated (term-by-term versus via a single observable), and systematically analyze all combinations thereof. The query-optimal combination, encoding the full inference sum as the expectation value of a single observable and applying quantum amplitude estimation, achieves a query complexity of O(∥α∥1/ε), removing the dependence on N from the query count and yielding a quadratic improvement in both ∥α∥1 and ε. We prove a matching lower bound of Ω(∥α∥1/ε), establishing query-optimality of our approach up to logarithmic factors. Beyond query complexity, we also analyze how these improvements translate into gate costs and show that the query-optimal strategy is not always optimal in practice from the perspective of gate complexity. Our results provide both a query-optimal algorithm and a practically optimal choice of strategy depending on hardware capabilities, along with a complete landscape of intermediate methods to guide practitioners. All algorithms require only amplitude estimation as a subroutine and are thus natural candidates for early-fault-tolerant implementations.
Estimating an N×N quantum kernel from circuit fidelities requires Θ(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≲16npairs) on sparse-sensitivity KRR, with the gap \emph{growing} from +8 to +25 pts over uniform as N scales 225→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}: sij⋆∝∣gij∣Kij(1−Kij) with explicit gradient gij for KRR (Lemma1, ∣βiαj+βjαi∣Kij(1−Kij)) and SVM via the envelope theorem (∣ηi∗ηj∗∣Kij(1−Kij)); a \emph{corrected} sparsity-aware Cauchy--Schwarz rate ρ≤2m/N matching empirics (vs.\ the naive m2/N2); an explicit-constant plug-in regret bound (Theorem2); and a tighter SVM ceiling ρSVM≤msv2/N2. We close with the first multi-seed live online adaptive shot allocation on quantum hardware: +17.0±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±8.5 pts, 5 seeds).
Kernel methods are powerful tools in machine learning but commonly used full-Gram kernels face three key limitations: (1) quadratic scaling with training set size; (2) the use of fixed, non-trainable kernels; and (3) the absence of an intrinsic formulation for multiclass classification. We present McQuack, a trainable quantum kernel method for multiclass problems that achieves linear scaling in the number of training samples. This is accomplished by replacing the full training-set Gram matrix with a trainable sample-to-(class-centroid) fidelity matrix. We evaluate the model in simulation and on 124 qubits of two IBM devices, across more than 150 datasets. In simulation, McQuack outperforms existing "pure" quantum baselines, while results from hardware inference -- obtained without training -- achieve performance similar to an RBF kernel. Finally, we study the trainability of the model and observe no evidence of barren plateaus in our experiments with up to 13 qubits, and highlight the importance of parameter initialization for successful optimization.
We investigate Gaussian process (GP) bandit optimization with quantum kernels, assuming the mean reward function lies in the reproducing kernel Hilbert space (RKHS) induced by the quantum kernel. This setting is motivated by NISQ-era tasks such as quantum control, state preparation and variational quantum algorithms. While quantum kernels can offer a `quantum advantage' via domain-specific inductive biases, naïvely using full, high-dimensional kernels increases model complexity and information gain, leading to higher cumulative regret and poor learnability. To address this, we propose projected quantum kernels and classical kernel approximation techniques that reduce feature dimensionality while preserving key quantum properties. Using these approximate kernels, we develop misspecified GP bandit algorithms and derive regret bounds that characterize the trade-off between approximation error and information gain. The regret bounds provide principled guidance for selecting the optimal model complexity. Empirically, our methods outperform full quantum kernels in sample efficiency, while substantially reducing computational overhead, enabling scalable GP optimization for quantum-native applications.