グラフ条件付きトラスト領域によるクエリ効率的な量子近似最適化

Abstract

量子近似最適化アルゴリズム（QAOA）の低深さ実装では、支配的なコストは回路深さというよりも目的関数の評価回数であることが多い。そこで本研究では、このクエリコストを削減するためのグラフ条件付けトラストリージョン法を提案する。グラフニューラルネットワークがQAOAの角度に関するガウス分布N(mu, Sigma)を予測する。平均は局所最適化器を初期化し、共分散は探索を制約する楕円体のトラストリージョンを定め、予測された不確実性はインスタンス依存の評価予算を決定する。したがって、学習された分布は単なる初期パラメータ推定ではなく、探索方策を定義する。 局所的な滑らかさ、曲率、キャリブレーション、ノイズに関する明示的な仮定のもとで、トラストリージョン内における目的関数の劣化に関する上界、勾配分散の下界、脱分極ノイズ下での期待目的関数の順序の保存性、有限サンプルにおけるカバレッジ保証を導出する。提案法を深さp = 2でMaxCutに適用し、頂点数n = 8-16のErdos-Renyi、3正則、Barabasi-Albert、Watts-Strogatzグラフ上で評価する。ランダム再起動および最も強い学習済みポイント予測のベースラインと比較して、本手法は回路評価回数の平均を343および85から45 +/- 7へと削減しつつ、サンプルされた近似比を濃度（concentration）ベースのヒューリスティックから3パーセンテージポイント以内に維持する。 本手法は絶対的な近似比を改善しない。その利点は、同等の解の質においてクエリコストが削減される点にある。予測的不確実性は実験でキャリブレーションされており、ECE = 0.052、Spearman相関rho = 0.770である。また、学習されたトラストリージョンは訓練時に用いなかったグラフサイズへも転移する。これらの結果は、QAOAのアンサンブルを変更することなく、グラフ条件付けトラストリージョンによりクエリコストを削減できる、低深さでクエリが支配的な状況を示している。