QAOA — 知識ノート

最適化側のノートに詳しく書いた。ここではアルゴリズムとしての位置づけを記す。

| ψ (\vec{γ}, \vec{β}) ⟩ = \prod_{k = 1}^{p} e^{- i β_{k} H_{M}} e^{- i γ_{k} H_{C}} | + ⟩^{\otimes n}

VQE との関係#

QAOA は VQE の一種と見なせる。 Ansatz が問題ハミルトニアンとミキサーの交互適用に固定されている点が違う。

パラメータが少ないので最適化しやすく、 良いパラメータが問題例をまたいで転用できるという報告もある。

$p \to \infty$ で量子アニーリングの断熱過程を再現する（トロッター分解）。 ゲート型で断熱計算を近似したものという読み方ができる。

$p = 1$ での 3-正則グラフ Max-Cut の近似比 0.6924 は原論文で証明されている。これは古典の Goemans-Williamson (0.878) に及ばない。

$p$ を増やせば改善するが、回路が深くなりノイズの影響が増す。 現時点で古典に対する明確な優位性は示されていない。

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