量子アニーリングの基礎
カナダのベンチャー企業、D-Wave Systems によって「量子コンピュータ」が開発・発売され、反響を呼んでいる。
量子コンピュータは、1994年に因数分解を高速で行う量子アルゴリズムが発見されたことを契機に、研究が一気に加速した。当初提案されたのは「量子ゲート方式」と呼ばれるタイプであった。この方式の強みは、量子力学系のシミュレーションなどのいくつかの計算が、通常のコンピュータより大幅に効率よく実行できることにある。しかし、大規模な回路を構成して安定的に演算を実行する技術の開発は途上である。
一方、これとはまったく異なるアプローチとして「量子アニーリング」が着目され、D-Wave 社がハードウェアの動作原理として実装して世に出すに至った。量子アニーリングは、当初は磁性体のイジング模型の基底状態を、量子力学的なゆらぎを利用して探索する方法として考案された。基本素子として量子ビットを使うという点では量子ゲート方式と同じだが、当面の目的やその実現方法は異なっている。量子アニーリングは、巡回セールスマン問題などの「組み合わせ最適化問題」に特化したアルゴリズムなのである。
本書は、量子アニーリングの計算原理の発案者による、日本語で書かれた唯一の解説書である。量子アニーリングの基本的な定式化や動作原理の説明だけでなく、機械学習への応用やベンチマークテストの例、さらにはD-Waveマシンのユーザーインターフェイスの解説まで幅広く取り上げている。
量子コンピュータは、1994年に因数分解を高速で行う量子アルゴリズムが発見されたことを契機に、研究が一気に加速した。当初提案されたのは「量子ゲート方式」と呼ばれるタイプであった。この方式の強みは、量子力学系のシミュレーションなどのいくつかの計算が、通常のコンピュータより大幅に効率よく実行できることにある。しかし、大規模な回路を構成して安定的に演算を実行する技術の開発は途上である。
一方、これとはまったく異なるアプローチとして「量子アニーリング」が着目され、D-Wave 社がハードウェアの動作原理として実装して世に出すに至った。量子アニーリングは、当初は磁性体のイジング模型の基底状態を、量子力学的なゆらぎを利用して探索する方法として考案された。基本素子として量子ビットを使うという点では量子ゲート方式と同じだが、当面の目的やその実現方法は異なっている。量子アニーリングは、巡回セールスマン問題などの「組み合わせ最適化問題」に特化したアルゴリズムなのである。
本書は、量子アニーリングの計算原理の発案者による、日本語で書かれた唯一の解説書である。量子アニーリングの基本的な定式化や動作原理の説明だけでなく、機械学習への応用やベンチマークテストの例、さらにはD-Waveマシンのユーザーインターフェイスの解説まで幅広く取り上げている。
第1章 量子アニーリングとはいったい何か
1.1 社会的背景
1.2 量子アニーリング
1.3 量子アニーリングは何を目指すのか
1.4 量子アニーリングはどうやって最適化問題を解くのか
第2章 イジング模型と組み合わせ最適化問題
2.1 イジング模型
2.2 フラストレーションとスピングラス
2.3 組み合わせ最適化問題とイジング模型
2.4 現実のデバイス上での表現(I): 多体相互作用
2.5 現実のデバイス上での表現(II): 長距離相互作用など
2.6 組み合わせ最適化問題の例
2.6.1 巡回セールスマン問題
2.6.2 分割問題
2.6.3 充足可能問題
2.6.4 クラスタリング
第3章 2状態系の量子力学
3.1 2つの状態が同時に実現するということ
3.2 重ね合わせの行列表現
3.3 状態の入れ替えの行列表現
3.4 ブラケットによる表記の簡略化
3.5 シュレディンガー方程式
3.6 複数のスピンがあるとき
第4章 横磁場イジング模型と量子相転移
4.1 横磁場イジング模型と量子アニーリング
4.2 有限時間での探索
4.3 横磁場イジング模型の量子相転移
4.4 横磁場イジング模型における量子相転移の例
第5章 断熱時間発展の条件
5.1 漸近的断熱条件
5.2 厳密な断熱条件
5.3 データベース探索問題の量子断熱解
5.4 非断熱遷移
第6章 量子相転移の次数とエネルギーギャップの関係
6.1 2次相転移
6.2 1次相転移
6.3 例外の例
第7章 収束条件
7.1 収束条件
7.2 古典アルゴリズムとの比較
第8章 量子ゲート模型との等価性
8.1 量子ゲート模型が量子アニーリングを効率よくシミュレートできること
8.2 拡張された量子アニーリングが量子ゲート模型を効率よくシミュレートできること
8.3 スピン模型での表現およびユニバーサリティ
8.4 非疑似古典確率的ハミルトニアンによる指数関数的な高速化
第9章 量子アニーリングのシミュレーション
9.1 マルコフ連鎖モンテカルロ法
9.2 シミュレーテッド・アニーリング
9.3 横磁場イジング模型の古典シミュレーション
第10章 機械学習との関わり
10.1 ボルツマン機械学習
10.2 QBoost
10.3 辞書学習
10.4 量子ボルツマン機械学習への挑戦
第11章 量子アニーリングマシンのベンチマーク
11.1 1億倍速いというのは本当か
11.2 より精密な比較
付録A 統計力学の処方箋
付録B D-Waveマシンの利用法
参考文献
索 引
1.1 社会的背景
1.2 量子アニーリング
1.3 量子アニーリングは何を目指すのか
1.4 量子アニーリングはどうやって最適化問題を解くのか
第2章 イジング模型と組み合わせ最適化問題
2.1 イジング模型
2.2 フラストレーションとスピングラス
2.3 組み合わせ最適化問題とイジング模型
2.4 現実のデバイス上での表現(I): 多体相互作用
2.5 現実のデバイス上での表現(II): 長距離相互作用など
2.6 組み合わせ最適化問題の例
2.6.1 巡回セールスマン問題
2.6.2 分割問題
2.6.3 充足可能問題
2.6.4 クラスタリング
第3章 2状態系の量子力学
3.1 2つの状態が同時に実現するということ
3.2 重ね合わせの行列表現
3.3 状態の入れ替えの行列表現
3.4 ブラケットによる表記の簡略化
3.5 シュレディンガー方程式
3.6 複数のスピンがあるとき
第4章 横磁場イジング模型と量子相転移
4.1 横磁場イジング模型と量子アニーリング
4.2 有限時間での探索
4.3 横磁場イジング模型の量子相転移
4.4 横磁場イジング模型における量子相転移の例
第5章 断熱時間発展の条件
5.1 漸近的断熱条件
5.2 厳密な断熱条件
5.3 データベース探索問題の量子断熱解
5.4 非断熱遷移
第6章 量子相転移の次数とエネルギーギャップの関係
6.1 2次相転移
6.2 1次相転移
6.3 例外の例
第7章 収束条件
7.1 収束条件
7.2 古典アルゴリズムとの比較
第8章 量子ゲート模型との等価性
8.1 量子ゲート模型が量子アニーリングを効率よくシミュレートできること
8.2 拡張された量子アニーリングが量子ゲート模型を効率よくシミュレートできること
8.3 スピン模型での表現およびユニバーサリティ
8.4 非疑似古典確率的ハミルトニアンによる指数関数的な高速化
第9章 量子アニーリングのシミュレーション
9.1 マルコフ連鎖モンテカルロ法
9.2 シミュレーテッド・アニーリング
9.3 横磁場イジング模型の古典シミュレーション
第10章 機械学習との関わり
10.1 ボルツマン機械学習
10.2 QBoost
10.3 辞書学習
10.4 量子ボルツマン機械学習への挑戦
第11章 量子アニーリングマシンのベンチマーク
11.1 1億倍速いというのは本当か
11.2 より精密な比較
付録A 統計力学の処方箋
付録B D-Waveマシンの利用法
参考文献
索 引
