5401009

勝間田 智

Groverアルゴリズムの
NMR量子計算シミュレータ試作

An Experimental Simulator
for NMR Quantum Computation
of Grover's Algorithm

日本大学文理学部

情報システム解析学科

谷 研究室

2005年2月12日(土)

目次

１． 研究の目的

２． 古典と量子

３． ファイル検索問題

４． シミュレーション

５． 今後の課題

目次

１． 研究の目的

２． 古典と量子

３． ファイル検索問題

４． シミュレーション

５． 今後の課題

１．研究の目的

1994年

Shorの因数分解アルゴリズム

量子コンピュータが実現すると

RSA暗号が破られる

1996年

Groverのデータベース検索アルゴリズム

ファイル検索が高速に

量子計算の仕組みはどうなっているのか…

１．研究の目的

比較的容易に実現可能なNMR量子計算機

・8項目のデータベース検索

・15の因数分解

NMR計算するシミュレータを作成

量子初学者の学習支援を目指して…

NMR：核磁気共鳴

(Nuclear Magnetic Resonance)

目次

１． 研究の目的

２． 古典と量子

３． ファイル検索問題

４． シミュレーション

５． 今後の課題

目次

１． 研究の目的

２． 古典と量子

２-１． 古典アルゴリズム

２-２． 量子アルゴリズム

３． ファイル検索問題

４． シミュレーション

５． 今後の課題

目次

１． 研究の目的

２． 古典と量子

２-１． 古典アルゴリズム

２-２． 量子アルゴリズム

３． ファイル検索問題

４． シミュレーション

５． 今後の課題

２-１．古典アルゴリズム

ファイル検索アルゴリズム

通常のアルゴリズム

・線形探索

・二分探索

２-１．古典アルゴリズム

ファイル検索アルゴリズム

通常のアルゴリズム

・線形探索

・二分探索

N個のデータ・・・最悪 O(N)

×

×

×

×

×

×

×

２-１．古典アルゴリズム

確率的アルゴリズム

×

×

×

×

×

×

×

N=8のとき N/2=4個探索

２-１．古典アルゴリズム

確率的アルゴリズム

×

×

×

×

①

②

③

④

×

×

×

N=8のとき N/2=4個探索

２-１．古典アルゴリズム

確率的アルゴリズム

×

×

×

×

×

×

×

N=8のとき N/2=4個探索

①

②

③

④

２-１．古典アルゴリズム

確率的アルゴリズム

×

×

×

×

×

×

×

N=8のとき N/2=4個探索

探索に成功する確率は1/2以上

比較回数はO(N/2)

①

②

③

④

目次

１． 研究の目的

２． 古典と量子

２-１． 古典アルゴリズム

２-２． 量子アルゴリズム

３． ファイル検索問題

４． シミュレーション

５． 今後の課題

２-２．量子アルゴリズム

量子コンピュータ

状態|0>と|1>が同時に存在

重ね合わせの状態

α|0>+β|1>

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

２-２．量子アルゴリズム

量子コンピュータ

状態|0>と|1>が同時に存在

重ね合わせの状態

α|0>+β|1>

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

確率

∣

β

∣

2

確率

∣

α

∣

2

∣

α

∣

2



∣

β

∣

2

=

1

|0> または |1> が観測される

２-２．量子アルゴリズム

0

0

0

3ビットの場合

すべてで8通り表せる

1

1

1

1

1

0

1

0

1

0

1

1

0

1

0

1

0

0

0

0

1

２-２．量子アルゴリズム

3キュービット

0

0

0

3ビットの場合

すべてで8通り表せる

重ね合わせを利用し8通りを一度に表現できる

0

1

0

1

0

1

1

1

1

1

1

0

1

0

1

0

1

1

0

1

0

1

0

0

0

0

1

２-２．量子アルゴリズム

|x>:ケットベクトル(列ベクトル)

共役作用素

２-２．量子アルゴリズム

作用素U がユニタリ

UU* = I

I ：単位行列

作用素U がユニタリ

UU* = I

２-２．量子アルゴリズム

ユニタリ変換

状態|x>はユニタリ作用素U により

|y> = U |x>

に推移する

２-２．量子アルゴリズム

システムの状態

２-２．量子アルゴリズム

システムの状態

確率振幅

２-２．量子アルゴリズム

システムの状態

確率振幅

２-２．量子アルゴリズム

ユニタリ変換を数回行う

☆ 目的の状態の確率振幅を増やす

☆ それ以外の状態の確率振幅を減らす

量子アルゴリズムで行うこと

目次

１． 研究の目的

２． 古典と量子

３． ファイル検索問題

４． シミュレーション

５． 今後の課題

目次

１． 研究の目的

２． 古典と量子

３． ファイル検索問題

３-１． Groverのアルゴリズム

３-２． NMR量子計算機上の

Groverのアルゴリズム

４． シミュレーション

５． 今後の課題

ファイル探索問題

N個のデータファイルがある

ファイル探索問題

.

.

.

.

.

.

mazda

0

N-1

z

1

ship

bridge

mmr

N個のデータファイルがある

mazda...

指定されたファイルを見つけ出す

ファイル探索問題

.

.

.

.

.

.

mazda

0

N-1

z

1

ship

bridge

mmr

N個のデータファイルがある

mazda...

指定されたファイルを見つけ出す

古典コンピュータでは

ファイル探索問題

.

.

.

.

.

.

mazda

0

N-1

z

1

ship

bridge

mmr

N個のデータファイルがある

mazda...

指定されたファイルを見つけ出す

古典コンピュータでは

量子コンピュータでは

ファイル探索問題

.

.

.

.

.

.

mazda

0

N-1

z

1

ship

bridge

mmr

目次

１． 研究の目的

２． 古典と量子

３． ファイル検索問題

３-１． Groverのアルゴリズム

３-２． NMR量子計算機上の

Groverのアルゴリズム

４． シミュレーション

５． 今後の課題

3-1. Groverのアルゴリズム

データ選択に役立つソートが

行われていないファイル数

0からN-1のアドレスが付けられている

f



x



=

1

if

x

=

z

f



x



=

0

if

x

≠

z

目的ファイルのアドレス

与えられるアドレス

オラクル関数

f(x)=1, f(x)=0は

一瞬で計算される

ものとする

3-1. Groverのアルゴリズム

f



x



=

1

if

x

=

z

f



x



=

0

if

x

≠

z

目的ファイルのアドレス

与えられるアドレス

オラクル関数

f(x)=1, f(x)=0は

一瞬で計算される

ものとする

仮定:オラクル関数が与えられる

入力:x

出力:f(z)=1となるz

データ選択に役立つソートが

行われていないファイル数

0からN-1のアドレスが付けられている

3-1. Groverのアルゴリズム

1. N個の各状態が同一の振幅を持つ重ね 合わせを生成

2. 以下のユニタリ変換をk回繰り返す

(a) f(x)=1 選択的回転変換

f(x)=0 何もしない

(b) 平均に関する反転変換

3. 最終状態を観測

キュービット n = 2

ファイル数 N = 4

目的アドレス z = 2

変換回数 k = 1

3-1. Groverのアルゴリズム

具体例

3-1. Groverのアルゴリズム

0

1/2

0

振幅

アドレス

初期状態

3

2

1

キュービット n = 2

ファイル数 N = 4

目的アドレス z = 2

変換回数 k = 1

3-1. Groverのアルゴリズム

1/2

0

振幅

アドレス

選択的回転変換

-1/2

1/4

0

1

2

3

キュービット n = 2

ファイル数 N = 4

目的アドレス z = 2

変換回数 k = 1

3-1. Groverのアルゴリズム

0

振幅

アドレス

平均に関する反転変換

-1/2

1/4

1

3

2

1

0

キュービット n = 2

ファイル数 N = 4

目的アドレス z = 2

変換回数 k = 1

3-1. Groverのアルゴリズム

ユニタリ変換をk回繰り返し

★目的ファイルの確率振幅を増やす

★それ以外は減らしたい

方針とkの値

3-1. Groverのアルゴリズム

ユニタリ変換をk回繰り返し

★目的ファイルの確率振幅を増やす

★それ以外は減らしたい

方針とkの値

最適な

k

=

π



N

/

4

目次

１． 研究の目的

２． 古典と量子

３． ファイル検索問題

３-１． Groverのアルゴリズム

３-２． NMR量子計算機上の

Groverのアルゴリズム

４． シミュレーション

５． 今後の課題

3-2. NMR量子計算機上の
Groverのアルゴリズム

NMR量子計算機

重ね合わせの状態

α|0>+β|1>

θ

=

∣

β

∣

2

−

∣

α

∣

2

観測値

∣

α

∣

2



∣

β

∣

2

=

1

3-2. NMR量子計算機上の
Groverのアルゴリズム

NMR量子計算機

重ね合わせの状態

α|0>+β|1>

θ

=

∣

β

∣

2

−

∣

α

∣

2

観測値

∣

α

∣

2



∣

β

∣

2

=

1

観測誤差ε

実際は…

∣

β

∣

2

−

∣

α

∣

2

−

ε

≤

θ

≤

∣

β

∣

2

−

∣

α

∣

2



ε

3-2. NMR量子計算機上の
Groverのアルゴリズム

NMR量子計算機

重ね合わせの状態

α|0>+β|1>

θ

=

∣

β

∣

2

−

∣

α

∣

2

∣

α

∣

2



∣

β

∣

2

=

1

∣

α

∣

2

<

1

/

2

∣

α

∣

2

1

/

2

∣

α

∣

2

≥

1

/

2

∣

α

∣

2

≥

1

/

2

If

If

Then

Then

目的ファイル=|0>

目的ファイル=|1>

以下が確率1で求まる

目次

１． 研究の目的

２． 古典と量子

３． ファイル検索問題

４． シミュレーション

５． 今後の課題

4. シミュレーション

Mathematicaによるデモ

4. シミュレーション

Mathematicaによるデモ

キュービット

ファイル数

目的アドレス

変換回数

キュービット

ファイル数

目的アドレス

変換回数

デモ1 ： 量子計算のアニメーション

デモ2 ： NMR量子計算

n =4

N=16

z =7

k =255

n =5

N=32

z =14

k =1

目次

１． 研究の目的

２． 古典と量子

３． ファイル検索問題

４． シミュレーション

５． 今後の課題

５．今後の課題

1) 観測誤差εを考慮したGrover

アルゴリズムのNMR量子計算

シミュレータ試作

2) Shorの因数分解アルゴリズムの

シミュレータ試作

3) 対称暗号系秘密鍵を解読する

NMR量子アルゴリズムの追実験

ご静聴ありがとうございました

ご指導宜しくお願い致します

おわり

2004-11-08T11:53:27