An efficient Hamiltonian-based quantum algorithm for characters of the symmetric group

問題提起

本論文は、対称群 $S_n$ の指標表の列に対応する量子状態を準備するという計算上の課題に取り組んでいる。具体的には、与えられたサイクル型 $\nu$（$n$ の分割）に対して、以下の指標列状態を準備することを目的とする：
$$|\chi_\nu\rangle := \frac{1}{\sqrt{z_\nu}} \sum_{\lambda \vdash n} \chi_\lambda(\nu) |\lambda\rangle$$
ここで、$\chi_\lambda(\nu)$ は、分割 $\lambda$ の既約表現の指標を共役類 $\nu$ で評価したものである。また、$z_\nu$ は正規化因子である。

個々の指標の値を評価することは、最悪の場合 $\#P$-hard であることが知られているが、確率分布 $P_\nu(\lambda) = |\langle \lambda | \chi_\nu \rangle|^2$ からのサンプリングは、量子優位性の候補として提案されている。Bravyiら[1]による先行研究では、このようなサンプリングは $S_n$ 上の量子フーリエ変換（QFT）を介して達成できることが示されたが、そのQFTの最良の既知の実装には $\tilde{O}(n^3)$ 個のゲートと $\tilde{O}(n^{3/2})$ 個の量子ビットが必要となる。著者らは、特に再構成可能な量子ビットを持つ近未来のハードウェアに適した、フルQFTを回避するより効率的かつ直接的な手法を求めている。

手法

著者らは、指標状態の生成に必要な転送メカニズムを直接実装することで、QFTをバイパスするハミルトニアンベースのアルゴリズムを提案している。

1. フェルミオン符号化と転送メカニズム:
このアルゴリズムは、CrichignoおよびPrakash [11]、ならびにBravyiら [1] によって確立された $S_n$ のフェルミオン符号化に基づいている。この符号化において、シード状態 $|1^n 0^n\rangle$ は空の分割に対応し、一連の電流演算子 $J_\nu = J_{\nu_1} \dots J_{\nu_\ell}$ を適用することで、正規化されていない指標列が生成される。
$J_s$（サイクル長 $s$ の電流演算子）はユニタリではないため、著者らは単一のアニシラ量子ビットを用いた転送メカニズムを導入している。彼らは以下のハミルトニアンを定義する：
$$H_s = |1\rangle\langle 0|_a \otimes J_s + |0\rangle\langle 1|_a \otimes J_s^\dagger$$
ここで、$J_s^\dagger J_s$ の固有値を $\zeta$ とすると、$H_s$ の下で正確な時間 $t_{s,j} = \pi / (2\sqrt{\zeta})$ だけ進化させることで、系は $|0\rangle_a |\phi\rangle \to |0\rangle_a (J_s |\phi\rangle / \sqrt{\zeta})$ という正確なラビ回転を実行する。

2. ラダー特性（Ladder Property）:
重要な洞察は、電流演算子のラダー特性である。著者らは、アルゴリズムによって訪問される状態が、$J_s^\dagger J_s$ の既知の整数固有値（$s$ の第 $j$ 回目の転送における $s \cdot j$）を持つ固有ベクトルであることを証明している。これにより、進化時間を事前に固定することが可能となり、事後選択（post-selection）なしでの決定論的な状態準備が可能になる。

3. 2つの実装戦略:
論文では、ハミルトニアンの進化 $e^{-iH_s t}$ をシミュレートするための2つの異なる手法を提示している：

• 再構成可能な量子ビットを用いたトロッター分解:

  • ハミルトニアン $H_s$ は、剰余（residue）ごとにサイトをグループ化する置換 $P_s$ を用いて、フェルミオンモードを並べ替えることで近接相互作用項へと分解される。
  • 再構成可能な量子ビット（例：中性原子アレイ）のための高速フェルミオン置換プロトコル（Maskaraら [16]）を用いて、置換 $P_s$ を定数デプスで $O(n)$ 個のゲートで実装する。
  • 進化は一次トロッター分解によってシミュレートされる。著者らは状態依存のエラー解析を行い、交換子エラーが、演算子のノルムに基づく最悪ケースの境界よりも、アルゴリズムが訪問する特定の状態上で著しく小さいことを示している。

• 量子特異値変換 (QSVT):

  • 厳密な最悪ケースの境界を提供するために、著者らはパウリ文字列を用いて $H_s$ のブロック符号化を構成する。
  • 逆誤差 $1/\delta$ に対する対数依存性で進化をシミュレートするために、QSVTを適用する。
  • このアプローチは、サイクル型のレジスタを、演算子 $N_s = J_s J_s^\dagger / s$ に対する位相推定を通じて（特異値増幅によりゲートコストを削減しながら）「消去」するプロセスを含む、量子指標変換 (QCT) へと拡張される。

主な貢献と結果

1. ゲート複雑性の改善:

• QSVTベースのCSP: 著者らは、任意のサイクル型に対して、指標状態準備（CSP）が $\tilde{O}(n^{5/2})$ 個のゲートと $O(n)$ 個の量子ビットで達成できることを証明した。これは、QFTベースのアプローチの $\tilde{O}(n^3)$ というゲート数と比較して改善されている。
• 量子指標変換 (QCT): 一般的な $S_n$ における初の明示的な多項式ゲート境界を $\tilde{O}(n^{5/2})$ ゲート、$O(n)$ 量子ビットのスケールで提供した。

2. 状態依存のトロッター境界:

• 一様サイクル型 $\nu = (s^m)$ に対して、著者らは主要項のレベルでの状態依存トロッターエラー境界を導出した。
• 量子優位性が想定される領域（$m = \Theta(\sqrt{n}/\log n)$）において、推定される十分なゲート数は $\tilde{O}(n^{7/4}/\delta)$ である。
• $n=48$ までの数値シミュレーションは、実際の必要ゲート数がこれらの解析的境界よりもさらに低いことを示唆しており、様々なサイクル型に対して $n^{1.2}$ から $n^{1.5}$ 程度のスケールで推移している。これは、解析的境界が保守的であることを示している。

3. 古典的複雑性解析:

• 本論文は、「グラニュラリティ・レジーム（粒度領域）」（Bravyiらが量子優位性を主張する領域）におけるすべてのサイクル型が古典的に困難であるという仮定に異議を唱えている。
• 一様サイクル ($\nu = (s^m)$) および準一様サイクル（例外的なサイクルの定数個の摂動によるもの）に対する厳密な古典サンプリングアルゴリズムを提示している。
• これらの古典サンプラーは、一様サイクルに対して期待時間 $\tilde{O}(n^2)$、例外的なサイクルが $b$ 個ある準一様サイクルに対しては $n^{4b+O(1)}$ で動作する。これは、このレジームにおける量子優位性は、例外的なサイクルの数が $n$ とともに増加するサイクル型においてのみ成立することを意味する。

4. CFTへの応用:

• 逆QCTを、対称オルビフォールド共形場理論（CFT）における**欠陥エントロピー（defect entropy）**の推定に適用する。逆QCTの出力を測定することで、欠陥エントロピーの公式における重みに比例した確率でサイクル型 $\nu$ をサンプリングできる。著者らは、これにより、エントロピーが $\Theta(n)$ でスケールする一般的な既約表現に対して、加法的誤差 $O(\sqrt{n})$ での効率的な推定が可能であることを示している。

意義と主張

本論文は、対称群の指標にアクセスするための、QFTベースのアプローチよりも単純かつ効率的な代替案を提供すると主張している。ハミルトニアンの進化と、電流演算子の代数的構造（ラダー特性）を活用することで、ゲート複雑性を $\tilde{O}(n^3)$ から $\tilde{O}(n^{5/2})$ へと減少させることを証明した。

その意義は二重である：

1. 理論的: 一般的な $S_n$ における初の明示的な多項式境界を確立し、古典的な困難性のランドスケープを精緻化した。これにより、一様サイクル（主要な候補領域）は古典的に実行可能であることが示された。
2. 実践的: トロッターベースの実装は、近接相互作用ゲートと高速置換を利用しており、再構成可能な量子ビットアーキテクチャ（中性原子アレイなど）向けに明示的に設計されている。数値的なベンチマークは、古典的な困難性を確保するために、例外的なサイクルを増やすサイクル型を選択すれば、このアプローチが近未来の量子優位性を実現するための有力な候補であることを示唆している。

著者らは、トロッター境界に関して謙虚な姿勢を保っており、厳密な最悪ケースの境界は、シミュレーションで観察された経験的なパフォーマンスと比較して、おそらく過大な見積もりであると述べている。また、主要項を超えた完全なエラー解析は依然として未解決の課題であるとしている。