QAOAリーディングメモ

Table of Contents

簡潔に日本語訳・内容まとめながら読もうと思います。

Blekos, Kostas, et al. “A review on quantum approximate optimization algorithm and its variants.” Physics Reports 1068 (2024): 1-66.

https://www.sciencedirect.com/science/article/pii/S0370157324001078

1. Introduction

2. Background

2.1. QUBO problems and applications

• QAOAはQUBO問題を解くためのもの
• QUBO問題はNP困難

2.2. MaxCut problem overview

最大カット問題の概要．

• 近似比率が0.9412を越える様な解を求める問題はNP困難らしい．
• 古典アルゴリズムの最良パフォーマンスは$\alpha\simeq 0.878$程度らしい

2.3. Classical algorithms for QUBO problem

一旦後回しにする

2.4. Variational quantum algorithms

• QAOAはVQAの一部

2.4.1. Variational Quantum Eigensolver(VQE)

• ハイブリッドの解法
• $\theta$の最適化を行う
• 変分原理を利用

2.4.2. Quantum Adiabatic Algorithm(QAA)

2.4.3. Barren plateaus

2.5. The Quantum Approximate Optimization Algorithm(QAOA)

3. QAOA analysis

3.1. Ansatz variants

回路の設計手法について．

$\hat{U}(\gamma,\beta)=e^{-i\beta_p\hat{H}_M}e^{-i\gamma_p\hat{H}_C}\cdots e^{-i\beta_1\hat{H}_M}e^{-i\gamma_1\hat{H}_C}$

• ansatzの選び方は問題による

当セクションではQAOAのansatzの設計やバリエーションについて紹介・議論する．

3.1.1. Multi-angle QAOA

https://www.nature.com/articles/s41598-022-10555-8

• 変分パラメータ数を増やすことで近似率を上昇

In ma-QAOA, new parameters are introduced into the circuit so that each element of the cost and mixer layers has its angle instead of one angle for the cost operator and one for the mixer operator

$$U_C(\gamma_l) = e^{-i\sum_{a=1}^{m}\gamma_{l,a}H_{C,a}} = \prod_{a=1}^{m}e^{-i\gamma_{l,a}H_{C,a}}$$

$$U_M(\beta_l) = e^{-i\sum_{v=1}^{n}\beta_{l,v}H_{M,v}} = \prod_{v=1}^{n}e^{-i\beta_{l,v}H_{M,v}}$$

• $\gamma_{l, m}$: $l$はレイヤ，$m$はグラフの辺の数
• $\beta_{l,m}$: $l$はレイヤ，$n$は頂点の数(=qubit数)
• コスト層，ミキサー層の各要素がそれぞれ角度のパラメータを持つ
  • 各要素とは？各量子ビットのこと？っぽい？
• 一般のQAOAはma-QAOAの一種：ビットやノードごとでのパラメータが一致したもの

3.1.2. QAOA+

3.1.3. Digitized counterdiabatic QAOA

3.1.4. Adaptive bias QAOA

3.1.5. ADAPT-QAOA

3.1.6. Recursive QAOA

3.1.7. Quantum alternating operator ansatz

3.1.8. Qarm-starting QAOA

3.1.9. FALQON

• ハイブリッド形式 → 将来的に情報のやり取りがボトルネックになる
  • 最適化も量子コンピュータで行うことができないか？

3.1.10. Fermionic QAOA

3.1.11. Quantum dropout

3.1.12. Spanning tree QAOA

3.1.13. Ansatz architecture search

3.1.14. Modified QAOA

3.2. Parameter optimization

パラメータの最適化手法について