Exact Diagonal Completion on Reachable Subspaces: Application to QAOA Placement

技術要約：到達可能部分空間における正確な対角成分補完：QAOA配置への適用

問題定義

量子回路は、アルゴリズムが小さな到達可能部分空間に限定されている場合でも、全ヒルベルト空間上で定義された演算子から合成されることがよくあります。対角コスト演算子の場合、到達不能な計算基底に対応するエントリは、理想的なアルゴリズムの出力に影響を与えません。しかし、これら「未指定」の対角成分の選択は、コンパイルの機会を構成します。同じ要求される作用を持つ異なる「正確な拡張（exact extensions）」は、異なるウォルシュスペクトル、ひいては異なる回路コスト（ゲート数）をもたらす可能性があります。本論文では、回路配置問題（回路セルを物理サイトに割り当て、相互接続長を最小化すること）に適用される量子近似最適化アルゴリズム（QAOA）に焦点を当て、「正確な対角成分補完（exact diagonal completion）」問題を調査しています。

手法

著者らは、回路合成を適用する前に、距離演算子（マンハッタン距離）の未指定のエントリを最適化するためのフレームワークを提案しています。

1. エンコーディングと到達可能部分空間:

   • ワンホット・エンコーディング（One-hot Encoding）: 行の励起を保存するXYミキサー（完全結合またはリング型）を使用し、$nm$ 個の量子ビットを使用します。
   • トークン置換エンコーディング（Token Permutation Encoding）: $n$ 個の実セルレジスタと、$m-n$ 個の区別可能な「EMPTY（空）」トークンレジスタ（各サイズ $k = \lceil \log_2 m \rceil$）を使用します。このエンコーディングは、レジスタのスワップ（フレドキンゲート）を介して有効なサイトラベルの置換を保存し、測定されるすべての配置が合法であることを保証します。トークン回路は、未使用のトークン数が増えると、ワンホットよりも少ない量子ビット数で済むという利点が消失または逆転する場合があるため（例：4セル・16サイトの場合、トークン回路は65量子ビットに対し、ワンホットは64量子ビット）、$mk+1 < nm$ の場合にのみワンホットより少ない量子ビットを使用します。

2. 正確な対角成分補完:

   • 距離演算子は、回路コストを最小化するために、無効なバイナリコード（未使用のラベル）へと拡張されます。
   • 重み付き $\ell_1$ 補完 (L1): 著者らは、すべての有効なサイトペアに対してマンハッタン距離に一致することを条件として、重み付き $\ell_1$ ノルム（スパース性のサロゲート）を最小化するウォルシュ係数 $c_j$ を求める線形計画法（LP）を定式化します。これは「重み付き基底追求（weighted basis pursuit）」のアプローチです。
   • 構造化再帰（Structured Recurrence）: 正則な座標インデックス配列に対して、高密度なLPを解くことなく正確な距離位相を構築するためのスパースな再帰関係が導出されており、バランスの取れた矩形に対しては $O(\sqrt{m})$ 項のみを必要とします。

3. 合成戦略:

   • 得られたウォルシュ係数は、**グレイ合成（Gray synthesis）**を用いて回路へと合成されます。これは、項を最高次量子ビットごとにグループ化し、隣接するCNOT (CX) ゲートのキャンセルを最大化するように、反射グレイ符号の順序で制御マスクを走査する手法です。
   • ゼロパディング、仮想座標拡張、最近傍コード拡張、平均充填拡張、および汎用的な対角合成手法（Qiskit, PyZX）との比較が行われます。

4. 実験設計:

   • コホート: 160のジオメトリ（100の初期値、60の複製）を用い、4つのセルと変動するサイト数（$m=6, 8, 9, 12, 16$）を対象とします。
   • 指標: CXゲート数、回路の深さ、および配置の品質（最適確率、期待される最良コスト）。
   • 統合: 選択されたQAOA配置をOpenROAD物理設計フローに統合し、合法性とダウンストリームの実現可能性を検証する別個の研究が行われています。

主な貢献

1. 正確なマンハッタン距離位相の構築: 著者らは、重み付き $\ell_1$ 線形計画法とスパースな座標再帰を用いて、正確な距離位相を構築します。彼らは、これらの構築が、割り当てられた値に関わらず、すべての到達可能状態において要求される作用と一致することを証明しています。
2. 合成依存のゲート節約: 160のジオメトリにおいて、グレイ合成の下では、L1補完は未使用のバイナリコードが存在する全96ケースにおいて、4つの代替拡張に対してCX数を削減しました。しかし、本論文は、これらの利得が合成手法に強く依存していることを強調しています。汎用的な対角合成を用いた場合、削減率は大幅に低下します（例：9サイトにおいて53.9%から1.3%へ）。
3. フル回路のリソース分析: 位相の節約が回路全体に与える影響を評価します。L1補完は位相成分のゲート数を削減しますが、全体的なリソースの優位性はミキサーの深さとシリアル化によって制限されます。並列ミキシングはトークン回路の深さを減少させますが、総深さやゲート数においてワンホットのベースラインを一貫して上回ることはありません。
4. 配置の品質と統合: 理想的なシミュレーションではベースライン依存の解の質が見られ、テストされた小規模なインスタンスでは古典的な探索がQAQAを上回ることが多いです。しかし、本論文は具体的な統合パスを示しており、6つのRTL設計から得られた72のQAOA生成ローカル配置が、オーバーフローゼロでOpenROADのクロックツリー合成およびグローバルルーティングを通過することに成功しました。

結果

• ゲート削減: グレイ合成の下で、L1補完は、6, 9, 12サイトに対して、仮想座標拡張と比較して、中央値でそれぞれ28.0%、53.9%、21.6%のCX削減を達成しました。
• 合成の感度: 汎用的な対角合成（固定角）を使用する場合、L1補完の利点は劇的に減退します（例：10.9%、1.3%、0.7%の削減）。これは、その恩恵がコンパイラに依存しないものではないことを示しています。
• リソースのトレードオフ: L1補完を用いたトークン回路は、未使用のトークン数が少ない場合にのみ、ワンホットよりも少ないデータ量子ビットを使用します。空き容量が増えると、幅の利点が失われるか逆転します（例：4セル/16サイトでは、65量子ビット vs 64量子ビット）。さらに、トークン回路はスワップネットワークにより回路が深くなる傾向があります。スワップの並列化は深さを約20-24%減少させますが、ワンホットエンコーディングに対して普遍的なリソース上の優位性を確立するには至りません。
• 解の品質: 一致した回路コストにおいて、トークンエンコーディングは一部の4セルケースでワンホットのベースラインよりも高い最適確率を示しますが、この優位性はより大きなサイズ（5-6セル）や異なる学習レジームでは一貫して保持されません。古典的なマルチスタート・グリーディ探索は、テストされたインスタンスにおいてQAOAよりも一貫して優れた解を見つけます。
• ダウンストリームの実現可能性: OpenROADの研究における72のQAOA配置および216の古典的配置はすべて、ゼロのオーバーフローでクロックツリー合成とグローバルルーティングを完了し、生成された配置の合法性を検証しました。

意義と主張

本論文は、正確な対角成分補完が、理想的なアルゴリズムの挙動を変えることなく実装コストを削減できる、実行可能な回路設計上の決定であることを控えめに主張しています。著者らは以下を強調しています：

• 自由度は存在するが、文脈依存である: 未指定の対角成分を選択できる能力は、最適化の真の機会を提供しますが、その恩恵の大きさは合成手法および特定のエンコーディングと密接に結びついています。
• エンドツーエンドの優位性は確立されていない: 位相の構築は改善されていますが、本論文は配置における量子優位性を確立したものではありません。フル回路の結果は、ミキサーのコスト、接続性、および変分回路の学習の難しさが、しばしば位相レベルの節約を打ち消してしまうことを示しています。
• 統合パス: 主要な実用的な貢献は、QAOAが標準的な電子設計自動化（EDA）フローと互換性のある、合法かつ高品質なローカル配置を生成できることを示した点にあります。たとえ量子ソルバーがこれらの小規模なインスタンスにおいて古典的なヒューリスティックをまだ上回っていないとしても、です。

本研究は、制約された量子アプリケーション（配置）内における、特定のコンパイル技術（補完）の厳密な評価として機能しており、理論的な演算子の簡略化と、実用的な量子リソース削減との間のギャップを明らかにしています。