1. HOME
  2. 刊行物
  3. 金融ITフォーカス
  4. カテゴリから探す
  5. 数理の窓
  6. セールスマンと量子コンピュータ

セールスマンと量子コンピュータ

2017年4月号

松本ゆかり

「巡回セールスマン問題」という有名な問題がある。これは、セールスマンが複数の都市をそれぞれ1回ずつ訪問して出発した都市に戻ってくる際に、どのような順序で都市を訪れると最短経路になるかを見つけ出す、というものである。

 この問題は状況をイメージしやすいが、全ての巡回パターンを洗い出すことでしか厳密な最短経路を導くことはできないとされている。巡回パターンは、訪問する都市の総数をnとすると(n-1)!/2通りとなり、6都市の場合は60通りだが、12都市になると1900万通りを超え、30都市の場合は、1秒あたり1京回の計算が可能なスーパーコンピュータ「京」でも、答えを出すのに1041万年もの時間がかかる。

 このように計算パターンが膨大な問題について、厳密な1つの最適解を見つけるのではなく、厳密解に近い最適解を短時間で見つけるためのアルゴリズムが研究されてきた。例えば、生物の生存適応過程を模した遺伝的アルゴリズムもその1つだ。

 近年、期待されているアルゴリズムに、量子コンピュータ上で動く「量子アニーリング」がある。これは、量子力学の「焼きなまし現象」を模倣したアルゴリズムである。焼きなましとは、金属に熱を加えた後、ゆっくり冷やした場合、元の状態よりもより原子が安定した状態に落ち着く現象のことだ。量子アニーリングは、金属の焼きなまし現象の用語を借りると、安定した原子の状態を最適解と位置づけ、温度の低下とともに原子の状態が変わっていく過程をアルゴリズム化したものである。

 量子コンピュータは、量子力学の性質である「重ね合わせ」状態を作り出すことで、1回の計算で同時に複数パターンの初期値から最適解を見つけ出すことができるので、計算スピードが格段に速くなる。また、最適化問題の従来のアルゴリズムでは、広く見れば他に最適解があるはずなのに、局所的に最適な解に陥ることがよくあった。それを、「量子トンネリング効果」により局所解から抜け出すことで解決できるのも量子アニーリングの1つの特長だ。

 この量子アニーリングアルゴリズムが適用できるのは、現状では限られた最適化問題(※1)のみであり、スーパーコンピュータのような汎用計算ができるわけではない。それでも、世の中には膨大な情報があふれており、それらを活用するためには最適化問題を解くことは必要不可欠であり、量子コンピュータへの期待は高まっている。

 明日あなたの家に届く商品は、もしかしたら量子コンピュータで導き出された最適な経路を辿って来るものかもしれない。

1) 最適化問題の中でも量子コンピュータが得意であるものとそうでないものが実験によって明らかになりつつある。

※組織名、職名は掲載当時のものです。

印刷用PDF

Writer’s Profile

導入事例

松本ゆかり

金融デジタル企画一部
副主任

このページを見た人はこんなページも見ています