Faster algorithm for achieving minimal-size quantum decision diagrams

技術要約：最小サイズ量子決定図を実現するための高速アルゴリズム

問題提起
決定図（Decision Diagrams: DDs）は、等価な部分関数を標準形へとマージすることで簡潔性を達成し、量子状態や演算を表現するためのコンパクトなデータ構造である。Local Invertible Map Decision Diagrams (LIMDDs) は、特定の回路クラス（例：クリフォード回路）に対して、Quantum Multiple-Valued Decision Diagrams (QMDDs) などの他の構造よりも理論的な指数関数的優位性を提供するが、既存の実装ではこれらの利点が十分に発揮されていない。

主なボトルネックは、標準化の手順、特に標準性を保証するために必要な**高決定性ルール（high determinism rule）**にある。このルールは、2つのノードが局所的可逆写像（LIM）の範囲内で同一の量子状態を表す際の自由度を解決するものである。群論的なタスクに基づく既存のアルゴリズムは、$n$ クビットのノードに対して $O(n^3)$ の最悪時間計算量を要する。さらに、既存のオープンソース実装（MQT-LIMDD および LimTDD）は、すべてのケースで最小サイズを実現できていないか、あるいは実装の複雑さを避けるために標準性の特性を意図的に省略しており、その結果、ノード数の指数関数的な増大を招く可能性がある。

手法
著者らは、セミ還元された Pauli-LIMDD ノードを完全還元された（標準的な）形式に変換するための、特に高決定性ルールを最適化する新しいアルゴリズムを提案している。

1. アルゴリズムの改善:

   • 著者らは、高決定性に必要な最小化問題を解決するために、ベクトル空間の共通部分と和集合を計算する手法である**ザッセンハウス法（Zassenhaus procedure）**を適応させている。
   • スタビライザー群の共通部分と余剰類を個別に計算する代わりに、Pauli ワードを表すバイナリベクトル、中間スタビライザー、および右スタビライザーの3つのレジスタを持つ「ザッセンハウス行列」を構築する。
   • Pauli-LIM 乗法規則を用いてこの行列に対してガウス消去法を実行することにより、最小の Pauli ワードと対応するスタビライザー生成元を同時に求める。
   • 計算量の削減:
     • 2つの異なる子を持つノードの場合、アルゴリズムは $O(n^3)$ の最悪計算量を維持するが、オーバーヘッドは軽減される。
     • 単一の子を持つノード（DDが簡潔性を達成する一般的なケース）の場合、問題は単一のスタビライザー群に対するベクトルの最小化へと簡略化される。これにより、計算量は $O(n^3)$ から $O(n^2)$ へと減少する。

2. 再帰的スタビライザー探索:

   • 著者らは、ザッセンハウスの結果を用いて、還元されたノードのスタビライザー生成集合を計算するための再帰的アルゴリズムを提示している。これにより、冗長な群の共通部分の計算を回避し、$O(n^2)$ のケースをさらに最適化している。

3. 実装 (QolDDer):

   • このアルゴリズムは、C/C++ で記述された新しいゼロベースの Pauli-LIMDD シミュレータである QolDDer に実装されている。
   • QolDDer には、コアとなる正規化ロジックのための独立したライブラリ PauliLim が含まれている。
   • この実装は、浮動小数点スカラーを構成可能な閾値（$\delta = 10^{-13}$）を用いて扱うことで数値精度を処理し、検索ツリーを使用して等価性チェックを行いながら、標準性を維持している。

主な結果
著者らは、QolDDer を 2 つの既存の LIMDD 実装（MQT-LIMDD、LimTDD）および QMDD シミュレータ（MQT-DDSIM）と比較評価した。評価には RandCliff（ランダム・クリフォード）および MQT-Bench データセットを用いた。

• クリフォード回路における指数関数的な高速化: ランダム・クリフォード回路（RandCliff）において、QolDDer は QMDD (MGT-DDSIM) に対して指数関数的な高速化を示している。これは、QMDD では高度に絡み合った状態を簡潔に表現できないのに対し、LIMDD がクリフォード回路の出力を多項式空間で表現できるという理論的優位性を裏付けるものである。
• 標準性の影響:
  • QolDDer で完全な標準性（高決定性）を有効にすると、クリフォード回路において、セミ還元（非標準）バージョンと比較して実行時間が大幅に短縮され、ノード数が劇的に減少する。
  • QolDDer は、MQT-LIMDD の部分的な標準性実装に起因する性能差により、多くのインスタンスにおいて MQT-LIMDD よりも 桁違いに高速である。
  • QolDDer は、標準性の保証を欠く LimTDD よりも、標準化によるノード数の削減を通じて、クリフォード回路において一貫して高速であり、しばしば 25 倍以上の差が生じる。
• 一般的なベンチマークにおける限界: 広範な MQT-Bench データセットにおいては、標準性の優位性が普遍的ではない。特定の回路タイプ（例：量子ニューラルネットワーク、グローバーのアルゴリズム）では、LIM は QMDD よりも多くのマージングを提供せず、標準性を維持するためのオーバーヘッドにより、QolDDer は MQT-DDSIM よりもわずかに遅くなる。ただし、スケーリングは線形のままである。

意義と主張
本論文は、LIMDD の理論的な力を実現する上での主要な障壁は、効率的かつ完全に標準的な実装の欠如であったと主張している。$O(n^2)$ のアルゴリズム（重要な単一子ケースに対して）と堅牢なオープンソース実装（QolDDer）を提供することで、著者らは以下を実証している：

1. LIMDD は、特定の重要な回路クラス（クリフォード回路）において、確かに QMDD に対する指数関数的な優位性を達成できる。
2. 標準性は不可欠である。 標準性がなければ、ノード数が膨れ上がり、データ構造の利点が打ち消されてしまう。
3. 本研究は、量子設計タスクおよび一般的な線形代数ベースのシステム解析の両方に対する、より広範な LIMDD 変体の開発を可能にするものである。

著者らは一般的なベンチマークについては慎重な姿勢を崩しておらず、LIM が QMDD よりも追加のマージングを提供しない回路においては、標準化のオーバーヘッドが正当化されない可能性があると述べている。今後の展望として、これらのアルゴリズムをより広い XP 群へと拡張し、回路等価性チェックや古典的な線形代数の問題に LIMDD を適用することが想定されている。