【量子】量子ウォークの実装例

##1.はじめに
業務で時系列データ解析を担当している中で、たまたま本屋で参考資料[1]を見かけ、量子コンピューティングと時系列データ予測でリンクしている部分があると知り、個人で勉強を進めていた。
アドベントカレンダー（量子コンピュータ）も見かけ、せっかくなので勉強したことをまとめ、同じ分野に興味を持っている同志との出会いを期待し、本記事を作成する。

##2.参考資料
[1] [今野紀雄著、量子ウォークによる時系列解析、日本評論社、2020年9月](https://www.amazon.co.jp/dp/B08JYBQCW8/)
[2] [webマガジン「RAD-IT21」,ランダムウォークから量子ウォークへ](https://rad-it21.com/%E3%82%B5%E3%82%A4%E3%82%A8%E3%83%B3%E3%82%B9/konno_norio_20200422/)
[3] [a memory less ephemeral 実装例](https://susan-stepney.blogspot.com/2014/02/mathjax.html)
[4] [今野紀雄著、量子ウォークの過去・現在・未来, 2013年5月](http://www.muroran-it.ac.jp/mathsci/danwakai/past/articles/201304-201403/01_2-20130529-konno.pdf)
[5] [Qiita記事,量子ウォークの量子コンピュータ実装1、2019年12月](https://qiita.com/YNUqw/items/e10f9a1fad9181415a35)

##3.量子ウォークと時系列解析
###3-1. ランダムウォーク
・いわゆる酔歩。
・確率$p$で右に、確率$(1-p)$で左に動く、１次元のランダムウォークを考える。
・$ \Phi[x,t] $が、時刻tに、地点xにいる確率とする。
・$ \Phi[x,t+1] = p*\Phi[x-1,t] + (1-p)*\Phi[x+1,t] $ で表される場合を、ランダムウォークという。
・株価の時系列データなどは、ランダムウォークでうまく表現できることが知られている。

###3-2. 量子ウォーク
・ランダムウォークの量子版。
・確率の表現に、量子コインを用いている。
・一番基礎的な手法に、「アダマールウォーク」がある。本ページでは、アダマールウォークの実装例を記載する。

##4.実装例
###4-1. ランダムウォーク
ランダムウォークの実装例を以下に示す。

```python:random_walk.py　
import numpy as np
import random
from matplotlib import pyplot as plt

N_steps = 1000
prob = 0.5

def SimpleRandomWalk(N, p, line):
   
    position = np.empty(N)
    position[0] = 0
    pos_counter = 0
    
    steps = np.arange(N)

    #ランダムウォークスタート 
    for i in range(1,N):

        test = random.random()

        if test >= p:
            pos_counter += 1
        else:
            pos_counter -= 1

        position[i] = pos_counter

    plt.plot(steps, position, line)
    plt.xlabel('Steps taken')
    plt.ylabel('Distance from Starting Position')


    return position

position_distribution = []
for i in range(1000):
    p = SimpleRandomWalk(N_steps, prob, line="-")
    position_distribution.append(p[-1])
    
plt.figure()
plt.hist(position_distribution)
plt.show()

```

ランダムウォークの軌跡を以下に示す。
![random_walk_orbit.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/509872/ad664df2-646c-e362-34e4-bc2f8680493a.png)
Fig.1 ランダムウォークの軌跡（Step=1000の場合）

![random_walk_dist.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/509872/75309ac2-2857-d2aa-405d-3025c4d0a210.png)
Fig.2 ランダムウォークのゴール地点の確率分布（Step=1000の場合）

###4-2. 量子ウォーク
量子ウォークの実装例を以下に示す。

```python:random_walk.py　
from numpy import *
from matplotlib.pyplot import *
from scipy import stats

def quantum_walk(N):
    P = 2*N+1    # number of positions

    coin0 = array([1, 0])  # |0>
    coin1 = array([0, 1])  # |1>

    C00 = outer(coin0, coin0)  # |0><0| 
    C01 = outer(coin0, coin1)  # |0><1| 
    C10 = outer(coin1, coin0)  # |1><0| 
    C11 = outer(coin1, coin1)  # |1><1| 

    C_hat = (C00 + C01 + C10 - C11)/sqrt(2.)

    ShiftPlus = roll(eye(P), 1, axis=0)
    ShiftMinus = roll(eye(P), -1, axis=0)
    S_hat = kron(ShiftPlus, C00) + kron(ShiftMinus, C11)

    U = S_hat.dot(kron(eye(P), C_hat))

    posn0 = zeros(P)
    posn0[N] = 1     # array indexing starts from 0, so index N is the central posn
    psi0 = kron(posn0,(coin0+coin1*1j)/sqrt(2.))

    psiN = linalg.matrix_power(U, N).dot(psi0)

    prob = empty(P)
    for k in range(P):
        posn = zeros(P)
        posn[k] = 1     
        M_hat_k = kron( outer(posn,posn), eye(2))
        proj = M_hat_k.dot(psiN)
        prob[k] = proj.dot(proj.conjugate()).real
    return prob, P

N = 100

prob ,P = quantum_walk(N)
fig = figure()
ax = fig.add_subplot(111)

plot(arange(P), prob)
show()

```
ゴール位置の確率分布を以下に示す。

![quantum_walk.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/509872/fd951e82-7d49-0b1f-b1b0-a799ca234176.png)
Fig.3 量子ウォークのゴール地点の確率分布

ランダムウォークでは、出発地点をピークに、正規分布を描くが、量子ウォークでは、二つのピークが現れる。

##5.終わりに
・応用例として、時系列データ予測に使えることが示唆されているが、応用例にそった実装例がない。今後は、応用例の実装例を共有したい。

## 更新履歴
Rev.0 2020/12/6 新規作成