How does one determine if a mixed bipartite quantum state is entangled or not? My question is based on the structure of the NP-hardness proof in section 6 (page 17) of this paper, http://arxiv.org/pdf/quant-ph/0303055v1.pdf



Mathematically one can think of being given a positive semi-definite linear map $\rho : \mathbb{C}^n \otimes \mathbb{C}^m \rightarrow   \mathbb{C}^n \otimes \mathbb{C}^m$ such that its trace is $1$ and one wants to determine if there exists some $k$ (column) vectors $x_i \in \mathbb{C}^n$ and another $k$ (column) vectors $y_i \in \mathbb{C}^m$ such that $\rho = \sum_{i=1}^{k} x_i x_i ^{\dagger} \otimes y_i y_i^{\dagger}$



If I understand right then this linked paper is proving the decision version of the above question to be NP-hard. (please correct me if my reading is wrong!) 


But I am curious to know as to what would be even a brute-force algorithm to solve this! (in my limited experience for all NP-hard questions there is a trivial brute force solution that is always obvious - but not here!)  




[Expanding the questions formulated in the comments]


Trivially it seems that there is no hope of being able to check this unless one allows for some finite precision error. But if with such a discretization the question is redefined then is the corresponding decision question still NP-Hard? 
So is there a difference between the decision question that is being shown to be NP-Hard and the actual entanglement question that needs to be solved? 




EDIT [$4^{th}$ August 2015]

I found this presentation by Aram Harrow which explains many of the issues that I was trying to get to but couldn't explain properly : http://simons.berkeley.edu/talks/aram-harrow-2014-09-25 (he explains pretty much this exact same question inside his lecture!)
In http://arxiv.org/pdf/quant-ph/0303055v1.pdf, it is shown that the weak membership problem for the set of separable states is NP-hard. As you can see in Definition 6.2 (page 18), this amounts to deciding if a state has a separable decomposition up to accuracy $\delta$.

If you want to convert this to a search problem, you can thus do so by using a $\delta$-net on the set of all separable decompositions and doing an exhaustive search.  Note that the maximal number of terms required in such a decomposition is bounded by $(d_Ad_B)^2$ (where $d_A$ and $d_B$ are the dimensions of the two systems). 

In particular, such a decomposition to accuracy $\delta$ can be used as a proof for weak membership in the set of separable states, proving that the problem is in NP.

Note that the problem clearly remains NP-hard for any higher accuracy (i.e. any accuracy which increases with the problem size).  On the other hand, since any separable decomposition with $N$ digits of accuracy can be verified in $\mathrm{poly}(N)$ time, the problem remains inside NP (and thus NP-complete) even with an exponential precision.