An efficient Pauli decomposition algorithm for structured matrices

技術要約：構造化行列のための効率的なパウリ分解アルゴリズム

問題設定
古典的な $2^n \times 2^n$ 行列をパウリ文字列の線形結合へと分解することは、近未来の量子アルゴリズム（特に量子化学、機械学習、金融分野）のエンドツーエンドの実装における重要なボトルネックとなっている。VQE（変分量子固有値ソルバー）や線形代数ソルバーなどの多くのアルゴリズムは、入力データがパウリ文字列のLCU（Unitaryの線形結合）として提供されることを前提としている。しかし、一般的な古典的に指定された行列に対しては、このような分解法はあらかじめ既知ではない。

既存のアルゴリズムは、一般的な密行列に対して指数関数的にスケールする。最も単純なアプローチは $O(32^n)$ の時間を必要とし、PennyLaneなどの既存の最良の手法（例）は $O(n4^n)$ でスケールする。この指数関数的なコストは、最悪の場合、行列がすべての $4^n$ 個のパウリ基底要素にサポートを持つ可能性があり、すべての係数を復元する必要があることに起因する。

本論文は、パウリ分解問題のプロミス（約束）版に対処する。これは、入力行列 $M$ が $k = \text{poly}(n)$ 個のパウリ文字列にのみサポートを持つことが保証されていると仮定するものである。さらに、行列は古典的疎クエリモデルを介してアクセスされるものとする。ここで、アルゴリズムはフルサイズの $2^n \times 2^n$ 行列をメモリ上に構築することなく、特定の行または列の非ゼロ成分を取得できる。目標は、$n, k, \log(1/\delta)$ に対して多項式時間のリソースを用いて、正確なパウリ分解（パウリ文字列の集合とその係数）を高確率で復元することである。

手法
著者らは、パウリ文字列のバイナリ・シンプレクティック形式の構造と、約束された疎性（$k$）を利用するランダム化された古典アルゴリズムを提案している。アルゴリズムは、問題を以下の3つの主要なステージに分解する：

1. 活性なパウリX部分 ($x$) の発見：
   行インデックス $v$、列インデックス $u$、およびパウリX部分 $x$ を $x = u \oplus v$ によって関連付けるLemma 1を用い、アルゴリズムは行列のランダムな行をクエリする。非ゼロ成分の列インデックスを収集し、それらを行インデックスとXORすることで、分解に含まれる異なる $x$ ビット文字列の集合 $X$ を特定する。このステップは、ランダムなクエリが活性な $x$ 文字列を高確率で明らかにするという、ブール不確定性原理（Fact 1）に基づいている。

2. 一意な $x$ 文字列のデコーディング：
   発見された各 $x$ について、それが「一意」であるか（すなわち、ちょうど一つのパウリ文字列に関連付けられている、$p_x = 1$）をチェックする。一意である場合、クエリ関数 $b_x(u) = M_{x \oplus u, u}$ は単一のウォルシュ特性 $\beta_x(z)(-1)^{z \cdot u}$ に簡略化される。アルゴリズムは、ゼロベクトルおよび標準基底ベクトルを評価することで、関連するパウリZ部分 $z$ と係数 $\beta$ を復元する。候補となる解が、クエリされた点と偶然一致しただけの退化的なケースではないことを確認するために、ランダムな入力を用いた認証ステップを行う。

3. 退化的な $x$ 文字列のデコーディング：
   $x$ が「退化的」（複数のパウリ文字列、すなわち $p_x \geq 2$ に関連付けられている）である場合、問題は疎なウォルシュ・アダマール・スペクトルの復元へと還元される。アルゴリズムは、**ランダム・フォールディング（ランダムな折り畳み）**技術を採用する：

   • $n$ ビットのスペクトルインデックス ($z$) を、ランダムなバイナリ行列 $R$ を用いて $m$ ビットのビン（箱）へとマッピングする（ここで $m \ll n$）。
   • この「フォールディング」により、高い確率で個々の $z$ 文字列を「シングルトン・ビン」へと隔離する。
   • シングルトン・ビンに対しては、シフトされたクエリを用いて $z$ 文字列のビットとその係数を決定する。
   • 復元された項を残差関数から減算し、すべての項が見つかるまでプロセスを繰り返す。
   • 最終的なランダム検証により、項の漏れがないことを確認する。

主な貢献

• アルゴリズム設計： 本論文は、$k$-疎性と疎クエリ・アクセスという約束の下でパウリ分解問題を解決するランダム化された古典アルゴリズム（Algorithm 1）を提示している。
• 複雑性の改善： $n$ に対して指数関数的にスケールする既存の手法とは異なり、提案されたアルゴリズムは $n, k, \log(1/\delta)$ に対して多項式時間およびクエリ複雑性を達成している。
• 理論的保証： アルゴリズムは、ユーザーが選択した任意の $\delta \in (0, 1)$ に対して、少なくとも $1-\delta$ の確率で成功する。著者らは、各ステージ（発見、一意デコーディング、退化デコーディング）における失敗確率の厳密な境界を提供している。
• 疎なウォルシュ・アダマール技術： 本研究は、ランダム・フォールディングとシフトベースのビット復元を利用して、ブール立方体における疎な復元技術（特に疎なウォルシュ・アダマール・デコーディング）をパウリ分解の文脈に適応させたものである。

結果

• 数値ベンチマーク： 著者らは、$n = 2$ から $30$、$k = 2^n$ のランダムなインスタンスに対してアルゴリズムをテストした。
  • 小さな $n$ ($n < 10$) では、ランダム化アルゴリズムのオーバーヘッドにより、既存の PennyLane の PauliDecompose ルーチンよりも遅くなる。
  • $n=10$ 付近でクロスオーバーが発生する。$n > 10$ の場合、提案されたアルゴリズムは指数時間のベースラインを大幅に上回る性能を示す。
  • 観測された実行時間とクエリ数は $n$ に対して多項式的にスケールしており、理論的境界と一致している。
  • テストされたすべての実行において、アルゴリズムは失敗することなく完全な分解を成功裏に復元した。
• スケーラビリティ： アルゴリズムは、$n=30$ までのインスタンスを正常に処理した。これは、フル行列の構築や密な分解アルゴリズムの実行が計算量的に実行不可能になる領域である。

意義と主張
本論文は、一般的な行列に対してパウリ分解を見つけることは指数関数的に困難であるが、パウリ基底において疎であることが分かっている行列に対しては、効率的に解決可能であることを主張している。この領域は、構造化された古典的入力データ上で動作する近未来の量子アルゴリズムにとって非常に重要である。

著者らは、本アルゴリズムが $k = \text{poly}(n)$ というプロミス問題向けに特別に設計されていることを強調している。彼らは、一般的な密なケースを解決すると主張しているのではない。その意義は、パウリ分解を必要とする量子アルゴリズムのための効率的な古典的前処理を可能にし、エンドツーエンドの量子ワークフローにおける主要なボトルネックを取り除く可能性がある点にある。また、簡潔な古典的ルールによって定義される行列や、クエリ・アクセスのみが利用可能な信頼できないサーバーに保持されているデータなど、具体的な適用コンテキストも示唆している。

論文は、導出された上限値は緩い可能性があることを述べ、今後の課題として、よりタイトな境界、下限、および近似的に疎な行列への拡張を検討することを挙げており、控えめな結論で締めくくられている。