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


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


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.

  • $\begingroup$ In the last paragraph, what do you mean by the inverse of a circuit? $\endgroup$ Oct 10, 2023 at 11:50
  • $\begingroup$ If you have a circuit $U$ such that $U|000\rangle=(|000\rangle+|111\rangle)/\sqrt{2}$, then run $U^\dagger$. $\endgroup$
    – DaftWullie
    Oct 10, 2023 at 11:54
  • $\begingroup$ But Isn't $UU^\dagger = I$? $\endgroup$ Oct 10, 2023 at 14:27
  • 1
    $\begingroup$ 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". $\endgroup$
    – DaftWullie
    Oct 11, 2023 at 7:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.