Polynomial-Time Algorithms for Nuclear Tensor Norms and Multipartite Separability

Technical Summary: Polynomial-Time Algorithms for Nuclear Tensor Norms and Multipartite Separability

Problem Statement
The paper addresses two fundamental computational problems in high-dimensional optimization and quantum information theory:

1. Nuclear Norm Weak Membership: Given a tensor $M \in (\mathbb{R}^d)^{\otimes k}$, decide whether its nuclear norm is at most 1, or if its distance to the unit nuclear-norm ball is at least $\epsilon$. The nuclear norm is defined as the infimum of the sum of absolute coefficients in a rank-one decomposition.
2. Multipartite Quantum Separability: Given a $k$-partite quantum state $\rho$ (either via an explicit classical description or as copies of an unknown state), decide whether $\rho$ is separable (i.e., a convex combination of product states) or if its distance to the set of separable states $\text{Sep}(d,k)$ is at least $\epsilon$ in the Frobenius norm.

Both problems are known to be NP-hard when the accuracy $\epsilon$ depends on the dimension $d$ or when the number of parties $k$ is part of the input in specific regimes. While previous works provided quasi-polynomial algorithms or polynomial-time solutions only for fixed $k$ or bipartite cases ($k=2$), a general polynomial-time algorithm for arbitrary $k$ and $d$ with constant additive accuracy remained open.

Methodology
The authors develop two distinct algorithmic frameworks: a classical deterministic approach for explicitly given tensors and a quantum approach for states given as copies.

1. Classical Algorithms (Deterministic)
The core of the classical approach is a recursive spectral compression technique that views the multilinear optimization problem as a cooperative multiprover game.

• Spectral Compression: Instead of discretizing the strategy space of each of the $k$ parties independently (which leads to exponential blowup), the authors compress the interaction between the first $j$ parties and the remaining $k-j$ parties into a single low-dimensional "message" space $V_j$.
• Recursive Prefix Compression: By applying spectral truncation (keeping only singular values above a threshold $\eta$) across cuts between $V_{j-1} \otimes H_j$ and the remaining systems, they maintain a message $p_j$ of dimension $O(\eta^{-2})$.
• Energy Argument: A crucial technical innovation is an "energy argument" that bounds the cumulative error. By showing that the squared norms of discarded components telescope to a bounded quantity (the initial norm), the total error is bounded by $O(\eta\sqrt{k})$ rather than the straightforward $O(\eta k)$. This allows the threshold $\eta$ to be set as $\Theta(\epsilon/\sqrt{k})$, keeping the dimension of message spaces polynomial in $k$.
• Meta-Algorithm: The algorithm constructs a $\delta$-cover of reachable messages iteratively. For small $k$ ($k \le d^2$), it uses convex optimization over local sets. For large $k$ ($k > d^2$), it groups sites into blocks and performs exhaustive search within blocks, leveraging the fact that local dimensions are small relative to $k$.
• Reduction to Weak Membership: Using the Frank-Wolfe algorithm, the solution to the dual optimization problem (maximizing $\langle M, \rho_1 \otimes \dots \otimes \rho_k \rangle$) is converted into a weak membership test for the nuclear norm and separability.

2. Quantum Algorithms (Property Testing)
For the setting where the input is an unknown state $\rho$ given as copies, the authors propose a dimensionality reduction protocol that avoids learning the explicit basis of the state.

• Signed Product-State Optimization: The algorithm extends the product-state learner of Bakshi et al. to qudits and signed objectives (maximizing $\text{Tr}((\rho - \sigma)\pi)$). It constructs a small "overlap product cover" using a local search procedure that identifies product states with high overlap with the target, utilizing subspace tomography and polynomial optimization.
• Dimensionality Reduction via Filtering: The algorithm defines local "Frobenius mass" operators $A_j = \text{Tr}_{-j}(\rho^2)$. It applies a quantum channel that filters out eigenvalues of $A_j$ below a threshold, effectively projecting the state onto a low-dimensional subspace of dimension $q = O(k^2/\epsilon^4)$.
• Schur-Weyl Duality: To implement this projection without explicitly learning the basis (which would take $\text{poly}(d)$ time), the authors utilize the Schur-Weyl duality. By applying the Schur transform to $N$ copies of the state, they isolate the permutation register from the unitary representation register. They discard the unitary register (which contains the unknown basis information) and replace it with a standard low-dimensional space, effectively performing a Haar-average over local unitaries. This preserves the distance to the set of separable states while reducing the local dimension to $q$.
• Result: The reduced state is then fed into the low-dimensional tester, achieving a runtime and sample complexity that are polynomial in $k$ and $\log d$, but independent of $d$.

Key Contributions and Results

• Theorem 1.1 (Nuclear Norm): The paper presents the first deterministic polynomial-time algorithm for weak membership in the nuclear-norm unit ball of high-order tensors with constant additive accuracy. The runtime is $d^{O_\epsilon(k)}$.
• Theorem 1.2 (Quantum Separability): The authors provide the first deterministic polynomial-time algorithm for the multipartite weak membership problem in the Frobenius norm for general $k$ and $d$, improving upon recent bipartite-only results. The runtime is $d^{O_\epsilon(k)}$.
• Theorem 1.3 (Separability from Copies): A quantum algorithm is provided that distinguishes separable states from those $\epsilon$-far in Frobenius norm using $k^{O_\epsilon(1)}$ copies and time $k^{O_\epsilon(1)} \cdot \text{polylog}(d)$. This is the first dimension-free test for weak membership in the set of separable states.
• Technical Novelty: The work introduces a recursive spectral compression mechanism that achieves a $O(\eta\sqrt{k})$ error bound, contrasting with previous $O(\eta k)$ bounds that limited algorithms to quasi-polynomial time. It also demonstrates how representation theory (Schur-Weyl duality) can be used to bypass the need for explicit classical descriptions of high-dimensional subspaces in quantum property testing.

Significance
The paper claims to resolve the open problem of finding polynomial-time algorithms for multipartite separability and nuclear norm evaluation in the constant accuracy regime. By combining cooperative game theory perspectives with spectral compression, the authors bridge the gap between quasi-polynomial and polynomial time for these problems. In the quantum setting, the ability to test separability with a number of copies and time independent of the local dimension $d$ (except for a polylogarithmic factor) represents a significant advancement over previous lower bounds and dimension-dependent algorithms. The work highlights that coherent measurements across copies are necessary to bypass known lower bounds for trace-norm separability, offering a new pathway for efficient quantum property testing.