# What is the minimum number of separable pure states needed to decompose arbitrary separable states?

Consider a separable state $\rho$ living in a tensor product space $\mathcal H\otimes\mathcal H'$, with $\mathcal H$ and $\mathcal H'$ of dimensions $D$ and $D'$, respectively. If $\rho$ is separable, then it is by definition possible to write it as a convex combination of (projectors over) separable pure states.

Because a state is Hermitian and positive by definition, we can trivially always write it in terms of its eigenvectors and eigenvalues as $$\rho = \sum_{k=1}^{D^{} D^\prime} \lambda_k |\psi_k\rangle\langle\psi_k|, \quad p_k\ge0,$$ where $\rho|\psi_k\rangle=\lambda_k|\psi_k\rangle$. However, $|\psi_k\rangle$ will in general be non-separable states.

What I am looking for is the decomposition of $\rho$ in terms of only separable states. For example, a trivial case is $\rho=\mathbb 1/DD'$, which is easily seen to be decomposable as $$\frac{1}{DD'}\mathbb 1=\frac{1}{DD'}\sum_{k=1}^D\sum_{l=1}^{D'}|k,l\rangle\langle k,l|.$$ This shows that, to decompose an unknown state $\rho$ in terms of separable states, at least $DD'$ elements are required. Is this number sufficient for any separable $\rho$?

In other words, what I'm looking for is the smallest $M$ such that a representation of the form $$\rho = \sum_{j=1}^M p_j \,|\alpha_j\rangle\langle\alpha_j|\otimes|\beta_j\rangle\langle\beta_j|$$ holds for all separable $\rho$. More formally, this is the problem of finding $$\min\left\{M\,:\,\,\forall\rho\exists\{p_k\}_k,\{|\alpha_k\rangle\}_k,\{|\beta_k\rangle\}\,:\,\rho=\sum_{j=1}^M p_j \,|\alpha_j\rangle\langle\alpha_j|\otimes|\beta_j\rangle\langle\beta_j|\right\}.$$

• I'm pretty sure this is a special version of a more general standard result, namely the maximum number of states needed to minimize the entanglement of formation (here for EoF=0). Unfortunately, I couldn't find a reference. I think I can prove $D^2D'$ as a bound, but I have doubts whether this is optimal. It might also depend on whether one insists on pure states in the decomposition. – Norbert Schuch Apr 20 '18 at 20:01

First of all, your problem is a special version of a more general problem, namely finding the minimum number of states which minimize the entanglement of formation, this is, given a state $$\rho$$ on AB$$\equiv \mathbb C^D\otimes \mathbb C^{D'}$$, find the decomposition $$\rho = \sum_{i=1}^m p_i |\psi_i\rangle\langle\psi_i|$$ which minimizes $$\sum_i p_i E(|\psi_i\rangle)$$, where $$E(|\psi_i\rangle) = S(\mathrm{tr}_B(|\psi_i\rangle\langle\psi_i|)$$, and find the minimum $$m$$ for which such a decomposition exists.

Your problem is just the variant of this where the state has entanglement of formation zero.

This is a well-studied problem and in turn a special case of a so-called "convex roof construction". Uhlmann, for instance, states that for any such problem, at most $$(DD')^2+1$$ states are needed for the optimal decomposition (Proposition 2.1).

It is likely that better bounds exist for the special problem of entanglement of formation, or the given problem of separable states. I was unable to find any in the literature, but one should be able to prove one along the following lines:

1. First, note that one can relax the optimization to all decompositions $$\rho=\sum p_i\rho_i\,\tag{1}$$ where one minimizes $$\sum p_i S(\mathrm{tr}_B\rho_i)$$, since the entropy is concave, i.e. the minimium will always be (also) attained on pure $$\rho_i$$.

2. Thus, we can instead consider decompositions of the reduced density matrix $$\rho^A = \sum p_i \rho_i^A$$ -- any such decomposition arises from a decomposition (1) of $$\rho$$ (e.g. by writing $$p_i\rho_i^A$$ as $$M_k\rho M_k^\dagger$$ with a POVM $$M_k$$ and applying $$M_k\otimes I$$ to $$\rho$$).

3. Now consider an optimal decomposition $$\rho^A = \sum p_i \rho_i^A$$. If it has more than $$D^2$$ terms, the $$\rho_i^A$$ must be linearly dependent. Thus, we can decrease the weight of some $$\rho_j^A$$ all the way down to zero by shifting the weights of all the other $$\rho_i^A$$ (keeping $$p_i\ge0$$!). Again, due to concavity, this will not change the average entanglement.

4. We are now left with an optimal decomposition $$\rho^A=\sum p_i\rho^A_i$$ with $$D^2$$ terms. This yields a decomposition of $$\rho$$, $$\rho=\sum p_i \rho_i$$, which minimizes $$\sum p_i S(\rho_i^A)$$ (as described in 2.). We can now decompose each $$\rho_i$$ in their eigenbasis (which has at most $$DD'$$ terms), which yields a total of $$D^3D'$$ terms.

5. There is likely space for improvement: For instance, one could rewrite each of the $$\rho_i^A$$ in a basis of pure states $$|\phi_{k,i}\rangle\langle\phi_{k,i}|$$. Such a basis has size at most $$D^2+1$$ ($$D^2$$ being the dimension of the convex space), and the coefficients are $$\mathrm{tr}(\rho_i^A|\phi_k\rangle\langle\phi_k|)$$ and thus positive. Again, convexity yields an optimal decomposition with pure $$\rho_i^A$$ and $$D^2$$ terms. It only remains to decompose the corresponding $$\rho_i^B$$, which results in a total of $$(D^2+1)D'$$ terms.

• Very interesting, thanks. I think I also just found the solution though. In the review of entanglement of the Horodeckis, in section VI, they state that in the case of finite-dimensional systems, it follows from Caratheodory theorem that the number in the convex combination can be bounded by the square of the total dimension of the Hilbert space. See bottom of pag 20 of quant-ph/9707035. – glS Apr 25 '18 at 14:43
• @glS Well, that's what Uhlmann says. (Though Cartheodory gives DIM^2+1, which is what Uhlmann says.) -- Nevertheless, I think my argument gives a better bound for separable states. – Norbert Schuch Apr 25 '18 at 15:06
• @Schuch In your fourth bullet, are you saying any separable state has a decomposition $\rho = \sum_i \rho_i^A \otimes \rho_i^B$ with at most $\dim(A)^2$ terms? If so, I don't think that can be right: for instance, if $\rho_i^B = |i\rangle\langle i|_B$ constitute $\dim(B)$ many orthogonal rank-1 projectors, and the $\rho_i^A = |v_i\rangle\langle v_i|_A$ are any distinct pure states, then this decomposition with $\dim(B)$ terms is actually unique, so the minimum number of terms must depend on $\dim(B)$. – Daniel Ranard Sep 29 '19 at 19:52
• @DanielRanard Good catch, this was indeed incorrect (as far as I can see right now). However, it was not essential to the argument, and I have fixed it - overall, for the special case of separable states, 4. gives a bound of $D^3D'$ terms in a separable convex decomposition made from product states. (For separable states, the $\rho_i$ in the argument need only satisfy $S(\rho_i^A)=0$, i.e. they are of the form $\rho_i=\vert\phi_i^A\rangle\langle\phi_i^A\vert\otimes \rho_i^B$.) – Norbert Schuch Sep 29 '19 at 22:29

It's obviously not always possible -- consider, for example, a pure entangled state. In this special case, the decomposition is unique and contains only one term, the entangled state itself $\rho=\lvert\psi\rangle\langle\psi\rvert$.

Given an arbitrary state, it may be tricky to determine if you can find a decomposition involving only separable states, but here's one suggestion that might help: you could check the eigenvalues of $\rho$.

1. Any decomposition $\sum_j \lvert\psi_j\rangle\langle\psi_j\rvert$ can contain only $\lvert\psi_j\rangle$ orthogonal to all the eigenstates with eigenvalues equal to zero.

2. In case any subset of the non-zero eigenvalues are degenerate and correspond to entangled states, you can try to construct linear combinations of them that are not entangled.

Here's an example: consider the state $\rho=\frac{1}{2}(\lvert00\rangle+\lvert11\rangle)(\langle.\rvert)+\frac{1}{2}(\lvert00\rangle-\lvert11\rangle)(\langle.\rvert)$. It has two distinct eigenvalues, $\frac{1}{2}$ and $0$, both degenerate. Therefore, no decomposition will include the terms $(\lvert01\rangle \pm \lvert10\rangle)(\langle . \rvert)$. Furthermore, since the eigenvalues for $(\lvert00\rangle \pm \lvert11\rangle)(\langle . \rvert)$ are degenerate, the density matrix will also be diagonal in any basis that uses a linear combination of these states. For example, we could use

$\{(\lvert 00\rangle+\lvert 11\rangle)\pm(\lvert 00\rangle+\lvert 11\rangle)\}= \{\lvert00\rangle,\lvert11\rangle\}$,

so the state can also be written $\rho=\frac{1}{2}\lvert00\rangle\langle00\rvert+\frac{1}{2}\lvert11\rangle\langle11\rvert$.

• of course you are right, sorry I forgot to specify that I was asking about separable states for which the decomposition is possible – glS Apr 13 '18 at 21:02
• @glS, then it's trickier :) I believe the answer still has to do with the number of non-zero eigenvalues. I would conjecture that the minimum number of projectors is equal to the number of non-zero eigenvalues. – ostrichCamel Apr 13 '18 at 21:08
• note that I'm asking the minimum number of elements required to describe any separable state. The minimum is therefore at least equal to $DD'$, because that is the number required to decompose the completely mixed state – glS Apr 13 '18 at 21:21
• right, you are suggesting that the minimum is $D^2$ then, with the totally mixed state (and equivalent states) are the ones that require the most elements in the decomposition. It may be the case, yes, but I would like to see how one can show that! :) – glS Apr 13 '18 at 21:36
• How does this answer the question? – Norbert Schuch Apr 17 '18 at 20:00