What justifies using tensor product of matrices for parallel gates when applying them to an entangled state?

Question

In my university we defined tensor product of two matrices $A$, $B$ as a matrix $A \otimes B$ such that for any vectors $\left| \phi \right>$, $\left| \psi \right>$ the following is satisfied: $$ \displaystyle (A \otimes B) (\left| \phi \right> \otimes \left| \psi \right>) = (A \left| \phi \right>) \otimes (B \left| \psi \right>). $$ Imagine we have 2 qubits and we want to apply to them some gates in parallel f.e. Hadamard $H$ to $q_0$ and $X$ to $q_1$ as in image below.

I was told that in order to obtain a single 4 by 4 matrix, which applies both of these gates in parallel to a 2 qubit state vector, I have to take a tensor product $H \otimes X$. In the case when the input is in separable state and I can write it as a product of two states of single qubits, it is clear for me that the above definition of the tensor product justifies this. In our example if the state on the input is $\left| q_0 \right> \otimes \left| q_1 \right>$, we can write

$$ \displaystyle (H \otimes X) (\left| q_0 \right> \otimes \left| q_1 \right>) = (H \left| q_0 \right>) \otimes (X \left| q_1 \right>), $$ so multiplying by $H \otimes X$ is as though we were applying each of those gates to the single corresponding qubit - $H$ to $\left | q_0 \right>$ and $X$ to $\left | q_1 \right>$.

The question: Why is taking tensor product of gate matrices in order to produce appropriate matrix for parallel gates still justified when the input is in entangled state? Because we cannot write a state as a product of single qubit states, the defining property of the tensor product doesn't tell us why the product matrix is the correct one for operations in parallel.

To sum up:

1. Input is a separable state - the use of the tensor product is undeniably correct, because of its defining property

2. Input is an entangled state - why the same tensor product of matrices works for parallel gates? Does it have some meaning or is it just an extrapolation?

Answer 1

It really follows from the bi-linearity and universal property of the tensor products.

Until you learn more about the general construction of tensor products of modules, just remember that even an entangled state can be written as a sum of product states. $A \otimes B$ acts separately on each of those product states.

Say, $(A \otimes B)(\frac{1}{\sqrt 2}|00\rangle + \frac{1}{\sqrt 2}|11\rangle) = \frac{1}{\sqrt 2}(A \otimes B)|00\rangle + \frac{1}{\sqrt 2}(A \otimes B)|11\rangle$.

This material is probably covered even in chapter 2 of Nielsen and Chuang.

Those curious about the math can check this answer by Arturo Magidin.

Answer 2

One way to see it is that an arbitrary (pure) bipartite state is represented as a vector $|\psi\rangle=\sum_{ij} c_{ij} |i,j\rangle$, where $|i,j\rangle\equiv |i\rangle\otimes |j\rangle$. One can intuitively understand the two indices as corresponding to the two different "parties" involved. The states $|i\rangle$ form a basis of possible outcomes for the first system, and $|j\rangle$ do for the second one.

Imagine you want to describe a situation where the two systems, call them $A$ and $B$, are evolved independently from one another. If the input is a product state $|i,j\rangle$ then this means that we get at the output $(U_A|i\rangle)\otimes(U_B|j\rangle)\equiv (U_A\otimes U_B)|i,j\rangle$. This characterises the action of the gate on a complete input basis (because $\{|i,j\rangle\}_{ij}$ is an orthonormal basis for $H_A\otimes H_B$), and thus the overall gate is just $U_A\otimes U_B$.