技術要約：2D格子における交換ゲートの効率的な回路トランスパイル

問題提起

最大カット（MC）や最大独立集合（MIS）といった組合せ最適化問題は、多くのアプリケーションにおいて中心的である一方、多くの場合NP完全である。量子近似最適化アルゴリズム（QAOA）は、これらの問題をハミルトニアンにマッピングすることで、量子的なアプローチを提供する。しかし、実用的なデジタル量子コンピュータへの実装は、限定的なハードウェア結合性による大きな障壁に直面している。

問題ハミルトニアン $H_C$ は通常、多くの量子ビットペア間の相互作用を誘発する。2D格子のような制限された結合性を持つハードウェアでは、これらの非隣接な相互作用を実現するために、量子ビットを隣接位置へとルーティングするためのSWAPゲートを使用しなければならない。このルーティングプロセスは、回路の深さと累積誤差を増大させ、量子アルゴリズムの利点を打ち消してしまうことが多い。Qiskitなどの標準的なトランスパイル手法（ランダムな初期マッピングや固定されたルーティングを使用するもの）は、特に疎な相互作用グラフに対して、しばしば最適とは言えない回路を生成する。さらに、完全結合グラフ向けに設計された既定のSWAPネットワークは、疎なコスト・ハミルトニアンに対しては非効率的である。

手法

著者らは、2次元（2D）格子ハードウェア上で、交換（commuting）する2量子ビットゲートのブロックで構成される回路（典型的なQAOAの性質）のために特別に設計されたトランスパイル・スキームを提案している。コアとなる手法は、問題依存のSWAPレイヤー・シーケンスの構築と、量子ビット・レイアウトの更新を交互に行うことである。

論文では、いくつかの戦略を導入し、比較を行っている：

1. 線形戦略 ($S_{line}, C_{line}^{grid}$): 2D格子を1Dの直線として扱う、最先端のベースライン。SWAPレイヤーは、グリッド内の最も長い線の偶数エッジと奇数エッジの間で交互に切り替わる。
2. ハイブリッド戦略 ($S_{line}, C_{grid}$): 線形戦略の修正版であり、線ベースのSWAPルーティングを適用するが、基礎となるSWAPネットワークを変更することなく、利用可能な2D格子のエッジを利用して $R_{ZZ}$ ゲート（相互作用）を直接適用する。
3. グリッド戦略 ($S_{grid}, C_{grid}$): 2Dの結合性を最大限に活用するために、水平および垂直のSWAPを交互に適用する、調整された基底集合 ($B_{grid}$) を利用する戦略。
4. 貪欲な問題依存戦略 ($S_{greedy}, C_{grid}$): 著者らの主要な貢献である。この手法は、問題インスタンスの特定のコスト・ハミルトニアンに合わせて、SWAPシーケンスと初期量子ビット・マッピングをカスタマイズするために、貪欲探索アルゴリズムを採用している。
   • 内側ループ: 到達可能な量子ビット構成のツリーを探索するために、深さ優先探索（DFS）を使用する。これは、必要なすべての相互作用を実装するための最短のSWAPレイヤーの経路を探索する。複雑さを管理するため、探索は最大深度 $k_{max}$ に達するまで制限され、その後、最適な部分シーケンスを選択して継続する。
   • 外側ループ: SATベースのマッピングソルバーを用いて、初期量子ビット・マッピング ($\pi_0$) を反復的に更新する。現在のSWAPシーケンス長が参照長を超えた場合、アルゴリズムは、より短いシーケンスを見つける可能性を持たせるために、新しい初期マッピングを用いて探索をリセットする。
   • 基底集合: 探索には、回路の深さを削減するために標準的なグリッド基底を超えた追加のSWAPレイヤーを含む、拡張基底集合 ($B_{extended}^{grid}$) が使用される。

主な貢献

1. 問題依存のトランスパイル: 本論文は、固定された問題に依存しないネットワークに頼るのではなく、最適化問題の特定の相互作用グラフに合わせて、SWAP戦略と初期マッピングを動的に構築する貪欲アルゴリズムを導入している。
2. ハイブリッド・ベースライン: 線形SWAPバックボーンを維持しながら、2Dグリッドのエッジを相互作用のために利用するハイブリッド戦略を提案し、中間的なベースラインとして提示している。
3. スケーラビリティ分析: グリッドベースの戦略、特に貪欲なアプローチが、疎なグラフに対して、線形戦略が $O(n)$ でスケールするのに対し、回路の複雑性の指標（SWAPレイヤー、深さ、ゲート数）において漸近的な $O(\sqrt{n})$ の改善を達成することを、理論的および経験的に実証している。
4. ハードウェア検証: 最大80量子ビットまでの問題について、IBMの矩形格子ハードウェア上でのQAOA回路の実行を行い、シミュレーション結果を検証した。

結果

著者らは、ランダム・レギュラー（RR）グラフ（次数 $d=3$）におけるMCインスタンスと、エルデシュ・レーニ（ER）グラフ（エッジ確率 $q=0.08$）におけるMISインスタンスを用いてベンチマークを行った。

• 回路の複雑性: 標準的な手法（線形戦略およびQiskitのSABREトランスパイラを含む）と比較して、貪欲戦略は、疎なグラフにおいて回路の深さと2量子ビットゲート数を約半分に削減した。
  • RRグラフでは、線形戦略ではSWAPレイヤー数、深さ、CZゲートがそれぞれ $n, n, n^2$ でスケールしたが、貪欲戦略はより低い定数と優れたスケーリング挙動を維持した。
  • ERグラフでは、貪欲戦略は線形戦略を大幅に上回り、CZゲート数は線形戦略の $O(n^3)$ に対して $O(n^{5/2})$ でスケールした。
• 実現可能領域: ゲート数の削減により、ノイズのあるハードウェアにおける実現可能な問題サイズが拡大した。固定されたCZゲート予算（例：3,600ゲート）において、貪欲戦略は最大100ノードのインスタンスの実行を可能にしたのに対し、線形戦略は約60ノードに制限された。
• 近似比: ハードウェア実験は、性能向上を示した：
  • 最大カット (MC): 貪欲戦略は、72量子ビットにおいて、線形戦略と比較して平均近似比を最大 6.62% 向上させた。
  • 最大独立集合 (MIS): 改善はさらに顕著であり、56量子ビットにおいて 9.32% に達した。
• 切り捨ての比較: 理論的な保証を犠牲にして深さを減らすためにコスト・ハミルトニアンを切り捨てるアプローチとは異なり、貪欲戦略は、同じ数のSWAPレイヤーに対して、より大きなサブセットのターゲット相互作用を実装し、より多くの問題構造を保持した。

意義と主張

論文は、実用的なノイズのあるハードウェア上でQAOAを機能させるためには、効率的なトランスパイルが極めて重要であると主張している。著者らは、問題を認識したトランスパイル・スキームが、特に疎な最適化問題において、量子アルゴリズムの性能を向上させる鍵であると断言している。

意義に関する主な主張は以下の通りである：

• より大規模な実験の実現: この手法は、回路の深さと誤差の蓄積を減少させることで、現在のハードウェア上で最大80量子ビットまでの実験を可能にする。
• ハードウェアの改善の増幅: ハードウェアの品質が向上し（利用可能なCZゲート予算が増加し）、効率的なトランスパイルの恩恵は増幅される。貪欲戦略は、ゲート予算が増えるにつれて、線形戦略と比較して、より大きな問題サイズの拡大を可能にする。
• 量子優位性への関連性: このアプローチは、古典的なソルバーが苦戦する困難な領域（例：低密度MISインスタンス、500ノード）を含む、潜在的な量子優位性の領域を調査することに特に適している。
• 将来への備え: 本研究は、エラー訂正コード（二変量バイサイクルコードなど）が矩形格子に基づいた構造的かつ非局所的な結合性を必要とする中で、2D結合性を活用するようにトランスパイル戦略を適応させることが、将来のアーキテクチャにおける回路の複雑さを軽減するために不可なるものであることを強調している。

著者らは、彼らの手法が既定のSWAPレイヤーに依存しているものの、問題認識型のトランスパイルが、理論的な量子アルゴリズムと実用的なノイズのあるハードウェア実行との間のギャップを埋めるために必要不可欠なステップであることを示している、と結論づけている。