<p>In <a href="http://arxiv.org/pdf/quant-ph/0303055v1.pdf" rel="noreferrer">http://arxiv.org/pdf/quant-ph/0303055v1.pdf</a>, it is shown that the <em>weak</em> 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 <em>up to accuracy $\delta$.</em></p>

<p>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). </p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-08-03T03:02:20.580Z
Thanks! So (1) we do not know whether the yes/no entanglement question is NP-hard or not. right? Gurvits' paper does not settle that, right? (2) Can you add in some comments about why you think that the multipartite case is more subtle? Instead of taking $\mathbb{C}^n \otimes \mathbb{C}^m$ one would just take $\otimes_{m=1}^{m=p} \mathbb{C}^{n_m}$ for some set of $p$ positive integers $n_m$ and write the same things. Or am I missing something here?
Student
CC BY-SA 3.0
2015-08-03T03:03:31.160Z
(3) I was wondering if this recent paper is somehow giving us a way of testing this entanglement : currently the best we can do seems to be to be a brute-force search with error.
Student
CC BY-SA 3.0
2015-08-03T06:23:13.590Z
(1) The exact question is clearly more hard than the approximate question, so yes, it is NP-hard. It might be outside NP, though, although you can efficiently verify a separable decomposition to any reasonable accuracy (which might scale with N), so I would say it is also in NP. (2) Multipartite entanglement in general is more subtle. If you talk about *full* separability, the same arguements apply. (3) But isn't the point of NP-hardness that there is no better way (unless ... ).
Norbert Schuch
CC BY-SA 3.0
2015-08-03T08:30:51.943Z
^(1) So there is no polynomial certificate for non-entanglement and hence non-entanglement yes/no question is in co-NP, right? (2) Well even if some question is NP-hard a "better" way to test is still possible in terms of various other kinds of improvements like reducing the exponent of the checking time or a simpler method though still exponential or even someone showing a NP-certificate for entanglement. I was wondering along these lines...
Student
CC BY-SA 3.0
2015-08-03T08:55:02.473Z
@Anirbit There is a certificate for a state being separable (i.e., non-entanglement), namely the separable decomposition.
Norbert Schuch
CC BY-SA 3.0
2015-08-03T09:01:38.700Z
Yeah! Sorry. I swapped the words! If $\rho$ is non-entangled then one can hope to give as cetificate the decomposition $\rho = \sum xx^T \otimes yy^T$ and that puts non-entanglement in NP (modulo issues of representing real numbers) But entanglement seems to be in co-NP.
Student
CC BY-SA 3.0
2015-08-02T09:06:33.227Z
2015-08-03T07:06:50.073Z
2015-08-03T07:06:50.073Z
Norbert Schuch
<p>My question is based on the structure of the NP-hardness proof in section 6 (page 17) of this paper, <a href="http://arxiv.org/pdf/quant-ph/0303055v1.pdf" rel="nofollow">http://arxiv.org/pdf/quant-ph/0303055v1.pdf</a></p>

<hr>

<p>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}$</p>

<hr>

<p>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!) </p>

<ul>
<li>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!)  </li>
</ul>

<hr>

<p>[Expanding the questions formulated in the comments]</p>

<ul>
<li><p>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? </p></li>
<li><p>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? </p></li>
</ul>

<hr>

<p>EDIT [$4^{th}$ August 2015]</p>

<p>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 : <a href="http://simons.berkeley.edu/talks/aram-harrow-2014-09-25" rel="nofollow">http://simons.berkeley.edu/talks/aram-harrow-2014-09-25</a> (he explains pretty much this exact same question inside his lecture!) </p>

CC BY-SA 3.0
2015-07-30T07:48:23.200Z
Enumerating all convex combinations of product states seems an obvious brute force solution for me. Of course, there are problems with real parameters, but I think that, in order to properly define the complexity, you need to deal with finite precision anyway.
Frédéric Grosshans
CC BY-SA 3.0
2015-07-30T07:56:39.140Z
^precisely my point! If you allow for finite precision then are we sure that the corresponding decision question will still be NP-hard? Or is there some subtle difference between what is being shown to be NP-hard vs the actual entanglement question that needs to be solved?
Student
CC BY-SA 3.0
2015-08-01T13:49:53.513Z
But isn't Gurvits' result also for finite accuracy $\delta$? Given an accuracy $\delta$, one can certainly give a separable decomposition with accuracy $\delta$ which could serve as a proof of separability, and which could be found by an exhaustive search over a $\delta$-net.
Norbert Schuch
CC BY-SA 3.0
2015-08-01T13:50:25.553Z
On an unrelated note, why does your title say "multipartite", while your question is about bipartite states?
Norbert Schuch
CC BY-SA 3.0
2015-08-02T01:24:39.747Z
@NorbertSchuch Thanks for the clarification. This is what I was suspecting. That may be Gurvits doesn't actually prove the yes/no entanglement question to be NP-hard but is actually proving it under an accuracy estimate. But somehow his language makes this a bit opaque. (1) May be you can point out the specific theorem in there which would correspond to it? (2) I guess there is no difference between the multipartite case and the bipartite case. Right? Whatever NP-hardness or exhaustive algorithm works for one should work for another. Right?
Student
CC BY-SA 3.0
2015-08-02T01:25:16.740Z
(3) You have any comments about the relationship between this and the recent work http://arxiv.org/pdf/1410.0951v1.pdf, about local tests for global entanglement?
Student
CC BY-SA 3.0
2015-08-02T09:08:24.477Z
@Anirbit (1) I think Gurvits is clear on that.  I have written an answer. (2) Multipartite entanglement is more subtle (though the full separability quesition should indeed  be the same). (3) Could you elaborate *why* you think there should be a relation?
Norbert Schuch
<cc.complexity-theory><complexity-classes><quantum-computing><quantum-information>
How does one determine if a mixed bipartite quantum state is entangled or not?
Student
# How does one determine if a mixed bipartite quantum state is entangled or not?

(Asked by: username_0 on 2015-07-30)

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!)

**Tags:** cc.complexity-theory, complexity-classes, quantum-computing, quantum-information
> **Comments:**
> **username_1**: Enumerating all convex combinations of product states seems an obvious brute force solution for me. Of course, there are problems with real parameters, but I think that, in order to properly define the complexity, you need to deal with finite precision anyway.  
> **username_0**: ^precisely my point! If you allow for finite precision then are we sure that the corresponding decision question will still be NP-hard? Or is there some subtle difference between what is being shown to be NP-hard vs the actual entanglement question that needs to be solved?  
> **username_2**: But isn't Gurvits' result also for finite accuracy $\delta$? Given an accuracy $\delta$, one can certainly give a separable decomposition with accuracy $\delta$ which could serve as a proof of separability, and which could be found by an exhaustive search over a $\delta$-net.  
> **username_2**: On an unrelated note, why does your title say "multipartite", while your question is about bipartite states?  
> **username_0**: @NorbertSchuch Thanks for the clarification. This is what I was suspecting. That may be Gurvits doesn't actually prove the yes/no entanglement question to be NP-hard but is actually proving it under an accuracy estimate. But somehow his language makes this a bit opaque. (1) May be you can point out the specific theorem in there which would correspond to it? (2) I guess there is no difference between the multipartite case and the bipartite case. Right? Whatever NP-hardness or exhaustive algorithm works for one should work for another. Right?  
> **username_0**: (3) You have any comments about the relationship between this and the recent work http://arxiv.org/pdf/1410.0951v1.pdf, about local tests for global entanglement?  
> **username_2**: @Anirbit (1) I think Gurvits is clear on that.  I have written an answer. (2) Multipartite entanglement is more subtle (though the full separability quesition should indeed  be the same). (3) Could you elaborate *why* you think there should be a relation?  

---

## 1 answers

### Answer by username_2 on 2015-08-02. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_0**: Thanks! So (1) we do not know whether the yes/no entanglement question is NP-hard or not. right? Gurvits' paper does not settle that, right? (2) Can you add in some comments about why you think that the multipartite case is more subtle? Instead of taking $\mathbb{C}^n \otimes \mathbb{C}^m$ one would just take $\otimes_{m=1}^{m=p} \mathbb{C}^{n_m}$ for some set of $p$ positive integers $n_m$ and write the same things. Or am I missing something here?  
> **username_0**: (3) I was wondering if this recent paper is somehow giving us a way of testing this entanglement : currently the best we can do seems to be to be a brute-force search with error.  
> **username_2**: (1) The exact question is clearly more hard than the approximate question, so yes, it is NP-hard. It might be outside NP, though, although you can efficiently verify a separable decomposition to any reasonable accuracy (which might scale with N), so I would say it is also in NP. (2) Multipartite entanglement in general is more subtle. If you talk about *full* separability, the same arguements apply. (3) But isn't the point of NP-hardness that there is no better way (unless ... ).  
> **username_0**: ^(1) So there is no polynomial certificate for non-entanglement and hence non-entanglement yes/no question is in co-NP, right? (2) Well even if some question is NP-hard a "better" way to test is still possible in terms of various other kinds of improvements like reducing the exponent of the checking time or a simpler method though still exponential or even someone showing a NP-certificate for entanglement. I was wondering along these lines...  
> **username_2**: @Anirbit There is a certificate for a state being separable (i.e., non-entanglement), namely the separable decomposition.  
> **username_0**: Yeah! Sorry. I swapped the words! If $\rho$ is non-entangled then one can hope to give as cetificate the decomposition $\rho = \sum xx^T \otimes yy^T$ and that puts non-entanglement in NP (modulo issues of representing real numbers) But entanglement seems to be in co-NP.  

---

