QAOA 定式化 ハミルトニアンサイクル セールスマン巡回問題

ハミルトニアン・サイクルとパス問題

グラフ $G = (V, E)$ $N=|V|$とします。有向グラフであっても、無向グラフであっても、この解法の結果に変わりはありません。

ハミルトンパス問題とは、グラフ内のあるノードから始めて、辺に沿って移動し、グラフ内の他のノードを訪問して、同じノードに 2 回戻ることなくグラフ内のすべてのノードに到達できるかどうかという問題です。

ハミルトンサイクル問題とは、これに加えて、最後に訪れたノードから出発点に戻ることができるかどうかという問題です。

ハミルトニアンサイクル問題

一般性を失うことなく、頂点に、$1,\cdots,N$ とし、集合 $(uv)$ 有向とする。すなわち、$uv$ の順番を問題にします。$(uv)$ が辺の集合に追加されるたびに $(vu)$ が辺の集合に追加された有向グラフを考えるだけで、無向グラフに拡張することは簡単です。

$v$を辺、$i$ を訪問する順序として、$N^2$ ビットの $x_{v,i}} 変数を考えます。

エネルギーは、３つの後からなり、最初の２つの制約条件は、頂点が一回だけ経路に含まれるということと、すべての $j$ に対して、$j^{th}$ ノードがなければならないということです。最後に、訪問する候補のノードに対して、 $x_{u,j}$ と $x_{v,j+1}$ が両方 $1$ で、もし $(u v) \notin E$ なら、エネルギーのペナルティを付け加えます。もし問題がとけたら、$N+1$ は、$1$ となることに注意してください。

$$
H=A \sum_{v=1}^{n}\left(1-\sum_{j=1}^{N} x_{v, j}\right)^{2}+A \sum_{j=1}^{n}\left(1-\sum_{v=1}^{N} x_{v, j}\right)^{2}+A \sum_{(u v) \notin E} \sum_{j=1}^{N} x_{u, j} x_{v, j+1} \text { . }
$$

$A\gt0$ は定数です。

ハミルトニアンパス問題

ハミルトニアンパス問題を解くには、最初と最後のノードが結合されているかどうかは問わないので、最後の和を$1$ から $N-1$ に変更します。この問題を解くには、$N^2$ 個のスピンが必要です。

ハミルトニアンサイクル問題のスピン数を減らす

ハミルトニアンサイクルのスピン数は、すこし減らすことができます。ノード $1$ はかならずハミルトニアンサイクルに含まれていないといけません。また、一般性を失うことなく、$x_{1, i}=\delta_{1, i}$ とすることができます。これは、ノード $1$ が最初に来るように順序づけさせることを表します。結果として、スピンの数は、$(N-1)^{2}$ となります。

セールスマン巡回問題

グラフ $G=(V, E)$ にたいするセールスマン巡回問題というのは、各辺 $uv$ にたいして、重み $W_{uv}$ が付けられていて、巡回したときの重みの和を最小にするという問題です。

この問題を解くには、$H_A$ を、ハミルトニアンサイクル問題のハミルトニアンとして、$H=H_{A}+H_{B}$ としたとき、単純に以下のハミルトニアンを付け加えます。

$$
H_{B}=B \sum_{(u v) \in E} W_{u v} \sum_{j=1}^{N} x_{u, j} x_{v, j+1}
$$

ここで、$B$ は、$H_A$ の制約条件を破らないために、$0<B \max \left(W_{u v}\right)<A$ を満たすように十分小さくしないといけません。もし、もとの位置に帰らなくてもいいなら、$j$ にたいする和を、$1$ から$N-1$ にすることができます。ハミルトニアンサイクル問題同様、スピンの数は、$(N-1)^{2}$ にできます。

参考資料

Andrew Lucas “Ising formulations ofmanyNPproblems” arXiv:1302.5843