Optimal algorithmic complexity of inference in quantum kernel methods

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 weighted sum of $N$ kernel values to additive precision $\epsilon$, where $\alpha$ is the vector of trained coefficients. The standard approach estimates each term independently via sampling, yielding a query complexity of $\mathcal{O}(N\Vert \alpha {\Vert }_2^2/{\epsilon }^2)$. In this work, we combine two independent improvements: estimating the kernel values via quantum amplitude estimation and collecting the sum under a single observable. We show that the improved approach achieves a query complexity of $\mathcal{O}(\Vert \alpha {\Vert }_1/\epsilon )$, removing the dependence on $N$ from the query count and yielding a quadratic improvement in both $\Vert \alpha {\Vert }_1$ and $\epsilon$. We prove a matching lower bound of $\Omega (\Vert \alpha {\Vert }_1/\epsilon )$, establishing query-optimality. 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. We identify a different strategy based on importance sampling, which yields a lower total gate count. We thus 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.