イジングモデルにおける混雑度計算（量子ゲートQAOA、量子アニーリング対応）

VWなどは道の混雑度を計算してそれを最適化することでタクシーの混雑を緩和しました。ここでは、勉強会で扱った混雑度の指標が使いやすかったので、みてみたいと思います。

イジングモデルを利用した混雑度はとても利用範囲が広く計算がしやすいです。混雑度を利用した問題は、（混雑度）＋（制約条件）を決めてあげることでいろいろな計算ができます。

混雑度はエッジに含まれる量子ビットの数を2乗することで求めることができます。

道路ネットワークを見てみます。道路をそれぞれに何台自動車がいるかで混雑を計算できます。

それぞれの場所にいる車の台数＝量子ビット数を足し合わせて二乗します。それを全体で足し合わせることで、混雑度を計算できます。

上記は、同じ道路にいる自動車を足し合わせてそれぞれ二乗します。それぞれ混雑度は1+1+4で6になります。自動車をずらすと混雑度が減ります。うまく二乗が使われます。

提案ルートの場合には、場所が一か所とは限りません。複数のエッジを経由する場合には、1量子ビットが複数の場所に現れます。

店舗の場合も同様です。棚割りから通路をモデル化します。人の配置を最適化するには、色塗り分け問題を応用し、場所に対して人の位置を最適化する制約条件をつけることで混雑度を計算できます。

人数に応じてグラフを通路ごとに作り、つながっている通路同士で対応する人間のノードをエッジで接続して制約条件をつけます。

混雑度はよく使われる指標ですが、基本的にはJijに複雑な値が出ず、整数で計算ができるので計算結果が出やすいのでお勧めです。是非色んな場面で活用してみてください。