量子アニーリングの事始め(1)

初めまして,これから量子アニーリングをメインに解説記事を書いていく予定です.

よろしくお願いします．

第一回目としては組合せ最適化問題の例について解説していきます．

量子アニーリングとは組み合わせ最適化問題と呼ばれる一般的に解くのが困難とされている問題に対して提案された計算手法です．

組み合わせ最適化問題の代表的な問題として巡回セールスマン問題やナップサック問題があります.

自分の行きたいお店を全部回るために最短な距離で回るにはどういう経路を通ればいいんだろうかっていう問題が巡回セールスマン問題です．

ナップサック問題とはある条件のもとで荷物をどうやったら最小化できるかという問題です．

この問題にコスト関数(エネルギー関数)Eと呼ばれる関数を定義します. 巡回セールスマン問題だとこのような感じになります.

この問題は経路を「通る」=+1 or 「 通らない」=0 の二値の問題になってます. が場所aと場所bの距離を表しています.

このように0or1の二値問題の最適化問題をQUBO (Quadratic unconstrained binary optimization)と言います．QUBOの問題を真面目に解こうとすれば10変数では2¹⁰通りの計算 30変数では2³⁰通りの計算が必要となり, 今の古典コンピュータでは解けない問題となっています．

そのためコンピュータサイエンスではこのようなNP困難な問題に対して, 近似的に解くアルゴリズムを開発してきました. 一番有名な方法はSimulated Annealing(SA,焼きなまし法)と呼ばれる方法で,

熱した鉄をだんだんと冷ましていき強固なものにしていくような手法を模したものに当たります．

次回はこのSAのアルゴリズムとその基本となったイジングモデルについて解説します．