Polynomial-Time Algorithms for Nuclear Tensor Norms and Multipartite Separability

We study a multilinear optimization problem for tensors with bounded Frobenius norm, where each of the k local factors of dimension d is chosen from a convex set. We give a deterministic algorithm running in time d O(k) for constant additive approximations. As applications, we obtain the first polynomial-time algorithms at constant accuracy for weak membership in the nuclear-norm unit ball of high-order tensors and for multipartite quantum separability in Frobenius norm. Our approach views tensor optimization as a cooperative multiprover game and combines this perspective with a recursive spectral compression procedure. We then show that related ideas admit a quantum implementation when the input state is given through copies, rather than an explicit classical description. In these settings we obtain an algorithm to solve Frobenius-norm separability testing using poly(k) copies and poly(k d) time.