6−5 - 日本大学生産工学部

ISSN 2186-5647
−日本大学生産工学部第49回学術講演会講演概要（2016-12-3）−
6-5
量子ウォーク
日大生産工
粒子のランダムな運動を表わすランダムウォーク
は，様々な現象を記述することができ，多方面で応
用されてきた．ランダムウォークの量子版である量
子ウォークも量子コンピュータの基礎理論構築と関
連し，その応用が考えられている．一例として，量
子探索アルゴリズムが挙げられる．Grover の探索ア
ルゴリズムは完全グラフ上の量子ウォークと考えら
れる．その他にもいくつかのグラフ上の探索アルゴ
リズムに量子ウォークは応用されている 1, 2) ．量子
ウォークは 2000 年頃より活発に研究され始め，各モ
デルに対する様々な定理の導出とともに，これまで
◦ 町田拓也
√
t でスケーリング
変換した確率分布は，中心極限定理により，t を十分
大きくしたとき，正規分布 (ガウス分布) で近似され
る．一方，量子ウォークの確率分布は，t で空間をス
ケーリング変換することで，逆正弦則の確率密度関
数のような，ある確率密度関数で近似される．量子
ウォークの確率分布がもつ大きな特徴は，ゆらぎと鋭
いピークをもつことである．粒子が原点から出発し
√
たとき，確率分布はランダムウォークの場合 O( t )
で広がるが，量子ウォークの場合は O(t) となる (図
3 参照)．
分布は二項分布であり，空間を
に興味深い性質が明らかにされてきた．日本語の解
0.03
0.04
説書として，今野 3, 4) ，町田 5) がある．
0.03
0.02
以下，ランダムウォークとの比較を交えつつ，量子
⏕₸
⏕₸
0.02
0.01
ウォークについて簡単に説明する．今回注目する 1 次
0.01
0
-100
元格子上の量子ウォークに対応するランダムウォーク
は，時刻 t ∈ { 0, 1, 2, . . . } で，Z = { 0, ±1, ±2, . . . }
-50
0
ⓨ㑆
50
100
(a) ランダムウォーク
上の，ある場所 x に存在する粒子が，時刻 t + 1 に確
0
-500
-250
0
ⓨ㑆
250
500
(b) 量子ウォーク
図 2: 確率分布の例
率 p で x − 1 に，確率 q ( = 1 − p) で x + 1 に移動す
るようなモデルである (図 1 参照)．量子ウォークで
は確率 p, q の代わりに，2 × 2 の確率振幅行列 P, Q
るものとする．
50
1
0.8
40
0.8
30
0.6
30
0.6
20
0.4
20
0.4
10
0.2
10
0
ⓨ㑆
p
0
-40 -20
q
0 20 40
ⓨ㑆
(a) ランダムウォーク
ᤨೞ
ᤨೞ
⏕₸
ᤨೞ
1
40
⏕₸
を考える．但し，P + Q はユニタリ行列になってい
50
0.2
0
0
-40 -20
0 20 40
ⓨ㑆
(b) 量子ウォーク
図 3: 確率分布の時間発展
さて，量子ウォークは，一般にグラフ上で定義でき
図 1: ランダムウォーク
るが，ここでは 1 次元格子上で定義される量子ウォー
クの標準的なモデルを説明する．まず，時刻 t におい
2
量子ウォークとランダムウォークの違いの 1 つは，て各場所 x(∈ Z) に，2 次の複素ベクトル |ψt (x)i ∈ C
粒子の空間的な分布 (確率分布) である (図 2 参照)．を考える．但し，C は複素数全体の集合である. 量
よく知られているように，ランダムウォークの確率
子ウォークの分野では，これらのベクトルは確率振
Quantum walk
Takuya MACHIDA
― 575 ―
幅ベクトルと呼ばれる．
0.03
0.02
⏕₸
0.01
⏕₸
0.01
0
-1000
-500
0
500
0
-1000
1000
x
0
500
1000
x
√
√
(a) α = 1/ 2, β = i/ 2
図 4: 各格子点上の確率振幅ベクトル
-500
(b) α = 1, β = 0
図 6: 時刻 1000 の確率分布 P(X1000 = x) (a = b =
√
c = −d = 1/ 2)
量子ウォークの時間発展を定義するために，以下
の 2 つの行列
"
#
a b
P =
,
0 0
#
0 0
Q=
,
c d
ここで紹介した量子ウォークに対しては，次の極
"
(1)
を導入する．但し，P + Q はユニタリ行列になって
いるものとする．量子ウォークの時間発展は，以下
で定義される (図 5 も参照)．
|ψt+1 (x)i = P |ψt (x + 1)i + Q |ψt (x − 1)i .
(2)
限定理が Konno6) により導出されている．実数 x に
対して，
µ
¶
Xt
≤x
t→∞
t
p
Z x
1 − |a|2
p
I(−|a|,|a|) (y)
=
2
2
2
−∞ π(1 − y ) |a| − y
"
(
¡
¢) #
aαbβ + aαbβ
2
2
× 1 − |α| − |β| +
y dy.
|a|2
lim P
(6)
但し，
ᤨೞ t
x Q
x
x (
I(−|a|,|a|) (x) =
P
1 (−|a| < x < |a|),
0 (otherwise).
(7)
ᤨೞ t 参考文献
図 5: 時間発展のダイナミクス
1) S. Venegas-Andraca, Quantum Walks for Computer Scientists, vol.1, Morgan & Claypool Publishers, (2008).
さらに，初期状態が
¯¯2
X¯¯¯¯
¯¯
¯¯|ψ0 (x)i¯¯ = 1,
(3)
x∈Z
を満たすもとで，ウォーカーが時刻 t で場所 x に観
測される確率を
¯¯
¯¯2
¯¯
¯¯
P(Xt = x) = ¯¯|ψt (x)i¯¯ ,
cessing, vol.11, no.5, (2012), pp.1015–1106.
3) 今野紀雄，量子ウォークの数理，産業図書，(2008)．
(4)
で定義する．ここで，Xt は時刻 t におけるウォーカー
の位置を表す確率変数である．初期状態を
(
T
[ α, β ] (x = 0),
|ψ0 (x)i =
T
[ 0, 0 ] (x 6= 0),
2) S.E. Venegas-Andraca, “Quantum walks: a comprehensive review,” Quantum Information Pro-
4) 今野紀雄，量子ウォーク，森北出版，(2014)．
5) 町田拓也，図で解る量子ウォーク入門，森北出版，
(2015)．
(5)
6) N. Konno, “Quantum random walks in one
dimension,” Quantum Information Processing,
vol.1, no.5, (2002), pp.345–354.
ととると，図 6 のような確率分布が得られる．但し，
α, β ∈ C は，|α|2 + |β|2 = 1 を満たすものとする．T
は転置作用素である．
― 576 ―

Download Report