[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 C4image.png Is. The quantum walk on this cycle ($ 00,01,10,11 $ (0 to 3 in decimal)) is defined below.

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.

\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 $.

\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 $.

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

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

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] $.

q[0]q[1]place(Decimal number 0~3) q[2](State 0 or 1) (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

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()

image.png

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)

image.png

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)

image.png

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.

Recommended Posts

Quantum computer implementation of quantum walk 2
Quantum computer implementation of quantum walk 3
Quantum computer implementation of quantum walk 1
Quantum computer implementation of 3-state quantum walk
Qiskit: Implementation of quantum Boltzmann machine
Qiskit: Implementation of Quantum Hypergraph States
Qiskit: Implementation of Quantum Circuit Learning (QCL)
Implementation of Fibonacci sequence
Implementation of TF-IDF using gensim
Explanation and implementation of SocialFoceModel
Implementation of game theory-Prisoner's dilemma-
Implementation of independent component analysis
Python implementation of particle filters
Implementation of quicksort in Python
Deep reinforcement learning 2 Implementation of reinforcement learning
Implementation of Scale-space for SIFT
Implementation of Bulk Update with mongo-go-driver
Read "Basics of Quantum Annealing" Day 5
Introduction and Implementation of JoCoR-Loss (CVPR2020)
Explanation and implementation of ESIM algorithm
Introduction and implementation of activation function
Python implementation of self-organizing particle filters
Summary of basic implementation by PyTorch
Implementation of a simple particle filter
Implementation of login function in Django
[Beginner] Quantum computer learning site [Free]
Implementation of life game in Python
Explanation and implementation of simple perceptron
Basics of Quantum Information Theory: Entropy (2)
Implementation of desktop notifications using Python
An implementation of ArcFace for TensorFlow
implementation of c / c ++> RingBuffer (N margins)
Python implementation of non-recursive Segment Tree
Implementation of Light CNN (Python Keras)
Qiskit: Implementation of QAOA without Qiskit Aqua
Implementation of original sorting in Python
Implementation of Dijkstra's algorithm with python
Read "Basics of Quantum Annealing" Day 6
Read "Quantum computer made in 14 days". Day 5 Quantum well improvement / addition of barriers