How to know if a given 2-qubit gate is separable into two single-qubit gates?

Question

This question seems fairly trivial but I'm struggling to find an elegant way to determine such. Suppose that you have a unitary matrix $U$ (not necessarily a density matrix) and you want to know if $U=U_1\otimes U_2$, for a given $U_1$ and $U_2$. This question is not trivial in the sense that if it was easy to determine such for any dimension of $U,U_1$ and $U_2$, then it would be easy to know if a density matrix is separable, nevertheless it remains as an NP-hard problem.

However, for the case where $U$ is a two qubit gate it should be relatively simple. Is there a criteria I could use to show if $U$ (4x4) is is separable into two single-qubit gates?

The only thing I could get is to diagonalize $U$ and check if there are some common factors.

Answer 1

This is relatively straightforward to do in practice. Remember that if $U$ has the structure you want, it has a block-matrix form (change to whatever size you want) $$ U=\left(\begin{array}{cccc} U^1_{00}U^2 & U^1_{01}U^2 & U^1_{02}U^2 & U^1_{03}U^2 \\ U^1_{10}U^2 & U^1_{11}U^2 & U^1_{12}U^2 & U^1_{13}U^2 \\ U^1_{20}U^2 & U^1_{21}U^2 & U^1_{22}U^2 & U^1_{23}U^2 \\ U^1_{30}U^2 & U^1_{31}U^2 & U^1_{32}U^2 & U^1_{33}U^2 \\ \end{array}\right). $$ So, all you have to do is look at $U$ and extract each block, and ask if they are all identical up to a scale factor for each block. If yes, then the matrix has the desired decomposition, otherwise not.

Notation: target decomposition is $U=U^1\otimes U^2$. Matrix $U^1$ has matrix elements $U^1_{ij}$.

A more procedural version. Let $U$ be $d^2\times d^2$ where we're expecting each matrix to be $d\times d$.

• Look at the top-left $d\times d$ block. Do all of the rows and columns have the same sum mod-square? No: $U$ not separable. Yes: Let $U^2$ be that block, renormalised so that sum-mod square of all rows and columns is 1.
• Calculate $U^1=\text{Tr}_2\left((I\otimes U^2)\cdot U\right)/d$
• Compare $U^1\otimes U^2$ to $U$. If equal, $U$ was separable. If not, $U$ was not separable.