Polynomial-Time Algorithms for Nuclear Tensor Norms and Multipartite Separability
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 dO(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(klog d) time.
Related
- Separability from Multipartite Measures
- Obtaining tensor-polarized nuclei with spin S≥1 via spin filtering upon nuclear beam transmission through an unpolarized target (spin dichroism effect)
- Polynomial-time classical algorithms for mean-field models up to the glass transition
- Convex optimization on moment polytopes: Hadamard mirror descent and efficient algorithms for quantum functionals and other tensor parameters
- Aspects of Symmetry in Nuclear Quantum Computing Variational Algorithms
BibTeX
@misc{bernasconi2026polynomialtime,
title = {{Polynomial-Time Algorithms for Nuclear Tensor Norms and Multipartite Separability}},
author = {Martino Bernasconi and Giulio Malavolta},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03637},
eprint = {2610.03637},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03637},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Polynomial-Time Algorithms for Nuclear Tensor Norms and Multipartite Separability
AU - Martino Bernasconi
AU - Giulio Malavolta
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.03637
UR - https://arxiv.org/abs/2610.03637
AB - 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(klog d) time.
ER -