応用物理学会微小光学研究会予稿 Vol.133, No.3 最適化問題を解く量子アニーリングと D-wave Quantum Annealing and the D-Wave Machine for Optimization Problems 西森 秀稔 Hidetoshi Nishimori 東京工業大学 大学院理工学研究科物性物理学専攻 Department of Physics, Tokyo Institute of Technology 152-8551 東京都目黒区大岡山 2-12-1-H41 2-12-1-H41 Oh-okayama, Meguro-Ku, Tokyo 152-8551 E-mail: [email protected] あらまし 量子アニーリングは，組み合わせ最適化問題を量子力学の原理を応用して解く汎 用アルゴリズムである。通常の計算機上でシミュレートすることも出来るが，高速性を生か すには専用の装置を使うことが望ましい。カナダの D-Wave 社は，量子アニーリングの原理 に従って動作する装置を開発し，Google や NASA などが導入したことがよく知られている。 本稿では，量子アニーリングの考え方や開発の現状について解説する。 Abstract Quantum annealing is a metaheuristic to solve combinatorial optimization problems using the principles of quantum mechanics. Quantum annealing can be simulated on a conventional computer, but its advantage can best be exploited on a machine dedicated to the physical realization of quantum annealing. D-Wave Systems, a Canadian venture, has developed a quantum annealer and has sold a few to corporate users including Google and NASA. I explain the basic principles of quantum annealing as well as the current status of the development of quantum annealers. 1．はじめに カナダの D-Wave システムズ（D-Wave 社） が量子アニーリングを実行する装置 （D-Wave マシン）を開発し，｢世界初の商 用量子コンピュータ｣として販売している。 既に数台が出荷されており，航空宇宙軍需企 業の Lockheed-Martin，Google，NASA など が顧客リストに載っている。また，複数の国 の国家プロジェクトや企業において，独自の 量子アニーリング装置の開発が始まってい る。こうした状況は，日本国内の専門誌だけ で な く ， New York Times, TIME ， BBC, Economist などの一般誌でもさかんに報道さ れており，研究者の間だけでなく社会的にも 注目を浴びている。 D-Wave マシンとは一体どんな装置なのだ ろうか。どのような原理に基づいて設計され， 何の目的に使えるのだろうか。本当に量子コ ンピュータなのだろうか。本稿では，これら の疑問を念頭に置いて，基本的な動作原理で ある量子アニーリングの提唱者[1]の立場か ら現状の分析と将来の予測を試みる。 2. 何に使えるのか D-Wave マシンは量子アニーリングに従っ て動作するよう設計されている。量子アニー リングは，組み合わせ最適化問題を解くこと を目的とする量子計算の方式である。離散値 を取る変数が多数あってそれらの関数（目的 関数）が与えられているとき，その関数の最 小値，および最小値を与える離散変数値を求 める問題である。例えば，多くの都市を回っ て元に戻る最短経路を求める巡回セールス マン問題はよく知られた例である。組み合わ せ最適化問題は広範な応用範囲を持ってい る。例えば，画像認識や医療診断などを目的 とする機械学習の多くの課題が組み合わせ 最適化問題として定式化できる。 Lockheed-Marti や NASA は，航空機の制御ソ フトのバク検出や系外惑星探索などを組み 合わせ最適化問題として表現し，D-Wave マ シンで解く試みを行っている。D-Wave 社は， 応用物理学会微小光学研究会予稿 Vol.133, No.3 医療，エネルギー，金融などの各分野での利 用に適した応用ソフトの開発を進めている。 量子アニーリングは，従来から広く研究さ れてきた量子ゲートの組み合わせによる量 子計算方式（量子回路モデル）と理論的には 等価であることが知られている。しかし，現 実には，この等価性を利用して量子回路モデ ルを実現するためのハード的な機構は D-Wave マシンには組み込まれてない。あく まで，組み合わせ最適化問題に目的を絞った 装置である。そのため，量子回路モデルにお いてよく知られた素因数分解の高速実行ア ルゴリズム（ショアのアルゴリズム）を D-Wave マシンで実行することは出来ない。 素因数分解の難しさはネット上の暗号の基 盤になっており，ショアのアルゴリズムの発 見は量子コンピュータの研究が大きく活性 化する重要なきっかけになった。このため， 量子アニーリングは量子コンピュータの研 究の主流をなしてきたアプローチとは趣を 異にしている。とは言え，組み合わせ最適化 問題は機械学習を中心として非常に幅広い 応用範囲を持っているので，素因数分解と量 子系のシミュレーションに高速性能がほぼ 限定された伝統的な意味での量子コンピュ ータよりも，量子アニーリングの実用的・社 会的な有用性はむしろ高いとも言える。 に向かって減少させていって（温度を下げる ことに対応），最終的に正解ないしそれに近 い状態に到達することを目指す。 量子アニーリングでは，すべての解候補 （状態）を量子力学的に同時に併存させる。 状態の量子力学的な重ね合わせを利用する のである。重ね合わせの際の係数の 2 乗が， それぞれの解候補（状態）の量子力学的な実 現確率に対応している。重ね合わせた全体が 量子力学的な波動関数となる。その波動関数 を，量子力学の基本方程式であるシュレディ ンガー方程式によって変化させていく。シュ レディンガー方程式に出てくるパラメータ をうまく制御すると，最終的な正解に対応す る状態の係数（確率）が次第に増加していき， 最後に正解だけが残るのである。すべての解 候補の係数をシュレディンガー方程式によ って同時に処理することが一種の超並列計 算となっているが，通常の並列計算と違って， 各係数の処理の仕方が量子力学に従って互 いに強く関連し合っているところに重要な 特徴がある。より詳細については，参考文献 [1]（量子アニーリングを提唱した原論文） や参考文献[8]-[13]の解説をご覧いただきた い。筆者のホームページ[14]にも最新の文献 リストなどの情報を収録してある。 4. D-Wave マシンとは 3. 量子アニーリング 量子アニーリングの考え方をかいつまん で説明しよう。組み合わせ最適化問題の汎用 近似解法（メタヒューリスティック）として は，シミュレーテッド・アニーリングがよく 知られており，現実の問題に広く応用されて いる。シミュレーテッド・アニーリングでは， コンピュータ上で発生させた解の候補を確 率的に遷移させながら，その確率を変化させ ていく。確率は，統計力学のボルツマン因子 に従って制御されており，温度に対応するパ ラメータを高温から低温に向けて変化させ ていく。目的関数の値を最小化することが目 標なので，目的関数値が現在の値よりも下が るような解候補への遷移は無条件に受け入 れる。一方，関数値が上がる遷移も一律には 却下せず，ある程度の確率で受け入れる。最 初はその確率を 1 に近く取って頻繁に遷移 を起こし（高温状態に対応） ，多くの解候補 を幅広く探索する。そして，確率を次第に 0 D-Wave 社は，量子アニーリングの理論を 実際にハードウェア的に実現する装置を開 発した。微小な超伝導回路を基本素子とし， 回路上を超伝導電流が右に回るか左に回る かを，それぞれ量子ビット（量子計算の最小 単位）の 1 と 0 に対応させる。超伝導閉回路 上で実際にどちらに回っているかは測定す るまで不確定であり，これら 2 つの状態の量 子力学的な重ね合わせが実現される。 このような量子ビットを縦に 4 つ，横に 4 つ並べ，縦横の素子が交差する場所に配置さ れた別の超伝導回路を介して結合する（図 1） 。 結合点において，2 つの量子ビットの間の結 合の強さを，解くべき最適化問題に応じて定 められた値に設定する。これが 1 単位となり， たくさんの単位を結合させてシステム全体 を構成する。 応用物理学会微小光学研究会予稿 Vol.133, No.3 金融などの社会の各方面向けの応用ソフト についても急速に開発が進んでいる。 5. 開発の歴史 図1 基本素子には縦に 4 本(Q1 から Q4)， 横に 4 本（Q5 から Q8）の細長い超伝導回路 が配置されている。 装置の外観は約 3 メートル立方の大きな 黒い箱だが，中心となる超伝導回路のチップ は数センチ四方の大きさしかない。超伝導回 路を外部磁場から遮蔽する幾層もの壁，チッ プを 20mK 以下に保つための冷却装置，内部 に人が入って各種調整をするためのスペー スなどが体積の大部分を占めている。 演算回路が超伝導素子で構成されている ので，チップ自体の消費電力は 0 に近い。装 置全体で 10kW 程度の消費電力は，ほぼすべ て冷却用である。そのため，今後システムが 大きくなっていっても消費電力は基本的に 増大しない。半導体技術に基づく通常のコン ピュータとの決定的な違いである。 最新の D-Wave マシン（Washington チッ プ）は 1152 量子ビットを有している。それ らの間の結合の強さを問題に応じて指定さ れた値に調整した後，量子効果の強さを決め るパラメータの値を理論に従って制御出来 るように作られている。これはきわめて高度 な技術である。D-Wave 社が所有しているコ ンピュータ製造技術関連の米国特許数は， IBM， HP， 富士通に次いで世界で 4 番目 とのことである。量子アニーリングの実現を 人々が疑問視して競争相手が現れない間に， 同じ考え方では追随が極めて困難なレベル に達していると言える。特に，超伝導素子に よる量子アニーリングの実装そのものに対 して米国の特許を取得しているとのことで ある。 実際の使用においては，通常のプログラミ ング言語により表現された目的関数を機械 語レベルの表現に翻訳して実行できるよう 設計されている。さらに，医療，エネルギー， 量子アニーリングの原理に従って動作す る装置の開発を進めていた D-Wave 社は， 2007 年に 16 量子ビットのプロトタイプを発 表した。量子回路方式の量子コンピュータの 開発が困難に直面している中で，商用機開発 という一般向けの発表をしたために， D-Wave 社を疑いの目で見る人が少なくなか った。2010 年には 128 量子ビットを持つ商 用機 D-Wave One（Rainer チップ）を発表し， Lockheed-Martin が購入した。このマシンは， 南カリフォルニア大学に設立された量子計 算センターに設置されていて，学術的な研究 に多大のマシンタイムが使われ，多くの論文 が出版されている。2011 年には，128 量子ビ ットのうちの 1 量子ビットおよび 8 量子ビッ トを使った動作検証の論文が Nature に発表 された[2]。量子アニーリングの手順を実行 したときの入出力関係を調べると，量子力学 に従って動作していると考えないと説明で きないデータになっていることを明確に示 した。学術的な意味で説得力のあるデータだ っただけでなく，Nature という「権威ある」 雑誌に掲載されたこと，Lockheed-Martin が 実際に購入したこと，こうしたいくつかの事 実の相乗効果で学問的のみならず社会的に も大きなインパクトを与えた。 2013 年には Google と NASA が設立した量 子人工知能研究所に 512 量子ビットの次世 代機 D-Wave Two（Vesuvius チップ）が納入 された。また，通常のコンピュータと比較し たベンチマークが発表された。その論文の記 述の一部が，前後の脈絡から切り離されて 「通常のコンピュータより 3600 倍速い量子 コンピュータ完成」というキャッチフレーズ で米英の大手マスメディアで取り上げられ るなど，社会的に大きな注目を浴びた。 その後現在に至るまでに， D-Wave One や D-Wave Two の動作検証や比較的小規模な問 題への応用，さらに関連した数値解析や理論 解析の論文が多数発表されている。例えば， タンパク質の安定な構造について，格子上に アミノ酸が配置された模型を使って組み合 わせ最適化問題として定式化することによ り D-Wave One 上で量子アニーリングを実行 応用物理学会微小光学研究会予稿 Vol.133, No.3 した研究では，小さいが 0 ではない頻度で正 しい安定配位が得られると報告されている [3]。また，8 量子ビットの系を D-Wave Two 上で動かして，量子効果の典型例である量子 もつれの大きさを測定したところ，理論予測 と良く一致したことにより，量子力学に従っ た動作が直接的に検証されたとの報告があ り[4]， 計算速度に関しては，スピングラスと呼ば れる問題で，D-Wave Twoを使って得られた 結果と通常のコンピュータによるシミュレ ーションを比較したとき，D-Wave Twoの計 算速度は平均的には通常のコンピュータと 同程度であるとする研究がある[5]。難しい 問題の典型例としてスピングラスについて のベンチマークの報告はこの他にも多数あ る。具体例によってばらつきはあるが，ざっ くり言うと，平均すると通常のコンピュータ と同程度の処理速度というのが現時点での 一般的な評価である 1。 る挙動が見られるという報告であった。最近， やはり 8 量子ビットまでの動作を検証した ところ，量子的なエネルギー構造の理論や量 子もつれの理論と一致するデータが得られ たという報告もある[4]。量子アニーリング 実行されていることの直接的な証拠を提供 したと評価されている。また，別の角度から， 40 量子ビットで量子性を検証した論文も現 れている[5]。40 量子ビット前後までなら， 実際に量子力学に従って動作していること は確立されたと言えるだろう。100 量子ビッ トのスケールになると，入出力関係が量子力 学によって理解されるという論文があるが， 量子力学を使わなくても同じデータが解釈 可能という意見も出ている。しかしながら， 量子力学を使った方が広範囲のデータの統 一的な説明が可能であり，量子効果が効いて ないという主張は受け入れられているとは 言い難い状況にある。 量子アニーリングを正しく実現していた としても量子コンピュータとは言えないと 6. 問題点と展望 する人もいる。量子コンピュータとは，あく D-Wave マシンに関する注目点は３つある。 まで伝統的な量子ゲートを使った量子回路 をハード的に実現した装置であるというこ 第 1 は，D-Wave マシンが本当に量子力学に とである。任意の論理演算を実行出来る（い 従って動作し，量子アニーリングを実現して わゆる｢万能量子計算｣が実現される）のが量 いるかどうかである。第 2 は，D-Wave マシ 子コンピュータだということである。これは， ンは通常のコンピュータに比べて処理が速 科学的な内容の正当性というよりむしろ定 いかどうか。3 番目としては，マシン自体と 義の問題である。 は直接関わりなく，量子アニーリングは従来 型の計算より高速な計算を可能にするのか 6.2 通常のコンピュータより速いのだろう という理論的な問題もある。これらについて か 現状と近い将来の展望を見ていこう。 通常のコンピュータより高速かどうかに 6.1. 本当に量子アニーリングマシンなのだ ついては，問題の種類や，アルゴリズム，コ ろうか ーディング技術，用いるハードの種類などに 2011 年の Nature の論文[2]は，D-Wave One よって答えが違ってくる。量子アニーリング の全システムのうち 1 量子ビットあるいは 8 と比較すべき古典アルゴリズムはシミュレ 量子ビットという小さな部分だけを動作さ ーテッド・アニーリングであるという立場か せたときに，量子力学に基づく理論と一致す ら，系統的かつ包括的に両者を比較した最近 の論文[6]は，高速な通常のコンピュータ上 1 で走る最適化されたコードを D-Wave Two と 日立製作所が，｢CMOS アニーリング｣による 新型コンピュータを作成し，量子アニーリング 比較して，一般には一概にどちらが速いとも を用いた量子コンピュータに匹敵する性能を 言えない，問題によるという報告をしている。 実現したと発表している（2015 年 2 月 23 日付 どのような問題に対して D-Wave Two が高速 の日立製作所ニュースリリース） 。現在の 性を発揮するかについての研究が進んでお D-Wave マシンの速度は通常のコンピュータと り，D-Wave マシンが得意とする問題群の特 同程度なので，日立の｢CMOS アニーリング｣ 徴が明らかにされつつある。 機も通常のコンピュータ上のソフト処理と同 後にも触れるが，あまり速度が上がらない 程度の性能である。 応用物理学会微小光学研究会予稿 Vol.133, No.3 主要な理由は，現在の技術では必ずしも理論 通りに装置の制御ができてないためだとい う見方が有力になってきている。 6.3 理論的な可能性 実際のマシンを離れて理論的にはどうだ ろうか。素因数分解のショアのアルゴリズム のような指数関数的な高速化のアルゴリズ ムが量子アニーリングでは見つかっていな いから，量子アニーリングは役に立たないと いうコメントを聞くことがあるが，実は，特 殊な問題については見つかっている[7]。し かし，素因数分解に比べると問題設定が特殊 で実用性が高くない。指数関数的な劇的な高 速化ではないが，データベース探索を 2 乗の 時間スケールで高速化するグローバーのア ルゴリズムの量子アニーリング版も開発さ れているが，D-Wave マシン上で実現するの は難しい。 指数関数的な高速化の厳密な保証にこだ わらなければ，量子アニーリングがシミュレ ーテッド・アニーリングより速く確実に正解 に行き着くという数値計算や理論解析の報 告は多数ある。通常の計算機で指数関数的な 時間がかかる難しい問題については，量子ア ニーリングでも一般的には同様に指数関数 的な時間がかかると予想されるが，その指数 の係数が小さくなる例が少なからず存在す ると思われる。この指数の係数が例えば半分 になれば，同じ時間で扱える問題の大きさが 倍になるので，実用的には十分意味がある状 況も出現するだろう。 6.4 キャリブレーション誤差と誤り訂正 量子性や高速性以外にも，注目すべき点が いくつかある。ひとつには，ハードウェアの 調整上の精度の問題である。目的関数に現れ るパラメータを問題に応じてマシン上で適 切な値に調整しなければならないが， D-Wave Two で 5%程度の誤差が生じるとの ことである。量子アニーリングを理論通り実 行するには，すべての量子ビットが完全に同 じ性能を持たなければならないが，どうして も少しずつ特性の違いが出てしまう。量子ビ ットごとの特性の差を補正するべく，各量子 ビットに微小な磁束をかけるのであるが，そ れでも完全には同じには出来ない。これによ って生じる量子ビットごとのわずかな特性 の違いは，ベンチマークにおける正答率の低 下の主因のひとつと考えられている。つまり， 現時点での D-Wave マシン （Vesuvius チップ） が通常のコンピュータより必ずしも速くな い主な原因のひとつが，解くべき問題をうま くシステムに入力できないという技術的な 困難なのである。動き始めたばかりの最新の Washington チップでは精度がかなり改善さ れているとのことなので，検証を待ちたい。 量子回路モデルにおいては，周りの環境と の相互作用による量子状態の破壊（デコヒー レンス）が深刻な問題であり，その影響を低 減するための誤り訂正の技術開発が進んで いる。例えば，ショアのアルゴリズムを，誤 り訂正を取り入れて実用的なレベルで実行 するには数千万量子ビットのシステムを構 築して精緻に制御する必要があると言われ ている。これは極めて遠大な目標と言わざる を得ず，仮に実現できるとしても，数十年以 上にわたる研究の積み重ねが必要であろう。 これに対して，量子アニーリングはエネルギ ーが最も低い状態をたどるアルゴリズムな ので，本質的な安定性を内蔵している。この 点は量子アニーリングの大きな強みの一つ である。しかしながら，熱雑音や超伝導素子 間の干渉などの影響をどうしても受けるの で，それらを軽減する誤り訂正符号の研究が 昨年あたりから本格的に始まっている。筆者 のグループも参加して，次世代機への搭載も 念頭に置きながら，理論的な解析と実機での 検証が急速に推進されている。 7. むすび 次世代あるいはその次の世代の D-Wave マ シンが，実用性の高い最適化問題の一群に高 速性を発揮するかもしれない。そうすると， そのような問題が製品開発に関連している 企業は D-Wave マシンを使わないと競争力が 維持できないという事態も起こりうる。実際 にそこまで行くかどうかはまだ分からない し，そうならない可能性も十分ある。まさに， ハイリスク・ハイリターンの世界である。購 入してはいないが，D-Wave 社内部に設置さ れたマシンをクラウドとして使い始めてい る企業も，エネルギーや金融系の会社を含め て少なからぬ数に上っているという話も耳 にしている。 D-Wave 社，Google，NASA，南カリフォ 応用物理学会微小光学研究会予稿 Vol.133, No.3 ルニア大学などでは，全世界から集まった優 れた科学者や技術者が D-Wave マシンの実証 実験や技術開発を集中的に行っており，次々 と新しい成果が論文や特許の形で出てきて いる。例えば，通常のコンピュータの OS， API，各種アプリケーション用のソフトウェ アの開発は D-Wave 社がゼロから作り上げて 独走している。理論研究でも，若い優秀な研 究者が他分野から量子アニーリングに転進 して注目すべき論文を次々に発表しつつあ る。アメリカやカナダの大学・企業の人材を 引きつける力や，新たな分野に迅速に集中投 資するダイナミズムには目を見張るばかり である。日本でも，量子アニーリングに興味 を持っている人は多いが，実際に研究開発に 参加している人はまだ限られている。多くの 研究者の参加を期待している。 参考文献 [1] T. Kadowaki and H. Nishimori: Phys. Rev. E, 58, 5355 (1998) [2] M. W. Johnson, M. H. S.Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson, P. Bunyk, E. M. Chapple, C. Enderud, J. P. Hilton, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Oh, I. Perminov, C. Rich, M. C. Thom, E. Tolkacheva, C. J. S. Truncik, S. Uchaikin, J. Wang, B. Wilson, and G. Rose: Nature 473, 194 (2011) [3] A. Perdomo-Ortiz, N. Dickson, M. Drew-Brook, G. Rose, and A. Aspuru-Guzik: Scientific Reports, 2, 571 (2012) [4] T. Lanting 他: Phys. Rev. X 4, 021041 (2014) [5] W. Vinci, Walter, T. Albash, A. Mishra, P. A. Warburton, and D. A. Lidar: arXiv:1403.4228 (2014) [6] T. F. Ronnow, Z. Wang, J. Job, S. Boixo, S. V. Isakov, D. Wecker, J. M. Martinis, D. A. Lidar, and M. Troyer: Science 420, 1252319 (2014) [7] R. Somma, D. Nagaj, amd M. Kieferová: Phys. Rev. Lett. 109, 050501 (2012) [8] A. Das and B. K. Chakrabarti: Rev. Mod. Phys., 80, 1061 (2008) [9] G. Santoro and E. Tosatti: J. Phys. A, 39, R393 (2006) [10] S. Suzuki, J. Inoue and B. K. Chakrabarti: Quantum Ising Phases and Transitions in the Transverse Ising Models, Springer (2012) [11] 大関真之, 西森秀稔: 量子アニーリン グ，日本物理学会誌, 66, 252 (2011) [12] 西森秀稔: 量子アニーリングと D-Wave， 情報処理，55, 716 (2014) [13] 西 森 秀 稔 : 量 子 ア ニ ー リ ン グ 法 と D-Wave マシン，計算工学，19, 27 (2014) [14] http://www.stat.phys.titech.ac.jp/~nishimori/
© Copyright 2024 ExpyDoc
