  Given the density matrix rho of a bipartite quantum state, the quantum
separability problem asks whether rho is entangled or separable. In 2003,
Gurvits showed that this problem is NP-hard if rho 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 != NP), and (2) NP-hardness
for the problem of determining whether a completely positive trace-preserving
linear map is entanglement-breaking.
