Now, in order to implement it with a quantum computer, it must be a finite system, not an infinite system such as one dimension, so we will implement a three-state Grover Walk on the cycle. The whole time evolution

W=\hat{S}\hat{C}

Let. Since we are considering a three-state Grover Walk, the $ 3 \ times3 $ Grover matrix is added to the shift operator $ \ hat {C} $.

\hat{C}=I\otimes C\\
\mbox{However}C=\frac{2}{3}\begin{bmatrix}1&1&1\\1&1&1\\1&1&1\end{bmatrix}-I=\frac{1}{3}\begin{bmatrix}-1&2&2\\2&-1&2\\2&2&-1\end{bmatrix}

Is adopted. The shift operator considers three states (00,01,10) on the cycle.

\hat{S}=\sum_{x}(|x-1\rangle\langle x|\otimes|00\rangle \langle 00|+|x\rangle\langle x|\otimes|01\rangle \langle 01|+|x+1\rangle\langle x|\otimes|10\rangle \langle 10|)

Let.

• If the status is 00, location-1,
• Stay in place if the status is 01
• Location +1 when state is 10 I am doing.

Think about the circuit

If two qubits are used to implement state 3, there will be four states, 00,01,10,11. Therefore, the coin operator and shift operator are converted into the four-state notation.

Coin operator

\hat{C}=I\otimes C\\
\mbox{However}C=\begin{bmatrix}\frac{-1}{3}&\frac{2}{3}&\frac{2}{3}&0\\\frac{2}{3}&\frac{-1}{3}&\frac{2}{3}&0\\\frac{2}{3}&\frac{2}{3}&\frac{-1}{3}&0\\0&0&0&1\end{bmatrix}

Shift operator

\hat{S}=\sum_{x}(|x-1\rangle\langle x|\otimes|00\rangle \langle 00|+|x\rangle\langle x|\otimes|01\rangle \langle 01|+|x+1\rangle\langle x|\otimes|10\rangle \langle 10|+|x\rangle\langle x|\otimes |11\rangle\langle 11|)

By taking this way, it is possible to create an independent state 11 that is not mixed with other states. Therefore, if state 11 is not given to the initial state, it is an implementation of a three-state quantum walk.

Circuit creation

Grover matrix

Create a $ 3 \ times 3 $ Grover matrix inside the $ 4 \ times 4 $ matrix. Here, only the result of examining the parameters by calculation is introduced.

import numpy as np
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister
from qiskit import execute
import math

th1=3*math.pi/2
th2=(math.pi+math.acos(1/3))*2
th3=math.pi/2

q = QuantumRegister(2, 'q')

grqc = QuantumCircuit(q)
grqc.x(q[0])
grqc.x(q[1])
grqc.cu3(th3,0,0,q[0],q[1])
grqc.cu3(th2,0,0,q[1],q[0])
grqc.cu3(th1,0,0,q[0],q[1])
grqc.x(q[0])
grqc.x(q[1])

If you make a gate like this, you will get $ 3 \ times 3 $ Grover coins in $ 4 \ times 4 $. Check below.

from qiskit import BasicAer

#Run with unitary simulator backend
backend = BasicAer.get_backend('unitary_simulator')
job = execute(grqc, backend)
result = job.result()

# Show the results
print(result.get_unitary(grqc, decimals=3))

[[-0.333+0.j 0.667+0.j 0.667+0.j 0. +0.j] [ 0.667+0.j -0.333+0.j 0.667+0.j 0. +0.j] [ 0.667+0.j 0.667+0.j -0.333+0.j 0. +0.j] [ 0. +0.j 0. +0.j 0. +0.j 1. +0.j]]

Circuit mounting

Consider quantum registers, classical registers, and quantum circuits from them.

• Location qbits $ \ Rightarrow q [0] q [1] $
• State qbits $ \ Rightarrow qc [0] qc [1] $
• Spare qbits $ \ Rightarrow qaf [0] $ Consider the circuit as. The basic idea of the $ \ pm 1 $ operation of the place is based on Quantum computer implementation 2 of quantum walk.

def cccx(circ,c1,c2,c3,tg,re):
    circ.ccx(c1,c2,re)
    circ.ccx(c3,re,tg)
    circ.ccx(c1,c2,re)

I want to use the cccnot gate, so when I prepare it, I make a circuit.

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

q = QuantumRegister(2, 'q')
qc = QuantumRegister(2, 'qc')
qaf = QuantumRegister(1,'qaf')
c = ClassicalRegister(2, 'c')

gqc = QuantumCircuit(q,qc,qaf,c)

th1=3*math.pi/2
th2=(math.pi+math.acos(1/3))*2
th3=math.pi/2

#time
t=1

#Set the initial state
gqc.x(qc[1])
gqc.barrier()
#Time evolution
for i in range(t):
    #coin-ope
    gqc.x(qc[0])
    gqc.x(qc[1])
    gqc.cu3(th3,0,0,qc[0],qc[1])
    gqc.cu3(th2,0,0,qc[1],qc[0])
    gqc.cu3(th1,0,0,qc[0],qc[1])
    gqc.x(qc[0])
    gqc.x(qc[1])
    gqc.barrier()
    #shift-ope cycle
    gqc.x(qc[1])
    cccx(gqc,q[1],qc[0],qc[1],q[0],qaf[0])
    gqc.ccx(qc[0],qc[1],q[1])
    gqc.x(qc[1])
    gqc.x(qc[0])
    gqc.x(qc[1])
    gqc.ccx(qc[0],qc[1],q[1])
    cccx(gqc,q[1],qc[0],qc[1],q[0],qaf[0])
    gqc.x(qc[0])
    gqc.x(qc[1])
    gqc.barrier()
    
#Observation
gqc.measure(q,c)

gqc.draw()

In the first part, the initial state is created. This time

\Psi=|00\rangle\otimes|01\rangle

make. The second part is the state part *** coin operator ***. The third part expresses the *** shift operator *** that "place +1 for state 10, place -1 for state 00, and place does not change for states 01 and 11".

Execute the above in the simulator.

provider=IBMQ.get_provider(group='open')
backend_cs=provider.get_backend('ibmq_qasm_simulator')
job_cs = execute(gqc, backend_cs,shots=4096)
result_cs = job_cs.result()
counts_cs = result_cs.get_counts(gqc)
print(counts_cs)
plot_histogram(counts_cs)

The result of this simulation is

\hat{S}\hat{C}|00\rangle\otimes|01\rangle\\
=\hat{S}\left\{|00\rangle\otimes\frac{2}{3}|00\rangle+|00\rangle\otimes\frac{-1}{3}|01\rangle+|00\rangle\otimes\frac{2}{3}|10\rangle\right\}\\
=\frac{2}{3}|11\rangle\otimes|00\rangle+\frac{-1}{3}|00\rangle\otimes|01\rangle+\frac{2}{3}|01\rangle\otimes|10\rangle

Therefore, the observation probabilities of the locations $ 11 $, $ 00 $, and $ 01 $ are $ \ frac {4} {9} $, $ \ frac {1} {9} $, and $ \ frac {4} {9} $, respectively. It should be, so you can see that the simulation was successful.

Supplement

Quantum walks on arbitrary graphs can be implemented by increasing the number of states and creating corresponding coin operators and shift operators. A 4-state quantum walk on a torus can be created by a simple application of a 2-state quantum walk on a cycle.

The retention term near the origin of Grover one-dimensionally introduced at the beginning can be confirmed by experiments on the cycle of the quantum computer when it is developed to about time 7 in cycle 16.