旅行セールスマン問題のための確率的SRAMビットを備えた28nmプロセスのコンパクトなデジタル・コンピュート・イン・メモリ・イジングアニーラ

より賢い経路とチップが重要な理由

毎日、配送トラックや航空便、データパケットは、すべてが時間どおりに、かつ最小のコストで届くようにどの経路を取るかを決めなければなりません。この種の課題は旅行セールスマン問題として知られ、立ち寄り地点が増えるにつれて強力な計算機でも手に負えなくなります。本要約の元論文は、磁性材料の考え方を取り入れ、標準的なコンピュータ記憶装置に直接組み込んだ新しいタイプの専用チップを提案し、こうした経路計画問題をはるかに効率的に扱います。

各地点を一度だけ訪れるという古典的パズル

旅行セールスマン問題は簡単に言うと次の問いです：都市のリストとそれらの間の距離が与えられたとき、各都市をちょうど一度訪れ出発点に戻る最短の巡回はどれか？問題は都市数が増えるにつれて可能な巡回の数が爆発的に増え、すべての選択肢を調べることは実際には不可能になる点です。そこで現実的な手法は最良とは限らないにせよ非常に良い経路を探索します。有望なアプローチの一つは、イジングモデルと呼ばれる小さな磁石のネットワークがエネルギーの低い状態に落ち着く性質を模したもので、ランダムな変化によってネットワークを慎重に「揺らし」徐々に落ち着かせることで局所的な悪い選択を抜け出し、より良い経路を見つけます。

メモリチップを問題解決器に変える

このプロセスを通常のプロセッサで動かす代わりに、著者らはそれをメモリハードウェア自体に組み込む、いわゆるコンピュート・イン・メモリの戦略を採りました。彼らは28ナノメートル技術でコンパクトなチップを設計し、各小さなメモリセルが距離情報を格納すると同時に計算に直接参加します。巧妙な点は、メモリセルの製造時の微小なばらつきを乱数の内蔵源として利用していることです。これにより大がかりな乱数発生器が不要になります。制御された電圧の“軽い刺激”で保存値を一時的に撹乱すると、一部のビットが確率的に反転し、追加回路なしでアニーリング過程に必要な柔らかいランダム性を供給します。

大きな地図を小さな近傍に分割する

イジング風のソルバーを大規模な経路計画に用いる際の主な障害の一つは、必要なデータ量の膨大さです：96都市の巡回を完全に表現しようとすれば通常は膨大な接続網とメモリが必要になります。これを避けるため研究者らは近接する都市を小さなクラスタにまとめ、さらにそれらを階層的にいくつかのレベルに配置します。最高レベルではクラスタの並び順を決め、次のレベルでは各クラスタ内の都市の順序を細かく決める、という具合です。この段階的な手法により必要なメモリと接続の量が劇的に削減され、ハードウェアの複雑さは都市数の四乗に比例して増えるものから二乗に抑えられ、さらに実際に必要な距離情報だけを詰めて格納することで圧縮されます。

チップが多くの選択を同時に更新する仕組み

チップ内部では3つの都市のグループが基本ブロックとなり、並列に処理されます。メモリアレイは各クラスタ内で巡回の一部を入れ替えたときの全体の巡回長の変化を高速に計算できるように整理されています。直接相互作用しないクラスタもあるため、システムはすべての「奇数」クラスタを一度に更新し、次に「偶数」クラスタを更新することで、あたかも一度に1つずつ変更しているかのように振る舞いつつ探索を高速化します。各ラウンドでチップはノイズのあるメモリセルを使って、性能の悪化する動きを確率的に受け入れるかどうかを決めます—探索初期は受け入れ確率が高く、後になるほど低くして落ち着かせる—これにより金属を冷やす過程を模倣して経路を短くしていきます。

実験室のチップから大規模経路へ

プロトタイプチップはこの特殊なメモリをわずか6キロビット搭載しているにすぎませんが、96都市の旅行セールスマン問題を約620マイクロ秒で解き、エネルギー消費はマイクロジュール未満です。同じ課題向けに設計された既存のハードウェアと比べると、問題サイズ当たりの必要メモリ量で数百倍に達する改善を示します。シミュレーションでも、多数のこうしたメモリブロックを並べれば、同じ設計が数千都市規模の問題にほぼ線形にスケールできることが示されています。一般読者にとっての重要な結論は、馴染みのあるメモリチップを能動的な問題解決器に作り替え、製造上避けられないばらつきを有用な特徴に変えることで、小型で高速、かつ省エネルギーなハードウェアがリアルタイムで複雑な経路やスケジュールの計画を支援できる可能性を示している点です。

引用: Kong, Y., Lu, A., Liu, H. et al. A compact digital compute-in-memory Ising annealer with probabilistic SRAM bit in 28 nm for travelling salesman problem. npj Unconv. Comput. 3, 15 (2026). https://doi.org/10.1038/s44335-026-00060-w

キーワード: 旅行セールスマン問題, イジングアニーラ, コンピュート・イン・メモリ, SRAMハードウェア, 組合せ最適化