Quantum circuit implementation of shift operator in quantum walk

Question

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 :

\begin{equation} 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\,. \end{equation}

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

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