arXiv:2610.03637
Polynomial-Time Algorithms for Nuclear Tensor Norms and Multipartite Separability
Martino Bernasconi, Giulio Malavolta
Abstract
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 $\text{poly}(k)$ copies and $\text{poly}(k\log d)$ time.
AI Summary
The paper studies constant-additive-accuracy optimization of bounded-Frobenius-norm tensors over products of locally tractable convex sets, and weak membership in their convex hulls. Applications include tensor nuclear-norm balls and fully separable multipartite quantum states. For $k$ local spaces of dimension at most $d$, it gives deterministic algorithms running in $d^{O_\epsilon(k)}$ time, assuming polynomial-time local linear optimization. Consequently, weak membership in the real tensor nuclear-norm unit ball and multipartite separability can be decided at constant Frobenius-distance gap $\epsilon$ in time polynomial in the explicit input size, including when $k$ grows. The nuclear-ball result extends beyond the fixed-order regime for which randomized polynomial-time algorithms were already available. The classical method recursively truncates singular directions across prefix–suffix cuts and maintains covers of feasible compressed messages. A telescoping squared-norm argument bounds cumulative compression error by $\eta\sqrt{k}$, with message dimension at most $\eta^{-2}$. Blocking handles large $k$ relative to $d$, and Frank–Wolfe converts product optimization into weak membership. For an unknown quantum state supplied through copies, a quantum tester uses $k^{O_\epsilon(1)}$ copies and $(k\log d)^{O_\epsilon(1)}$ time. It combines signed product-state optimization with local filtering to support dimension $O(k^2/\epsilon^4)$; Schur–Weyl compression exploits that support without learning its basis. Guarantees concern constant Frobenius accuracy, not trace-norm testing or nuclear-norm evaluation. Copy testing requires coherent measurements across copies. Dependence on accuracy is hidden in polynomial exponents, and a precise extension to complex tensor nuclear balls is left for future work.
we used ChatGPT to extend the algorithm of \citet{bakshi2025learning} to arbitrary local dimensions and to navigate representation theory for the dimensionality reduction.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.