Quantum circuit partition as a maze: emerging percolation transition via path finding

本論文は、量子回路の分割を迷路切り問題として定式化する新しいフレームワークを提案しており、特にCNOTゲートの数が量子ビット数と同程度である場合に、ゲートを取り除くことなく回路を2つのCNOTクラスターに最適に分割できるかどうかが、パーコレーション相転移によって決定されることを示している。

要約

巨大で絡まり合った毛糸玉を、複雑な量子コンピュータのプログラムだと想像してみてください。あなたの目標は、この毛糸玉を真っ二つに切り、2台の異なるコンピュータがそれぞれの半分を同時に処理できるようにして、プロセスを高速化することです。しかし、一つ問題があります。この「毛糸」は、CNOTゲートと呼ばれる特別な結び目でできています。もし結び目（ノット）を切り裂いてしまうと、プログラムは壊れて停止してしまいます。あなたは、結び目を一切切ることなく、毛糸玉を切り裂く方法を見つけなければなりません。

この論文では、その問題を迷路を解くことになぞらえています。

迷路の比喩

著者らは、量子回路をビデオゲームのレベルのようなグリッド（格子状のマップ）に変えました。

• 壁： CNOTゲートは迷路の壁です。これらは通り抜けることができない固い障壁です。
• 経路： あなたは迷路の左側から右側へと線を引く（「カット」を描く）必要があります。
• ゴール： もし壁に当たることなく、左から右へと線を引くことができれば、回路を2つの独立した部分に分割することに成功したことになります。もし壁に当たってしまったら、その回路は分割すると壊れてしまうほど複雑に絡み合っているということです。

問題：「混雑した中心部」

これらの迷路を最初に構築した際、著者らはあるパターンに気づきました。壁（結び目）が、まるで都市の中心部での交通渋滞のように、迷路のちょうど真ん中に集まってしまうのです。中心部が非常に混雑しているため、壁に当たることなくそこを直進して通り抜けることは、ほぼ不可能です。

解決策：家具の配置換え（アニーリング法）

これを解決するために、著者らは**シミュレーテッド・アニーリング（焼きなまし法）**と呼ばれる巧妙なトリックを用いました。これは、迷路の行（ロウ）を並べ替えることができる、非常に賢く忍耐強いロボットのようなものです。

1. シャッフル： ロボットは「ワイヤ」（量子ビットが移動する線）の順序をシャッフルします。これは、トランプの束をシャッフルして、壁がデッキの端（上または下）に移動するかどうかを確認するようなものです。
2. 目標： ロボットは、すべての壁を中心部から遠ざけ、迷路の上端や下端へと押し出すことを試みます。
3. 結果： ロボットが成功すれば、「中央の回廊（セントラル・コリドー）」、つまり迷路の真ん中を真っ直ぐ貫く、空っぽの明るい通路が生まれます。これで、壁に一度も当たることなく、簡単に切り込みの線を引くことができるようになります。

「相転移」：ティッピングポイント（転換点）

この論文で最もエキサイティングな発見は、壁（CNOTゲート）の数とワイヤ（量子ビット）の数の関係を変化させたときに何が起こるかという点です。

彼らは、水が突然氷に変わる時のように、**ティッピングポイント（転換点）**があることを見出しました。

• 「簡単な」ゾーン： 壁の数がワイヤの数とほぼ等しい（あるいはそれ以下である）場合、ロボットはほぼ確実に迷路を再配置して、先ほどのクリアな中央回廊を作り出すことができます。この回路は**分割可能（partitionable）**です。
• 「不可能な」ゾーン： 壁があまりに多すぎる（CNOTゲートが多すぎる）場合、迷路は非常に混雑し、たとえロボットがどのように行をシャッフルしたとしても、壁があらゆる経路を塞いでしまいます。この回路は**分割不可能（non-partitionable）**です。

この、「分割できる」状態から「分割できない」状態への突然の変化は、**パーコレーション転移（浸透転移）**と呼ばれます。これは洪水のようなものです。水位がある一定の高さに達すると、水が突然湖全体を繋げてしまいます。ここでも、ゲートの密度がある一定のレベルに達すると、壁が突然迷路全体を繋ぎ合わせ、あらゆる経路を遮断してしまうのです。

なぜこれが重要なのか

この論文は単に「回路を分割するのは難しい」と言っているだけではありません。実用的なルールを提示しています。**「もし、量子ビット1つに対しておよそ1つのCNOTゲートがあれば、回路を分割できる可能性が高い」**ということです。もし量子ビットよりも多くのゲートがあるなら、おそらく分割できません。

複雑な数学の問題を「迷路解き」のゲームに変えることで、著者らは、量子回路を壊すことなく、その回路を分割して最適化できるかどうかを知るための、明確で視覚的な方法を提供しました。彼らは「迷路エージェント」（単純なコンピュータプログラム）を使用して最適な経路を見つけ出し、この「回廊」戦略が多くの種類の量子回路において有効であることを証明しました。

技術概要

技術要約：迷路としての量子回路分割：経路探索による創発的パーコレーション転移

問題提起
量子回路の最適化、特にノイズのある中規模量子（NISQ）デバイスにおいては、二量子ビットゲート（通常はCNOTゲート）の数を削減することが主要な目標となる。これは、CNOTゲートが顕著なノイズの影響を与えるためである。回路の分割は、複数のデバイス間での並列最適化を可能にするが、既存のアプローチは多くの場合、中間回路測定や量子ビットのリセットを用いてCNOTゲートを「切断」することに依存している。本研究では、CNOTゲートを切断することなく、回路を2つのサブ回路に最適に分割できるかどうかを判定する基準を特定するという、重要なギャップが存在する。課題は、ゲートの切断に頼ることなく、回路が分割可能（サブ回路の独立した再合成が可能）であるか、そうでないかを区別する基準を特定することである。

手法
著者らは、回路分割問題を「迷路」内での経路探索タスクとして定式化している。手法は以下の主要な段階を経て進行する：

1. 回路表現:

   • ワイヤ表現 ($W$): 行が量子ビットのワイヤ、列がCNOTゲートに対応するグリッド。ある量子ビットがCNOTに関与する場合、そのセルに印が付く。
   • 迷路表現 ($M$): 変換されたグリッドであり、行は量子ビットワイヤ間の空間（およびパディング）を表し、列は空の空間とCNOTゲートが交互に現れる。この表現において、CNOTゲートは「壁」として機能する。有効な分割とは、迷路の壁と交差することなく、左端から右端まで到達する連続した経路に相当する。

2. 量子ビット順序の最適化（シミュレーテッド・アニーリング）:

   • ランダムに生成された回路は、当初、迷路の中央にピークを持つ壁の分布を示すため、水平方向の移動が困難になる。
   • 著者らは、ワイヤ表現における量子ビットの順序を置換するために、シミュレーテッド・アニーリング（SA）を採用している。この置換は迷路表現へとマッピングされる。
   • SAの過程で、中央領域をまたぐCNOT相互作用をペナルティとして課すコスト関数が最小化される。目標は、相互作用を上部および下部の境界へと押しやり、「中央の回廊（コリドー）」と呼ばれる壁のない領域を作り出すことである。

3. 経路探索ヒューリスティック:

   • 迷路が最適化された後、ヒューリスティックなエージェントが迷路を探索する。2つの決定論的なエージェント（壁に当たった際に上方へ移動するものと、下方へ移動するもの）が、第1列の各セルから放出される。
   • エージェントは、結果として得られるサブ回路が時系列的に一貫していることを保証するため、単調に移動（時間的に逆行したり、垂直方向に方向を反転したりしない）するように制約される。
   • 重み付きコスト関数 ($L_{tot}$) は、3つの指標（分割間におけるCNOTの不均衡、セル（面積）の不均衡、および理想的な水平軌道からの経路長の偏差）に基づいて候補経路を評価する。

4. ネットワーク科学的分析:

   • 著者らは、回路を、ノードがCNOTイベントを表し、エッジが因果的またはもつれ関係を表す有向グラフとして分析する。
   • 中心性指標（次数および媒介中心性）とコンセンサス・ダイナミクス（DeGrootモデル）を利用して、SA最適化前後における量子ビット領域の分離度と情報流の混合度を定量化する。

主な結果

• パーコレーション相転移: 本研究は、量子回路の空間における相転移を特定している。有効でバランスの取れた分割経路が存在する領域（分割可能）と、CNOTを切断することなしにはそのような経路が存在しない領域（非分割可能）が存在する。
• スケーリング基準: 転移は、CNOTゲートの数 ($N_c$) と量子ビットの数 ($N_q$) の比率によって支配される。著者らは、$N_c$ が $N_q$ とほぼ等しいときに、2つのバランスの取れたCNOTクラスターへの分割が可能であることを観察している。CNOTの密度が量子ビットに対して増加すると、「中央の回廊」は閉鎖され、回路は非分割状態となる。
• シミュレーテッド・アニーリングの効果: SAは回路のレイアウトを再構成し、CNOT相互作用を周辺部に移動させ、低密度の中央回廊を作り出す。この変換により、壁の分布は単峰性（ベータ分布）のプロファイルから双峰性のプロファイルへと変化し、水平方向のカットの存在を容易にする。
• ネットワーク・ダイナミクス: 中心性分析は、分割可能な領域において、SAがレジスタの端にある量子ビットに相互作用を集中させ、中心部を弱結合にすることを示している。コンセンサス・ダイナミクスは、疎な領域では回路が2つの弱結合クラスターに分離する一方で、密な領域では情報がグローバルに混合し、分離を妨げることを裏付けている。
• 3つの領域: 経路探索スコアに基づき、3つの異なるフェーズが明らかになった：
  1. 第1フェーズ（分割可能）: 厳密に水平なカットが存在し、CNOTとセルがバランスしている。
  2. 過渡領域: パスが壁を回避するために垂直ステップと水平ステップを交互に行う必要があり、その結果、不均衡な分割となる。
  3. 第2フェーズ（非分割可能）: 回路を分離する有効なカットが存在しない。エージェントは境界へと追い込まれ、一方の分割は無視できるほど小さくなり、もう一方は回路のほぼ全体を含むことになる。

意義と主張
本論文は、量子回路の分割をパーコレーション現象として理解するための理論的および数値的な枠組みを提供すると主張している。問題を迷路にマッピングすることで、著者らは、CNOTゲートを切断することなく量子回路を分割できるかどうかを識別するための、スケーラブルで実用的な基準を確立している。

本研究は、エンタングルメント・ゲートを切断せずに回路を分割できる能力を、パーコレーション転移の第1フェーズとして位置づけ、量子回路の最適化を、測定誘起相転移やトポロジカル転移といったより広範な臨界現象に関連付けている。著者らは、この枠組みが、中間回路測定のオーバーヘッドなしに、複数のデバイス間で並列最適化タスクを実行可能かどうかを判断する手法を提供し、量子回路最適化におけるアルゴリズム開発の基礎となることを主張している。結果は、エンタングルメント・ゲートの数が量子ビットに対して線形にスケールする回路においては、このような分割が理論的に可能であり、提案されたパーコレーション基準を通じて識別できることを示唆している。