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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.