論文の概要: Optimal algorithmic complexity of inference in quantum kernel methods

• arxiv url: http://arxiv.org/abs/2604.15214v1
• Date: Thu, 16 Apr 2026 16:45:02 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-17 21:29:32.009548
• Title: Optimal algorithmic complexity of inference in quantum kernel methods
• Title（参考訳）: 量子カーネル法における推論の最適アルゴリズム的複雑さ
• Authors: Elies Gil-fuster, Seongwook Shin, Sofiene Jerbi, Jens Eisert, Maximilian J. Kramer,
• Abstract要約: 量子カーネル法は、教師あり学習において量子優位性を達成するための主要な候補の一つである。 標準アプローチでは、各項をサンプリングによって独立に見積もっており、クエリの複雑さは$O(NlVertrVert2/varepsilon2)$である。 単一可観測体の期待値として全推論和を符号化したクエリ-最適組合せを提案する。 この結果から,クエリ最適化アルゴリズムと,ハードウェア能力による戦略選択の両立が期待できる。
• 参考スコア（独自算出の注目度）: 0.815557531820863
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $\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 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(\lVertα\rVert_1/\varepsilon)$, removing the dependence on $N$ from the query count and yielding a quadratic improvement in both $\lVertα\rVert_1$ and $\varepsilon$. We prove a matching lower bound of $Ω(\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.
• Abstract（参考訳）: 量子カーネル法は、教師あり学習において量子優位性を達成するための主要な候補の一つである。 新しいデータ上でトレーニングされたモデルを評価するには、重み付けされた和 $\sum_{i=1}^N α_i k(x,x_i)$ of $N$ kernel value to additive precision $\varepsilon$ ここで、$α$は訓練された係数のベクトルである。 標準的なアプローチでは、各項をサンプリングによって独立に推定し、クエリの複雑さは$O(N\lVertα\rVert_2^2/\varepsilon^2)$となる。 本研究では,(1)個々のカーネル値がどのように推定されるか(サンプリングと量子振幅の推定)、(2)和がどのように近似されるか(長期対観測可能か)、およびそれらの組み合わせを体系的に解析する。 単一の観測可能量の期待値として完全な推論和を符号化し、量子振幅推定を適用するクエリ最適組み合わせは、$O(\lVertα\rVert_1/\varepsilon)$のクエリ複雑性を達成し、クエリカウントから$N$への依存を除去し、$\lVertα\rVert_1$と$\varepsilon$の2次改善をもたらす。 一致する$Ω(\lVertα\rVert_1/\varepsilon)を証明し、対数因子へのアプローチのクエリ最適化を確立する。 クエリの複雑さ以外にも、これらの改善がゲートコストにどのように変換されるかを分析し、ゲートの複雑さの観点から、クエリ-最適化戦略が常に最適であるとは限らないことを示す。 本研究は,クエリ最適化アルゴリズムと,ハードウェア能力に依存した戦略選択と,実践者を支援するための中間手法の完全な景観を提供する。 すべてのアルゴリズムはサブルーチンとして振幅推定しか必要とせず、したがってアーリーフォールトトレラントの実装の自然な候補である。

関連論文リスト

• Provably Adaptive Linear Approximation for the Shapley Value and Beyond [73.0940890296463]
  基本的で長期にわたる課題は、その効率的な近似である。 一般に用いられるすべての半値に対して$P(|hatboldsymbol-boldsymbol|_2geq)leq$を必要とする線形空間アルゴリズムを開発する。 本アルゴリズムは,各ユーティリティ関数の平均二乗誤差の明示的最小化を可能にする。
  論文  参考訳（メタデータ） (2026-04-09T16:38:14Z)
• Quantum Algorithms for Non-smooth Non-convex Optimization [30.576546266390714]
  本稿では、リプシッツ連続目的の$(,epsilon)$-Goldstein定常点を求める問題を考える。 代理オラクル関数に対するゼロ階量子推定器を構築する。
  論文  参考訳（メタデータ） (2024-10-21T16:52:26Z)
• Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
  ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。 我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
  論文  参考訳（メタデータ） (2023-06-28T16:33:39Z)
• Private estimation algorithms for stochastic block models and mixture models [63.07482515700984]
  効率的なプライベート推定アルゴリズムを設計するための一般的なツール。 最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
  論文  参考訳（メタデータ） (2023-01-11T09:12:28Z)
• Unitarity estimation for quantum channels [7.323367190336826]
  ユニタリティ推定は、量子デバイス認証とベンチマークにおいて基礎的で重要な問題である。 我々は、アンシラ効率のアルゴリズムを誘導するユニタリティ推定のための統一的なフレームワークを提供する。 アルゴリズムの$d$-dependenceと$epsilon$-dependenceの両方が最適であることを示す。
  論文  参考訳（メタデータ） (2022-12-19T09:36:33Z)
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end [114.3957763744719]
  本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。 このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。 また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
  論文  参考訳（メタデータ） (2022-12-03T02:45:23Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Best of Both Worlds: Practical and Theoretically Optimal Submodular Maximization in Parallel [17.462968952951883]
  主アルゴリズムは、独立した関心を持つ可能性のある2つのコンポーネントから組み立てられる。 LINEARSEQの変種は、文献のどのアルゴリズムよりも小さい$O(log(n))$の適応複雑性を持つ。
  論文  参考訳（メタデータ） (2021-11-15T17:10:40Z)
• Proper Learning, Helly Number, and an Optimal SVM Bound [29.35254938542589]
  適切な学習アルゴリズムにより最適なサンプル複雑性を達成できるクラスを特徴付ける。 双対ヘリー数が有界であることと、$epsilon$ と $delta$ に適切な合同依存が存在することを示せる。
  論文  参考訳（メタデータ） (2020-05-24T18:11:57Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。