１次元量子ウォークをJuliaでシミュレーションする

$$
\def\bra#1{\mathinner{\left\langle{#1}\right|}}
\def\ket#1{\mathinner{\left|{#1}\right\rangle}}
\def\braket#1#2{\mathinner{\left\langle{#1}\middle|#2\right\rangle}}$$
初めての投稿です。
大学学部時代に量子ウォークを勉強していました。量子ウォークの面白さを知ってもらいたいので、ニーズがあると思い情報共有として書こうと思います。以下書くことは、学術参考書とは程遠い質の記事であり、注意して書くものの、物理学的に間違った書き方が多々ある可能性もあるので、ご了承ください。

初めに量子ウォークは
(1) 量子情報 
(2) 物性物理 
(3) 応用数学
などの分野で研究されています。主に量子情報としての研究が強い印象ですが、(2) 物性物理にも応用できるみたいです。(3)は量子ウォークの挙動について議論されている印象です。

自分が実際に購入したり、参考にした、上記に対応した参考書籍や参考pdfは
(1) 中山茂：量子アルゴリズム
(2)「トポロジカル相と対称性を活用した量子状態制御」
http://www.qi.t.u-tokyo.ac.jp/workshop/NQuIC2018/slide/obuse_slide.pdf
(3) 今野紀雄：量子ウォーク
(4) 町田拓也：図で解る量子ウォーク入門
などです。
特に(1)はわかりやすく、物理学出身者以外の方でも理解できると思います。(3)は本格的な数理的量子ウォークを学ぶ人向けで、個人的に難しく挫折しました。ただ、この本の序盤に書いてある、量子ウォークの定義や説明などは為になります。(4)は量子ウォークのシミュレーションをとりあえず先にやってみたい方や、簡単に量子ウォークというものを知りたい人におすすめです。(C++のコードが付属付きです)

ここから本題に入ります。
量子ウォークは連続時間量子ウォークと離散時間量子ウォークに分かれます。今回は離散時間量子ウォークについて説明します。この量子ウォークモデルは、ランダムウォークと類似していることから、一言で、「ランダムウォークの量子版」と言われています。よって、ランダムウォーク同様に、コイントスを
行い、表であれば右に移動し、裏であれば左に移動するといった形で量子を歩行させます。このシステムは、ヒルベルト空間に属します。つまり、$H_{qwalk}=H_{N}\otimes H_{x}$の空間で量子状態が時間発展します。ここで、位置の自由度$\ket{\vec{x}}\in H_{N}$、内部自由度$\ket{s}\in H_{k}$です。これらから、量子ウォークの時間発展する量子状態は以下のようにあらわすことができます。
$$\ket{\Psi(t)}=\sum_{x=0}^{n}\sum_{l=0}^{s}\alpha\ket{x}\otimes\ket{s}$$
ここで、$\alpha$は確率振幅、$s$は内部自由度の総数です。今回は右左方向をそれぞれ$l=0,1$と表します。つまり、
$$\ket{l=0}=\ket{R},\ket{l=1}=\ket{L}$$
さらに前述した量子モデルについて、量子の移動方向を決定させるコインを量子コイン演算子$C$と言い、コインを投げた後にシフトさせる演算子をシフト演算子$S$と呼びます。
![quantum.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/263910/fa7c4ea4-9b77-365c-86e8-552d2f696dfd.png)


量子状態の内部状態を操作する量子コインはユニタリー行列で定義されます。これらの演算子を数式を用いて表現すると以下のようになります。

```math
C(\theta)\otimes\ket{x}\bra{x}=\begin{pmatrix}
\cos{\theta} & \sin{\theta} \\
\sin{\theta} & -\cos{\theta} 
\end{pmatrix}\otimes\ket{x}\bra{x}
```
$$S=\sum_{x}\Bigl(\ket{x+1}\bra{x}\otimes\ket{R}\bra{R}+\ket{x-1}\bra{x}\otimes\ket{L}\bra{L}\Bigr)$$
初期状態 $\Psi(t=0)=\begin{matrix}[\alpha_{rx}& \alpha_{lx}]\end{matrix}$とおくと、上の図の量子状態の時間発展式は以下の式で表せます。
$$\ket{\Psi(t)}=(SC)^t\ket{\Psi(t=0)}$$

以上を踏まえて、今回は初期状態を$$\psi(x=n/2,t=0)=\begin{bmatrix}\frac{1}{\sqrt{2}}&\frac{i}{\sqrt{2}}\end{bmatrix}$$
として、Juliaでシミュレーションを行います。

```julia
n=100 
#コイン演算子を定義
function coin(theta)
   return C=[cos(theta) sin(theta);sin(theta) -cos(theta)]
end
#コイン作用
function coin(theta,psi)
    cpsi = coin(theta)*psi
    return cpsi
end
```
```julia
#x座標の量子の存在確率を計算する関数
function probab(psi)
    prob=Float64[]
    for x in 1:n
        push!(prob, dot(psi[x,:],psi[x,:]))
    end
    return prob
end
```
```julia
#量子ウォーク
using LinearAlgebra
using ProgressMeter

function walk(theta,step)
    stage=complex(zeros(Float64,n,2)) #量子ウォークさせるステージ生成
    stage[div(n,2),:]=[1, 1im]#/sqrt(2) #初期状態
    progress=Progress(step) #progress and next!でシミュレーションの計算時間測定
    anim=@animate for t in 1:step #gif生成用
    #for t in 1:step        
        next_stage = complex(zeros(Float64,n,2)) #t+1秒後の量子状態を収納する用
        for x =1:n
            #周期境界条件
            x0 = ((x-1 + (n-1))%n) + 1
            x1 = ((x+1 + (n-1))%n) + 1
            #コイントス
            psi = coin(theta,stage[x,:])
            #シフト
            next_stage[x0,1]=psi[1]
            next_stage[x1,2]=psi[2]
        end
        stage = next_stage #t+1秒後の値をt秒後として代入
        plot(probab(stage),lw=1,color=:black,ylim=(0,0.6),size=(250,250),fill=(0,:cyan))
        next!(progress)
    end
    return gif(anim,fps=10)
end
```
以上から$\theta$の変化に対する量子ウォークの結果です。横軸がｘ軸、縦軸がそれぞれのx軸にいる量子の存在確率です。
![1_12_walk.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/263910/1a2be308-d6e4-e10c-4144-aab94a51c330.gif)![hadamard_walk.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/263910/c857917f-1e4f-3600-694b-1a03462b25c2.gif)![5_12_walk.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/263910/496e1d64-d4df-7be3-a43d-6f07a16a6ca8.gif)![pi_2_walk.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/263910/66878d8d-b359-4a03-2170-7ed26a26e653.gif)![11_12_walk.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/263910/69a0be11-d69d-64b0-38f2-d8992bcaa4fc.gif)![12_12_walk.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/263910/31eb9435-9e1a-63be-e4b9-6bcc3155649d.gif)

$\theta$によって挙動が異なるのが面白いですね。$\theta=\pi/4$の時の量子ウォークはアダマールウォークと呼ばれます。

まとめ）
今回、量子ウォークというものを簡単に説明し、Juliaでシミュレーションした。

ひとこと）
プログラミングは得意ではないので、分かりにくい部分や無駄な部分があるかもしれません。アドバイス頂けたら幸いです。また今回のシミュレーションは完全オリジナルで参考書籍(4)に書いてあるやり方とは全く異なります。

今後の展望として、この知識を前提に２、３次元量子ウォークや、量子ウォークを用いた量子探索について書いていこうと思います。

追記）
コードについて、計算速度向上のためのアドバイスをいただきました。

```julia
n=100 ではなく、
const n=100　のほうが良い

push!は効率が悪いので、以下のようにあらかじめ必要な配列を作り代入することにしました。
function probab(psi)
    prob=zeros(Float64,n)
    for x in 1:n
        prob[x] = dot(psi[x,:],psi[x,:])
    end
    return prob
end

```

ありがとうございます！