Quantum Spectral Clustering Framework via Compact Circuit Structures

技術要約：コンパクトな回路構造による量子スペクトルクラスタリング・フレームワーク

問題提起
スペクトルグラフ理論に基づいたスペクトル機械学習手法は、クラスタリングや多様体学習において強力なツールである。しかし、その実用的な適用は高い計算コストによって阻害されている。$M$ 個のサンプルに対するカーネル（隣接）行列の構築には通常 $O(M^2)$ の時間を要し、関連する固有値問題を厳密に解くには $O(M^3)$ のコストがかかる。Nyström 法、ランダム・フーリエ特徴量、Lanczos 法などの古典的な近似手法が存在するが、これらは依然として部分的または完全なカーネル行列への明示的なアクセスを必要とすることが多い。量子機械学習の文脈では、カーネルの各要素はカーネル行列から直接読み取られるのではなく、量子サブルーチン（SWAP テストなど）を介して推定されるため、行列全体を推定する場合のコストは $O(\epsilon^{-2}M^4)$ となり、要素ごとのアクセスは極めて困難になる。著者らは、カーネル行列を構築したり個々の要素を推定したりすることなく、量子カーネルを用いて効率的にスペクトルクラスタリングを行う手法におけるギャップを特定している。

手法
本論文は、カーネル行列の構築を完全に回避する、スペクトルクラスタリングのための変分フレームワークを提案している。代わりに、集約された二次形式を通じて、コンパクトな量子回路から必要な量を直接推定する。

1. 目的関数: 著者らは、対称グラフラプラシアン ($L_{sym}$) から導出された正規化レイリー商の目的関数を定式化している。目標は、以下を最大化することである：
   $$J(\alpha) = \frac{\alpha^\dagger A \alpha - \xi \alpha^\dagger D \mathbf{1}\mathbf{1}^\dagger D \alpha}{\alpha^\dagger D \alpha}$$
   ここで、$A$ は隣接行列、$D$ は次数行列、$\mathbf{1}$ はすべての要素が 1 のベクトルであり、$\xi > 0$ はペナルティパラメータである。分子には、自明な固有ベクトル（定数ベクトル）を抑制するためのペナルティ項が含まれており、これにより非自明なクラスタリング解を保証している。

2. 量子回路設計: 本フレームワークは、カーネル行列を構築することなく目的関数の項を評価するために、3 つの特定の量子エスティメータを利用する：

   • $q_a(\alpha)$: 隣接二次形式 ($\alpha^\dagger A \alpha$) を推定する。
   • $q_d(\alpha)$: 次数重み付き二次形式 ($\alpha^\dagger D \alpha$) を推定する。
   • $q_p(\alpha)$: プロジェクター・ペナルティ項 ($\alpha^\dagger D \mathbf{1}\mathbf{1}^\dagger D \alpha$) を推定する。

   これらのエスティメータは、データのインデックス付き重ね合わせを準備するデータ埋め込みユニタリ $U_{\phi, D}$ と、インデックスレジスタ上の学習可能な重み状態 $|\alpha_\theta\rangle$ に依存している。回路は、量子状態間の忠実度（類似性）を計算するために、SWAP テスト型のサブルーチンを使用する。

3. 推論（テスト）: 未知のデータ点 $\hat{x}$ に対して、テスト状態と学習済み重み状態とのオーバーラップの位相に基づくスコア関数が定義される。位相 $\hat{\phi}(\hat{x}, \hat{\alpha})$ は干渉回路（$\sigma_x$ および $\sigma_y$ 基底での補助量子ビットの測定）を介して抽出され、閾値処理または円形クラスタリングを介してクラスターラベルの割り当てに使用される。

4. 学習ワークフロー: 重み状態 $|\alpha_\theta\rangle$ のパラメータは、量子エスティメータに導かれた古典オプティマイザ（勾配降下法）を用いて最適化される。勾配はパラメータシフト則を用いて計算される。

主な貢献

• コンパクトな回路構造: 著者らは、レイリー商の構成要素を直接推定する一連の量子回路を提示している。このアプローチは、フルまたは部分的なカーネル行列の構築、および個々のカーネル要素の推定という、他の量子スペクトル手法におけるボトルネックを回避する。
• 厳密なショット複雑性の分析: 理論的分析により、ペナルティ項（$q_p$）のサンプリング複雑性が扱いやすいことが示された。ペナルティ項の大きさが小さいことが、より多くのショットを必要とするという直感に反して、著者らは集中不等式を用いて、必要なショット数が失敗確率に対して高々準多項式的に増加することを証明した。これにより、ペナルティエスティメータが全体のサンプリング予算を支配しないことが検証された。
• 統一された学習・テストワークフロー: 本フレームワークは、変分最適化から、位相ベースのスコアリングメカニズムを用いた未知のデータに対する推論まで、完全なパイプラインを提供している。

結果
著者らは、標準的なデータセットを用いたノイズレス量子シミュレーションを用いてフレームワークを検証した：

• データセット: Iris データセット（Setosa 対 Versicolor/Virginica の二値クラスタリング）および MNIST データセット（PCA により 4 次元に削減された数字 '0' と '1' の二値クラスタリング）。
• 性能:
  • Iris: 相対的に浅い回路（4 レイヤー、24 パラメータ）で、モデルは平均テスト精度 98.7% を達成した。レイヤー数を 6 以上に増やすと、精度は 99.8% 以上で安定した。
  • MNIST: 信頼できる性能は 6 レイヤーから始まり、8 レイヤー以上で平均精度 97.2% で安定した。
• 有限ショットの挙動: シミュレーションにより、ペナルティエスティメータが予測通りに動作することが確認された。ペナルティ項の標本平均は急速にゼロに収束し、分散も同様に収縮した。決定的なことに、ペナルティ項は、理論的分析と一致して、比較的少ないショット数（例：256–1024）で信頼性高く推定可能であった。

意義と主張
本論文は、本研究を、浅いハードウェア効率的な量子回路と互換性のあるスペクトルクラスタリング・フレームワークの「概念実証」として位置づけている。主な意義は以下の通りである：

1. カーネル行列のボトルネックの回避: 集約された二次形式上で動作することにより、本手法は量子設定における $O(M^2)$ または $O(M^4)$ の要素ごとのカーネル推定コストを回避する。
2. スケールの不一致の緩和: 厳密な分析により、数値的不安定性や高いサンプリングコストの原因となりやすいペナルティ項が、効率的に推定可能であることが示され、変分目的関数が実用的であることが裏付けられた。
3. 教師なし学習の文脈: 著者らは、量子カーネル手法は教師あり学習においてはよく研究されているが、教師なしのスペクトルクラスタリングへの適用はあまり探索されていないと述べている。本研究は、スペクトルグラフ理論と、この特定の領域における変分量子アルゴリズムを結びつけるものである。

著者らは、より広い主張については慎重な姿勢を保っており、量子忠実度カーネル自体が一般的なタスクに対して古典的カーネルよりも量子優位性を提供するかどうかについては言及していない。むしろ、焦点は、量子カーネルが選択された類似度尺度であると仮定した場合に、効率的な実装を提供することにある。また、将来の研究として、このペナルティ分析のアプローチを他のペナルティ項を持つ変分アルゴリズム（QUBO 問題など）に拡張することや、教師なし設定における量子エンコーディングの理論的特性をさらに調査することを提案している。