Pauli Decomposition by Character Theory: A Memory-Bounded Algorithm for Qubits and Qudits

技術要約：文字論によるパウリ分解

問題提起
パウリ分解は、トロッター化、位相推定、疎なハミルトニアンのシミュレーション、および変分観測量を含む量子アルゴリズムの基本的な前提条件である。本タスクは、任意の$n$量子ビット演算子$H$を、パウリ文字列の線形結合として表すことを目的とする：
$$H = \sum_{x,z} c_{x,z} P(x, z)$$
ここで、$P(x, z)$は$\{I, X, Y, Z\}$のテンソル積である。これらの係数をトレース射影（$c_{x,z} = \text{Tr}(H \cdot P(x,z))/2^n$）を通じて直接計算するアプローチは、実装に応じて$O(2^{5n})$または$O(2^{3n})$の指数関数的なコストを要するため、大規模なシステムへの適用は不可能である。先行研究（Georgesら、Hamaguchiら）では、高速ウォルシュ・アダマール変換（FWHT）を用いることで漸近的な時間計算量を$O(n \cdot 4^n)$に削減しているが、これらの手法は通常、フルサイズの$2^n \times 2^n$演算子行列をメモリ上に展開することを要求する。これは「メモリの壁」を生み出し、ピークメモリ使用量が$O(4^n)$でスケールするため、結果としてのパウリ展開が疎であっても、実用的な適用範囲を概ね$n \le 15$量子ビット程度に制限してしまう。

手法
本論文は、パウリ分解を**アーベル群 $(\mathbb{Z}_2)^n$ の文字論（Character Theory）**を通じて再定義する。

1. 文字論的導出:

   • 著者らは、対角パウリ文字列（$Z^{\otimes z}$）を、群 $(\mathbb{Z}_2)^n$ の文字 $\chi_z(v) = (-1)^{\langle v, z \rangle}$ であると特定している。
   • 一般的なパウリ文字列 $X^{\otimes x}Z^{\otimes z}$ は、文字 $\chi_z$ と結合したシフト演算子 $X^{\otimes x}$ と見なされる。
   • この分解は、$2^n$ 個の独立した高速ウォルシュ・アダマール変換（FWHT）を実行することと同等であることが示されている。固定されたシフト $x$ に対して、係数は行列要素のベクトル $\{T_{v, v+x}\}_v$ を文字に対して変換することで得られる。
   • 本論文では、「裸の（bare）」基底（$X^{\otimes x}Z^{\otimes z}$）と、「真の（genuine）」基底（重なり合う量子ビットに $Y = iXZ$ が挿入されたもの）を区別している。アルゴリズムは、まず「裸の」基底で分解を行い（ステップ1）、次に位相補正 $i^{|x \wedge z|}$ を適用して「真の」基底へ変換する（ステップ2）。この分離により、計算コストが両者で同一であること、および基底の選択は代数的な必然性ではなく、ゲート・コンパイルにおけるエルミート項の必要性に起因する位相の慣習であることを明確にしている。

2. メモリ制限付きストリーミング実装 (paulikit):

   • メモリのボトルネックを克服するため、著者らはストリーミング・アルゴリズムを実装している。
   • 入力レジームの区別: 疎な行列入力に対しては、paulikitは$(x, z, \text{coefficient})$のチャンクをストリーミングするため、フルサイズの$2^n \times 2^n$演算子を一度も実体化（materialize）する必要がない。一方で、既に密な入力（assume_dense=True）に対しては、各チャンクの作業セットは小さく保たれるものの、プロセス全体のメモリには密な入力行列自体（13量子ビットで約1 GiB）が保持される。
   • チャンクの独立性: レマ2を活用し、シフト集合 $x$ を互いに素なチャンクに分割する。各チャンクは独立して処理される：行 $T_{v, v+x}$ が収集され、FWHTによって変換され、位相補正および閾値処理が行われる。
   • ストリーミング蓄積: 密な中間配列を保持する代わりに、アルゴリズムは各チャンクに対して生の $(x, z, \text{coefficient})$ トリプルを出力する。これにより、疎な入力に対するピークメモリ使用量は、フル演算子サイズではなく、$O(\text{chunk\_size} \times 2^n + N_{\text{terms}})$（ここで $N_{\text{terms}}$ は生存する係数の数）に抑えられる。
   • 最適化: 実装では、Pythonレベルのループを、FWHTおよび係数抽出のためのコンパイル済みCカーネルに置き換えることでオーバーヘッドを最小限に抑えている。また、コンパイル済みカーネルの有無に基づいた自動選択メカニズムを備えており、GIL（Global Interpreter Lock）の競合を回避しながら、プロセスプールおよびスレッドプールの並列処理をサポートしている。

主な貢献

1. 文字論的定式化: 本論文は、$O(n \cdot 4^n)$ のパウリ分解アルゴリズムを、$(\mathbb{Z}_2)^n$ の文字論に明確に根ざしたものとして提供し、これは（系として）$(\mathbb{Z}_p)^n$ 上の離散フーリエ変換へと自然に一般化される（系1）。
2. 基底の明確化: 「真の」パウリ基底は、中央拡大（central extension）としての $(\mathbb{Z}_2)^n \times (\mathbb{Z}_2)^n$ 内の位相慣習に過ぎず、変換自体に $Y$ を用いることは必須ではないことを明示的に示した。これにより、エルミート性を確保するための慣習としての $Y$ の使用が整理された。
3. メモリ制限付きアルゴリズム: 主なエンジニアリング上の貢献は、時間計算量 $O(n \cdot 4^n)$ を維持しつつ、疎な入力に対するピークメモリ使用量をフル演算子サイズから独立させたライブラリ paulikit である。これにより、利用可能なRAMの容量を大幅に超えるヒルベルト空間次元を持つ演算子の分解が可能となった。
4. 厳密な検証と境界: 著者らは、全項にわたる徹底的な正当性チェック（最大 $1.47 \times 10^9$ 項）を行い、理論的な Work-Span およびメモリ帯域幅の天井を導出した。これらの境界値は、特定のローエンドLinuxプラットフォーム上での実測値によって検証されている。

結果

• スケーラビリティ: アルゴリズムは、完全に結合した（fully coupled）調和振動子ネットワークを用いてテストされた。$N=150$ の振動子（14量子ビットが必要、ヒルベルト空間次元 $2^{14} = 16,384$）において、演算子は $91,652,096$ 個の非ゼロ・パウリ項を持っていた。この規模でのナイーブな密行列アプローチは数GiBを要し、ラップトップのメモリ範囲内である。
• メモリ効率: 疎な入力に対するストリーミングにおいて、生存する項の数が$1165$倍増加した際（$N=50$から$N=300$）、paulikitの分解メモリ使用量は13.2 MiBから46.0 MiBへ、プロセス全体のピークRSSは64.7 MiBから99.6 MiBへと、非常に限定的な増加に留まった。これは、メモリ使用量が結果のサイズ（$N=300$では生存トリプルだけで約44 GiB、フル密行列では64 GiBに達する）からデカップルされていることを示している。
• パフォーマンス: 4コアのプラットフォームにおいて、スレッド化された実装は $1.81\times$（2ワーカー）および $3.36\times$（4ワーカー）のスピードアップを達成し、実測されたシリアル分から導出されたアムダールの法則の予測と密接に一致した。コンパイル済みカーネルは $1.34$GFLOPs/s のスループットを達成し、カーネルがメモリ制限的（プラットフォームの持続的な帯域幅天井の約$34%$ で動作）であることを裏付けた。
• 正当性: すべての係数は、独立した射影法によって検証され、最大絶対誤差は $8.7 \times 10^{-19}$ であり、マシン精度と一致した。

意義と主張
本論文は、その主要な貢献は漸近的な時間計算量の削減（依然として $O(n \cdot 4^n)$ であり、先行研究と同等）ではなく、メモリのスケーラビリティにあると控えめに主張している。意義は、メモリ制約のためにこれまでアクセス不可能であった大規模かつ疎な演算子のパウリ分解を可能にした点にある。

• 理論的範囲: 本研究は、「真の」パウリ基底が $(\mathbb{Z}_2)^n \times (\mathbb{Z}_2)^n$ の中央拡大内における位相慣習であることを確立し、文字論的アプローチが（系として）クディットへ自然に拡張できることを示している。
• 実用的範囲: paulikit ライブラリは、非エルミート演算子（第一級の入力として扱う）や、大規模な疎ハミルトニアンを、スーパーコンピューティング資源を必要とせずに分解することを可能にする。
• 限界: 著者らは、係数抽出はクディットへと持ち上げられるものの、クリフォード・トウィリング（Clifford twirling）の設計特性（例：2-design）は、合成次元へと自動的には持ち上げられないことを明記している。本論文は、クディットに対するクリフォード・トウィリングの問題を解決するものではなく、またクディット用のモジュールを提供することも目的としていない。また、パフォーマンスの境界はテストされた特定のハードウェアに特化したものであり、あらゆるレジームにおける他の実装に対する普遍的な優位性を主張するものではない。

要約すると、本論文は、理論的な $O(n \cdot 4^n)$ の複雑さと、大規模な量子シミュレーションにおける実用的な制約との間の溝を埋める、理論的に裏付けられたメモリ効率の高いパウリ分解の実装を提示している。