BrainPad株式会社ブレインパッドのデータ活用に関する取り組みや製品・サービス開発の裏側、社員の日常などをご紹介します。分析エントリーこんにちは、A.I.開発部の太田です。今回は量子アニーリングの簡単なシミュレータを作ってみたり、実際のD-Waveを使ってみた経験から、物理を専門としない人向けに量子アニーリングについて解説しようと思います。(シミュレータのコードはgithubで公開しています。私自身、量子アニーリングについては最近勉強し始めたところなので、色々ご指摘いただけると幸いです。技術調査や社内への展開を行っており、その一環として昨年12月に早稲田大学の田中先生をお呼びして開催した量子アニーリング勉強会が社内で大変好評でした。昨年度は量子アニーリングに関する一般書籍が発売されたり、科学雑誌「Newton」でも特集されており、物理学者以外の一般の方にも、量子アニーリングが認知され始めているように感じます。2017)という量子アニーリング分野での最重要な国際会議1が日本で開催されることもあり、日本国内での盛り上がりは昨年以上になるのではないかと個人的には思っています。「量子」という言葉を聞くと、何やら難しそうな印象を受けるかと思います。私も最近までは、「そもそもどうやって使うものなの?普通にプログラミングするの?何か物理的な操作をするの?物理の知識はどれくらい必要なの?」という状況でした。そんな中、3月に運良く実際にD-Waveを操作できる機会2があり、その時に思ったのがシミュレータを使うのも実機を使うのも、使い方という観点からは大差がない(怖がらなくて良い)量子アニーリングの理論に踏み込まないのであれば、物理の知識は必要ない(怖がらなくて良い)ということでした。シミュレータを書いたし、D-Waveの使い方もわかったし、使うだけなら物理がいらないこともわかったし、コツコツ勉強してきたことを物理を専門としない人向けに展開するのも意味があるかな、と思ったので、可能な限り物理用語を使わずに量子アニーリングについて解説してみようと思います。量子アニーリングとはなにか近年注目を浴びている「量子コンピュータ」の作り方には、大きく分けて2つあります。1つ目は「量子回路方式(ゲート式)」と呼ばれるもので、1980年代から研究が続けられてきました。1つが「量子アニーリング方式」と呼ばれるもので、1998年に東京工業大学の西森教授たちが提案した手法です。その代わりに、扱える変数の数4はゲート式よりも圧倒的に多くなっています。量子アニーリング方式は、できることが限られている反面、使い方はとてもシンプルです。古典コンピュータやゲート式の量子コンピュータでは、自分のやりたいことを実現するには、まずプログラミングをしなければいけませんが、量子アニーリング方式の場合はパラメータを設定するだけです。一般のウェブサービスやウェブAPIを使うのと似た感覚です。インターネット経由でAPIをコールする形で利用可能です。D-Waveの実態を知るという意味で、以下の動画はとても面白いので興味のある方はぜひご覧ください。イジングモデル量子アニーリングを利用するにはパラメータさえ設定できれば良いのですが、具体的にどんなパラメータがあるのかについて説明します。数式が出てきますが、ご容赦ください。組み合わせをみつけることができます。実数値のパラメータです。ことをスピンと呼びます。optimization)と呼ぶことが多いのですが、とすればお互いに変換することができるので、QUBOとイジングモデルは等価です5。解釈する上で便利なことがあるので残してあります。明らかなのですが、手で変形しているとついつい忘れがちなので気をつけてください。数式だけ見てもイメージがつかないと思うので、簡単な例を見てみましょう。組み合わせを書き下すと以下の表の通りになります。とることがわかります。組み合わせを見つけることだけです。と膨大な数となります。最小とする組み合わせ)を選んでくれるのが量子アニーリングです。上記の例だけだと、具体的な使い方やどんなことに使えそうかイメージがわかないと思うので、2つめの例として、画像の修復を紹介します。ここでは2値画像を対象としますが、グレースケール画像やカラー画像にも適用可能です。以下のような2値画像があったとします。きれいな「量子」という文字でしたが、様々な経緯でノイズが混じってしまったという設定です6。この画像からノイズを除去することを考えます。いう関数を最小化する問題に帰着させなければいけません。画像をスピンで表す方法を考えます。いろいろな方法が考えられますが、今回の場合は画像の各画素が2値なので、素直に各画素をスピンの値に対応させてみましょう。画素が1であれば、対応するスピンが+1、0であれば-1です。決めていきたいのですが、ノイズの混じっている画像以外に使えるデータがないので、いわゆる外部知識として、以下の性質を仮定します。最小化し、その時のスピンを読み取ることで、上記の性質を満たすような画像を見つけることができます。なおしたもの)として、という項を入れれば良さそうです。小さくなることが確認できます。依存しない正の定数として、という項を考えます。ついてだけ和を取ることを意味します。小さくなることが簡単にわかります。大きさをどうしたらよいか、という問題はありますが、それは結果をみながら調整します。設定するコードを示します。量子アニーリングマシンに投げれば、ノイズの除去された結果がかえってきます。いえ量子アニーリングマシンの実機は使えないので、シミュレーションをしてみました。シミュレータに投げてみた結果が以下となります。元画像ではなくランダムなスピンで初期化しているので、ランダムだったスピンが徐々にそろっていく様子がわかるかと思います(上記のコードで定式化すると、左端と上端にゴミが残ります)。このように、量子アニーリングを使うには、適切なパラメータを探し出す作業(イジングモデルへのマッピング)が必要となります。するか考えなければいけません。構成していくのが良さそうです。次に、もう少し複雑な例として、巡回セールスマン問題を紹介します。巡回セールスマン問題は、「セールスマンが都市をまわるときに最小の移動距離で回りなさい」という問題です。この問題そのものをビジネスで応用する機会はあまりないかと思いますが、少し拡張することで配送計画の最適化など多彩な応用先があります。上述の論文にそって、下図のようにイジングモデルにマッピングします。)であることに注意してください。いうようになっています。ように書くと、全都市を回ったときの総距離はで表せます。ついて二次形式なので、量子アニーリングで最適化することができそうです。