量子アニーリングを用いたクラスタ分析

(1)

量子アニーリングを用いたクラスタ分析

田中宗 (早稲田大学高等研究所)

機械学習における重要な技術であるクラスタ分析に対する、量子アニーリングの性能評価を行った。

量子モンテカルロ法を用いた擬似シミュレーションの結果、

シミュレーテッドアニーリングに比べ、量子アニーリングの方が、性能面で優位であることを示唆する結果を得た。

本講演では、量子アニーリングの基礎について述べた後、

我々の研究結果について紹介する。

K. Kurihara, S. Tanaka, and S. Miyashita, UAI2009 I. Sato, K. Kurihara, S. Tanaka, H. Nakagawa, and S. Miyashita, UAI2009

(2)

共同研究者

佐藤一誠博士 (東大情報基盤センター、さきがけ研究員)

栗原賢一博士 (グーグル株式会社)

宮下精二教授 (東大院理物理学専攻)

中川裕志教授 (東大情報基盤センター)

(3)

２つのキーワード

量子アニーリングクラスタ分析

量子性を用いた新計算技術

分かることは

分けること

(4)

講演の流れ

量子アニーリングの基礎 ^{物理学と情報科学}

量子アニーリングの性能に関する先行研究

量子アニーリングマシン D-Wave の性質

量子アニーリングを用いたクラスタ分析クラスタ分析のモデリング

量子アニーリングの導入方法

量子アニーリングの優位性

(5)

物理学と情報科学

イジング模型

多数の要素の協同効果を表現する、最も簡単な統計力学模型

強磁性体反強磁性体

H =

i,j

J_ij _i^z _j^z

i

h_i _i^z _i^z = ±1

スピン間の相互作用スピンに働く磁場 J_ij > 0

J_ij < 0

：強磁性的相互作用

：反強磁性的相互作用

ランダム磁性体

一般に、

基底状態を

求めること

は難しい

(6)

組合せ最適化問題

多数の選択肢から、ベストな解を選ぶ問題

(7)

組合せ最適化問題

多数の選択肢から、ベストな解を選ぶ問題

巡回セールスマン問題

✔ 各点を一度だけ通過 ✔ 全ての点を回る

✔ コストを

最小

にする条件

(8)

組合せ最適化問題

多数の選択肢から、ベストな解を選ぶ問題

巡回セールスマン問題

✔ コストを

最小

にする条件

(9)

組合せ最適化問題

多数の選択肢から、ベストな解を選ぶ問題

巡回セールスマン問題

✔ コストを

最小

にする条件

全ての選択肢を試した場合

点が少ない：簡単点が多い：困難 ^{選択肢の数：N!}

(10点:10⁶通り、20点:10¹⁸通り)

(10)

組合せ最適化問題

多数の選択肢から、ベストな解を選ぶ問題

多変数実関数の

最小値(最大値)

を取る条件を求める問題

x = argmin

_x

f (x)

問題のサイズ解の候補

x = (x

₁

, · · · , x

_N

)

(11)

組合せ最適化問題

多数の選択肢から、ベストな解を選ぶ問題

最小値(最大値)

x = argmin

_x

f (x)

問題のサイズ解の候補

指数関数的増⼤大

x = (x

₁

, · · · , x

_N

)

(12)

組合せ最適化問題

多数の選択肢から、ベストな解を選ぶ問題

最小値(最大値)

x = argmin

_x

f (x)

都市数巡回経路路数 ^計算時間(京を利利⽤用として)

5 12 10^-‐‑‒15秒

10 2x10⁵ 2x10^-‐‑‒11秒

15 4x10⁸ 4x10^-‐‑‒8秒

20 6x10¹⁶ 6秒

25 3x10²³ 359⽇日

30 4x10³⁰ 1401万年年

x = (x

₁

, · · · , x

_N

)

(13)

イジング模型でのマッピング

組合せ最適化問題の最適解 = イジングモデルの基底状態

H^opt. =

i,j

J_ij _i^z _j^z

i

h_i _i^z

iz = ±1

イジングモデル

✔ 組合せ最適化問題のハミルトニアン

✔ 基底状態を求めることは困難(組合せ爆発) スピン(ビット)間

相互作用

磁場(強制力)

様々な分野に、応用展開可能

集積回路設計

グラフ二分割問題高分子安定構造決定

巡回セールスマン問題

(14)

アニーリング(徐冷)

温める

物質を構成する原子が、自在に動き回る。

熱による「ゆらぎ」現象

冷やす(アニーリング)

物質を構成する原子が、最適な位置に自然に落ち着く。

安定状態が自然に作られる(自己組織化)。

自然現象から着想を得た計算技術

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

通常のコンピュータを用いて実装可能な汎用アルゴリズム

(15)

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

温度

(熱ゆらぎ効果) 絶対ゼロ度(基底状態)

イジングモデルの基底状態を効率よく求める方法

H^opt. =

i,j

J_ij _i^z _j^z

i

h_i _i^z

iz = ±1

イジングモデル

相互作用

磁場(強制力)

(16)

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

温度

(熱ゆらぎ効果)

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

温度を徐々に下げる絶対ゼロ度(基底状態)

S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, Science, 220, 671 (1983).

イジングモデルの基底状態を効率よく求める方法

H^opt. =

i,j

J_ij _i^z _j^z

i

h_i _i^z

iz = ±1

イジングモデル

相互作用

磁場(強制力)

(17)

量子アニーリング

温度

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

温度を徐々に下げる絶対ゼロ度(基底状態)

イジングモデルの基底状態を効率よく求める方法

H^opt. =

i,j

J_ij _i^z _j^z

i

h_i _i^z

iz = ±1

イジングモデル

相互作用

磁場(強制力)

(18)

量子アニーリング

温度

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

温度を徐々に下げる量子ゆらぎ効果

絶対ゼロ度(基底状態)

イジングモデルの基底状態を効率よく求める方法

H^opt. =

i,j

J_ij _i^z _j^z

i

h_i _i^z

iz = ±1

イジングモデル

相互作用

磁場(強制力)

(19)

量子アニーリング

温度

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

量子アニーリング

量子効果を徐々に弱める

T. Kadowaki and H. Nishimori, Phys. Rev. E, 58, 5355 (1998).

イジングモデルの基底状態を効率よく求める方法

H^opt. =

i,j

J_ij _i^z _j^z

i

h_i _i^z

iz = ±1

イジングモデル

相互作用

磁場(強制力)

(20)

量子アニーリング

ハミルトニアンを行列を使って表現する

H^opt. =

i,j

J_ij _i^z _j^z

i

h_i _i^z _i^z = ±1

(21)

量子アニーリング

ハミルトニアンを行列を使って表現する

H^opt. =

i,j

J_ij _i^z _j^z

i

h_i _i^z _i^z = ±1

H^opt. =

i,j

J_ij ˆ_i^z ˆ_j^z

i

h_iˆ_i^z ˆ_i^z = 1 0

0 1

パウリ行列による表現

(22)

量子アニーリング

2^Nx2^Nの対角行列

ハミルトニアンを行列を使って表現する

H^opt. =

i,j

J_ij _i^z _j^z

i

h_i _i^z _i^z = ±1

H^opt. =

i,j

J_ij ˆ_i^z ˆ_j^z

i

0 1

パウリ行列による表現

(23)

量子アニーリング

ハミルトニアンを行列を使って表現する

H^opt. =

i,j

J_ij _i^z _j^z

i

h_i _i^z _i^z = ±1

H^opt. =

i,j

J_ij ˆ_i^z ˆ_j^z

i

0 1

ˆ_i^z | = + | ˆ_i^z | = |

パウリ行列による表現

(24)

量子アニーリング

ハミルトニアンを行列を使って表現する

H^opt. =

i,j

J_ij _i^z _j^z

i

h_i _i^z _i^z = ±1

H^opt. =

i,j

J_ij ˆ_i^z ˆ_j^z

i

0 1

ˆ_i^z | = + | ˆ_i^z | = |

ˆ_i^z | = 1 0

0 1 1

0 = 1

0 = + |

パウリ行列による表現

(25)

量子アニーリング

量子揺らぎ効果(非対角項)の導入

H^q =

i

ˆ_i^x ˆ_i^x = 0 1

1 0

(26)

量子アニーリング

量子揺らぎ効果(非対角項)の導入

H^q =

i

ˆ_i^x ˆ_i^x = 0 1

1 0

ˆ_i^x | = | ˆ_i^x | = |

(27)

量子アニーリング

量子揺らぎ効果(非対角項)の導入

H^q =

i

ˆ_i^x ˆ_i^x = 0 1

1 0

ˆ_i^x | = | ˆ_i^x | = |

ˆ_i^x | = 0 1

1 0 1

0 = 0

1 = |

(28)

量子アニーリング

量子揺らぎ効果(非対角項)の導入

H^q =

i

ˆ_i^x ˆ_i^x = 0 1

1 0

ˆ_i^x | = | ˆ_i^x | = |

スピン反転(ビット反転) 量子力学的遷移

ˆ_i^x | = 0 1

1 0 1

0 = 0

1 = |

(29)

量子アニーリング

の固有状態

量子揺らぎ効果(非対角項)の導入

H^q =

i

ˆ_i^x ˆ_i^x = 0 1

1 0

ˆ_i^x | = | ˆ_i^x | = |

スピン反転(ビット反転) 量子力学的遷移

ˆ_i^x

ˆ_i^x | = 0 1

1 0 1

0 = 0

1 = |

| = 1

2 (| + | ) , | = 1

2 (| | )

重ねあわせ状態の実現

(30)

量子アニーリング

量子揺らぎ効果(非対角項)の導入

H^q =

i

ˆ_i^x ˆ_i^x = 0 1

1 0

ˆ_i^x | = | ˆ_i^x | = |

スピン反転(ビット反転) 量子力学的遷移

ˆ_i^x | = 0 1

1 0 1

0 = 0

1 = |

(31)

量子アニーリング

量子揺らぎ効果(非対角項)の導入

H^q =

i

ˆ_i^x ˆ_i^x = 0 1

1 0

ˆ_i^x | = | ˆ_i^x | = |

スピン反転(ビット反転) 量子力学的遷移

ˆ_i^x | = 0 1

1 0 1

0 = 0

1 = |

H^qの基底状態：_| _{· · ·}

(32)

量子アニーリング

量子揺らぎ効果(非対角項)の導入

H^q =

i

ˆ_i^x ˆ_i^x = 0 1

1 0

ˆ_i^x | = | ˆ_i^x | = |

スピン反転(ビット反転) 量子力学的遷移

ˆ_i^x | = 0 1

1 0 1

0 = 0

1 = |

H^qの基底状態：_| _{· · ·}

| = 1

2 (| + | + | + | ) ２スピンの場合：

(33)

量子アニーリング

量子揺らぎ効果(非対角項)の導入

H^q =

i

ˆ_i^x ˆ_i^x = 0 1

1 0

ˆ_i^x | = | ˆ_i^x | = |

スピン反転(ビット反転) 量子力学的遷移

ˆ_i^x | = 0 1

1 0 1

0 = 0

1 = |

H^qの基底状態：_| _{· · ·}

| = 1

2 (| + | + | + | ) ２スピンの場合：

重ねあわせ状態の実現

(34)

量子アニーリング

量子アニーリングを実行するためのハミルトニアン

H^opt. =

i,j

J_ij ˆ_i^z ˆ_j^z

i

0 1

組合せ最適化問題のハミルトニアン (2^Nx2^Nの対角行列)

量子揺らぎのハミルトニアン (2^Nx2^Nの非対角行列)

H^q =

i

ˆ_i^x ˆ_i^x = 0 1

1 0

スピン反転(ビット反転)

量子力学的遷移

(35)

量子アニーリング

量子アニーリングを表現する時間依存ハミルトニアン

H(t) = A(t)H^opt. + B(t)H^q

組合せ最適化問題量子揺らぎ

(36)

量子アニーリング

時刻

t 1

0 0

量子アニーリングを表現する時間依存ハミルトニアン

(37)

量子アニーリング

A(t) B (t)

時刻

t 1

0 0

量子アニーリングを表現する時間依存ハミルトニアン

量子揺らぎ

ハミルトニアン

組合せ最適化問題ハミルトニアン

(38)

量子アニーリング

温度

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

量子アニーリング

イジングモデルの基底状態を効率よく求める方法

H^opt. =

i,j

J_ij _i^z _j^z

i

h_i _i^z

iz = ±1

イジングモデル

相互作用

磁場(強制力)

(39)

量子アニーリングの性能

収束定理

S. Geman and D. Geman, IEEE Trans. Pattern Anal. Mach. Intell. Vol. 6, 721 (1984)

非常にゆっくりパラメータを変えれば、

確実 ^{に基底状態に到達する}

(40)

収束定理

時刻

t

非常にゆっくりパラメータを変えれば、

確実 ^{に基底状態に到達する}

温度度、量量⼦子揺らぎ

(41)

収束定理

時刻

t

T (t) N

log(t + 1)

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

非常にゆっくりパラメータを変えれば、

確実 ^{に基底状態に到達する}

(42)

収束定理

時刻

t

T (t) N

log(t + 1)

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

^c/N

量子アニーリング

非常にゆっくりパラメータを変えれば、

確実 ^{に基底状態に到達する}

数学的に確実性が保証された計算技術

(43)

先行研究の項目に関して、著作権の観点から発表時に用いたスライドを削除しました。

ご興味のある方は、個別にご連絡ください。

(44)

講演の流れ

量子アニーリングの基礎 ^{物理学と情報科学}

量子アニーリングの性能に関する先行研究

量子アニーリングマシン D-Wave の性質

量子アニーリングを用いたクラスタ分析クラスタ分析のモデリング

量子アニーリングの導入方法

量子アニーリングの優位性

(45)

２つのキーワード

量子アニーリングクラスタ分析

量子性を用いた新計算技術

分かることは

分けること

(46)

２つのキーワード

量子アニーリング

温度

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

量子アニーリング

イジングモデルの基底状態を効率よく求める方法

H^opt. =

i,j

J_ij _i^z _j^z

i

h_i _i^z

iz = ±1

イジングモデル

相互作用

磁場(強制力)

量子アニーリングを用いた クラスタ分析

量子アニーリングを用いた クラスタ分析

田中 宗 (早稲田大学 高等研究所)

機械学習における重要な技術であるクラスタ分析に 対する、量子アニーリングの性能評価を行った。

量子モンテカルロ法を用いた擬似シミュレーションの結果、

シミュレーテッドアニーリングに比べ、量子アニーリングの 方が、性能面で優位であることを示唆する結果を得た。

本講演では、量子アニーリングの基礎について述べた後、

我々の研究結果について紹介する。

共同研究者

２つのキーワード

量子アニーリング クラスタ分析

量子性を用いた 新計算技術

分かることは

分けること

講演の流れ

量子アニーリングの基礎 物理学と情報科学

量子アニーリングの性能に関する先行研究

量子アニーリングマシン D-Wave の性質

量子アニーリングを用いたクラスタ分析 クラスタ分析のモデリング

量子アニーリングの導入方法

量子アニーリングの優位性

イジング模型

多数の要素の協同効果を表現する、最も簡単な統計力学模型

一般に、

基底状態を

求めること

は難しい

組合せ最適化問題

多数の選択肢から、ベストな解を選ぶ問題

組合せ最適化問題

多数の選択肢から、ベストな解を選ぶ問題

巡回セールスマン問題

最小

組合せ最適化問題

多数の選択肢から、ベストな解を選ぶ問題

巡回セールスマン問題

最小

組合せ最適化問題

多数の選択肢から、ベストな解を選ぶ問題

巡回セールスマン問題

最小

全ての選択肢を試した場合

組合せ最適化問題

多数の選択肢から、ベストな解を選ぶ問題

最小値(最大値)

x = argmin

f (x)

x = (x

, · · · , x

)

組合せ最適化問題

多数の選択肢から、ベストな解を選ぶ問題

最小値(最大値)

x = argmin

f (x)

指数関数的増⼤大

x = (x

, · · · , x

)

組合せ最適化問題

多数の選択肢から、ベストな解を選ぶ問題

最小値(最大値)

x = argmin

f (x)

x = (x

, · · · , x

)

イジング模型でのマッピング

組合せ最適化問題の最適解 = イジングモデルの基底状態

イジングモデル

様々な分野に、応用展開可能

アニーリング(徐冷)

自然現象から着想を得た計算技術

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

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

イジングモデルの基底状態を効率よく求める方法

イジングモデル

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

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

イジングモデルの基底状態を効率よく求める方法

量子アニーリングを用いたクラスタ分析

量子アニーリングを用いたクラスタ分析

田中宗 (早稲田大学高等研究所)

機械学習における重要な技術であるクラスタ分析に対する、量子アニーリングの性能評価を行った。

シミュレーテッドアニーリングに比べ、量子アニーリングの方が、性能面で優位であることを示唆する結果を得た。

量子アニーリングクラスタ分析

量子性を用いた新計算技術

量子アニーリングの基礎 ^{物理学と情報科学}

量子アニーリングを用いたクラスタ分析クラスタ分析のモデリング

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