Quantum circuit implementation of shift operator in quantum walk

I'm considering discrete-time quantum walk on $$2\times2$$ grid with periodic quantum walk. In particular focus on shift operator which has the form :

$$$$S|i,j\rangle \otimes |x,y\rangle =|1-i,1-j\rangle \otimes |x+(-1)^i \delta_{ij},y+(-1)^j (1-\delta_{ij})\rangle\,.$$$$

In this case, If the position space qubits are $$|00\rangle,|01\rangle ,|10\rangle ,|11\rangle$$ where the first qubit stands for $$x$$-direction and second qubit stands for $$y$$-direction. We can write shift operator

$$S = (|11\rangle\langle 00| + |00\rangle \langle 11|)\otimes \sigma_x\otimes I + (|01\rangle\langle 10| + |10\rangle\langle 01|)\otimes I\otimes \sigma_x$$

Can you help me in constructing a circuit for such an operator? If it were usual shift operator in which there are term of kind $$|00\rangle\langle 00|$$ in coin space then it would be straight forward with control operator, but I'm not sure how to go about this.

Edit : I able to implement this but I'm not having problem with shift operator with open boundary condition.

In this case, the shift operator has explicit form

$$S = |11\rangle \langle 00| \otimes |1\rangle \langle 0|\otimes I + |00\rangle \langle 11|\otimes |0\rangle \langle 1|\otimes I + |00\rangle \langle 00|\otimes |0\rangle \langle 0| \otimes I + |11\rangle \langle 11|\otimes |1\rangle \langle 1|\otimes I + |10\rangle \langle 01|\otimes I \otimes |1\rangle \langle 0|+ |01\rangle \langle 10|\otimes I \otimes |0\rangle\langle 1| + |10\rangle \langle 10|\otimes I \otimes |1\rangle\langle 1| + |01\rangle \langle 01|\otimes I \otimes |0\rangle \langle 0|$$

Or,

$$|000i\rangle \rightarrow |111i\rangle \ \ \ |111i\rangle \rightarrow |000i\rangle \ \ \ |01i0\rangle \rightarrow |10i1\rangle \ \ \ |10i1\rangle \rightarrow |01i0\rangle$$ and all other goes to itself. Here $$i = 0,1$$.

Once you have some operator form, one method is just to start multiplying it by unitary operators (pre- or post- or both, doesn't matter) until you can make it into identity. For example, maybe you can eventually find $$USV=I$$. Then you can just apply the inverse sequences to find $$S=U^\dagger V^\dagger$$.
In this particular case, my inclination would by to try and make the operation diagonal on the first two qubits to start with. For example, $$(X\otimes X\otimes I\otimes I)S=(|00\rangle\langle 00|+|11\rangle\langle 11|)\otimes X\otimes I+(|01\rangle\langle 01|+|10\rangle\langle 10|)\otimes I\otimes X$$ Now think about what this says: "if the first two qubits are the same, do $$X\otimes I$$. If they're different, do $$I\otimes X$$". I could just as easily say "Always do X\otimes I. Then, if the two qubits are different, do $$X\otimes X$$". This is a very easy circuit to implement: if you have two controls and one target, doing a controlled-not off each of the controls onto the target, then that does $$X$$ on the target only if the two qubits are different.
So, let $$C^i_j$$ denote controlled-not with control $$i$$ and target $$j$$. You now have $$(X\otimes X\otimes X\otimes I)S=C^1_3C^1_4C^2_3C^2_4.$$ That should give you your circuit for the first case you ask about.
For your second operator, I'd write that to start with as $$S=(|000\rangle+|111\rangle)(\langle 000|+\langle 111|)_{123}\otimes I_4+(|010\rangle+|101\rangle)(\langle 010|+\langle 101|)_{124}\otimes I_3.$$ Here, the most annoying thing is the different qubit ordering between the two terms. If you co $$c^1-SWAP_{34}\cdot c^2-SWAP_{34}$$, this will just swap qubits 3 and 4 in the second term (where the first two qubits are different). From there, notice that the first 3 qubits are in GHZ-like states, so run the inverse of a circuit for creating GHZ states.
• If you have a circuit $U$ such that $U|000\rangle=(|000\rangle+|111\rangle)/\sqrt{2}$, then run $U^\dagger$. Oct 10, 2023 at 11:54
• But Isn't $UU^\dagger = I$? Oct 10, 2023 at 14:27
• Yes. So what? I'm not saying run $U$ then run $U^\dagger$. I'm saying "use this to identify what $U$ is, but run \$U^\dagger". Oct 11, 2023 at 7:04