Optimizing QAOA circuit transpilation with parity twine and SWAP network encodings

技術要約：Parity Twine と SWAP ネットワーク・エンコーディングによる QAOA 回路トランスパイルの最適化

問題提起
現在の超伝導量子プロセッサ（QPU）は、限定的な量子ビット結合性に苦しんでおり、通常、特定のトポロジー（例：heavy-hex 格子）上の近接隣接相互作用に制限されています。QAOA（Quantum Approximate Optimization Algorithm）のようなアルゴリズムの実行には、しばしば完全結合または高密度な二量子ビット相互作用を必要とするため、トランスパイル（コンパイル）プロセスが必要となります。このプロセスでは、論理量子ビットを物理量子ビットにマッピングし、結合性の制約を満たすために SWAP ゲートを挿入します。しかし、SWAP ゲートは複数の二量子ビットゲート（例：3つの CNOT）に分解されるため、これらが近未来型のデバイスにおけるノイズとエラーの主要な原因となります。SWAP ネットワークや Parity Twine Chains (PTC) のような構造化されたエンコーディングは、完全結合グラフに対して解析的なリソース上の利点を提供しますが、疎な結合を持つグラフ（非完全結合グラフ）への適用は依然として最適ではありません。さらに、ゲート数を最小化するための最適な初期量子ビットマッピングを見つけること（部分グラフ同型問題）は NP 困難であり、SATMapper のような既存のソルバーは、大規模なシステムにおけるスケーラビリティと実行時間の面で限界があります。

手法
著者らは、構造化エンコーディング戦略と、初期の論理対物理量子ビットのマッピングを最適化するためのシミュレーテッド・アニーリング（SA）ヒューリスティックを組み合わせたハイブリッド・アプローチを提案しています。

1. エンコーディング:

   • SWAP ネットワーク: 1次元鎖上の構造化されたルーティング・スケジュールであり、交互に配置された近接隣接 SWAP ゲートのレイヤーによって、論理量子ビットを移動させ、必要な隣接関係を作成します。
   • Parity Twine Chains (PTC): 多量子ビットの Z 情報（Z-information）を、パリティを通じて単一の物理量子ビットにエンコードする方法です。これにより、非局所的な相互作用をローカルな単一量子ビット回転（$R_Z$）として実行できるようになり、SWAP ネットワークと比較して二量子ビットゲート数を削減できます。この手法は、パリティ基底で測定を行い、古典的な後処理によって論理ビット列を復元するデコーディング戦略を利用しており、計算基底に戻るための追加の CNOT ゲートを必要としません。

2. シミュレーテッド・アニーリング (SA) 最適化:

   • 著者らは、SWAP および PTC エンコーディングの両方に対して、部分グラフ同型問題を解くための SA ベースのアルゴリズムを導入しています。
   • コスト関数: コスト関数は組合せ的かつ非平滑であり、回路から削除（プルーニング）可能な二量子ビットゲートの数を評価します。これは、マップされた量子ビットペアがハードウェアの結合グラフのネイティブなエッジに対応しているかどうかを、レイヤーごとにチェックします。もし要求される相互作用が問題グラフに存在しない場合、エンコーディング・スケジュールの対応するゲートは省略されます。
   • プロセス: アルゴリズムは、量子ビットラベルのペアを反復的に入れ替えることで、総二量子ビットゲート数と回路の深さを最小化する置換を見つけ出します。このアプローチは、離散的な探索空間に対して勾配ベースの手法が不適切であり、厳密な手法が計算量的に困難であるために選択されました。

3. ベンチマークとノイズモデリング:

   • 本手法は、標準的なトランスパイラ（Qiskit-T, Qiskit-P, Qiskit-AI, TKET）および SATMapper と比較検証されています。
   • ノイズシミュレーションでは、Weighted MaxCut (WMC) 問題に対する Linear Ramp QAOA (LR-QAOA) プロトコル内の二量子ビットゲートに作用するデポーラリジング・ノイズモデルを使用しています。
   • 実験的検証は、IBM 量子デバイス（ibm_fez および ibm_kingston）を用いて行われています。

主な貢献

• SA 最適化されたエンコーディング: 非完全結合グラフを特にターゲットとした、SWAP および PTC エンコーディングのための初期量子ビット順序を最適化するシミュレーテッド・アニーリング戦略の導入。
• スケーラビリティ: SA アプローチが、（シミュレーションにおいて）最大 200 量子ビットまで効果的にスケールし、SATMapper に対して数桁の実行時間の優位性を提供しつつ、同等の解の質を実現できることを実証。
• PTC デコーディング: 計算基底に戻るための回路の深さを増大させる CNOT ゲートを不要にする、PTC のデコーディング戦略の詳細な記述。
• 実験的検証: 実機量子ハードウェア上での PTC エンコーディングの最初の実験的実装。

結果

• ゲート数と深さの削減: エッジ密度 ($E_d$) が特定の閾値を超える QAOA 回路において、PTC+SA および SWAP+SA は標準的なトランスパイラを大幅に上回ります。
  • 接続性が 25% である 120 量子ビットのインスタンスにおいて、提案手法は Qiskit トランスパイラ（最適化レベル 3）と比較して、回路の深さを 87% 削減し、二量子ビットゲート数を 29% 削減しました。
  • PTC+SA が Qiskit-T をゲート数で上回る閾値は、システムサイズが増加するにつれて減少します（20 量子ビットでは $E_d \approx 0.35$、120 量子ビットでは $E_d \approx 0.13$）。
• 実行効率: SA メソッドは、200 量子ビットの問題に対して数秒で高品質な解に収束しますが、SATMapper は数百から数千秒を要します。
• ノイズ耐性:
  • シミュレーション: ノイズシミュレーションにおいて、PTC はゲート数が少ないため、低〜中程度のノイズレベルにおいて SWAP よりも高い成功確率 ($p_{gs}$) を示しましたが、近似比 ($r$) は両者とも同様でした。
  • 実機ハードウェア (ibm_fez): PTC エンコーディングは、有用な LR-QAOA 実験の範囲を拡張しました。PTC を使用した場合、問題サイズは最大 20 量子ビットまで最適解が見つかりました（SWAP では 15 量子ビットまで）。ランダムサンプリングとの区別は、PTC では 22 量子ビットまで、SWAP では 20 量子ビットまで維持されました。
  • 実機ハードウェア (ibm_kingston): $E_d = 0.298$ の 20 量子ビット問題において、SWAP+SA は最良の近似比（ランダムに対して 20.83% の改善）を達成し、PTC+SA（13.99%）を上回りました。著者らは、PTC はゲート数は少ないものの、非完全結合シナリオにおける単一の物理量子ビットへの論理ペアのエンコーディングが、ノイズ蓄積に対してより敏感である可能性があると指摘しています。
• トランスパイラ比較: 標準的なトランスパイラ（Qiskit-T など）は、しばしば回路の深さを大幅に増大させることでゲート数を最小化しようとしますが、これはノイズを悪化させます。提案手法は、より低い深さを持つコンパクトな回路を維持します。

意義と主張
本論文は、減少した量子ビット結合性を伴うシナリオにおいて、標準的なトランスパイラ手法を SWAP および PTC エンコーディングが上回ることを示した最初のデモンストレーションであると主張しています。また、これは PTC エンコーディングの最初の実験的実装でもあります。

著者らは、構造化されたエンコーディングが完全結合グラフに対してはよく知られている一方で、提案された SA ベースの最適化を介して部分結合グラフに適用することで、大幅なリソース削減が得られることを強調しています。結論として、20 量子ビットまでのシステムにおいて、PTC エンコーディングは実機ハードウェア上での性能を向上させ、LR-QAOA の実行可能な問題サイズを拡張すると述べています。しかし、非完全結合の実験（ibm_kingston）において、SWAP+SA が時として PTC+SA を上回ったことを謙虚に認め、ゲート数とノイズ感受性のトレードオフは、エンコーディング構造と問題のトポロジーに強く依存することを示唆しています。本研究は、オーバーヘッドを削減して、結合性に制約のある近未来型のデバイス上で QAOA を実行するための実用的な経路を確立するものです。