{"id":"arxiv/2604.15214","url":"https://arxiv.org/abs/2604.15214","tags":["quant-ph","cs.LG"],"score":0,"title":"Optimal algorithmic complexity of inference in quantum kernel methods","domain":"quant-ph","source":"arxiv","authors":["Elies Gil-Fuster","Seongwook Shin","Sofiene Jerbi","Jens Eisert","Maximilian J. Kramer"],"reviews":0,"subject":"quant-ph","summary":"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 $\\sum_{i=1}^N α_i k(x,x_i)$ of $N$ kernel values to additive precision $\\varepsilon$, where $α$ is the vector of trained coefficients. The standard approach estimates each term independently via sampling, yielding a query complexity of $O(N\\lVertα\\rVert_2^2/\\varepsilon^2)$. In this work, we identify two independent axes for improvement: (1) How individual kernel…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-04-16","reactions":{}}