It's well known that determining whether a bipartite mixed state is separable or entangled is a $\mathsf{NP}$-hard problem under some accuracy estimates (cf. this TCS SE discussion). Now I'm curious whether there exist detailed treatises on the complexity analysis of various possible cases of complete1 and partial separability of multipartite (pure and mixed) states.

Could someone provide some insight into this? Say, is there any specific case of partial separability, determining which would be a problem in $\mathsf{P}$ rather than in $\mathsf{NP}$?

1: For complete separability, I believe the same arguments apply as for the bipartite case, as mentioned by Norbert Schuch. However, it'd be interesting to look at partial separability too.

  • $\begingroup$ What do you mean by "partial separability"? As soon as you group the multipartite state into two (or more) blocks, you just reduce to the bipartite case again. $\endgroup$
    – DaftWullie
    Sep 24, 2021 at 6:30


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.