Help us understand the problem. What is going on with this article?

量子アニーリングと断熱量子計算の基本的な論文のまとめ

はじめに

量子アニーリング(Quantum Annealing)は、量子ゆらぎを利用して組み合わせ最適化問題の近似解を求めるヒューリスティックな方法です。本記事では量子アニーリング及び、それを拡張した量子計算の1つである断熱量子計算(Adiabatic Quantum Computation)の基本的な理論の論文についてまとめます1。本記事では基礎理論に焦点を当て、D-Waveのマシンを使った研究や量子アニーリングの応用については触れません。

この記事で紹介する文献よりも簡単でかつ日本語で量子アニーリングについて学べるサイトには、

があります。

レビュー論文

「とりあえず、これを読んどけ!」という論文について。

今までの量子アニーリングの研究成果を整理してまとめたレビュー論文が複数出版されています。

比較的最新の研究成果を含め網羅的にまとめたレビュー論文が、2018年のAlbashとLidarによる次の論文です。

このレビューでは主に断熱量子計算と、外界からのノイズがない孤立した系での理想的な量子アニーリングについてまとめられてます。定性的な説明よりも、数学的に厳密な定理等がよくまとめられているので便利です。外界との相互作用がある開放系での量子アニーリングについては他のレビューがでるみたいです。

この論文より10年前、量子アニーリングが今ほどバズっていなかった時代のレビューもあります。

基本的には、AlbashとLidarのレビューを読めば良いと思います。

量子アニーリング・断熱量子計算の提案

そもそもの研究の源流。

現在のIsing模型と横磁場を利用した形の量子アニーリングが提案されたのは、上のレビューからさらに10年昔の1998年のことです。提案者は現在DENSOにいる門脇さんと東工大の西森先生です。

この論文では、シュレディンガーダイナミクスを利用した横磁場イジング模型による量子アニーリングと、温度を徐々に下げていく通常のシミュレーテッド・アニーリングの比較を行っています。少数スピンの系での数値計算による研究です。この時点では「断熱的」という考えはなかったように思えます。

量子効果(トンネル効果)を利用してスピングラス模型の最小エネルギー状態を求めるというアイデア自体は、門脇・西森以前にも提案されています。

また、量子アニーリングという言葉自体も門脇・西森以前の論文で使われています。

一方、断熱的な時間発展を利用した量子計算である断熱量子計算は、アメリカのEdward Farhiらにより2000年に提案されました。

断熱定理

無限に長い時間をかけて磁場を減少させれば、量子アニーリングにより必ず基底状態を見つけることができます。これを保証するのが「断熱定理」です。名前に断熱とついていますが熱力学の熱とは関係なく、非常にゆっくり(準静的)であること指しています。断熱定理自体は、量子力学の黎明期に発見されいます。断熱定理を拡張して、量子アニーリングと断熱量子計算の最終的に得られる結果のエラーを厳密に評価したのが次の論文です。

S. Jansen, M. B. Ruskai, and R. Seiler "Bounds for the adiabatic approximation with applications to quantum computation." J. Math. Phys. 48, 102111 (2007)|arXiv:quant-ph/0603175

断熱量子計算

断熱量子計算と量子回路モデルとの等価性(万能性)の証明

Farhiが断熱量子計算を提案した時点では、断熱量子計算が通常の量子計算(量子回路)と等価であるかどうか、つまり断熱量子計算により量子回路による計算を多項式時間のオーバーヘッドでシミュレーションできるかはわかっていませんでした。この等価性は後にDorit Aharonov(Aharonov–Bohm効果のAharonovの姪)らによって示されました。

この論文以降にも、証明を改良しより簡単な相互作用のハミルトニアンでの断熱量子計算の万能性を示した論文がいくつかでています。

断熱量子計算のアルゴリズム

探索アルゴリズム

探索問題については、断熱量子計算でも通常の量子計算(Groverアルゴリズム)と同様にO(√N)の計算量で実行することができます。

この論文では、ハミルトニアンを変化させるときに局所的な断熱条件を満たすようにすることで、Groverアルゴリズムと同等の計算量が実現されることを示しています。

一方、横磁場を使った量子アニーリングでは、O(√N)の計算量で実行することは不可能だと考えられています。

素因数分解

量子回路との等価性を使うことで、素因数分解のShorのアルゴリズムを断熱量子計算で実行することができます。しかし、その手順は複雑なものとなります。現在、素因数分解を多項式時間で実行する実用的な断熱量子計算のアルゴリズムまたは量子アニーリングの手法は見つかっていません。

量子アニーリング

量子アニーリングの実験

今では量子アニーリングを実際に行うと言ったらD-Waveのマシンですが、量子アニーリングを実験で初めて実現したのはD-Waveではありません。

D-Waveによるマシンについての初めての論文が出たのは2011年です。

誤り訂正

量子アニーリング、断熱量子計算における誤り訂正の方法は完成していません。以下に先駆的な研究論文をあげておきます。

あとがき

将来的には、量子アニーリングとシミュレーテッド・アニーリングの性能の比較についての研究や、D-Waveのマシンのベンチマークの研究についてもまとめていきたいです。


  1. 断熱量子計算といった場合には、断熱時間発展を利用した万能な量子計算を指します。一方、量子アニーリングは、Ising模型(QUBOと等価)に横磁場をかけて、その横磁場を変化させることで基底状態を求める限定的な手法のことを指します。もう少し広い意味での量子アニーリングは、なんらかのコスト関数に横磁場のような量子ゆらぎの項を導入して、量子ゆらぎを小さくしていくことでコスト関数の最小値を求めるヒューリスティックを指します。 

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away