世界的には、CMOSではなく超電導Qubitを使うD-Wave社の量子アニーラが先行しており有名であるが、国内のコンピュータ各社では、組み合わせ最適化問題を解くCMOSアニーラの開発、商用化が盛んである。

組み合わせ最適化問題というのはどのようなものか。どのようにして解くのか。アニーラとはどのようなものか。なぜ、日本のメーカーがCMOSアニーラの開発に力を入れているのか。各社のアニーラはどのようなものかなどを順に見ていこう。

組み合わせ最適化問題

組み合わせ最適化問題の説明で良く用いられる例は、巡回セールスマン問題(Traveling Salesman Problem:TSP)である。

巡回セールスマン問題では、セールスマンが各都市にある顧客を順番に訪問して行くのであるが、すべての都市を1回だけ訪問するという経路でなければならず、同じ都市を複数回訪問してはならない。そして、最後には出発点の都市に戻る。その時に、旅行した合計の距離が最短になる訪問経路を求めるという問題である。

例えば、訪問すべき都市が5つであれば、すべての組み合わせを列記するとして、スタートする都市の選択は5都市、2番目に訪問する都市の候補は4都市、3番目に訪問する都市は3都市、4番目に訪問する都市の候補は2都市で、最後に残った都市が5番目となるので、5×4×3×2×1=120通りということになる。

これらすべての経路について、旅行する距離を求めて一番短くなる経路が求める経路である。5都市の場合はコンピュータを使わなくても求められるくらい簡単であるが、都市数が多くなると状況は一変する。

50都市の場合は、経路の数は50!(階乗)で約3.04×1064となる。仮に1つの経路の評価を10-9秒で行ったとしても、3×1055秒、約1048年掛かる計算になる。これでは太陽の寿命が尽きるまで計算しても、全部の経路の距離の計算は終わらない。

このような問題はNPハードな問題であり、うまい解法は存在しない。巡回セールスマンのケースは実際には起こらないとしても、組み合わせ最適化は、荷物の配送をどの経路で行えば効率が良いか、道路網にどのように車を流せば渋滞が起きないかなど、多くの現実的な問題に解を与えてくれる。このため組み合わせ最適化問題の解を得ることは多くのビジネスにとって重要であり、国内のコンピュータメーカーが、そのためのマシンの開発に力を入れているのは当然であると言える。

(次回は5月30日に掲載します)