とあるエンジニアの作業ブログ

コンサル ビジネス書要約 量子コンピュータ

『絵で見てわかる量子コンピュータの仕組み』まとめ アニーリング編

投稿日:2020年3月3日 更新日:

アニーリングについて概要レベルをさらっと勉強したかったので「絵で見てわかる量子コンピュータの仕組み」を読了。
アニーリング部分についてまとめ。
作中で該当する部分は1、2、3、7、8章。

量子コンピュータの基礎と古典コンピュータとの違い

量子コンピュータの定義

量子コンピュータとは「量子力学特有の物理状態を積極的に用いて高速計算をするコンピュータ」。

量子力学特有の物理状態とは、原子、電子、光子や超電導などの非常に低音に冷やした物質においては、「重ね合わせ状態」や「量子もつれ状態」など私たちが普段目にしない不思議な現象が起こるというもの。

量子コンピュータの種類

量子コンピュータの種類

ノイマン型から非ノイマン型へ

古典コンピュータもさらなる進化を続けており、非ノイマン型コンピュータと呼ばれる計算機が開発されている。
これは古典コンピュータであることに代わりはないが、「ある決まった問題を高速に解くマシン」であり、通常のコンピュータの「CPU+メモリ」という基本構成以外の構成になっているものを指す。

例えば、膨大な行列計算にい特化してチップや機械学習のある処理に特化したチップというもの。
ニューロモーフィックチップと呼ばれる神経回路を模した構成の回路や、GPUを使った高速化、FPGA(Field Programmable Gate Array)を利用したシステムなどがすでに開発されている。

量子スプレマシー(量子超越性)

量子スプレマシーとは、量子コンピュータの古典コンピュータに対する優位性を示すこと。
「古典コンピュータでは困難な計算を量子コンピュータでは効率よく計算できること」を示すこと。
例えば、古典コンピュータだと膨大な時間かかる計算を量子コンピュータであれば現実的な時間内で処理できることを示すといった具合。
これを示すために社会的に有意である必要はない。

量子スプレマシーのための量子ビットの目安

精度の良い50量子ビット程度の量子コンピュータが行う計算を古典コンピュータでシミュレートするのは計算量が大きすぎて難しくなってくる(量子スプレマシー)。
現状、IBM Qでは5量子ビットと16量子ビットの量子回路モデルによる計算が可能。

古典コンピュータが苦手な問題とは?

一般的に「多項式時間での解放が知られていない」問題。
多項式時間で解ける問題
多項式時間で解けない問題

量子アニーリングの現在地点

量子回路モデルが現在、数十〜数百量子ビットの実現を目指しているのに対して、量子アニーリングはD-Wave Systemsがすでに2000量子ビットの量子アニーラーを実現している。
しかしD-Wave Systemsの量子アニーリングの量子ビットはコヒーレンス時間と呼ばれる「梁思成」を維持できる時間、つまり量子ビットの寿命が短く大規模な組み合わせ最適化問題を解くことはできない。

量子コンピュータが注目を集める理由

  1. 量子科学技術の発展 ··· 2012年に、「個別の量子系に対する計測および制御を可能にする画期的な実験的手法に関する実績」でノーベル物理学賞を受賞したことに始まり、量子力学的な状態を実験的に制御可能になってきた。更に、一応の計算ができる、クラウドでのお試し利用ができるところまで技術が発展してきた。
  2. ムーアの法則の終焉 ··· ムーアの法則とはIntelのゴードン・ムーアが1965年に提唱した「半導体の集積密度(≒計算性能)は18ヶ月で倍増する」という法則。この法則がそろそろ限界を迎えていると言われている。曽於のため、現在はCPUのマルチコア化やGPUによる並列計算や非ノイマン型コンピュータ等のアクセラレータによる高速化などの方法が計算性能向上策として検討されている。
  3. 計算資源のさらなる需要 ··· ディープラーニングに代表される機械学習技術やブロックチェーンなど膨大な計算処理に立脚した技術がどんどん実用化されているため。

量子ビットとその特性

重ね合わせ状態

古典ビットが”0″ or “1”とどちらか一方の状態しか取れないのに対して、量子ビットは”0″ or “1”の両方の状態を同時に取れる。これを重ね合わせ状態と呼ぶ。
重ね合わせ状態

量子ビットの重ね合わせ状態は振幅と位相という2つの数値によって表せる。
矢印の高さ(地球で言うと緯度)に対応するのが「振幅」で、ブロッホ球を真上から見たときの回転角度(地球で言うと経度)が「位相」。
位相と振幅

量子ビットの測定

量子ビットは「測定」(という行為)をすると、その前後で状態が大きく変わるという量子力学的な性質を持つ。
量子ビットの測定

  1. 測定する前は、”0″と”1″の重ね合わせ状態にあり、ブロッホ球の表面を指し示す矢印として表される(振幅と位相で表される)
  2. この量子ビットを「測定」すると、確率的に”0″状態か”1″状態にばちっと決まる
  3. 量子ビットを測定して”0″や”1″が出る確率は、測定する前に指し示していた矢印を0と1を通る軸に射影することによって決まり、射影された矢印が”0″に近ければ”0″が出る確率が高く、”1″に近ければ”1″が出る確率が高い。
  4. 測定により、0か1かの古典ビットの情報を読み出すことができ、測定後の量子ビットの状態は、測定結果と同じ”0″状態か”1″状態に変化している。

また、測定に伴う測定結果の確率は、振幅の二乗となり以下のように決まる。
振幅のことを「確率振幅」と呼ぶ。
射影と測定結果の確率

量子ビットの波と粒子の性質

波の性質=”0″と”1″の状態を同時に持つ重ね合わせ状態
粒子の性質=測定により一定の状態に決まる
量子ビットの波の性質と量子の性質

イジングモデルと量子アニーリング

イジングモデルとは

イジングモデルとは物理学の1分野である統計力学で用いられる量子系の単純なモデル。
イジングモデルは磁石の性質を持つ物質(磁性体)の性質を説明するためのモデル。
このモデルは格子状に小さな磁石が配置されているだけのシンプルなモデル。この小さな磁石は量子力学的な性質を持っておりスピンと呼ばれる。このスピンは上か下を向くことができ、更に量子的な性質を持っているので上を向いた状態と下を向いた状態の重ね合わせ状態になります。このスピンの上下が|0>と|1>に対応させれば、量子ビットと同様に扱うことができる。
イジングモデル

イジングモデルにおける相互作用とエネルギー

イジングモデルでは、格子状に並んだスピン同士が影響を及ぼし合い、これを相互作用と呼ぶ相互作用は1つの結合につき1つ設定され、正負の数(実数)によって定められる。
相互作用が正の場合を強磁性、負の場合は反磁性と呼ぶ。また、イジングモデルのスピンは放っておくと安定な状態=基底状態になりたがると言う性質を持っている。
イジングモデルの総合作用

イジングモデルでは必ずしも全てのスピンが安定な状態になれるわけではなく、どのスピンの組み合わせでも不安定なスピンが出てきてしまう場合がある。この状態を「フラストレーションがある」と言う。
イジングモデルのフラストレーション

イジングモデルのスピンがどのくらい安定しているかはエネルギー(全てのスピンのエネルギーの総和)によって表される。不安定の状態ではエネルギーが高く、安定な状態はエネルギーが低くなる。
つまり、不安定な状態のスピンがたくさんあればあるほど全体のエネルギーが上昇する。
また、この全体のエネルギーは温度と関係している。磁性体の温度を上昇させるとエネルギーが高く不安定な状態となり、温度を下げることによって安定な状態を作り出すことができる。
このことは後述するシミュレーテッドアニーリングと関係している。
イジングモデルのエネルギー

そして、組み合わせ最適化問題はイジングモデルの基底状態を求める問題として表現することができるのである。(ただしある問題をイジングモデルにマッピング(変換)するのに多くの計算時間をようする場合あり)

組み合わせ最適化問題の定式化

世の中の様々な問題を数式を用いて記述し解決する方法は数理最適化と呼ばれる。
数理最適化では、問題を「目的関数」、「決定変数」、「制約条件」の3つの関係式によって表すことでで定式化を行う。

  • 目的関数 ··· コストや作業時間などの最小化(または最大化)したいものを表した関数
  • 決定変数 ··· 目的関数内で用いられる変数
  • 制約条件 ··· 決定変数が満たすべき条件式

(つまり決定変数を含む目的関数と制約条件の連立方程式になると理解。これがエネルギー方程式ってやつか?)
制約条件を満たしながら目的関数が最小(または最大)になるような決定変数んお組み合わせを求めるものが、数理最適化ということになる。

イジングモデルの基底状態を求める問題に対して定式化を行うと、目的関数は全体のエネルギーに、決定変数はスピンの組み合わせに、制約条件は相互作業(と局所磁場)にそれぞれ対応する。

組み合わせ最適化に属する問題は様々あるが、似た問題をまとめて代表的な「標準問題」に分類することができる。
通常、解きたい組み合わせ最適化問題を標準問題のどれと近いかを考え、その近い標準問題の定式化方法やよく用いられる解き方を考える。それぞれの標準化問題の解き方は、すでに研究された解法・アルゴリズムの定石が存在する。
組み合わせ最適化の標準問題

イジングモデルの基底状態の探索

シミュレーテッドアニーリング

シミュレーテッドアニーリングとは近似解法のアルゴリズムである。
その前に、最急降下法という基底状態を探索する単純な方法を説明する。

  1. ランダムなスピンの組み合わせを初期状態とする
  2. イジングモデルのスピンの1つをランダムに反転し、反転した後に再度全体のエネルギーを計算し、反転前後でエネルギーが低くなる場合は反転したままにし、エネルギーが高くなった場合には元に戻す
  3. これを一番エネルギーが低くなる(収束)するまで繰り返す。ただしこの方法だと局所最適解(ローカルミニマム)に陥ってしまう

最急降下法とローカルミニマム
この問題を解消するためにシミュレーテッドアニーリングという方法が開発された。
シミュレーテッドアニーリングは上記の手順に加えて以下の2つのポイントを考慮する。

  • 反転後の方がエネルギーが高くなる場合にも、ある確率で反転を「受理」する
  • 「エネルギーが高くなるスピンの反転を受理する確率」を最初は高く設定し、だんだん低くしていく。つまり、最初はエネルギーが低くならなくても積極的にスピンを反転させて状態を変化させていき、次第にエネルギーが低くなるスピンの反転のみ受理するようにする

こうすることで、高い確率でグローバルミニマム(大域最適解)、またはそれに近いローカルミニマムにに行き着くことが知られている。
シミュレーッテッドアニーリング

量子アニーリング

  1. 量子アニーラーには多数の量子ビットが実現されており、全ての量子ビットを”0″と”1″の均等な重ね合わせ状態にする。この操作は、量子アニーリングでは「横磁場」をかける、または「量子揺らぎ」を印加すると呼ばれる。これにより、”0000…0″から”1111…1″の全ての重ね合わせ状態が同時に実現される
  2. 解の探索は、量子揺らぎを弱める一方、イジングモデルの相互作用の強さを強めていく。これにより、だんだん相互作用の影響でより全体として安定になるように状態が決まっていく。解きたい問題はイジングモデルの基底状態を求める問題に変換されており、最終的に量子揺らぎを十分に弱くすると量子ビットたちは古典ビットと同じ状態となり基底状態(もしくはそれに近しい状態)に収束する
  3. この最終状態の組み合わせは十分に長い時間アニーリング操作をお行うことで基底状態に行き着くことが示されているが、長い時間をかけていては計算時間がかかりすぎるため、ある程度の速さでアニーリング操作を行う。これでも、基底状態(厳密解)に近い近似解に行き着くことが実験的に示されている

量子アニーリングがシミュレーテッドアニーリング(=古典計算)に対して優位かどうかはまだ示されていない。
しかし、量子アニーリングの方が計算が高速であるという説明を直感的に説明した例があるので示しておく。
シミュレーテッドアニーリングがエネルギーの壁を乗り越えてローカルミニマムを脱するのに対して、量子アニーリングでは量子トンネル効果によるすり抜けが可能であると説明されている。これはエネルギーの壁が薄い場合に可能であり、これによりグローバルミニマムにいくことができる。この説が正しい場合、エネルギーの壁が高くて薄い場合、量子アニーリングの有用性があることになる。
量子トンネル効果

量子回路モデルと量子アニーラーのビット数の違い

量子回路モデルと量子アニーリングの量子ビット数は10倍以上の開きがある。しかし、量子回路モデルと量子アニーリングの量子ビット数を直接比較してはいけない。
量子回路モデルで用いられているトランズモン型の量子ビットと量子アニーリングで用いられている磁束量子ビット型は、現状量子ビットそのものの「性能」が大きく異なるからである。
量子ビットの性能の重要なものとして「コヒーレンス時間」があり、コヒーレンス時間は量子ビットが量子力学的な性質を保てる時間である。いわば量子ビットの寿命である。コヒーレンス時間が短いと計算中にノイズが入ってしまい計算精度が劣化する。
つまり量子計算にかかる時間に比べてコヒーレンス時間が長い方が量子ビットの性能が高いということである。

このコヒーレンス時間が、トランズモン型では現在およそ数十マイクロ秒程度であるのに対して、D-Waveマシンの磁束量子ビットでは、数十ナノ秒であると考えられている。

量子アニーラーの実際

代表としてD-Wave Systesの量子アニーラーに指摘されている課題を列挙する。

  1. コヒーレンス時間がアニーリング時間に比べて短い
    ··· コヒーレンス時間が短いので計算時間を長くできない。ただし、量子アニーラーではたとえ計算時間よりも短いコヒーレンス時間であったとしてもそれなりの近似解を得ることができるという報告もあり、この辺りは現在研究段階である
  2. 実ビジネスに適応するには量子ビット集積度が低すぎる
    ··· 現状2000量子ビット、次世代機でも5000量子ビット。それでも実ビジネスに適用するのはまだまだ量子ビット数がすくなく、大規模な問題を解くことができない
  3. 有限温度の効果で基底状態からの熱励起が生じる
    ··· D-Waveマシンは熱伝導回路によって実現されており、計算時は極低温にする必要があるが、実際には若干の熱が残っており、これがエラーの発生原因となる。また、量子ビットが増加するとますます冷却能力が必要となるため、冷却技術の開発か、熱ノイズに対するエラー訂正方法、ノイズに強いアニーリングアルゴリズムの開発等が課題となる
  4. 相互作用が限定的
    ··· 量子ビットの結合が密なほど計算可能な問題の自由度は広がるが、現在のD-Waveマシンではキメラグラフと呼ばれる疎な結合となっている。そのため、解きたい問題をハードウェアに埋め込むために変換が必要となる。結合の数が増えることでより大規模な問題を扱えるようになる一方、ノイズ体制とのトレードオフも課題として考えられる。

-コンサル, ビジネス書要約, 量子コンピュータ
-,

執筆者:


comment

メールアドレスが公開されることはありません。

関連記事

銀行システムのセキュリティ要件整理

銀行システム/組織のセキュリティ要件を整理する機会がありました。セキュリティはあんまり詳しくないので自分の勉強がてらメモ。 目次 ざっくり結論 各評価項目の定義 セキュリティ要件解説 前提の整理 セキ …

中心極点定理ぃぃぃ????

【備忘】中心極限定理に関する自分なりの解釈

中心極限定理を自分なりに腹落ちするためのメモ。 要するにの中心極限定理の理解は、 元データが正規分布に従ってなくても、そのデータをサンプル抽出していくつか足し合わせたものはたいてい正規分布に従う とい …

様々な言語モデルを箇条書きで解説

本やWebで調べた自然言語処理における言語モデルやアルゴリズムに関する知識を箇条書きまとめ。 文章の確からしさ 5-gram言語モデル(n-gram言語モデル) n-gram言語モデルは単語の出現確率 …

改めてリーンスタートアップの要点まとめ(1/3) 全体概要&第1部

ここ2、3年の仕事はプロジェクトをアジャイルで進めることが多く、かつ今度リーンスタートアップで提唱されているプロセスを採用するということで改めてリーンスタートアップを読んでみた。 以前読んだときは自分 …

改めてリーンスタートアップの要点まとめ(3/3) 第3部

リーンスタートアップの第3部のまとめ。 第1部、第2部のまとめは以下から。 第1部 第2部 目次 リーン実践にあたっての案件サイズ(バッチサイズ) :本書 9、11章に対応 事業拡大において注力すべき …