[PYTHON] Quantum computer implementation of quantum walk 1

Quantum computer implementation of quantum walk 1 ~ Cycle 4 Hadamard walk ~

I am a graduate student in mathematics belonging to Konno Lab., Yokohama National University, who studies quantum walks. Started studying quantum information with the members of the laboratory in 2017. Since 2018, we have also implemented it using IBM Q. Since I have accumulated notes on the implementation of quantum algorithms and quantum walks so far, I will summarize them one by one.

This time, we will implement the Hadamard walk on *** cycle 4 ***. The method introduced here is almost the same as Efficient quantum circuit implementation of quantum walks.

About Hadamard Walk on Cycle 4

Quantum walk

Quantum walk is [Quantum version of random walk](https://ja.wikipedia.org/wiki/%E9%87%8F%E5%AD%90%E3%82%A6%E3%82%A9%E3 It was introduced as% 83% BC% E3% 82% AF). The difference from the random walk is that the probability is obtained by considering the time evolution of the probability amplitude, not the time evolution of the probability, and by taking the norm square of the probability amplitude. As an explanation book of mathematics "Quantum Walk", and also summarized from mathematics to physics, engineering, and information science ["New Quantum Walk" Development ~ Deepening and application of mathematical structure ~ "](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).

We will define the model with a brief explanation. The cycle to think about this time is Is. The quantum walk on this cycle ($ 00,01,10,11 $ (0 to 3 in decimal)) is defined below.

• Quantum coin (Hadamard matrix)

U=\frac{1}{\sqrt{2}}\begin{bmatrix}
1&1 \\
1&-1  
\end{bmatrix}

here,

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}

Let.

• initial state

\Psi(0)=\frac{1}{\sqrt{2}} \begin{bmatrix}1\\i\end{bmatrix},　\Psi(1)=\Psi(2)=\Psi(3)=\begin{bmatrix}0\\0\end{bmatrix}

However, $ \ Psi (x) $ is the probability amplitude of the location $ x $.

• Time evolution *** The time evolution of the quantum walk is the time evolution of the probability amplitude. *** ***

\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}

However, since $ x + 1 and x-1 $ are on the cycle, consider $ mod4 $.

• Observation The probability is obtained by taking the norm square of the probability amplitude.

\mu(x)=\|\Psi(x)\|^2

Coin operator and shift operator

The above expression is easy to understand the dynamics, but as the dynamics of the whole system to implement $ W=\hat{S}\hat{C}\\ $ It is represented by. Each operator is shown below.

• Coin operator $ \ hat {C} $

\hat{C}=(I\otimes H)\\
\mbox{However,}I=\sum_{x}|x\rangle\langle x|,\quad H=\frac{1}{\sqrt{2}}\begin{bmatrix}
1&1\\1&-1
\end{bmatrix}

• Shift operator $ \ hat {S} $

\hat{S}=\sum_{x}|x-1\rangle\langle x|\otimes|0\rangle\langle 0|+|x+1\rangle\langle x|\otimes|1\rangle\langle 1|

Let. Also,

• initial state $\Psi=\frac{1}{\sqrt{2}}|0\rangle\otimes|0\rangle+\frac{i}{\sqrt{2}}|0\rangle\otimes|1\rangle$ Can be expressed by.

Considering the gates of the *** coin operator *** and the *** shift operator ***, the time evolution of the quantum walk can be expressed as a quantum walk.

In particular, *** Coin operator *** $ \ hat {C} = I \ otimes H $ can be expressed by passing $ H $ only through the qubit of the state. *** Shift operator *** $ \ hat {S} $ is -If the state is 0, the location $ x $ is subtracted. -If the state is 1, the place $ x $ is added. Think of a gate to do.

Implementation in IBM Q

3qubits ($ q [0] q [1] q [2] $) is used for this implementation. Consider $ q [0] q [1] $ as the qbit corresponding to the location (00,01,10,11) and $ q [2] $ as the qubit corresponding to the state.

Construction of shift operators (about cycle 4)

Although it is amakudari, the following calculation is performed for the 2-digit binary number $ q [0] q [1] $ and the state $ q [2] $.

As shown in the table, Input: $ q [0] q [1] q [2] \ Rightarrow $ Output: $ (q [0] \ oplus \ overline {q [1]} \ oplus q [2]) (\ When combined with overline {q [1]}) (q [2]) $, it is subtracted if the state is `0```, and added if the state is `1```, and it becomes a shift operator. It corresponds. This input / output should be implemented in a quantum circuit.

Creation of circuit part

Quantum register, classical register, and set quantum circuit qwqc from them

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)

Time evolution part

#Time evolution
t=1

#Set the initial state
qwqc.h(q[2])
qwqc.s(q[2])

#Time evolution
for i in range(t):
    #Coin operator
    qwqc.h(q[2])
    #Shift operator
    qwqc.x(q[1])
    qwqc.cx(q[2],q[0])
    qwqc.cx(q[1],q[0])
#place(q[0]q[1])Observed state (q[2]) Is not observed
qwqc.measure(q[0],c[0])
qwqc.measure(q[1],c[1])

#Circuit drawing
qwqc.draw()

Simulator results at t = 1

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)

Theoretically

\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}

Than

\mu(1)=\mu(3)=\frac{1}{2}

It becomes. Since it is a simulator, the result was reasonable.

Results of the actual machine at t = 1

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)

Summary

The Hadamard walk on cycle 4 has a relatively simple circuit and time evolution t = 1, so it may be said that errors are not accumulated so much.

Also, if the Hadamard matrix $ H $ of the coin operator is replaced with another unitary matrix $ U $, it becomes a quantum walk of another spatially uniform quantum coin. With IBM Q, you can make your favorite quantum coin with $ U_3 (\ theta, \ phi, \ lambda) $.

In the future, I would like to summarize other cycles, other graphs, multi-state numbers models, and spatial-temporal non-uniform models in sequence. I would also like to summarize the algorithm using the quantum walk.