Towards High Performance Quantum Computing (HPQ): Parallelisation of the Hamiltonian Auto Decomposition Optimisation Framework (HADOF)

本論文は、単一および複数のIBM量子プロセッサにわたってハミルトニアン自動分解最適化フレームワーク（HADOF）を並列化することで、実世界のゲノムアセンブリ事例を含む大規模組み合わせ最適化問題の解決にかかるウォールクロック時間を大幅に短縮し、かつ解の品質を維持しつつ高性能量子コンピューティングの実現に向けた進展を達成することを示している。

要約

巨大で極めて複雑なジグソーパズルを解こうとしていると想像してください。これは単なるパズルではなく、ゲノムを構築するために DNA 鎖の正しい順序を特定するなど、現実世界の課題を表す「量子パズル」です。

問題は、このパズルが誰か一人（あるいは単一の量子コンピュータ）が手に収められるほどには大きすぎることです。ピースが多すぎて、部屋にある「ノイズ」（ハードウェアエラー）のために画像を明確に見ることが困難です。もし無理やり全体を小さなテーブルに載せようとすれば、収まらず、間違いを犯す可能性が高くなります。

この論文は、これを解決するための新しい戦略、HADOF（ハミルトニアンの自動分解最適化フレームワーク）を紹介しています。その仕組みを、簡単な比喩を用いて説明します。

1. 問題：「手に収められない」パズル

現在の量子コンピュータは、小さく騒がしい作業台のようなものです。一度に扱えるパズルのピースは数個に限られています。もし、数千の DNA 断片からなるゲノムのような巨大な問題を、こうした作業台の一つで一度に解こうとすれば、コンピュータは圧倒され、ピースは「ノイズ」によって混乱し、解は失敗します。

2. 解決策：「ミニパズル」への分解

巨大なパズルを一度に解こうとする代わりに、HADOF は熟練の整理係のように機能します。それは巨大なパズルを、数百の小さく管理可能な「ミニパズル」（部分問題）に分解します。

• マジックのトリック: 単にパズルを無作為に切り取るのではありません。すでに配置済みのピースを分析する賢いシステムを用いて、次のミニパズルを解くのを助ける情報を活用します。
• 反復: ミニパズルを解き、そこから学び、全体の画像に関する理解を更新し、次に次のミニパズルを解きます。画像が明確になるまでこれを繰り返します。

3. 新しい転換点：「組立ライン」（並列化）

以前、この手法は組立ライン上の単一の作業者のように機能していました。ミニパズル#1 を解き、次に#2、そして#3 と進みます。これには長い時間がかかります。

この論文の著者たちは、システムを複数の組立ラインを持つ忙しい工場のように稼働させるようにアップグレードしました。

• 単一の作業者対チーム: 一人の人間がミニパズルを一つずつ解く代わりに、チームの作業者（複数の量子コンピュータ、または QPU）が異なるミニパズルを同時に解くようにしました。
• 結果: 単一の量子コンピュータを使用する場合と比較して、4 台の量子コンピュータのチームを使用することで、作業を3 倍から 4 倍速く完了できることが判明しました。さらに、1 台のコンピュータを使用する場合でも、作業を並列に整理することで3 倍速くなりました。

4. 現実世界でのテスト：DNA の「物語」の再構築

これが現実世界で機能することを証明するため、チームは特定の生物学的問題、ゲノムアセンブリでテストを行いました。

• 比喩: 本を数千の小さな紙の破片（DNA リード）に破り捨てたと想像してください。あなたの仕事は、物語を読めるようにそれらを正しい順序でテープで貼り直すことです。
• テスト: 彼らは実際の生物学的データセット（$\phi$X174 というウイルス）を取り、新しい「量子コンピュータのチーム」を使用して再構築しようとしました。
• 結果:
  • 速度: 並列アプローチは、結果を得る上で非常に速かったです。
  • 品質: ノイズの多い量子コンピュータは、ハードウェアの「ノイズ」により 100% 完璧なスコアは得られませんでしたが、非常に良い解を見つけました。実際、彼らが生成した解の 50% 以上は、標準的な後処理ツールを用いて完璧な答えに修正できるほど正確でした。
  • 比較: 分解せずに単一の量子コンピュータで DNA パズル全体を解こうとした場合、コンピュータは良い解を見つけることができませんでした。「分解する」方法（HADOF）は、「一度にすべて」の方法が失敗した場所で成功しました。

5. 全体像：「高性能量子」（HPQ）

著者たちはこのアプローチを高性能量子（HPQ）コンピューティングと呼んでいます。

• スプーンで砂の山を動かそうとする単一の人間と、協力して働くトラックの群れとの違いと考えてください。
• この論文は、量子コンピュータを大きな問題に対して真に有用なものにするためには、それらがより大きく、より静かになるのを待つだけでは不十分だと主張しています。私たちが変えなければならないのは、それらの「使い方」です。つまり、問題を小さなピースに分解し、多数の機械間で並列に解くようにすることです。

主張のまとめ

• 速度: 複数の量子コンピュータを並列に使用することで、これらの問題の解決が 3〜4 倍速くなります。
• スケーラビリティ: この手法により、単一の量子コンピュータでは現在処理しきれない問題（500 変数など）を解くことが可能になります。
• 精度: ノイズの多い不完全なハードウェアであっても、この手法は、問題全体を一度に解こうとするよりも優れた解を見つけます。
• 実用応用: 現実世界のゲノムアセンブリタスクでこれを成功裏に実証しており、単なる理論ではなく、機能するツールであることを示しました。

要約すれば、この論文はこう述べています。「象全体を一口で食べようとしてはいけません。それを小さなピースに分解し、量子コンピュータのチームにそれらを同時に食べさせなさい。それは速く、よりうまく機能します。」

技術概要

以下は、論文「Towards High Performance Quantum Computing (HPQ): Parallelisation of the Hamiltonian Auto Decomposition Optimisation Framework (HADOF)」の詳細な技術的サマリーです。

1. 問題提起

組合せ最適化問題（二次制約なし二値最適化、すなわちQUBOとして定式化）に対する量子最適化の実用的応用は、現在、雑音中間スケール量子（NISQ）デバイスの限界によってボトルネックとなっています。主な制約は以下の通りです：

• 限られた量子ビット数: 現在のハードウェアは、数百の変数を必要とする大規模な QUBO 問題をホストできません。
• ハードウェアの雑音: 深い回路における雑音の蓄積が、解の質を低下させます。
• スケーラビリティ: 既存の分解手法（HADOF など）は主に逐次的であり、分散量子アーキテクチャや高性能コンピューティング（HPC）リソースで利用可能な並列性を活用できていません。
• シミュレーションの限界: 大規模な量子回路を古典的にシミュレートすることは、計算コストが高く、メモリを大量に消費します。

本論文は、ハミルトニアンの自動分解最適化フレームワーク（HADOF）を拡張し、単一および複数の量子処理ユニット（QPU）全体にわたる並列実行をサポートすることで、これらの課題に対処し、高性能量子（HPQ）コンピューティングの実現を目指しています。

2. 手法

コアフレームワーク：HADOF

HADOF は、大域的な QUBO ハミルトニアンを、反復的に解くことができるより小さく管理しやすい部分ハミルトニアンに分解します。

1. 分解: 大域的問題は部分問題（変数の部分集合）に分割されます。
2. 反復解法: 各部分問題は量子オプティマイザ（QAOA）を用いて解かれます。
3. コンテキスト統合: 解かれた部分問題からの変数の期待値（$E[x_i]$）は、後続の部分問題のコンテキストを近似するために使用されます。
4. 集約: 解は再結合され、大域的な解を形成します。

並列拡張

著者らは、逐次的なベースラインと 2 つの主要な点で異なる HADOF の並列化バージョンを導入しました：

• 独立生成: 各反復において、すべての部分ハミルトニアンは、前回の反復からの期待値を使用して同時に生成されます（現在の反復内で逐次的に値を更新するのではなく）。
• 非同期実行: 部分回路は並行して解かれます。これにより以下が可能になります：
  • QPU 内並列性: スケジューラを活用して、単一の QPU で複数のジョブを実行します。
  • QPU 間並列性: 複数の異なる QPU（例：IBM Kingston, Pittsburgh, Fez, Marrakesh）にジョブを分散します。

実装詳細

• オプティマイザ: パラメータ $\beta$ と $\gamma$ のための古典的オプティマイゼーションループを回避するため、トロッター化されたアニーリングパラメータ化を用いたデジタル化された QAOA アプローチを使用します。
• 回路深度: 回路は層ごとに構築されます（最大 5 層）。各反復において、すべての部分回路に 1 層が追加されます。
• 部分問題のサイズ: 現在のハードウェアで高い忠実度を維持するため、5 量子ビット（$k=5$）に固定されています。
• 対象アプリケーション: 重なりグラフ上の巡回セールスマン問題（TSP）としてモデル化されたゲノムアセンブリです。この問題は、ハミルトニアン経路を見つけることを目的とした QUBO に符号化されます。

3. 主要な貢献

1. 初の実機 HADOF 実装: 本研究は、HADOF を理論的なシミュレーションから実 IBM QPU（Kingston, Pittsburgh, Fez, Marrakesh）上での実行へと移行させました。
2. 並列化戦略: 分解された部分問題の並行実行のフレームワークを実証し、解の質を損なうことなくウォールクロック時間を大幅に短縮しました。
3. HPQ パラダイムの検証: アルゴリズム的分解とシステムレベルの並列性を統合することで、HADOF を高性能量子コンピューティングへの実用的な道筋として位置づけました。
4. 実世界への応用: ゲノムアセンブリ問題（$\phi$X174 バクテリオファージ）にフレームワークを成功裏に適用し、計算生物学におけるその有用性を実証しました。
5. ベンチマーク: 逐次的 HADOF、並列 HADOF（単一およびマルチ QPU）、標準的なフル回路 QAOA、および古典的シミュレーテッドアニーリングの間で包括的な比較を行いました。

4. 主要な結果

速度と効率

• ウォールクロック時間:
  • マルチ QPU 並列: 実ハードウェア上の逐次実行と比較して、ウォールクロック時間を3〜4 倍短縮しました。
  • 単一 QPU 並列: 効率的なジョブ編成により、単一デバイスであっても最大3 倍の高速化を達成しました。
  • シミュレーション: 並列シミュレーションモードでは5 倍以上の高速化が予測されました。
• QPU 使用量: 総 QPU 使用時間は回路数に比例して残りますが、メイクスパン（解に至るまでの総時間）は劇的に短縮され、時間制約のあるアプリケーションに対して実用的なアプローチとなります。

精度と堅牢性

• 標準 QAOA との比較: HADOF は実ハードウェア上でフル回路 QAOA を大幅に上回ります。
  • 標準 QAOA の精度は、雑音の蓄積により、雑音のあるハードウェア上の 50 変数問題でほぼゼロ（例：0.02）まで低下しました。
  • HADOF は、同様のサイズの実ハードウェア上で0.80 以上の精度を維持しました。
• 雑音耐性: 分解により回路深度を制限し、単一回路で見られるような精度の指数関数的な劣化を防ぎます。
• ゲノムアセンブリのケーススタディ:
  • 理想的シミュレーション: 逐次的および並列 HADOF の両方が、シミュレーテッドアニーリングと一致する 100% の最高精度を達成しました。
  • 実ハードウェア: 最高精度は競争力のある水準（0.88〜0.91）を維持しましたが、雑音により正確な基底状態を見つける頻度はゼロに低下しました。しかし、52% 以上のサンプリングされた解は、標準的なバイオインフォマティクスツール（GFAtools）を用いたポストプロセッシングにより、正しい配列を回復できました。

スケーラビリティ

• HADOF は、シミュレーションでは最大500 変数、実ハードウェアでは300 変数の QUBO 問題を、わずか5 量子ビット回路を使用して成功裏に解きました。
• 標準的なフル回路 QAOA は、接続性とエンベディングの制約により、同じハードウェア上では約 50 変数に制限されています。

5. 意義と結論

この研究は、分解と並列性が単なる現在のハードウェア制限への回避策ではなく、実用的な量子優位性の根本的な促進要因であることを実証しています。

• スケーラビリティ: HADOF は現在のデバイスの物理的量子ビットの限界を迂回し、ハードウェアがネイティブにサポートできるよりもはるかに大規模な問題の解決を可能にします。
• HPQ への整合性: このフレームワークは、分散量子アーキテクチャが大幅な性能向上をもたらすことを示す、新興の高性能量子コンピューティングパラダイムと整合しています。
• 実用性: ゲノムアセンブリへの成功した適用により、雑音が分解と並列実行戦略を通じて管理される限り、量子最適化を実世界の科学的パイプラインに統合できることを証明しました。

著者らは、今後の研究は適応的分解戦略、誤り軽減技術、および実シーケンシングデータを用いた標準的なゲノムアセンブリパイプラインへの HADOF の統合に焦点を当てるべきであると結論付けています。