「1億倍速いコンピュータ」に利用--量子アニーリング理論の可能性(1)

吉澤亨史 山田竜司 (編集部)

2016-08-25 06:30

 カナダのD-Wave Systemsが開発し、GoogleやNASAが導入した量子コンピュータ「D-wave」が「既存のコンピュータの1億倍速い」という実験結果を出したのが記憶に新しいところだが、このD-Waveの実現に大きく貢献したのが「量子アニーリング」理論だ。量子アニーリングは、どんな組み合わせが最適かを計算する「組み合わせ最適化問題」の解法の1つとして研究されているものだが、D-Waveの登場で注目が集まっている。

 そこで今回、量子アニーリングの舞台となる組み合わせ最適化問題と量子コンピュータの研究で平成28年度文部科学大臣表彰若手科学者賞を受賞した京都大学大学院情報学研究科システム科学専攻助教、大関真之氏と、量子コンピュータに関係する研究で第9回日本物理学会若手奨励賞を受賞し、学位取得後より量子アニーリングの研究を進めている早稲田大学高等研究所助教である田中宗氏に、量子アニーリングについて対談していただいた。

--「量子アニーリング」とは何でしょうか。

大関氏 量子アニーリングは「組み合わせ最適化問題」を量子力学、つまり物理の理論を利用して解くための汎用的な解法です。量子効果の働く磁石を模した実験装置を利用し、量子力学の現象のひとつである「量子ゆらぎ」により、組み合わせ最適化問題の計算を実行します。

 複数のものの組み合わせを最適化したいというときに、どの要素がどんな効果をもたらすかを示す「コスト関数」を考えるのですが、その組み合わせは膨大にあるので全部試すわけにはいきません。そこで適度に均しながら、最適なものを求めていくことになります。

 つまり、最初は乱雑にさまざまな組み合わせを試していきます。組み合わせを「ゆらす」というわけです。その中で目的にはまってくるもの見つけ、揺らす効果(ゆらぎ)を減らしていきます。それがアニーリング(徐冷)です。これは「焼きなまし法」とも呼ばれます。刀鍛冶が刀を鍛えていくときに、熱した鋼をゆっくり冷やすことで落ち着きが出て、粘りが出てくることと同じです。

 刀鍛冶は、熱して柔らかくした鋼を叩いて成形し、急速に冷やすことで硬度を上げ(焼き入れ)、さらに折れにくくするために焼きなましと焼き入れをくり返します。このようにして最も安定した状態を作り出せるということは、古来より自然科学的に知られていました。

 これは熱アニーリングと呼ばれますが、1983年頃に当時のコンピュータ上で擬似的にシミュレーションを行うことで組み合わせ最適化問題に適用した、「シミュレーテッドアニーリング」というものが提案されました。それを元に、熱による駆動ではなく量子力学に基づく動かし方を提案したのが、1998年の東京工業大学の西森秀稔教授と当時博士課程に在学中の門脇正史氏であり、それが量子アニーリングです。要は動かし方で、落ち着いたと思われるものを動かしてみて、まだ動くようなら変更の余地があるというわけです。それをくり返すことで最も安定した状態、つまり最終的な解を得ようというものです。

田中氏 最も落ち着いた状態はよい答え。それは自然の真理なんですね。でも、落ち着くところを見つけるためには、あれこれ試行錯誤しなければいけない、その試行錯誤が賢い試行錯誤であれば、とてもいいわけです。自然界にあるさまざまなことは、結構賢く最適化されています。そういう自然界を模倣する、もっと挑戦的にいえば、自然法則を使って計算をする。そのひとつがアニーリングなのです。


組み合わせ最適化問題のひとつ、巡回セールスマン問題(あるセールスマンが幾つかの都市を一度ずつ訪問し出発点に戻る場合、移動が最短になる経路を求める問題)を、「シミュレーテッドアニーリング」により解く 動画(1分34秒ほどから)。
スタート当初は解を出すために与えられる温度のパラメータが大きく、解は大きく変化するが、温度パラメータは下がるにつれ、解の変化が小さくなり収束していく様子が見て取れる

ZDNET Japan 記事を毎朝メールでまとめ読み(登録無料)

ZDNET Japan クイックポール

自社にとって最大のセキュリティ脅威は何ですか

NEWSLETTERS

エンタープライズ・コンピューティングの最前線を配信

ZDNET Japanは、CIOとITマネージャーを対象に、ビジネス課題の解決とITを活用した新たな価値創造を支援します。
ITビジネス全般については、CNET Japanをご覧ください。

このサイトでは、利用状況の把握や広告配信などのために、Cookieなどを使用してアクセスデータを取得・利用しています。 これ以降ページを遷移した場合、Cookieなどの設定や使用に同意したことになります。
Cookieなどの設定や使用の詳細、オプトアウトについては詳細をご覧ください。
[ 閉じる ]