Go to Qiita Advent Calendar 2024 Top
LoginSignup
23
16

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

@Kashalpha(かしゃるふぁ)

量子アニーリングの性能に関する論文のまとめ

Last updated at Posted at 2020-08-15

はじめに

この記事は量子アニーリングの基本的な論文紹介の続編です。前回の記事では、断熱量子計算と量子アニーリングの基礎理論の論文について紹介をしました。本記事では量子アニーリングに限定して、その最適化アルゴリズムとしての能力に焦点を当てて、約20年間の研究を時系列順に紹介していきたいと思います。この記事では、量子アニーリングについて基礎的な内容は理解していることは前提にしています。

記号と用語の定義

量子アニーリングという言葉は曖昧なので、テクニカルな内容になりますが、まずはじめに本記事における「量子アニーリング」の定義について説明をします。本記事では、孤立した系での断熱的なダイナミクスのみを対象とします。したがって、開放系であるD-Waveの量子アニーラーについては、この記事に書かれている内容が当てはまるとは限りません。また量子ゆらぎの項としては横磁場のみを考えます。つまり、この記事では次の形で書けるハミルトニアンを考えます。$$H(t)=-A(t)\sum_{i}\sigma_i^x+B(t)H_{\mathrm{P}}(\sigma_1^z,\dots, \sigma_N^z)$$右辺第１項が横磁場を表し、第２項が問題ハミルトニアンを表しています。ここで$H_{\mathrm{P}}:\lbrace -1,+1\rbrace^N\to\mathbb{R}$は任意の関数です。$H_{\mathrm{P}}$は常に$$H_{\mathrm{P}}(\sigma_1^z,\dots, \sigma_N^z)=\sum_{p=0}^N\sum_{i_1,\dots,i_p}J_{i_1,\dots,i_p}\sigma_{i_1}^z\cdots \sigma_{i_p}^z$$のように$N$体のIsing模型として表すこともできます。

以上の設定のもとで量子アニーリングが行うタスクは、関数$H_{\mathrm{P}}(\sigma_1^z,\dots, \sigma_N^z)$が最小値をとるような$(\sigma_1^z,\dots, \sigma_N^z)$の値（スピン配位）を求めることです。このとき$H_{\mathrm{P}}(\sigma_1^z,\dots, \sigma_N^z)$の最適解を探す組み合わせ最適化問題はNP困難問題になっています。したがって、その一般的な問題に対して最適解を多項式時間で見つけることは、古典計算機でも量子計算機でも不可能であると考えられています。量子アニーリングの研究における課題の1つは、「上の最適化問題もしくはサブクラスの問題に対して、どの程度の速度で量子アニーリングは近似解を求めることができるか」を明らかにすることです。そして最終的には、古典的な手法に比べて、量子アニーリングが速く最適解を見つけることができる問題のクラスが存在するのか1という疑問に決着をつけることです。

計算時間とエネルギーギャップ

詳しく解説はしませんが、量子アニーリングの計算時間とエネルギーギャップの関係について説明します。エネルギーギャップとは、行列$H(t)$の1番小さい固有値と２番目に小さい固有値の差の大きさのことです。とくに、時間$t$を変化させたときのエネルギーギャップの最小値のことを最小エネルギーギャップと呼び、$\Delta$という記号で表すことにします。すると量子アニーリングの計算時間$T$は、大まかに$$T\sim\Delta^{-2}$$となります。これは数学的には全く厳密ではありませんが、計算時間を見積もるのには便利な式です。この式が意味することは、エネルギーギャップが小さくなるほど量子アニーリングの計算時間は長くなるということです。したがって、量子アニーリングが多項式時間で問題の近似解を見つけ出す場合には、エネルギーギャップは問題のサイズ（qubit数）$N$に対して、$\Delta \sim N^{-\alpha}$となることが分かります。

黎明期（1998-2001）

量子アニーリングの黎明期に出版された2つの有名な論文を紹介します。以下の論文の他にも、小規模な系で数値計算を行った研究がいくつかあります。

量子アニーリングを提案したとされている論文です。この論文では数値計算により、量子アニーリングで最適解が見つかる確率の$T$依存性を調べています。とくに計算時間を長くすると、最適解が見つかる確率が1に近づいていくことをデモンストレーションしています。ただ扱っている問題は小規模な$N=8$の問題であり、大規模な問題に対しての性能については議論していません。

この論文ではNP完全問題の1つであるexact cover問題に対して、量子アニーリング（論文ではquantum adiabatic evolution algorithmと呼ばれています）を適用した論文です。$1/8$以上の確率で最適解を見つけるのに必要な時間を、ランダムに生成した問題のインスタンスについて数値計算により求めています。このとき問題のサイズを$N=10$から$N=20$まで変化させ、そのときの計算時間$T$のスケーリング（$N$依存性）を調べています。この論文の結果で衝撃的なのは、この計算時間のスケーリングが2次式でフィットできたことです。もしこの振る舞いが任意の$N$について正しいならば、量子アニーリングでNP完全問題を近似的にですが多項式時間で解くことができることを表しています。しかし、現代では多項式でフィットできるのは$N$が小さいところだけで、$N$が大きい場合には指数的になると考えられています。

発展期（2002-2010）

小規模な系やトイモデルでの計算から離れ、大規模な系の数値計算が量子モンテカルロ法を使って行われるようになった時代です。この時代の重要な成果の1つとして、Farhiらの2001年の数値計算は不十分であり、問題サイズが大きくなるとNP完全問題に対するスケーリングは指数スケーリングになるというPeter Youngらの研究があります。

量子モンテカルロ法を使ったシミュレーションで、大規模なスピングラス模型における量子アニーリングを分析した論文です。問題ハミルトニアンとして、スピングラスの模型として有名なEdwards-Anderson模型を用いています。Edwards-Anderson模型は、ハミルトニアンが$$H_{\mathrm{P}}=\sum_{\langle i,j\rangle}J_{i,j}\sigma_{i}^z\sigma_{j}^z$$で与えられるスピングラス模型です。ここで、$\sum_{\langle i,j\rangle}$は格子上で隣接している頂点について和を取ることを表し、$J_{i,j}$は独立な標準正規分布に従う乱数です。この論文では$80\times 80$の2次元正方格子のEdwards-Anderson模型で計算を行っています。

タイトルの通り量子アニーリングの最適解への収束を理論的に示した論文です。横磁場の変化のさせ方を$$A(t)/B(t)\geq (\xi t)^{-1/(2N-1)}$$を満たすようにすれば、どんな問題のインスタンスに対しても、$t\to\infty$の極限で確率1で最適解に収束することを明らかにしました。ただし、$\xi$は$N$について指数的に小さくなる量であるため、右辺は$N$について指数的に大きくなります。よって、この議論では指数関数的に長い時間があれば最適解が得られるということしか言えていません。

解析のしやすい単純な模型を考えることは、理解を深める上で重要です。この論文では、スピングラスの基本的な模型であるランダムエネルギー模型に対する量子アニーリングを議論しています。ランダムエネルギー模型は、各スピン配位の持つエネルギーが正規分布に従う乱数により定められた模型です。ランダムエネルギー模型に横磁場を加えた模型では、ある横磁場の値で常磁性相からスピングラス相への相転移（1次相転移）が起こります。この論文では摂動論を使った議論により、その相転移点上でエネルギーギャップが$N$について指数関数的に小さくなることを示しています。つまり、ランダムエネルギー模型の最小エネルギー状態を求めるのに、量子アニーリングは指数関数的に長い時間を要するということです。ランダムエネルギー模型ではエネルギーがランダムに定まっていて、問題に特に計算上利用できる構造が存在しないため、全探索と同じだけの計算時間が必要になることは直感的にも納得できると思います。

黎明に行われた数値計算で、量子アニーリングのNP完全問題に対する計算時間が$N^2$でスケールすることが発見されていました。しかしこの数値計算の結果は、問題のサイズが小さいことに起因するものではないかと疑問視されていました。上記のYoungらによる2本の論文は、量子モンテカルロ法によりサイズの大きい問題を取り扱うことで、$N^2$のスケーリングはアーティファクトであることを間接的に示しました。これらの論文では、Farhiらの2001年の論文と同じexact cover問題について、それぞれ$N=128$と$N=256$のサイズまで計算をしています。後者の論文では、一次相転移が起きるようなインスタンスの割合が$N$とともに増大することから、$N\to\infty$の極限では一次相転移が典型的なインスタンスで起こると推察しています。一次相転移が起こる場合には、最小エネルギーギャップは$N$について指数関数的に小さくなると考えられています。したがって上記の結果は間接的にですが、量子アニーリングの計算時間が指数関数的に長くなることを意味しています。

古典コンピュータで効率的に解ける問題は、量子アニーリングでも効率的に解くことができるのでしょうか？このJörgらの論文は、最適解が自明であるような単純な模型でも、量子アニーリングが上手く行かないことがあることを示した論文です。考えている模型は**$p$-スピン模型**と呼ばれる平均場スピン模型です。$p$-スピン模型の問題ハミルトニアンは$$H_{\mathrm{P}}=-\frac{1}{N^p}\sum_{i_1,\dots,i_p}\sigma_{i_1}^z\cdots \sigma_{i_p}^z$$で与えられ、ランダムネスがない模型です。この模型の基底状態は、全てのスピン$+1$をとるときであると簡単にわかります。ちなみに$p\to\infty$の極限ではGroverの問題になります。この模型は解析的に調べることができ、$p>2$では常磁性相と強磁性相の間で一次相転移が起こることが分かります。一次相転移点ではエネルギーギャップは指数関数的に小さくなるため、この模型での量子アニーリングの計算時間は指数的に長くなります。したがって答えが自明なときでも、量子アニーリングが上手くいかないことがあるのです。より詳細に分析した論文として、V. Bapst, and G. Semerjian, "On quantum mean-field models and their quantum annealing" J. Stat. Mech. 12, P06007 (2012), arXiv:1203.6003があります。

流行期（2011-2018）

D-Wave Systemsが128qubitの量子アニーラーを発表したのが、2011年の5月のことです。その後2017年まで、２年おきにD-Waveのマシンのアップデートが行われてきました。この期間では、D-Waveの量子アニーラーが本当に量子性を使って計算をしているのかなど、量子アニーラーの使った研究が数多く行われました。一方この時期の理論の論文では、量子アニーリングでは上手く解くことのできない問題について、探求した研究が多い印象です。この節では、そんな量子アニーリングのバズリが起こった時期の理論研究について紹介します。

この論文も量子モンテカルロ法を使って、NP完全問題に対する量子アニーリングを解析した論文です。exact cover問題よりも構造が単純である2つのNP完全問題、locked 1-in-3 SATとlocked 2-in-4 SATを対象として、エネルギーギャップの$N$依存性を数値的に計算しています。この問題についても、エネルギーギャップは指数関数的に小さくなってしまうことが判明しました。また、この論文では古典的な局所探索アルゴリズムであるWalkSATと量子アニーリングの性能を比較して、WalkSATで解くことが難しい問題は量子アニーリングでも解くことが難しいと結論づけています。

3-regular 3-XORSATという組み合わせ最適化問題に対する量子アニーリングの性能を数値計算で調べた論文です。この問題には、多項式時間で最適解を見つけることのできる古典アルゴリズムが知られています。しかしながら、この問題ではスピングラス転移があり、エネルギーギャップが指数関数的に小さくなるため、量子アニーリングでは効率的に解くことができないことを明らかにしました。

今まで、量子アニーリングのボトルネックとなる指数的に小さいエネルギーギャップは、常磁性相-スピングラス相の相転移点上にあると考えられていました。しかし、それは必ずしも正しいわけではなく、ボトルネックとなる部分がスピングラス相の内部にあることを明らかにした論文です。より具体的には、エネルギーギャップが指数的に小さくなる点がスピングラス相に複数現れることを、$H_{\mathrm{P}}=\sum_{i_1,i_2}J_{i_1,i_2}\sigma_{i_1}^z\sigma_{i_p}^z$で$J_{i_1,i_2}=\frac{1}{N}\sum_{\mu=1}^2\xi_{i_1}^{(\mu)}\xi_{i_2}^{(\mu)}$とした模型で示しました。ここで$\xi_{i}^{(\mu)}$は標準正規分布に従う乱数です。

幻滅期（2019-）

上述のように2010年代の後半から、一部の民間企業も量子アニーリングは新しいテクノロジーとして注目されるようになりました。しかしながら、徐々に量子アニーリングやD-Waveのアニーラーを使って組み合わせ最適化問題を解くことに旨味がないことがわかってきました。アカデミックの世界でも量子アニーリングの研究は下火になっていく可能性は高いですが、重要な論文が出た場合には以下に追加をしていく予定です。

  • ???

むすび

この記事では分かりやすさよりも正確性を重視して説明をしました。量子アニーリングの勉強に役立てて頂けたら幸いです。

  1. 2020年8月の段階では、この記事の定義での量子アニーリングについて、古典アルゴリズムよりも高速に解ける問題は知られていません。 ↩

23
16
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
23
16

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?