Quantum circuit evolutionary framework applied on set partitioning problem

本論文は、収束の停滞を克服し古典的オプティマイザを不要とすることで集合分割問題を効果的に解決するために、可変トポロジーと疑似対カディアバティック進化項を利用する量子回路進化フレームワークを提案する。

要約

巨大で複雑なパズルを解こうとしていると想像してください。目標は、航空会社の乗務員のような人々のグループをチームに分け、すべてのフライトが重複も欠落もなく、ちょうど一度ずつカバーされるようにし、かつコストを最小限に抑えることです。数学の世界では、これを集合分割問題と呼びます。これは悪名高い難問であり、人員やフライトが増えるにつれて、難易度は指数関数的に高まります。

この論文は、量子コンピュータがこのパズルに取り組むための新しい方法を紹介します。ほとんどの量子アルゴリズムが従う標準的な「レシピ」の代わりに、著者たちはコンピュータが作業しながら自らレシピを進化させることができるフレームワークを構築しました。

以下に、彼らのアプローチを簡単な比喩を用いて解説します。

1. 旧来の方法：「固定された設計図」（VQE）

現在のほとんどの量子アルゴリズム、例えば変分量子固有値ソルバー（VQE）は、厳格で変更不可能なレシピ本に従うシェフのように機能します。

• 設定： 「回路」（コンピュータが踏む手順）の構造は固定されています。材料を追加したり削除したりすることはできず、分量（パラメータ）を微調整するだけです。
• 問題： パズルが大きくなるにつれて、シェフはしばしば「平坦な谷」に立ち往生します。霧の立ち込めた広場で、地面が完全に平坦だと想像してください。どの方向に歩いても、上にも下にも進みません。解決策に近づいているのかどうかも判断できません。量子物理学では、これをバレーン・プラトーと呼びます。改善の方向性を見つけられないため、コンピュータは学習を停止します。

2. 新しい方法：「進化する彫刻家」（QCE）

著者たちは、量子回路進化（QCE）と呼ばれるフレームワークを提案します。固定されたレシピの代わりに、小さな粘土の塊から始め、各ステップで粘土を追加、削除、または再成形することを許可された彫刻家を想像してください。

• 仕組み： コンピュータは非常に単純な回路（おそらくゲート一つだけ）から始めます。その後、構造をランダムに変異させる（新しい手順を追加する、古い手順を削除する、または接続を変更する）ことで、自分自身とわずかに異なるバージョンの「ファミリー」を作成します。
• 選択： これらすべてのバージョンをテストします。パズルを最もよく解くものが、次のラウンドの「親」として生き残り、他のものは廃棄されます。
• 利点： 構造自体が変化するため、コンピュータは平坦な谷に立ち往生しません。霧の中から抜け出す道を見つけるために、アプローチ全体を再成形することができます。

3. 検証された 2 つの戦略

論文では、この「進化する彫刻家」アプローチの 2 つの具体的なバリエーションが検証されました。

• 戦略 A：純粋な進化主義者（アンザッツフリー）
  このバージョンは、ほぼ何もない状態から始まり、自然選択のように試行錯誤を通じて構造を完全にコンピュータ自身に発見させます。解決策がどのように見えるかを推測するのではなく、機能するまで進化させます。

• 戦略 B：物理学に着想を得た進化主義者（疑似反断熱）
  これが論文の「主役」です。著者たちは、問題の物理学に基づいてコンピュータにヒントを与えました。回路に特別な「促し」（疑似反断熱項と呼ばれる）を追加しました。

  • 比喩： 重い箱を丘の上へ押し上げようとしていると想像してください。「純粋な進化主義者」は、登る方法が見つかるまでランダムに押し続けます。一方、「物理学に着想を得た」バージョンは丘の形状を知っており、箱が平坦な場所に立ち往生しないよう、スムーズに動き続けるための特定の抗力を加えます。
  • 結果： この戦略が最も良好なパフォーマンスを示しました。他の手法よりもはるかに「立ち往生」（収束の停滞）を回避し、パズルが非常に大きくても機能しました。

4. 結果

著者たちは、航空会社スケジューリング問題の 35 種類の異なるバージョンを用いて、シミュレータ（量子コンピュータのように振る舞うコンピュータプログラム）上でこれらの手法をテストしました。

• 勝者： 物理学に着想を得た進化手法（APCD-QCE）は、標準的な「固定された設計図」手法（VQE）よりも一貫して優れた解決策を見つけました。
• 行き詰まり点： 新しい手法ははるかに優れていましたが、パズルが極めて大きくなると（約 20 量子ビット）、依然として苦労しました。進化する彫刻家さえも、完璧な解決策を見つけるために時間や複雑さの限界に直面することがありました。
• ノイズ： また、コンピュータが誤りを犯す場合（現実世界の「ノイズ」をシミュレート）に何が起こるかもテストしました。新しい手法は性能が低下しましたが、これは予想通りであり、それでも相当な耐性を示しました。

結論

この論文は、量子回路の設定を微調整するだけでなく、その形状自体を変化させることで、現在のアルゴリズムを閉塞させる「行き止まり」を回避できると主張しています。具体的には、この進化プロセスに物理学に基づいた「促し」を加えることで、コンピュータはより優れた解決策をより迅速に見つけることができます。

これはまだすべての問題（特に非常に巨大な問題）を解決するものではありませんが、スケジューリングやリソース管理のような複雑な最適化問題を解決するために量子コンピュータを利用するための有望な新しい道筋を提供します。これにより、最適化の重労働を古典コンピュータに任せる必要性を潜在的に回避できる可能性があります。

技術概要

技術的概要：集合分割問題への量子回路進化フレームワークの適用

問題定義
本論文は、よく知られた NP 困難な組み合わせ最適化課題である集合分割問題（SPP）を取り扱っている。SPP は、すべての要素がちょうど 1 つの部分集合に属することを保証しつつ、総重みを最小化するために、要素の集合を互いに排他的かつ網羅的な部分集合に分割する問題である。実用的な応用例には、航空会社の乗務員スケジューリングが含まれる。量子ハードウェア上でこれを解決するため、著者らは SPP を二次制約なし二値最適化（QUBO）問題として定式化し、これをイジングハミルトニアンにマッピングしている。本研究は特に、量子ビット数が増加するにつれて勾配が指数関数的に消失し、収束の停滞を引き起こす「 barren plateaus（不毛な高原）」という現象に悩まされることが多い、変分量子固有値ソルバー（VQE）などの現在の変分量子アルゴリズム（VQA）の限界をターゲットとしている。

手法
著者らは、標準的な VQE 手法とは異なる**量子回路進化（QCE）**フレームワークを提案している。固定された回路トポロジー（アンサッツ）を用い、古典的オプティマイザによって変化するパラメータを最適化する VQE とは異なり、QCE フレームワークは回路トポロジー自体を進化させる。本研究はこのフレームワーク内で 2 つの異なる戦略を評価している。

1. アンサッツフリー量子回路進化（AF-QCE）：

   • 先行文献 [13] に着想を得たこのアプローチは、最小限の回路（単一のランダムゲート）から開始し、事前に定義されたアンサッツなしで反復的に進化させる。
   • 進化は、INSERT（ゲートの追加）、DELETE（ゲートの削除）、SWAP（ゲートの置換）、MODIFY（ゲートパラメータの調整）という突然変異操作に依存する。
   • 回路の集団を生成し測定し、最も性能の優れた回路を次世代の親として選択することで、コスト関数の単調な減少を保証する。

2. 疑似反断熱進化項付きアンサッツ（APCD-QCE）：

   • このアプローチは、収束を改善するためにアンサッツに物理学に着想を得た構造を組み込んでいる。ハミルトニアン $H_T(\lambda) = H_{ad}(\lambda) + H_{pcd}(\lambda)$ を利用する。ここで、$H_{ad}$ は断熱時間進化ハミルトニアンを表し、$H_{pcd}$ は疑似反断熱進化項である。
   • ユニタリ演算子は $U = U_{ad}U_{pcd}$ と定義される。$U_{ad}$ 成分は固定（1 つのトロッターステップ）であるのに対し、$U_{pcd}$ は AF-QCE と同じ進化突然変異戦略を用いて進化させられる。
   • 初期状態の準備には $|+\rangle^{\otimes n}$ を用い、ヒルベルト空間の探索を促進するために特定のパラメータ設定（$\beta=0, \delta=0.5$）が適用される。

実験設定
実験は、高性能シミュレータ（KUATOMU）上で Qiskit ライブラリを用いて、2 つのシナリオ下で行われた。

• ノイズフリー： SPP の 35 インスタンス（6 から 20 量子ビットの範囲）がテストされた。
• ノイズあり： NISQ デバイスの限界を模倣するため、特定の量子ビットに脱分極エラーチャネル（$\epsilon = 0.01$）を含むシミュレーションが行われた。
• 比較： QCE 戦略は、標準的な VQE（2 局所線形エンタングルメントアンサッツと COBYLA オプティマイザを使用）に対してベンチマークされた。
• 指標： 性能は、古典的な参照値（Gurobi ソルバー）と量子アルゴリズムによって見つかった最小期待値との比として定義される**近似率（$R$）**を用いて測定された。

主要な結果

• VQE に対する優位性： ノイズフリーのシナリオでは、AF-QCE と APCD-QCE の両方が VQE を大幅に上回った。VQE の性能は量子ビット数の増加とともに急速に劣化し（10 量子ビット以上のインスタンスでは収束に失敗することが多かった）が、進化アプローチはより良い性能を維持した。
• APCD-QCE の性能： APCD-QCE 戦略は最も堅牢な結果を示し、35 インスタンスのうち 25 で 1.00（最適）の近似率を達成した。VQE や AF-QCE が苦労した多くのケースで、収束の停滞を効果的に回避した。
• スケーラビリティの限界： 改善にもかかわらず、スケーラビリティの課題は残った。20 量子ビットのインスタンス（特に 20.1、20.6、20.7）では、APCD-QCE を含むすべての手法が収束停滞の兆候を示し、近似率が大幅に低下した。
• ノイズの影響： ノイズありのシミュレーションでは、特に小規模なインスタンスにおいて、すべてのアルゴリズムの性能が劣化した。しかし、QCE フレームワークは一般的に VQE に対して同等かそれ以上の性能を維持した。

意義と主張
本論文は、提案された QCE フレームワークが、整数最適化問題に対する固定アンサッツ型変分アルゴリズムの有望な代替手段であると主張している。主な貢献点は以下の通りである。

• 停滞の緩和： 特に APCD-QCE 変種は、標準的な VQA における barren plateaus に伴う収束停滞を回避する驚くべき能力を示している。
• 古典的オプティマイザの排除： 回路トポロジーを直接進化させることで、パラメータを調整するための古典的オプティマイザ（COBYLA など）の必要性を回避し、現在の VQA ワークフローにおけるボトルネックに対処している。
• スケーラビリティへの道筋： 20 量子ビットの停滞に対する完全な解決策ではないものの、結果は可変トポロジー回路が、大規模な最適化問題を解決するための「興味深い道筋」を提供することを示唆している。著者らは、十分な数の世代が与えられれば、APCD-QCE 戦略は収束停滞の影響に対して「ほぼ免疫がある」が、突然変異のランドスケープにおける局所最小値からの脱出は依然として課題であると指摘している。

著者らは、この手法が量子ビット数の増加に伴うスケーラビリティの課題に直面しているものの、疑似反断熱項のような物理学に着想を得た項を進化回路探索に統合することは、NISQ デバイス上で組み合わせ問題を解決するための有望な結果をもたらすと結論付けている。