# Why, in a discrete-time quantum walk,we first apply the tensor product of the coin operation with the identity?

When we apply coin step in the quantum walk, for example considering the H gate, we first do it's tensor product with Identity vector of the position Hilbert space. Why is this so? Please see below statement for more details:

You started with the state $$|\psi \rangle = |0\rangle \otimes |0\rangle$$ which belongs to the space $$\mathbb{C}^2 \otimes \mathbb{C}^2$$. To operate state on this space, your operator must also have the same dimension. Thus, you need to have $$H \otimes I$$ and not just $$H$$ if you want to operate the Hadamard gate $$H$$ on the first qubit. Operations on qubits are just matrix multiplication after all so you need to make sure you have the correct dimensionality. In this case, $$H \otimes I$$ does that. It makes sure you have the right dimension along with doing exactly what you were looking to do, by applying $$H$$ to the first qubit and leave the second qubit alone.

To be more explicit, we have the state $$|00\rangle = \begin{pmatrix} 1 \\0 \\ 0 \\ 0 \end{pmatrix}$$. The Hadamard gate, $$H$$, can be written in the computational basis as $$H = \dfrac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$$. We can't apply $$H$$ to the state $$|00\rangle$$ directly, since the there is a mismatched in the dimensionality. However, $$H \otimes I = \dfrac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix} \otimes \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = \dfrac{1}{\sqrt{2}}\begin{pmatrix} 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1\\ 1 & 0 & -1 & 0\\ 0 & 1 & 0 & -1\end{pmatrix}$$ Now they have the same dimension, and if you apply this to the state $$|00\rangle$$, we have

\begin{align} (H\otimes I) (|0\rangle \otimes |0\rangle) &= \dfrac{1}{\sqrt{2}}\begin{pmatrix} 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1\\ 1 & 0 & -1 & 0\\ 0 & 1 & 0 & -1\end{pmatrix} \begin{pmatrix} 1 \\0 \\ 0 \\ 0 \end{pmatrix} = \dfrac{1}{\sqrt{2}} \begin{pmatrix} 1 \\0 \\ 1 \\ 0 \end{pmatrix} \\ &= \dfrac{1}{\sqrt{2}} \begin{pmatrix} 1 \\ 1 \end{pmatrix} \otimes \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \dfrac{|0\rangle + |1 \rangle}{\sqrt{2}}\otimes|0\rangle \end{align}

Now, the above is the explicit way of writing out the operation in matrix form but as you can see, it is cumbersome and a lot more work than necessary. So often, we use the linear mapping property of tensor product, which tells us that $$(H\otimes I) (|0\rangle \otimes |0\rangle) = H \big(|0\rangle \big) \otimes I \big( |0\rangle \big) = \dfrac{|0\rangle + |1 \rangle}{\sqrt{2}} \otimes |0\rangle$$

• Thanks for your explanation. – Binshumesh sachan Nov 5 '20 at 18:14
• In your explanation, you have choosen the Identity matrix of 2*2. But if we have k-dimensional vector, what would be the size of Identity matrix? – Binshumesh sachan Nov 8 '20 at 15:32
• The size of the Idenity matrix will be $2^{k-1} \times 2^{k-1}$ then. Notice how it always in the power of 2. – KAJ226 Nov 8 '20 at 23:18

A (discrete-time) quantum walk can be thought of as the direct "quantization" of a classical random walk.

In a classical random walk, at each iteration, you flip a coin and move the walker in a direction conditionally to the result of the coin flip.

The quantum generalisation of this is to think of the "coin" as a "coin state", that is, a qubit, and to make the "coin flip" into a similarly unbiased quantum gate (although one can generalises this to allow for arbitrary quantum gates as coin operations).

The "coin operation" gate must therefore, by conception, be an operation that only affects the coin space. In your notation, a state such as $$|0\rangle\otimes|0\rangle$$ lives in the coin+walker space, with the first space being the coin space. It follows that to act locally on the coin space amounts to perform a local operation of the form $$U\otimes I$$.

The idea is that by applying Hadamard just to the coin and doing nothing to the position state, this is the equivalent of tossing the coin.

To see this in a very crude way, imagine applying Hadamard to a qubit in the state $$|0\rangle$$. You get a state $$(|0\rangle+|1\rangle)/\sqrt{2}$$ which, if we were to measure it, would be equivalent to a coin giving heads or tails with 50:50 probability.

The shift operator then says "depending on whether the coin is in heads or tails, update the position register appropriately".