QAOA 定式化まとめと留意点

これまで紹介してきた定式化は、以下の通りです。

参考資料には、その他、以下のような定式化が紹介されています。

Tree Probrems
- Minimal Spanning Tree with a Maximal Degree Constraint
- Steiner Trees
- Directed Feedback Vertex Set
- Undirected Feedback Vertex Set
- Feedback Edge Set
Graph Isomorphisms

また、参考資料の結論には、以下のように書かれていることには、十分留意をする必要があります。

AQO（adiabatic quantum optimization、断熱量子最適化) が、これらの問題に対する効率的な解決策を提供するのにどの程度役立つかは、解決策が正確であるか近似であるかどうかは未解決の問題です。AQO が従来の多項式時間アルゴリズムよりも効率的に多項式時間で解決できる「簡単な」問題が存在し、AQOが実装されたデバイスを使用して簡単な問題を解決できる場合があります。

整数のリスト $n_{1}, \ldots, n_{N}$ から最大値をみつける問題を考えます。$i=1, \ldots, N$ に対して、バイナリ変数 $x_i$ を導入すると、イジングモデルは、以下のようになります。汎用量子コンピュータは、この問題を効率的に解けます。

$$
H=A\left(1-\sum_{i} x_{i}\right)^{2}-B \sum_{i} n_{i} x_{i}
$$

$A>B \max \left(n_{i}\right)$ とすれば、この問題は解けます。

実際、この問題は完全グラフの確率場イジングモデルのように見えますが、これには非常に単純な $O(N)$ 古典的なアルゴリズムがあります。問題自体を解決するよりも、このアルゴリズムを量子デバイスでプログラムする方が確実に時間がかかります。

上記の例は、問題の「難しさ」が時として人を欺く可能性があることを示しています。つまり、簡単に解くことのできる問題をことさらに難しく見えるようにすることができるということです。

これらのハミルトニアンは、一見、難しそうに見えますが、それは、単に多くのスピンを用いているだけなのかもしれません。

量子アルゴリズムを簡素化したり、エネルギーギャップを増やす方法を研究することは、非常に必要な取り組みです。