スマートフォン用の表示で見る

量子アニーリング

サイエンス

量子アニーリング

りょうしあにーりんぐ

組み合わせ最適化問題を量子力学的な効果を利用して解くための汎用の解法 。Quantum annealing。

量子焼きなまし法とも呼ばれる。

概要

この手法は確率的な探索法の一種である「シミュレーテッド・アニーリング(模擬焼きなまし法)」における確率的探索を、量子力学的な並列処理で置き換えたものであり、従来の手法より効率の向上が見られることが知られている。東京工業大学理学部長である西森秀稔が考案したとされる。

カナダのD-Wave社は、この手法ハードウェアレベルで実現した装置を商品化しており*1ロッキード・マーティンNASAなどはこのハードウェア「D-Wave Two」を用いて、航空機の制御ソフトのバグ検出や系外惑星の探索などを「組み合わせ最適化問題」として表現し、解く試みを行っている。

またビッグデータなど莫大なデータを効率的に扱えるとして注目されている。

使用例

この解法を適用できる「組み合わせ最適化問題」の代表例に、セールスマンが複数の都市の全てを訪問する場合に、最も距離が短くなる経路を探し出す「巡回セールスマン問題」がある。

巡回する都市が少ないと、都市の組み合わせの数が少ないので最短経路は比較的簡単に見つけ出せるのだが、都市が増えるに従って巡回経路が爆発的に増加するため、理化学研究所のスーパーコンピュータ「京」を使っても、現実的な時間で最短経路を見つけられない。そのため現在はその問題に対する「近似解」を出そうとしているが、この解法を用いれば誤差のない完璧な解である「厳密解」を得たり、従来より精度の高い近似解を得る可能性を秘めている*2