We consider the complex cut polytope: the convex hull of Hermitian rank-one matrices xx*, where the elements of the n-dimensional vector x are complex m-th unit roots. These polytopes find applications in MAX-3-CUT, digital communication, and more generally, complex quadratic programming. For m = 2, the complex cut polytope corresponds to the well-known real cut polytope. We provide an exact description of the complex cut polytope for m = n = 3 and investigate semidefinite programming relaxations of the complex cut polytope. For such these relaxations, we show a method for reducing the size of the involved matrix, without weakening the approximation. We support our theoretical findings with numerical experiments.