Strong NP-hardness of the quantum separability problem (pp0343-0360)
          Sevag Gharibian
          doi: https://doi.org/10.26421/QIC10.3-4-11
Abstracts: Given the density matrix ρ of a bipartite quantum state, the quantum separability problem asks whether ρ is entangled or separable. In 2003, Gurvits showed that this problem is NP-hard if ρ is located within an inverse exponential (with respect to dimension) distance from the border of the set of separable quantum states. In this paper, we extend this NP-hardness to an inverse polynomial distance from the separable set. The result follows from a simple combination of works by Gurvits, Ioannou, and Liu. We apply our result to show (1) an immediate lower bound on the maximum distance between a bound entangled state and the separable set (assuming P 6= NP), and (2) NP-hardness for the problem of determining whether a completely positive trace-preserving linear map is entanglement-breaking.
Key words: entanglement, entanglement detection, NP-hard, quantum separability problem, weak membership, entanglement-breaking