技術的概要：AQKA：ショット制約下における能動的量子カーネル取得

1. 問題定義

古典的入力を量子特徴空間にマッピングして忠実度 $K(x_i, x_j) = |\langle \phi(x_j)|\phi(x_i)\rangle|^2$ を計算する量子カーネル法は、ノイズあり中規模量子（NISQ）ハードウェアにとって最もアクセスしやすいワークロードの一つである。しかし、その実用的な展開は測定コストによってボトルネックとなっている。$N \times N$ のカーネル行列を推定するには、所望の精度を達成するための各エントリあたりのショット数 $S$ を用いて $\Theta(N^2 S)$ 回の回路実行（ショット）が必要となる。現在のハードウェアでは、回路の遅延がミリ秒から秒の範囲にあるため、このスケーリングにより展開可能な問題サイズは数百程度に制限される。

既存の予算節約戦略（例：Nyström-QKE、ShoFaR、カーネル・ターゲット整合）は、測定するエントリをどのように部分サンプリングするか（例：ランドマーク列や訓練点の選択）によってこの問題を解決しようとする。しかし、これらの手法は通常、選択された部分集合内でショット予算を均一に割り当てる。これらは、各特定のカーネルエントリが下流の分類器のパフォーマンスにどの程度寄与するかという不均質性を考慮できていない。核心的な未解決の問いは以下の通りである：固定されたショット予算 $B$ が与えられたとき、下流タスクの損失を最小化するために、ペアレベルでショットをどのように割り当てるべきか？

2. 手法：AQKA

著者らは、ショット制約付き量子カーネル学習を、総ショット予算制約 $\sum s_{ij} \leq B$ の下で期待損失 $\mathbb{E}[L(\hat{K})]$ を最小化する最適化問題として定式化した。

理論的導出

一次解析（デルタ法）とカルーシュ・キューン・タッカー（KKT）条件を組み合わせて用いることで、著者らは閉形式の最適割り当て則を導出した。$s_{ij}$ 個のショットで推定されたカーネルエントリ $K_{ij}$ に対して、分散は $K_{ij}(1-K_{ij})/s_{ij}$ となる。損失推定量の分散を最小化する最適割り当て $s^*_{ij}$ は、そのエントリに対する損失の感度に比例する：
$$s^*_{ij} \propto |g_{ij}| \sqrt{K_{ij}(1-K_{ij})}$$
ここで、$g_{ij} = \partial L / \partial K_{ij}$ はカーネルエントリに対する損失の勾配である。

• カーネルリッジ回帰（KRR）の場合: 勾配は明示的に $g_{ij} = -2\lambda^2(\beta_i \alpha_j + \beta_j \alpha_i)$ と導出される。ただし、$\alpha = (K+\lambda I)^{-1}y$、$\beta = (K+\lambda I)^{-1}\alpha$ である。
• サポートベクターマシン（SVM）の場合: 包絡定理（ダンスキンの定理）を用いて、勾配は $g_{ij} = -y_i y_j \eta^*_i \eta^*_j$ と導出される。ここで $\eta^*$ は最適双対変数である。

アルゴリズム的実装

著者らは、ラウンド単位で動作する実用的なアルゴリズム**AQKA（能動的量子カーネル取得）**を提案する：

1. ウォームアップ: 予算の少量（$\eta_w B$）を均一に費やし、初期カーネル推定値 $\hat{K}$ をシードする。
2. 感度推定: 該アルゴリズムは $\hat{K}$ 上で KRR（または SVM）問題を解き、勾配ベースの感度スコア $g_{ij}$ を計算する。
3. ターゲットフィル割り当て: 多項分布からのショットサンプリング（確率的なスパイクにより低感度のペアが飢餓状態になる可能性がある）の代わりに、AQKA は決定論的な「ターゲットフィル」アプローチを使用する。各ペアに対して目標ショット数 $s^*_{ij}$ を計算し、その差分 $\max(0, s^*_{ij} - s_{ij})$ を各ペアに追加する。
4. 探索: 高次効果や推定ノイズにより重要になる可能性のあるペアをアルゴリズムが完全に無視するのを防ぐため、少量の探索分（$\eta_e B$）を均一に追加する。

3. 主要な貢献

1. 完全な領域分解

本論文は、異なる割り当て戦略が最適となる時期の原理的な特徴付けを提供する：

• AQKA は、スパース感度の KRR タスクにおいて、予算制限領域（$B \lesssim 16 n_{pairs}$）で優位性を発揮する。
• Nyström-QKE（低ランク再構成）は、低ランク構造が完全に復元可能な飽和予算における植込みスパースデータにおいて勝利する。
• ShoFaR 風の手法は、極端な低予算領域でのみ競争力を持つ。

2. 閉形式ペアレベル取得理論

• KKT 最適割り当て: ショットノイズ下での KRR および SVM に対する閉形式の勾配 $g_{ij}$ の導出。
• 修正されたスパース性認識境界: 著者らは、達成可能な分散削減率 $\rho$ に対するコーシー・シュワルツの境界を導出した。$g$ が $S \times S$ でサポートされると仮定した単純な $\Theta(m^2/N^2)$ スケーリングを、より正確な $\Theta(m/N)$ スケーリング（KRR の場合 $\rho \leq 2m/N$）に修正した。これは、解ベクトル $\alpha$ がスパースであっても、感度ベクトル $\beta = (K+\lambda I)^{-1}\alpha$ は一般的に密であるという構造的な事実を反映しており、つまりサポート集合に触れる任意のペアは非ゼロの感度を持つことを意味する。
• 後悔境界: 明示的な定数を伴うプラグイン後悔境界が提供され、ウォームアップ予算の増加に伴い誤差がオラクル最適値に収束することを示している。

3. 実用的なターゲットフィルアルゴリズム

本論文は、特に予算制限領域において、決定論的なターゲットフィル方式が自然な多項サンプリングを上回ることを実証している。多項サンプリングは、少数の高スコアペアに集中的に依存し、他のペアを飢餓状態にして行列逆演算におけるノイズを増幅する傾向があるのに対し、ターゲットフィルは最小のカバレッジ床を維持する。

4. 量子ハードウェア上での初のマルチシードライブオンライン適応

著者らは、現在の 156 量子ビット IBM Heron クラスデバイス上でのオンライン適応型ショット割り当ての初公開デモンストレーションを報告する。

• IBM Aachen (N=20): 均一割り当てに対して +17.0 ± 4.8 パーセントポイント（3.5$\sigma$ の有意性）。
• IBM Berlin (N=30): 高予算において +14.0 ± 8.5 パーセントポイント。

4. 実験結果

合成およびシミュレーション設定

• 植込みスパース KRR: スパースな解ベクトルを持つ合成データにおいて、AQKA（推定感度を用いたターゲットフィル）は、$N$ が 225 から 1000 にスケールするにつれて、均一割り当てに対して +8 から +25 パーセントポイントの改善を達成する。
• ノイズなし量子カーネル: ノイズなしの 4 量子ビット ZZFeatureMap シミュレーションに利益が転移し、均一割り当てに対して +13 から +18 ポイントの改善を示す。
• ハードウェア再サンプリングアブレーション: IBM Pittsburgh（156 量子ビット）で測定されたカーネルを使用し、ショットノイズで再サンプリングした場合、AQKA は $B = n_{pairs}$ で均一割り当てに対して +26.3 ± 6.1 ポイント、$B = 4n_{pairs}$ で +31.9 ± 7.2 ポイントを達成する。

実データベンチマーク

• 乳がん（密な $\alpha$）: 解ベクトルが密（スパースではない）な実世界データセットにおいて、AQKA は均一に優位性を示さない。競争力はあるが領域依存のパフォーマンスを示し、この手法の利点がペアレベルの感度不均質性が高いことに依存していることを浮き彫りにする。
• SVM 対 KRR: 本論文は、理論的枠組みが SVM に拡張可能である一方、ノイズのあるウォームアップ下でのサポート集合の不安定性により、プラグイン版はより脆いことを指摘している。小規模 N、ノイズのあるウォームアップ領域では、SVM 用の AQKA は均一割り当てより劣る可能性があるのに対し、KRR 版は堅牢である。

5. 意義と主張

本論文は、理論的なショット予算最適化と NISQ ハードウェア上での実用的展開の間のギャップを埋めると主張する。その主な意義は以下の点にある：

1. 均一割り当ての超越: 予算が厳しい場合、特に近未来の量子カーネル学習において、非均一で感度を意識したショット割り当てが重要であることを実証する。
2. ハードウェア検証: 実際の量子ハードウェア上で、マルチシードかつライブオンラインな適応型ショット割り当て戦略の検証を初めて行い、理論的な利益がデバイスのノイズや較正ドリフトを生き延びることを証明する。
3. 領域認識: 単一の手法が普遍的に優れているわけではないことを確立する。AQKA は、現在のハードウェアにとって運用上関連性の高い領域である、予算制限されたスパース感度領域のために特別に設計されている。

著者らは主張において控えめであり、密な感度の問題や飽和予算の場合には、他の手法（Nyström など）や均一割り当ての方が好ましい可能性を認めている。また、SVM プラグインのノイズを現在の限界として特定し、将来の作業（例えば、マージン安定化取得など）が必要であると指摘している。