量子ウォークの量子コンピュータ実装1

# 量子ウォークの量子コンピュータ実装1 ~サイクル４上アダマールウォーク~
量子ウォークの研究をする横国大の今野研所属の数学系大学院生です．研究室のメンバーと2017年から量子情報の勉強をはじめ．2018年からはIBM Qを用いて実装もおこなってきました．これまでの量子アルゴリズムや量子ウォークの実装に関するノートが貯まってきたこともあり，せっかくなので順次まとめる．

今回は，***サイクル4上のアダマールウォークの実装***を行う．
ここで紹介する方法は，[Efficient quantum circuit implementation of quantum walks](https://arxiv.org/abs/0706.0304)とほぼ同様である．

##サイクル４上 Hadamard Walk について
###量子ウォーク
量子ウォークは，[ランダムウォークの量子版](https://ja.wikipedia.org/wiki/%E9%87%8F%E5%AD%90%E3%82%A6%E3%82%A9%E3%83%BC%E3%82%AF)として導入された．ランダムウォークとの違いは，確率の時間発展ではなく，確率振幅の時間発展を考えること，そして確率振幅のノルム2乗をとることで確率になるという点です．数学の解説本として[「量子ウォーク」](https://www.morikita.co.jp/books/book/2762)，また数学から物理学，工学，情報科学までまとめた[「量子ウォークの新展開~数理構造の深化と応用~」](https://www.amazon.co.jp/%E9%87%8F%E5%AD%90%E3%82%A6%E3%82%A9%E3%83%BC%E3%82%AF%E3%81%AE%E6%96%B0%E5%B1%95%E9%96%8B%E2%80%95%E6%95%B0%E7%90%86%E6%A7%8B%E9%80%A0%E3%81%AE%E6%B7%B1%E5%8C%96%E3%81%A8%E5%BF%9C%E7%94%A8-%E4%BB%8A%E9%87%8E-%E7%B4%80%E9%9B%84/dp/4563011622)などがある．

簡単な説明とともにモデルの定義をしていく．
今回考えるサイクルは，
![C4image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/547806/cd098e43-51f7-ed65-b71d-ef958ba0df1f.png)
である．このサイクル（$00,01,10,11$(10進数で0~3))上の量子ウォークを以下で定義する．

* 量子コイン(アダマール行列)

```math
U=\frac{1}{\sqrt{2}}\begin{bmatrix}
1&1 \\
1&-1  
\end{bmatrix}
```
ここで，

```math
P=\frac{1}{\sqrt{2}}\begin{bmatrix}
1&1 \\
0&0  
\end{bmatrix}\\
Q=\frac{1}{\sqrt{2}}\begin{bmatrix}
0&0 \\
1&-1  
\end{bmatrix}
```
とする．

* 初期状態

```math
\Psi(0)=\frac{1}{\sqrt{2}} \begin{bmatrix}1\\i\end{bmatrix},　\Psi(1)=\Psi(2)=\Psi(3)=\begin{bmatrix}0\\0\end{bmatrix}
```
ただし，$\Psi(x)$は場所$x$の確率振幅である．

* 時間発展  
***量子ウォークの時間発展は，確率振幅の時間発展になる．***

```math
\begin{align}
\Psi(x)=&P\Psi(x+1)+Q\Psi(x-1)\\
=&\frac{1}{\sqrt{2}}\begin{bmatrix}
1&1\\0&0
\end{bmatrix} \Psi(x+1)+\frac{1}{\sqrt{2}}\begin{bmatrix}
0&0\\1&-1
\end{bmatrix}\Psi(x-1)
\end{align}
```
ただし，$x+1,x-1$はサイクル上なので$mod4$で考える．

* 観測  
確率振幅のノルム2乗を取ることによって，確率が得られる．
 
```math
\mu(x)=\|\Psi(x)\|^2
```

## コイン作用素とシフト作用素
上の表現はダイナミクスの理解はしやすいが，実装するために系全体のダイナミクスとして，
$$
W=\hat{S}\hat{C}\\
$$
で表す．それぞれの作用素は以下で表す．

* コイン作用素$\hat{C}$  

```math
\hat{C}=(I\otimes H)\\
\mbox{ただし，}I=\sum_{x}|x\rangle\langle x|,\quad H=\frac{1}{\sqrt{2}}\begin{bmatrix}
1&1\\1&-1
\end{bmatrix}
```  
* シフト作用素$\hat{S}$

```math
\hat{S}=\sum_{x}|x-1\rangle\langle x|\otimes|0\rangle\langle 0|+|x+1\rangle\langle x|\otimes|1\rangle\langle 1|
```
とする．また，

* 初期状態
$$\Psi=\frac{1}{\sqrt{2}}|0\rangle\otimes|0\rangle+\frac{i}{\sqrt{2}}|0\rangle\otimes|1\rangle$$
で表せる．

この***コイン作用素***と***シフト作用素***のゲートを考えれば，量子ウォークの時間発展を量子ウォークを表現できる．
  
  
具体的には，
***コイン作用素*** $\hat{C}=I\otimes H$ は，状態の量子ビットだけに $H$ を通せば表せる．
***シフト作用素*** $\hat{S}$ は，
・状態 が```0```ならば場所 $x$ が減算
・状態 が```1```ならば場所 $x$ が加算
するゲートを考えればよい．

## IBMQでの実装
今回の実装には 3qubits ($q[0]q[1]q[2]$) を使う．場所 (00,01,10,11) に対応する qbit として$q[0]q[1]$を，状態に対応する qubit として $q[2]$ を考える．

### シフト作用素の構築(サイクル４について)
天下り的だが，2桁2進数 $q[0]q[1]$ と状態 $q[2]$ に対して次の計算をする．

|$q[0]q[1]$場所(10進数0~3)|$q[2]$(状態0or1)||$(q[0]\oplus\overline{q[1]}\oplus q[2])(\overline{q[1]})$ |
|:---:|:---:|:---:|:---:|:---:|
|00|0|$\Rightarrow$|11|
|01|0|$\Rightarrow$|00|
|10|0|$\Rightarrow$|01|
|11|0|$\Rightarrow$|10|
|00|1|$\Rightarrow$|01|
|01|1|$\Rightarrow$|10|
|10|1|$\Rightarrow$|11|
|11|1|$\Rightarrow$|00|
表のように，入力: $q[0]q[1]q[2] \Rightarrow$ 出力: $(q[0]\oplus\overline{q[1]}\oplus q[2])(\overline{q[1]})(q[2])$ と組むと，状態が```0```なら減算，状態が```１```なら加算になっており，シフト作用素に対応している．この出入力を量子回路で実装すればよいことになる．


### 回路部分の作成
量子レジスター、古典レジスター、そしてそれらから量子回路qwqcを設定

```python
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister
from qiskit import execute
from qiskit.tools.visualization import plot_histogram

q = QuantumRegister(3, 'q')
c = ClassicalRegister(2, 'c')
qwqc = QuantumCircuit(q,c)
```

時間発展部分

```python
#時間発展回数
t=1

#初期状態をセット
qwqc.h(q[2])
qwqc.s(q[2])

#時間発展
for i in range(t):
    #コイン作用素
    qwqc.h(q[2])
    #シフト作用素
    qwqc.x(q[1])
    qwqc.cx(q[2],q[0])
    qwqc.cx(q[1],q[0])
#場所(q[0]q[1])を観測　状態（q[2]）は観測しない
qwqc.measure(q[0],c[0])
qwqc.measure(q[1],c[1])

#回路描画
qwqc.draw()
```
>![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/547806/d970a94a-1918-9935-0822-7aae46186556.png)


### t=1でのシミュレーターの結果

```python
from qiskit import BasicAer

backend = BasicAer.get_backend('qasm_simulator')
job = execute(qwqc, backend,shots=1024)
result = job.result()
counts = result.get_counts(qwqc)
plot_histogram(counts)
```
>![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/547806/3d0f758d-81ef-4fee-6a41-bb54a2ac2d0c.png)

理論的には，

```math
\begin{align}
W\Psi&=\hat{S}\times\left(|0\rangle\otimes\frac{1+i}{2}|0\rangle+|0\rangle\otimes\frac{1-i}{2}|1\rangle\right)\\
&=\frac{1+i}{2}|3\rangle\otimes|0\rangle+\frac{1-i}{2}|1\rangle\otimes|1\rangle
\end{align}
```
より

```math
\mu(1)=\mu(3)=\frac{1}{2}
```
となる．シミュレーターなのでそこそこの結果になった．

### t=1での実機の結果

```python
from qiskit import IBMQ
from qiskit.tools.monitor import job_monitor

provider = IBMQ.get_provider(hub='ibm-q')
provider.backends()

backend_r=provider.get_backend('ibmqx2')
job_r = execute(qwqc, backend=backend_r,shots=1024)
job_monitor(job_r)
```
>Job Status: job has successfully run

```
result_r= job_r.result()
counts_r = result_r.get_counts(qwqc)
plot_histogram(counts_r)
```
>![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/547806/196ef9e1-e536-218b-411c-4017ba287c8d.png)


## まとめ
サイクル４上アダマールウォークは，回路が比較的簡単で時間発展t=1だったため，そこまでエラーも蓄積されない結果と言えるかもしれない．

また，コイン作用素のアダマール行列$H$を別のユニタリ行列$U$で置き換えると，別の空間的一様な量子コインの量子ウォークになる．IBM Qでは$U_3(\theta,\phi,\lambda)$で好きな量子コインを作れる．

今後は，他のサイクル上，他グラフ上，多状態数モデル，空間的時間的非一様モデルについても順次まとめていきたい．また量子ウォークを用いたアルゴリズムについてもまとめたい．