Setting angles in quantum approximate optimization at utility-scale

本論文は、近似手法と転移学習戦略のベンチマークを行うことにより、現在および将来の量子ハードウェア上での効率的なエンドツーエンドの実行に向けた実用的な運用の指針を提供し、ユーティリティスケール（100量子ビット以上）における量子近似最適化アルゴリズム（QAOA）の最適なパラメータ決定という課題に取り組むものである。

要約

あなたは、100もの異なる都市を訪れる配送トラックの、迷ったり燃料を無駄にしたりしないための「絶対的な最適ルート」を見つけようとしていると想像してください。これは古典的な「組合せ最適化」問題です。量子コンピューティングの世界では、こうしたパズルを解くための特別なツールとして、**量子近似最適化アルゴリズム（QAOA）**があります。

しかし、QAOAは高性能なラジオのチューナーのようなものです。最もクリアな信号（最良の解）を得るためには、2つのダイヤル、すなわち角度（$\beta$ と $\gamma$ と呼ばれます）を、正確な位置に回さなければなりません。もし、ほんの少しでも回し方を間違えると、信号はノイズだらけになり、悪い答えしか得られません。

問題は、非常に巨大なパズル（100都市以上、あるいは「ユーティリティ・スケール」）において、このダイヤルを正しく回すことが極めて困難であることです。それは、電池が切れかかっている、ノイズが多くて壊れたラジオで、静電気の音を聞きながらラジオのチューニングを試みるようなものです。ノイズが大きすぎて量子コンピュータに答えを聞くこともできませんし、普通のコンピュータで答えをシミュレーションするには時間がかかりすぎます。

この論文は、ノイズのない完璧な量子コンピュータを必要とせずに、これらのダイヤルを正しく回す方法を試した、30種類の戦略による大規模な「フィールドテスト」の結果です。その内容は、以下のように分かりやすく説明されています。

1. 「勘と経験」対「地図」

著者たちは、正しい角度を見つけるための2つの主要な方法をテストしました。

• 「地図」（パラメータ転送）： ゼロから始める代わりに、すでに解いたことがあり、より単純で小さなパズルを参考にしました。「もし20都市のルートでこの角度が機能したなら、100都市のルートでも機能するだろうか？」と問いかけたのです。結果として、多くの問題において、小さなパズルの設定を大きなパズルへと「コピー＆ペースト」できることが分かりました。これは、自分の近所の地図を使って街全体のナビゲーションを行うようなものです。完璧ではありませんが、即座に正しい方向へと導いてくれます。
• 「勘と経験」（反復法）： これは、彫刻家が像を彫る時のように、大まかな推測から始めて、層を重ねるごとに少しずつ洗練させていく方法です。これはしばつ非常に優れた角度を見つけ出すことができますが、石を削り取るのに非常に長い時間がかかります。

2. 「シミュレータ」の問題

彼らは、完璧な量子コンピュータ上で100都市のフルパズルを実行することができなかったため、角度をテストするために「シミュレータ」（量子コンピュータのふりをする古典的なコンピュータ）を使用しました。彼らは2種類のシミュレータを試しました。

• 「ラフスケッチ」（MPS）： 解を近似する、より高速でシンプルなシミュレーションです。
• 「詳細な設計図」（Pauli Propagation）： 数学をより精密に追跡する、より複雑なシミュレーションです。

驚きの事実： 実際に本物の量子ハードウェアでテストを実行した際、時として「ラフスケッチ」の方が「詳細な設計図」よりも優れた結果を与えることがありました。これは、ハイパー精密なGPSが実際の交通ノイズに混乱してしまう一方で、手書きのラフな地図がドライバーをうまく導くことがあるのと似ています。著者たちは、必ずしも最も完璧なシミュレーションが必要なわけではなく、単に正しい方向を素早く指し示してくれるものがあればよいのだということを学びました。

3. 「スピードと品質」のトレードオフ

著者たちは、「時間」と「品質」の間の最適なバランスを示すグラフ上に線を引く、いわゆる「パレート・フロンティア」を作成しました。

• 「急行レーン」： もし、素早く（数秒以内に）「良い」答えが欲しいのであれば、「固定角度」（問題の種類に基づいた事前設定のダイヤル）や「パラメータ転送」が勝者となります。これを使えば、最良の解の約80〜85%をほぼ瞬時に得ることができます。
• 「緩行レーン」： もし、角度を「削り出す」ために何時間も何日も費やせば、わずかに高い品質（おそらく1〜2%程度の向上）を絞り出すことができます。しかし、本物の量子コンピュータがあまりにノイズが多いため、「完璧な」角度と「十分な」角度の区別すらつかないことを考えると、その追加の努力は多くの場合、割に合いません。

4. 万能な解決策は存在しない

彼らは、異なる種類のパズル（グループの友人を2つのチームに分ける「MaxCut」や、互いを知らない最大のグループを見つける「MIS」など）についてもテストを行いました。

• 教訓： あるタイプのパズルには完璧に機能する戦略が、別のタイプでは惨めに失敗することもあります。例えば、「Fourier」と呼ばれる手法は、友人をチームに分ける問題には全く役に立ちませんでしたが、見知らぬ人たちの最大のグループを見つける問題には非常に優れていました。特定の仕事に対して、適切な道具を選ばなければならないのです。

結論

この論文は、今日のノイズの多い量子コンピュータにおいては、完璧主義者になる必要はない、と結論づけています。

数学的に完璧な角度設定を見つけようとすることは、多くの場合、時間とエネルギーの無駄です。なぜなら、ハードウェアがあまりにノイズが多いため、その精密さを享受できないからです。むしろ、「ユーティリティ・スケール」の問題（100量子ビット以上）に対する最善のアプローチは、以下の通りです。

1. 事前設定された角度、または類似の小さな問題から転送された角度を使用すること。
2. 仕事を確認するために、高速で近似的なシミュレーションを使用すること。
3. 「完璧な」解を追い求めて時間を浪費するのではなく、素早く手に入る「十分に良い」解を受け入れること。

要するに、チューニングに悩みすぎる必要はありません。良い地図を使い、車に乗り込み、走り出しましょう。

技術概要

技術要約：ユーティリティスケールにおける量子近似最適化の角度設定

問題提起
量子近似最適化アルゴリズム（QAOA）は、量子ハードウェア上で組合せ最適化問題を解くための主要なヒューリスティックである。しかし、QAOA回路の最適な変分パラメータ（角度 $\theta$）を特定することは、特に「ユーティリティスケール」（ここでは100量子ビット以上と定義）において、重大なボトルネックとなっている。このスケールでは、量子回路の厳密な古典シミュレーションは不可能であり、ノイズ、コヒーレンス時間の制限、およびキューへのアクセス制限のために、量子ハードウェアを用いたクローズドループ最適化を行うことは極めて高コストである。さらに、理論的な結果は、最適な角度を見つけることがNP困難であり、最適化のランドスケープが局所解に満ちていることを示している。その結果、リソース集約的な量子・古典間のフィードバックループに頼ることなく、大規模な問題に対してどの角度設定戦略が最良の解をもたらすかについての経験的な指針が不足している。

手法
著者らは、QAOAの実践者に運用上の指針を提供するために、包括的なベンチマーク調査を実施した。その手法は以下の通りである：

1. 分類学の構築： 既存の角度設定手法を、物理学に着想を得たもの（例：線形ランプ、反転対角成分）、パラメータ転送（例：固定角度、クラスタリング）、反復的（例：補間、レイヤーごとの最適化）、および機械学習の4つのカテゴリに分類した。
2. 近似的なエネルギー評価： 厳密な古典シミュレーションや即時のハードウェアアクセスを回避するため、本研究では、訓練フェーズ中にコスト関数 $\langle H_C \rangle$ を評価するための近似的な古典的手法を採用した。具体的には、以下を用いた：
   • 行列積状態 (MPS)： 量子ビットのマッピング（SATマッピング）を最適化したテンソルネットワークを使用し、もつれ構造を処理する。
   • パウリ伝播 (PP)： パウリ演算子の変換を追跡するハイゼンベルク描像の後方伝播法であり、疎なグラフに対して効果的である。
3. ベンチマーク・プロトコル： 著者らは、3つの問題クラス（MaxCut、最大独立集合 (MIS)、低自己相関バイナリ系列 (LABS)）に対して、30種類の異なる角度設定戦略をテストした。
   • スケール： ベンチマークは、厳密な状態ベクトルシミュレーションが可能な小規模インスタンス（20–50量子ビット）から、ユーティリティスケールのインスタンス（最大144量子ビット）まで多岐にわたる。
   • ハードウェア検証： 選択された最適な角度は、実際の量子ハードウェア（IBM Quantumデバイス、具体的には ibm_boston および ibm_fez）で実行され、実際の近似比を測定し、古典的な訓練結果を検証した。
4. リソース分析： 本研究では、計算予算（古典的な最適化と量子サンプリングを含む総実行時間）と解の品質の間のトレードオフを分析するために、ストカスティック・ベンチマーク・フレームワークを利用した。

主な貢献

• 経験的な分類学とベンチマーク： 本論文は、小規模な古典シミュレーション可能なインスタンスを超えて、ユーティリティスケールにおけるQAOA角度設定手法の、初の大規模かつ体系的な比較を提供している。
• 近似手法の検証： MPSおよびPPといった古典的な近似手法が、最大144量子ビットまでの問題に対して効果的に角度最適化を導けることを実証した。特にPPは、特定のグラフトポロジー（heavy-hex）において、ハードウェアの結果に対する優れた相関を示した。
• ハードウェア検証： 近似的な手法によって古典的に最適化された角度が、量子ハードウェア上でも意味のある性能に変換されることを検証した。ただし、回路の深さが増すと、ノイズによって手法間の区別が困難になる。
• 運用上の指針： リソース制約や問題の種類に基づいた具体的な推奨事項を導き出し、どの手法が実行時間と解の品質の間で最良のトレードオフを提供するかを特定した。

結果

• 手法の性能：
  • 線形ランプおよび補間手法は、ほとんどのグラフタイプおよびエネルギー評価手法において、概して最良の角度を提供した。
  • 固定角度（ランダム正則グラフから導出されたもの）は、同様の問題インスタンスに転用された際、極めて高い性能を発揮し、最小限の最適化で近似比90%以上を達成することが多かった。
  • パラメータ転送戦略（固定角度または小規模から大規模インスタンスへの転用を使用）は非常に効率的であり、多くの場合、反復的な手法よりも「解への時間（time-to-solution）」において優れていた。
  • フーリエ手法は高い分散を示し、MISのようなケースでは他の手法を上回ったが、MaxCutでは性能が劣った。
• 近似評価器：
  • パウリ伝播 (PP) は、一般にMPSよりも、ハードウェア上での真のエネルギーランドスケープをより良く近似した。特にheavy-hexグラフにおいて顕著であり、推定された近似比とハードウェアの近似比との間に強い正の相関（0.89–0.93）を示した。
  • MPS は特定のトポロジーでは高速であったが、小さなサイクルを持つラインベースのグラフにおいて、ハードウェアの結果との負の相関に苦しんだ。
• ハードウェアの現実： ユーティリティスケール（144量子ビット、深さ $p=10$）では、ノイズにより異なる角度設定手法の区別が困難になる。反復的な手法（Interp.など）はシミュレーションでは高品質な角度を生成したが、実際のハードウェア上では、より高速な非反復的手法（Fixed AnglesやLinear Rampsなど）に対する優位性が減少した。
• リソースのトレードオフ： パレート最適フロント分析により、低コストの戦略（パラメータ転送、固定角度）が、高品質な解への最も速い経路を提供することが明らかになった。反復的な手法は、ハードウェアの近似比に対してわずかな利得を得るために、多大な計算コスト（しばしば $10^4$ 秒超）を要する。

意義と主張
本論文は、「ユーティリティスケール」時代における量子最適化のための不可欠な運用指針を提供すると主張している。最適化された角度を見つけることは理論的に困難であるが、以下の活用によって実用的なワークフローは成功できると論じている：

1. 転移学習： 小規模または代表的なインスタンスで訓練された固定角度やパラメータを使用して、大規模インスタンスにおける最適化を初期化する。
2. 近似訓練： 角度を見つけるために、クローズドループの量子ハードウェア訓練ではなく、古典的な近似シミュレータ（MPS/PP）に依存し、最終的なサンプリングのためにハードウェアへのアクセスを確保する。
3. コストを考慮した選択： 実行時間と品質のバランスを取る手法を優先する。著者らは、多くの実用的なアプリケーションにおいて、広範な角度最適化による「収穫逓減」は、ハードウェアのノイズが小さな性能差を覆い隠してしまう場合、高速な転移ベースの手法が、計算コストの高い反復的最適化よりも好ましいことを示唆している。

本研究は、標準的なQAOAが、深さ $p \le 10$ で、ハードウェア・トポロジーに適合した問題に対して、これらの戦略を用いてエンドツーエンドで効率的に実行可能であることを結論付けている。また、これらの知見は、対称性や局所性といった構造的な障害を克服するQAOAのバリアント（例：warm-start, R-QAOA）にも転用可能であるとしている。