「組み合わせ最適化問題」を瞬時に解く「CMOSアニーリング」とは何か：5分でわかる最新キーワード解説

膨大なパターンから実用に適した解を導く「組み合わせ最適化問題」を、量子コンピュータ並みの性能で実現する新型コンピュータを日立製作所が開発しました。中核となる技術が「CMOSアニーリング」です。

[キーマンズネット]

　今回のテーマは、組合せ最適化問題を従来の1800倍のエネルギー効率で計算可能な、室温で動作する新しいコンピュータ。利用されているのが「CMOSアニーリング」という技術です。「世界初の商用量子コンピュータ」と言われ話題となった「D-Wave」と同様に組合せ最適化問題の計算を、一般的なCMOS製造プロセスで作れるチップで実現します。

「CMOSアニーリング」って何？

　物流など社会インフラの各領域で求められる「組合せ最適化問題」をスピーディに解決（近似解の導出）する、半導体を用いた新しい手法。2015年2月に日立製作所がこの手法を採用した半導体回路を試作し、2万0480のパラメータ（組合せパターンとしては約1兆の500乗通り）の中から最適に近い実用的に用いることの可能なパターン（近似解）をわずか数ミリ秒で求められることを実証した。試作での処理に要する電力は0.05Wで、これは汎用コンピュータによる従来手法に比べ約1800倍のエネルギー効率だ。

図1 試作CMOSアニーリング専用LSIチップ（資料提供：日立製作所）

　組合せ最適化問題を迅速に解く「量子アニーリング」手法を用いる超電導素子を使用したコンピュータ（D-Waveが開発、製品化した商用量子コンピュータ/「関連するキーワード」の項参照）で必須な極低温までの冷却が不要で、一度に処理可能なパラメータ数が40倍（量子コンピュータは現在512、今回の試作機では20480）という特長がある。しかも一般的なLSIのほとんどが採用するCMOS構造をとるため、製造プロセスのさらなる微細化やチップの超並列化が容易で、圧倒的に大規模な組合せ最適化問題に対応できると期待される。

• 一体、何に役立つの？

　従来型のコンピュータでは「どこまで計算すれば最適解が見つかるのか分からない」というような、組合せ最適化問題の解決は難しい。有名な組合せ最適化問題に「巡回セールスマン問題」がある。これは複数都市を1回ずつ訪問して最初の出発地に戻るための最短経路を求めるという問題だ。巡回する都市が5〜6都市程度ならそう大変でもないが、30都市となるとどうだろう。巡回経路の数は（30-1）!/2になるので、約4.42×（10の30乗）という途方もない数になる。このような組合せ最適化問題では決定するパラメータがn個あれば、図2に示すように計算は2のn乗回繰り返すことになる。仮にnを100としても、1.27×（10の30乗）回の計算が必要だ。このような「組合せ爆発」が起きると、全ての組合せを計算していては、現在のスーパーコンピュータでも年単位の時間がかかってしまう。

図2 従来型の計算手法では計算量が爆発的に増加する（資料提供：日立製作所）

　そこで、正攻法で最適解を求めるのではなく、何らかの「裏ワザ」を使って、本当に最適解とは限らないが、実用に供するのに十分な解を現実的な時間内で求める必要がある。現実的な問題になぞらえるなら、トラックの一番低コストな荷物集配経路を探すのに、何時間もかけてはいられない。集配地点が決まった時点で、正解ではなくてもいいからそれに近い経路（近似解）を示して欲しい。このような需要は、例えば、交通システムで渋滞解消をするために最適な交通量や移動コストの見極めや、電力システムが電力を安定供給するために必要な蓄電量の想定など、大規模なパラメータでの計算が必要な、多くの社会インフラ課題に共通するものだ。