I was reading this tutorial about discrete random walk and got confused by the following paragraph.

enter image description here

After the succession of Hadamard applications ($H$), I wonder how do we get skewed distribution. I can understand this could happen with noise or erroneous $H$ operation. If the Hadamard operation is perfect, then it would produce the equal split and yield the classical behavior, no?



2 Answers 2


You get a skewed distribution because you start with a "skewed" coin state (I'm assuming the system you are considering starts with the walker state in a single fixed state).

In fact, you can verify that the asymmetry of the output distribution depends on the choice of initial coin state. If the initial coin state is for example $|0\rangle+i|1\rangle$, then you get a symmetric distribution.

This might be a bit of an overkill here, but there is actually a nice way to write the transition amplitudes corresponding to an arbitrary $n$-steps discrete-time quantum walk. Suppose the initial state has the form $|i,s\rangle$, with $|i\rangle$ the initial walker state and $|s\rangle$ the initial coin state, and we want to know the probability amplitude of ending up with the state $|j,t\rangle$ after $n\ge1$ steps. Assume that $s,t\in\{0,1\}$ (we don't lose much with this assumption: if the initial or final coin states are superpositions of computational basis ones, we can go back to this case by changing the description of the coin operations).

Denote with $\mathcal W\equiv \mathcal S\mathcal C$ the walk operator, where $\mathcal S$ and $\mathcal C$ are the controlled-shit and coin operation, respectively. Denote with $u_{ss'}$ the matrix elements of the coin matrix (in your case, these would be the matrix elements of the Hadamard matrix). We then have $$\langle j,t|\mathcal W^n|i,s\rangle = %\sum_I \prod_{\ell=1}^n u_{I_\ell} \equiv \sum_I u_{I} \equiv u_{I_1 I_2} u_{I_3 I_4} \cdots u_{I_{2n-1}I_{2n}},$$ where the short-hand notation $u_I$ denotes the product of matrix elements $u_{\alpha\beta}$ with the indices taken progressively from the $2n$-bit string $I$ (this is way easier to understand in practice than to explain in full generality, I'll give an example in a bit). The sum is taken over all binary strings $I$ of length $2n$ such that

  1. $I_1\equiv t, I_{2n}=s$;
  2. denote with $\tilde I$ the elements of $I$ obtained removing the extremal ones (e.g. if $I=(011001)$ then $\tilde I=(1100)$). Then $\tilde I$ must be made up of pairs of equal elements. For example, you can have $\tilde I=(1111)$ and $\tilde I=(1100)$, but not $\tilde I=(1101)$;
  3. the number of $1$s in $I$ is related to the initial and final positions $i$ and $j$. More precisely, $j-i=\sharp_1-\sharp_0+\delta_{I_1,1}-\delta_{I_1,0}$, where $\sharp_p\equiv\sharp_p(\tilde I)$ is the number of elements of $\tilde I$ which equal $p\in\{0,1\}$.

While these rules appear rather convoluted, they can be used to directly compute input/output probability amplitudes quite easily. For example, consider the case of three steps, and assume the initial state to be $|0,0\rangle\equiv |0,\uparrow\rangle$. Then (some of) the output probability amplitude $3$ steps corresponds to the tuples (and therefore amplitudes) $$|-3,0\rangle \to (000000) \simeq u_{00} u_{00} u_{00}, \\ |+3,1\rangle \to (111110) \simeq u_{11} u_{11} u_{10}, \\ |+1,0\rangle \to (011110) \simeq u_{01} u_{11} u_{10}, \\ |+1,1\rangle \to (100110),(111000) \simeq u_{10} u_{01} u_{10} + u_{11} u_{10} u_{00}, \\ |-1,0\rangle \to (011000), (000110) \simeq u_{01} u_{10} u_{00} + u_{00} u_{01} u_{10}, \\ |-1,1\rangle \to (100000) \simeq u_{10} u_{00} u_{00}.$$

Now, for the Hadamard walk you have $u_{ij}\equiv H_{ij}=\frac{1}{\sqrt2}(-1)^{ij}$, and therefore the probability amplitudes are clearly asymmetric: we have (up to $2^{-3/2}$ constant factors) $$|-3,0\rangle \to 1, \qquad |+3,1\rangle \to 1, \\ |+1,0\rangle \to -1, \qquad |+1,1\rangle \to 0, \qquad |-1,0\rangle \to 2,\qquad |-1,1\rangle \to 1.$$

  • $\begingroup$ thank you for the detailed explanation. I am a bit slow at picking up 1, 2, 3 points above. the bit string is 2^n or 2^n+1? Excluding the coin bit then 2^n I think looking at the explanation further. As for 2, could you elaborate why "I~ must be made up of pairs of equal elements"? $\endgroup$ Jun 21, 2021 at 19:28
  • $\begingroup$ @JohnParker it means that if you take pairs of elements from it sequentially from the left, you will only encounted identical values in pairs. So 1111 is fine, 1100 is fine, 0011 is fine, but 1000 is not fine. Really, these rules seem complicated when stated like this, but if you try writing down explicitly the amplitudes after two or three steps for a generic coin operation, I think you'll see how they arise much more clearly. You can also probably ignore all of this for the purpose of the question itself $\endgroup$
    – glS
    Jun 21, 2021 at 21:07

I did the math for the first three steps when the coin qubit is initialized to $|\uparrow\rangle$ using the link @Mark S commented. We use as the coin flip operator the Hadamard gate, and the conditional shift operator is given by

$$ S = |\uparrow\rangle\langle\uparrow| \otimes \sum_i |i+1\rangle\langle i| + |\downarrow\rangle\langle\downarrow|\otimes\sum_i|i-1\rangle\langle i |. $$

Our inital state is $|\uparrow\rangle|0\rangle$. Applying the Hadamard gate we get $\frac{1}{\sqrt{2}}(|\uparrow\rangle + |\downarrow\rangle)|0\rangle$. And applying $ S$ we get $\frac{1}{\sqrt{2}}(|\uparrow\rangle|1\rangle + |\downarrow\rangle|-1\rangle)$. That's our final state after a single time step.

Now the second step. Applying $H$ we get

$$ \frac{1}{2}((|\uparrow\rangle+|\downarrow\rangle)|1\rangle + (|\uparrow\rangle-|\downarrow\rangle)|-1\rangle). $$

Then we apply $S$ and get

$$ \frac{1}{2}(|\uparrow\rangle|2\rangle + |\downarrow\rangle|0\rangle + |\uparrow\rangle|0\rangle - |\downarrow\rangle|-2\rangle). $$

Here you can see that being in position $2$ has a probability of $1/4$, $0$ has $1/2$, and $-1$ has $1/4$. You can start to see some bias to the center-right. Let's apply another step.

First the $H$ gate takes us to

$$ \begin{align} &\frac{1}{2\sqrt{2}}((|\uparrow\rangle + |\downarrow\rangle)|2\rangle + (|\uparrow\rangle - |\downarrow\rangle)|0\rangle + (|\uparrow\rangle + |\downarrow\rangle)|0\rangle - (|\uparrow\rangle - |\downarrow\rangle)|-2\rangle) \\ &= \frac{1}{2\sqrt{2}}((|\uparrow\rangle + |\downarrow\rangle)|2\rangle + 2|\uparrow\rangle|0\rangle - (|\uparrow\rangle - |\downarrow\rangle)|-2\rangle). \end{align} $$

You can see that interference in the step above helped cancel a state where the position vector was $0$ and the coin vector was $|\downarrow\rangle$. It removed a coin vector that would take the position vector to the left, leaving more coin vectors that take the position to the right. Here you can see how the bias is getting stronger for the right. Applying $S$ takes us to

$$ \begin{align} &\frac{1}{2\sqrt{2}}(|\uparrow\rangle|3\rangle + |\downarrow\rangle|1\rangle + 2|\uparrow\rangle|1\rangle - |\uparrow\rangle|-1\rangle + |\downarrow\rangle|-3\rangle) \\ &= \frac{1}{2\sqrt{2}}(|\uparrow\rangle|3\rangle + (|\downarrow\rangle + 2|\uparrow\rangle)|1\rangle - |\uparrow\rangle|-1\rangle + |\downarrow\rangle|-3\rangle). \end{align} $$

In this state, the probability of being in position $3$ is $1/8$, for $1$ it's $5/8$, and for $-1$ and $-3$ it's also $1/8$. The bias to the right is very clear now, and applying more steps will make it even clearer.

You can apply the same procedure with the coin qubit initialized to $|\downarrow\rangle$ and you will see bias to the left show up after a few steps like above.


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.