Strong NP-hardness of the quantum separability problem

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 NP), and (2) NP-hardness for the problem of determining whether a completely positive trace-preserving linear map is entanglement-breaking.