跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2604.15214 · v3

Optimal algorithmic complexity of inference in quantum kernel methods

首次提交 2026-04-17 00:45
版本更新 2026-11-19 19:54
雷达观测 2026-11-20 16:53
arXiv ↗PDF ↗

摘要

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)\sum_{i=1}^N α_i k(x,x_i) of NN 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∥α∥22/ε2)O(N\lVertα\rVert_2^2/\varepsilon^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/ε)O(\lVertα\rVert_1/\varepsilon), removing the dependence on NN from the query count and yielding a quadratic improvement in both ∥α∥1\lVertα\rVert_1 and ε\varepsilon. We prove a matching lower bound of Ω(∥α∥1/ε)Ω(\lVertα\rVert_1/\varepsilon), 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.

作者备注:37 pages (13+24), 5 figures, published as Conference Paper in the 40th Conference on Neural Information Processing Systems (NeurIPS 2026)

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v3,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v3 · 2026-11-19 19:54 · 最新观测版本

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 trained model on new data requires estimating a weighted sum ∑i=1Nαik(x,xi)\sum_{i=1}^N α_i k(x,x_i) of NN 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∥α∥22/ε2)O(N\lVertα\rVert_2^2/\varepsilon^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/ε)O(\lVertα\rVert_1/\varepsilon), removing the dependence on NN from the query count and yielding a quadratic improvement in both ∥α∥1\lVertα\rVert_1 and ε\varepsilon. We prove a matching lower bound of Ω(∥α∥1/ε)Ω(\lVertα\rVert_1/\varepsilon), 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.

查看此版本解读 →查看此版本原文 ↗