Is there an algorithm for determining if a given vector is separable or entangled?

Question

I'm trying to understand if there is some sort of formula or procedural way to determine if a vector is separable or entangled, i.e., whether or not a vector of size $mn$ could be represented by the tensor product of two vectors of size $m,n$, respectively.

For example, I understand that the following 9-dimensional vector is separable because it can be represented as a tensor product of two 3-dimensional vectors:

\begin{equation} \begin{pmatrix} 0 \\ \frac{1}{2} \\ \frac{1}{2} \\ 0 \\ 0 \\ 0 \\ 0 \\ \frac{1}{2} \\ \frac{1}{2} \\ \end{pmatrix} = \begin{pmatrix} \frac{1}{\sqrt{2}} \\ 0 \\ \frac{1}{\sqrt{2}} \\ \end{pmatrix} \otimes \begin{pmatrix} 0 \\ \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \\ \end{pmatrix} \end{equation}

Whereas the following 9-dimensional vector can't be represented as the tensor product of two 3-dimensional vectors:

\begin{equation} \begin{pmatrix} \frac{1}{2} \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ \frac{1}{2} \\ \end{pmatrix} \neq \begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ \end{pmatrix} \otimes \begin{pmatrix} b_0 \\ b_1 \\ b_2 \\ \end{pmatrix} \end{equation}

So I'm looking for a computational way of determining if a vector is separable or entangled. Thanks for your help! Let me know if I can clarify anything.

Answer 1

Imagine you have a vector that can be written in the form $$ |\psi\rangle=\sum_{i=0}^{d_A-1}\sum_{j=0}^{d_B-1}c_{ij}|i\rangle|j\rangle. $$ The coefficients can be arranged as a $d_A\times d_B$ matrix $C$, with the elements $c_{ij}$ (in your special case, you're talking about setting $d_A=d_B=\sqrt{m}$).

Now, if you calculate $\rho_A=CC^\dagger$, this is known as the reduced density matrix of subsystem $A$. If the state $|\psi\rangle$ is separable, then $\rho_A$ corresponds to a pure state. Otherwise, it is mixed. Separability can be detected using a quantity known as the mixedness, effectively the condition $\text{Tr}(\rho_A^2)=1$. If $|\psi\rangle$ is not separable (i.e. $\rho_A$ is mixed), it is entangled.

Answer 2

Here is a possible, though expensive, way. First, find all prime factors of the dimension d of your vector. In your example, the dimension is 9, and the only prime factor is 3. Next for each prime factor $p$, try a tensor product of a vector of dimension p and another vector of dimension $d/p$. Then you need to solve $d$ quadratic equations with $p+d/p$ variables to ensure the tensor product holds, you also need two additional quadratic equations to ensure unit vectors.

When your vectors are sparse, i.e., with lots of zeros, it might be easy to trace out variables that must be zero first. In your second example, $a_0, b_0$ cannot be zero due to $a_0 b_0=\frac{1}{2}$, so $b_1=b_2=0$ to satisfy the second and third entries. Later when considering the last entry, you will find $b_2$ cannot be zero, hence there is no solution. In your first example, you can determine the two zero entries and solve the rest by solving the equations.