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

# 量子ウォークの量子コンピュータ実装2 ~サイクル2のべき乗上アダマールウォーク~
***サイクル $8$ 上のアダマールウォークの実装***をまとめる．サイクル8上が実現すれば，同様のやり方でサイクル$2^n$上ができるため，サイクル8の場合だけ紹介する
ここで紹介する方法は，[Efficient quantum circuit implementation of quantum walks](https://arxiv.org/abs/0706.0304)に同様．


##サイクル8上 Hadamard Walk について
量子ウォークの簡単な説明は[量子ウォークの量子コンピュータ実装1](https://qiita.com/YNUqw/items/e10f9a1fad9181415a35)を参考．

今回考えるサイクルは，
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/547806/030893de-c085-a372-1aff-ca001d0f8e03.png)



である．このサイクル（ $000,001,...,110,111$ (10進数で0~7))上の量子ウォークを定義する  


## コイン作用素とシフト作用素
全体のダイナミクスとして，
$$
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|
```
とする．ただし，$x\pm 1$は$mod8$で考える．

* 初期状態
$$\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}$は，
・状態 $q[3]$ が```0```ならば場所```x```に対応する $q[0]q[1]q[2]$ が-1
・状態 $q[3]$ が```1```ならば場所```x```に対応する $q[0]q[1]q[2]$ が+1
するゲートを考えればよい．

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

### シフト作用素の構築(サイクル8について)
$n$桁2進数の+１操作と-１操作のアルゴリズムを考えると，

* -1 操作
![add_min1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/547806/25b2415a-092b-cb84-2fc8-dc261be4fca2.png)

* +1 操作
![add_min21.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/547806/e5eb72bd-8b35-4e8e-449b-4ed0458185fb.png)
になる．n桁2進数を入力すると，それぞれ$\pm 1$される．

このゲートひとつひとつを，状態$q[3]$でコントロールさせればよい．したがってシフト作用素は次のようになる．
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/547806/e2de3438-a35e-ee74-3fab-e12f81228996.png)
<font color="Red">赤枠</font>は最下位 qubit が```0```なら上位３qubits が -1。
<font color="Blue">青枠</font>は最下位 qubit が```1```なら上位３qubits が +1。


ただし，IBM-Qで実装するためには，3つ以上のコントロール部分を持つtoffoliゲートは，次の書き換えが必要．
![toffo1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/547806/954481ee-c1fb-f9d8-e4d4-50fd7511c21a.png)

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

toffoliゲートの書き替えを準備しておく．

```python
def toffoli(circ,c1,c2,c3,t,a1):
    circ.ccx(c3,c2,a1)
    circ.ccx(a1,c1,t)
    circ.ccx(c3,c2,a1)
```
この置き換えを使って，サイクル8のコードを作る．

* 場所qbits $\Rightarrow q[0]q[1]q[2]$
* 状態qbits $\Rightarrow q[3]$
* 予備qbits $\Rightarrow aq[0]$

```python
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister
from qiskit import execute

from qiskit.tools.visualization import plot_histogram

q = QuantumRegister(4, 'q')
aq =QuantumRegister(1, 'aq')
c = ClassicalRegister(3, 'c')
qwqc = QuantumCircuit(q,aq,c)

#t回時間発展
t=1

#初期設定
qwqc.h(q[3])
qwqc.s(q[3])

for i in range(t):
    #コイン
    qwqc.u3(pi/3,0,0,q[3])
    #シフト -1
    qwqc.x(q[3])
    qwqc.cx(q[3],q[2])
    qwqc.ccx(q[3],q[2],q[1])
    toffoli(qwqc,q[1],q[2],q[3],q[0],aq[0])
    qwqc.x(q[3])
    #シフト +1
    toffoli(qwqc,q[1],q[2],q[3],q[0],aq[0])
    qwqc.ccx(q[3],q[2],q[1])
    qwqc.cx(q[3],q[2])
    
qwqc.measure(q[0],c[0])
qwqc.measure(q[1],c[1])
qwqc.measure(q[2],c[2])
qwqc.draw()
```
>![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/547806/fe8930f3-2357-1791-df52-5b82cdad5be2.png)

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

```python
from qiskit import IBMQ

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

backend_s=provider.get_backend('ibmq_qasm_simulator')
job_s = execute(qwqc, backend_s,shots=1024)
result_s = job_s.result()
counts_s = result_s.get_counts(qwqc)
plot_histogram(counts_s)
```
>![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/547806/ceea966a-a624-9b2c-8eac-22585b240d75.png)

```math
\begin{align}
W\Psi&=SC\left(\frac{1}{\sqrt{2}}|0\rangle\otimes|0\rangle+\frac{i}{\sqrt{2}}|0\rangle\otimes|1\rangle\right)\\
&=\frac{1}{2}S\left((1+i)|0\rangle\otimes|0\rangle+(1-i)|0\rangle\otimes|1\rangle\right)\\
&=\frac{1}{2}\left((1+i)|7\rangle\otimes|0\rangle+(1-i)|1\rangle\otimes|1\rangle\right)
\end{align}
```
したがって
$$\mu(1)=\mu(7)=\frac{1}{2}$$
でほぼ理論通りの結果．

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

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

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

```python
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/7b52b92e-d218-92e5-dbef-7791a797deee.png)

サイクル８はコントロールゲートの量が多く、時間発展1回でも誤差の蓄積大きい結果になる．

## まとめ
サイクルが大きくなると実機ではエラーの蓄積が大きくなることがわかる．
同じようにシフト作用素を作っていけば，サイクル $8,16,32,....$と大きくしていくことができる．

サイクル上量子ウォークを，背景に持つ $n$ qubitsの量子アルゴリズムやシステムは，今回の実装方法が基本になる．