QAOA

ゲート型量子計算機で組合せ最適化を解く変分アルゴリズム。 Quantum Approximate Optimization Algorithm。 Farhi、Goldstone、Gutmann が 2014 年に提案した。

仕組み#

2 種類のハミルトニアンを交互に適用する回路を作る。

$$|\psi (\overrightarrow{\gamma },\overrightarrow{\beta })⟩=\prod _{k=1}^p{e}^{-i{\beta }_k{H}_M}{e}^{-i{\gamma }_k{H}_C}|+{⟩}^{\otimes n}$$

• $H_C$ … コストハミルトニアン。解きたいイジング模型
• $H_M$ … ミキサー。通常 ${\sum }_i{\sigma }_i^x$。状態を混ぜて探索させる
• $p$ … 層の数。深さ

パラメータ $(\overrightarrow{\gamma },\overrightarrow{\beta })$ を古典最適化器で調整する。 $⟨H_C⟩$ を測って最小化するので、 VQE と同じ構造。

断熱過程の離散化として#

$p\to \infty$ の極限で量子アニーリングの 断熱過程を再現できる（トロッター分解）。 つまり QAOA は断熱過程をゲート型で近似したものとも読める。 有限の $p$ でどこまで近づけるかが実用上の問題になる。

現状の評価#

• $p=1$ の QAOA は 3-正則グラフの Max-Cut で 近似比 0.6924 を保証する（原論文）
• これは古典の Goemans-Williamson (0.878) に及ばない
• $p$ を上げれば改善するが、パラメータ最適化が難しくなり、 ノイズの影響も増す

「QAOA が古典を超えた」という主張は、比較対象を確認する必要がある。

パラメータ最適化の難所#

• barren plateau — 勾配が消える
• 期待値がショットノイズを持つので、SPSA のような ノイズ前提の手法が要る
• $p$ 層で $2p$ 個のパラメータ。非凸な景観

参考文献#

• Edward Farhi, Jeffrey Goldstone, Sam Gutmann. A Quantum Approximate Optimization Algorithm. 2014. https://arxiv.org/abs/1411.4028
• Leo Zhou et al. Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices. Physical Review X 10(2), 2020. https://doi.org/10.1103/PhysRevX.10.021067
• Kishor Bharti et al. Noisy intermediate-scale quantum algorithms. Reviews of Modern Physics 94(1), 2022. https://doi.org/10.1103/RevModPhys.94.015004