4
$\begingroup$

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

Improve this question
$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – Frédéric Grosshans
    Jul 30, 2015 at 7:48
  • $\begingroup$ ^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? $\endgroup$
    – Student
    Jul 30, 2015 at 7:56
  • $\begingroup$ 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. $\endgroup$
    – Norbert Schuch
    Aug 1, 2015 at 13:49
  • $\begingroup$ On an unrelated note, why does your title say "multipartite", while your question is about bipartite states? $\endgroup$
    – Norbert Schuch
    Aug 1, 2015 at 13:50
  • $\begingroup$ @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? $\endgroup$
    – Student
    Aug 2, 2015 at 1:24

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – Student
    Aug 3, 2015 at 3:02
  • $\begingroup$ (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. $\endgroup$
    – Student
    Aug 3, 2015 at 3:03
  • $\begingroup$ (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 ... ). $\endgroup$
    – Norbert Schuch
    Aug 3, 2015 at 6:23
  • $\begingroup$ ^(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... $\endgroup$
    – Student
    Aug 3, 2015 at 8:30
  • $\begingroup$ @Anirbit There is a certificate for a state being separable (i.e., non-entanglement), namely the separable decomposition. $\endgroup$
    – Norbert Schuch
    Aug 3, 2015 at 8:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.