2020年の論文, "MaxCut algorithm selection"の検索でヒット;
- Moussa, Charles, Henri Calandra, and Vedran Dunjko. "To quantum or not to quantum: towards algorithm selection in near-term quantum optimization." Quantum Science and Technology 5.4 (2020): 044009.
要旨
MaxCut求解において, QAOA(The Quantum Approximate Optimization)が どのような問題に有効かをGW(Goemans and Williamson)の比較により検証する
QAOA / GWとは
- どちらも近似アルゴリズムである.
- QAOAはゲート方式量子アルゴリズムで, circuitの深さpに応じて2p個のパラメタ.
- GWは有名な近似アルゴリズムでSDP緩和を用いる. 近似率は約0.878だが, グラフの性質によってはより良い近似率を出す. (e.g. 3-正則グラフであれば近似率0.932)
ちなみに, 近似アルゴリズム(approximation algorithm)は, 解の精度(近似率)保証が可能なもので, そうでないものは単に heuristic algorithmと区別されているみたい.
評価方法
- インスタンス; 4-正則グラフ(ランダム生成)を用いる(生成が容易で, まだ先行研究で調査されていないためと述べられている) ノード数は 11 から 24 の間で, それぞれ20個のインスタンス, 合計280個の問題を用意
- 評価基準
- それぞれの問題に対して最適解は総当たりにより取得. それをもとに下記の2つの評価基準を使用
- (基準 1); QAOA vs. GW; QAOAがGWよりも良い近似率であるか
- (基準 2); the good heuristic criterion; QAOAが良い近似率を出すか, 具体的には近似率0.98以上で, GWに0.02の差をつけているか
- それぞれの問題に対して最適解は総当たりにより取得. それをもとに下記の2つの評価基準を使用
性能調査手法
- (1) 与えられたグラフから特徴量を抽出する
- (2) 学習
- (1)を説明変数, 基準ごとのYES/NOをラベルとする訓練データを生成し, LightGBM, XGBoostにより学習を行う.
- 学習結果から, QAOAが有効な問題の性質が何かを逆説的に調べる
実験結果
- QAOAが有効な問題が存在
- LightGBM, XGBoostによる学習がうまくいっていることを示し, (予測精度96%)
- その上で予測により効いている項目2つを抽出.
- expected_costGW_over_sdp_cost: the expected cost over the 1000 random projections per instance divided by the cost of the relaxation C_{rlx}.
- std_costGW_over_sdp_cost: the standard deviation of the cost approximated using 1000 random projections divided by C_{rlx}.
