出典検証済みレベル 3
QAOA（量子近似最適化アルゴリズム）
QAOAは組合せ最適化のためのハイブリッド量子古典アルゴリズムです。コスト層とミキサー層を交互に適用し、古典オプティマイザがパラメータを調整します。
どういう意味か
一様重ね合わせ|+>^nから始め、コストハミルトニアンCによる進化exp(-i*gamma*C)とミキサーBによる進化exp(-i*beta*B)をp層交互に適用します。古典オプティマイザが2p個の角度を調整して目的関数の期待値を最大化します。pが大きいほど近似品質は下がらず、無限大の極限では断熱アルゴリズムに接続します。日常のたとえ
パン生地を何度もこねるようなものです: 押して形に近づけ（コスト層）、折って混ぜる（ミキサー層）を繰り返すと、欲しい形にだんだん近づきます。
古典オプティマイザはコーチ、量子回路は選手: 選手が演技し、コーチが点数を見て次の設定を調整します。
よくある誤解
- 古典アルゴリズムを上回る保証はありません -- 一般的な証明済み高速化は知られていません。
- 有限のpでは近似的な手法で、確定した最適解は返しません。
- 純粋な量子ではなくハイブリッドです。
要点
- コスト層とミキサー層をp回交互に適用。
- 古典オプティマイザが2p個の角度を調整。
- p無限大の極限で断熱アルゴリズムに接続。
理解度チェック
QAOAの各層で交互に適用される2つの操作は？
- A.オラクルと拡散
- B.コストハミルトニアン進化とミキサーハミルトニアン進化
- C.QFTと逆QFT
- D.符号化と誤り訂正
答えを見る
答え: B. コストハミルトニアン進化とミキサーハミルトニアン進化
理由: コストCの進化とミキサーBの進化を交互に適用します。
前提となる概念
一次資料: Farhi, Goldstone, Gutmann, A Quantum Approximate Optimization Algorithm, arXiv:1411.4028 (2014)
Graded 2026-07-10 (human sign-off): established per Farhi, Goldstone, Gutmann arXiv:1411.4028 (2014).