@yuichirominato 2018.08.19更新 70views

NASA&Googleの量子コンピュータは「一億倍速い」の論文(量子アニーリング)

D-Wave 量子アニーリング

はじめに

巷では量子コンピュータや量子アニーリングなどが流行っています。しかし実際に使用してみると速度を活かすのはとても困難であることがわかります。量子アニーリング型のD-Waveマシンなどは解く問題によって速度向上の具合が大きく変わります。

また、一般的な情報ではなんでも速くなると思われている一方、組合せ最適化問題の中でもD-Waveマシンの速度向上を活かせるアルゴリズムはわずかです。それら高速化を活かせるアプリケーションはD-Waveの高速化の原理を正しく理解する必要がありますが、残念ながらそれらが正しく伝えられているような雰囲気がありませんので、NASA&Googleの一億倍速いという論文を元に、高速性を活かす方法を正しく理解し古典計算機でのヒューリスティック解法などとのすみわけをおこなう方法を検証してみたいと思います。

ちなみに、今回検証するのはD-Waveマシンの高速性検証で、富士通のデジタルアニーラ、日立のCMOSアニーラ、NTTのコヒーレントイジングマシンなど他のイジングマシンとは原理アルゴリズムが異なるので同様の活用は厳しいと思います。

D-Waveマシンとは?

カナダのベンチャー企業で、量子アニーリングと言われる量子効果を活用したアルゴリズムをハードウェア実装したマシンです。

企業情報:
本社所在地:カナダブリティッシュコロンビア州バーナビー
設立:1999年
事業内容:量子コンピュータのハードウェアとソフトウェアを商用製品として提供
従業員数:160名(Ph.D 55名)

イジングモデルや量子アニーリングに関しては過去の記事を参照ください。
http://blog.mdrft.com/post/6

引用元:https://www.dwavesys.com/resources/media-resources

引用元:https://www.dwavesys.com/resources/media-resources

詳細はカナダのホームページを参照してくださいませ。
https://www.dwavesys.com/

日本語サイトもあります。
http://dwavejapan.com/

早速検証する論文

今回は2015年/2016年に発表されたNASA&Googleの論文を取り上げます。

What is the Computational Value of Finite Range Tunneling?

Vasil S. Denchev,1 Sergio Boixo,1 Sergei V. Isakov,1 Nan Ding,1 Ryan
Babbush,1 Vadim Smelyanskiy,1 John Martinis,2 and Hartmut Neven1
1Google Inc., Venice, CA 90291, USA
2Google Inc., Santa Barbara, CA 93117, USA
(Dated: January 26, 2016)

https://arxiv.org/pdf/1512.02206.pdf
ちなみにこちらの発表は当時量子コンピュータが流行るきっかけとなった大きなターニングポイントでした。

D-Waveの量子コンピュータは「1億倍高速」、NASAやGoogleが会見
https://tech.nikkeibp.co.jp/it/atcl/news/15/120904017/

グーグルの量子コンピューター、従来型PCよりも「1億倍高速」と発表
https://wired.jp/2015/12/11/google-quantum-computing/

概要

量子アニーリングは量子トンネル効果を利用した最適化マシンとして提案されていますが、ここでは、このトンネル効果がどのような計算上のメリットをもたらすかを検証しています。D-Wave2Xの量子アニーリングマシンは局所解同士を隔てるエネルギー障壁が高く、細い形状をしているような問題に対して有利で、Simulated Annealing(SA)にくらべても優位性があるといわれています。945量子ビットの場合で、SAにくらべて、およそ$10^8$倍高速(成功率99%)で、古典計算機でトンネル効果をシミュレートする量子モンテカルロ法(QMC)と比較しても同様に高速です。

ここでは、量子アニーリングマシンの高速性と量子モンテカルロ法の計算速度のスケーリングに関して議論をしています。

ハミルトニアンとSA、QA

今回検証を行う際にシミュレーテッドアニーリング(以下SA)と量子アニーリング(今回は量子モンテカルロ法をつかっているので、以下QMC)が使用されています。

ときたい問題は一緒で、ハミルトニアンと呼ばれるコスト関数を最小にするようにアルゴリズムが働き、その最小基底状態に至る過程がSAとQMCでは原理が異なります。

SAでは熱をシミュレートして、熱で基底状態の探索を行います。一方QMCでは熱の代わりに磁力を使って、量子トンネル効果を活用しながら探索を行います。

SAではあるコスト関数がある場合、グラフの起伏をきちんとなぞるようにエネルギー障壁(以下エナジーバリア)を超えて探索を行うためエネルギー関数のコストをあげて探索を行わないといけませんが、QMCの場合にはトンネル効果によりエナジーバリアを越えるために熱のコストを上げる必要がなく、確率的にトンネル効果で起伏の向こう側に到達できると考えられます。

これらのエナジーバリアをトンネル効果で越える条件もありますので、できるだけエナジーバリアの高さが高くて、障壁の厚みが薄い方が確率的に超えやすいので、SAで行う場合には、かなり条件が厳しく、QMCや量子アニーリングに有利な条件となります。この条件を人為的に問題を作ることで、SAに対して速度優位性を持たせようという検証です。

つまり、求めたいコスト関数に高くて薄いエナジーバリアがたくさんあるほどD-WaveマシンやQMCアルゴリズムが有利になると推測されます。

計算時間の評価の準備

それぞれのアルゴリズムの計算時間を準備します。

今回D-Waveマシンの量子アニーリング(以下QA)は、トンネル効果を考慮して計算時間を下記のようにしています。

$
T_{QA} = B_{QA}e^{\alpha D}
$

QMCもシミュレーションですが同様なので、

$
T_{QMC} = B_{QMC}e^{\alpha D}
$

一方SAは、計算時間はエナジーバリアを登るエネルギー差を考慮して、

$
T_{SA} = B_{SA}e^{\frac{\Delta E}{k_BT}}
$

SAによる探索はコスト関数のエナジーバリアの高低差によって大きく影響を受けそうです。

局所解から局所解への渡り

仮定として量子アニーリングマシンの量子トンネル効果を活用した速度向上は高くて狭いエナジーバリアの時に発揮され、平坦で起伏のゆるいエネルギーランドスケープでは発揮されないことになります。下記は論文からの引用図で、


引用:https://arxiv.org/pdf/1512.02206.pdf

上記のA地点からD地点までの状態の遷移を表しています。上記では、AからBに至る過程、BからCに至る過程はうまくトンネル効果を活用してすり抜けを行うことができていますが、CからDに至る過程ではトンネル効果は部分的にしか活用できないため、SAに対する速度有意性が発揮できないと考えられます。必ずしも基底状態や良い局所解を求めるために量子効果が期待できないという好例です。

上記、A地点では系が熱を利用してコストを上昇させ、量子効果を発揮できる部分まで上がったところで量子トンネルですり抜けを行う。Bでは一旦量子状態から緩和で局所解に落ち、再度またコスト上昇→トンネル効果→緩和という過程を繰り返して局所解を渡っています。CからDに至る過程に関しては量子効果は極めて限定的で、この過程は量子アニーリングマシンであっても熱を使って探索を行なっていると予想されています。

図の青い部分が量子効果で、赤い部分が熱効果です。NASA&Googleの論文では、量子アニーリングマシンは量子効果と熱効果を使い分けながら局所解探索をしていると推測されています。量子アニーリングマシンの温度設定は固定で20mKなので、極めて限定的な有限温度の範囲での使い分けになるかと思います。

トンネル効果を検証するweak-strong cluster問題

Google先生が設定した問題はWeak-Strong Clusterという2つの量子ビットのクラスターを繋げる問題です。D-Waveはキメラグラフという接続を使用しており、8量子ビットで1ユニットセルという単位です。このユニットセルを2つ用意した、16量子ビットの2つのクラスターを構成する問題を用意しています。

全ての量子ビットはキメラグラフで接続されており、ferromagneticカップリングで結合されています。値が同じになるような結合です。一方局所磁場と呼ばれる量子ビットが-1か+1になりやすいように設定されたパラメータが工夫されています。右側のクラスターはすべて$h_2=-1$という値が設定されている一方で、左側のクラスターの量子ビットには$h_1=0.44$というように設定されています。これにより、計算過程において、左側の量子ビットがまとめて8個同時にフリップして右側のクラスターと揃うという過程がおきます。局所磁場の値が、左がweak-clusterで右がstrong-clusterでweak-strong cluster問題です。

ハミルトニアンは、論文からの引用で、

2つのクラスターのハミルトニアンは左右のクラスター内部のコストとクラスター間のコストの和で求まります。これによって、各クラスターごとに局所解に落ちながら、フリップをして最小基底状態に向かうとのこと。

さらに、クラスター16量子ビットの組みを複数用意し、strong-cluster同士を4量子ビットの結合でferro/anti-ferroをランダムで+1or-1でつなぐことで巨大なweak-strong clusterを作ったとのこと。

D-Waveにはところどころ不良量子ビットもあるので、それを避けるようにクラスターを配置し、上記の巨大クラスター構築では、黒丸が-1のstrong cluster。グレーが0.44のweak cluster。青い接続がferroで赤い接続がanti-ferroとなっています。

D-Wave vs SA

D-Waveは計算速度がマシンで$20\mu sec$で固定になっているため、成功確率における計算速度は調整が必要です。成功確率$p_j$から、

$
T = 20\mu sec \times \frac{log(1-0.99)}{log(1-p_j)}
$

SAの計算時間は

$
n_{sweeps} \times N \times T_{su}
$

ただし、全部の量子ビットの更新を行った回数$n_{sweeps}$、Nは量子ビット数、$T_{su}$は1量子ビットのスピン更新にかかる計算時間で$1/5ns$となっています。

D-wave vs QA

QMCの計算時間は今回使用するアルゴリズムの世界線に関わっていて、

$
n_{sweeps} \times N \times T_{worldline}
$

$T_{worldline} = \beta \times 870ns$となっている。

結果

結果1億倍程度の速度差が生まれたとなっています。参考は下図。

せっかくなので少し計算実装してみる

少し実際のアルゴリズムでやって見ます。解析的に解いてもいいですが、仕事の合間にやってるので面白そうなことは研究者の方々にお任せして、実用的に解いて見ます。とりあえず16量子ビットのクラスターを今回は検証して見たいと思います。

まず面白いのは、量子ビット同士の結合がすべてferromagneticということです。設定する値は論文と符号が逆ですが、すべて-1(D-Waveマシンの設定できる最小値)を入れます。

上記量子ビットで今回の実験の肝は量子ビットの局所磁場を設定するところで、上記オレンジの右側のクラスターの量子ビットの局所磁場の設定をすべて+1に。上記水色の左側のクラスターの量子ビットの局所磁場の設定を全て-0.44にします。また、便宜的に16量子ビットに通し番号をふりました。局所磁場は$h_0$から$h_{15}$まで、量子ビット間の相互作用強度はJijの表記を$J_{0,4}$のように量子ビットの番号で表現します。

まずは何も考えずにSAをかけて見たいと思います。

キメラグラフの実装

キメラグラフでの結合係数の決定をします。今回はせいぜい16量子ビットなので、そのまま16*16のmatrixを作って実現して見ます。

こんな感じです。オレンジの-1がユニットセル内の16の結合。クラスタが2つあるので、合計32のユニットセル内部の結合があります。次に赤の-0.44はクラスタ1の局所磁場。青の+1はクラスタ2の局所磁場。紫はクラスタ間の-1の結合を表しています。

定義上は$E=-1*J_{12}*q_1*q_2$なので、ferroは+1にすべきなのかもしませんが、D-Waveでの設定値はferroが-1なのでそちらに合わせました。局所磁場の符号は理論上はどちらもでいいかなとは思いますが、一応理論の逆として合わせました。

やってみた

まずは自前のシミュレータでやって見ました。局所解はこちらです、右側のクラスターがすべて-1で、左側のクラスターがすべて+1。フリップ反転はメトロポリス法で実装しました。速度重視なのでSAのパラメータはかなり落としてあります。

基底状態、最適解は全ての量子ビットが-1です。

また、D-Wave本体でもやってみました。パラメータは論文と一緒です。

結果は、やっぱり速い!超電導量子ビットの実装でこのクラスターの相転移が解けるのはやっぱりすごい。

成功率98.6%で基底状態です。論文とほぼ同じ。shotは1000回にして見ました。

この問題はぜひ興味ある人は実装が難しくないので小さな問題からチャレンジして、大きな問題にチャレンジして欲しいです。実用というよりも研究の要素がとても大きかったと思います。正直SAでは局所解から最適解への相転移は容易ではないと思います。その辺りがD-WaveやQMCなどの量子アルゴリズムの利点なのかなと思いました。すべては左側のクラスターの量子ビットの局所磁場$h_0=-0.44$という数字がポイントになるので、この値を調整して見ても勉強になるかと思います。

あわせて読みたい

SERVICE

汎用量子コンピュータ向けアプリケーション開発SDK

詳しく見る Githubで入手する(無料)

汎用量子コンピュータ向け高速シミュレータ

詳しく見る

量子コンピュータ向けクラウドサービス(準備中)

詳しく見る

イジングマシン向けアプリケーション開発SDK

詳しく見る Githubで入手する(無料)

COMMUNITY

量子コンピュータのことを学びたい、仕事としたいなどの情報交換の場を設け、コミュニティの形成を進めています。オフラインの勉強会と、オンラインのチャットコミュニティの2種類あります。オフラインのConnpassは1400名、オンラインのSlackは880名を超える参加があります。どちらも無料ですのでお気軽にご参加ください。

CONNPASS SLACK

CONTACT

弊社あての連絡はinfo@mdrft.comより用件を明記の上、メールで連絡を頂けますと幸いです。

ブログトップに戻る

Recent Posts