  The problem of determining whether a given quantum state is separable is
known to be computationally difficult. We develop an approach to this problem
based on approximations of convex polytopes in high dimensions. By showing that
a convex polytope constructed from a polynomial number of hyperplanes
approximates the Euclidean ball arbitrarily well in high dimensions, we find
evidence that a polynomial-sized set of approximate entanglement witnesses is
potentially sufficient to determine the entanglement of a state with high
probability.
