Faster Algorithms for Multimarginal Optimal Transport

We study constructive discrete multimarginal optimal transport (MOT) among $m$ distributions on $n$ points, where the cost tensor has $N=n^m$ entries. Let $\kappa =\max \{1,(\max C-\min C)/\epsilon \}$. Classically, we give two algorithms that return exactly feasible additive-$\epsilon$ couplings. A deterministic box–simplex method with rounding runs in $O(m^{2}N\kappa \log N)=\tilde{O}(m^{3}N\kappa )$ time, while an exact reduction to positive packing followed by rank-one completion runs in randomized time $\tilde{O}(m^{2}N\kappa )$. At fixed $\kappa$, both match the $\Omega (N)$ cost of writing a dense coupling, up to factors in $m$ and logarithms. Quantumly, in the general entry-access model, tensor Sinkhorn followed by sparse recovery returns an exactly feasible additive-$\epsilon$ coupling as a classical list of $\tilde{O}(m^{2}n{\kappa }^2)$ atoms, using $\tilde{O}(m^4\sqrt{Nn}{\kappa }^3)$ coherent cost queries without materializing the tensor. Finally, for fixed $m$ and constant normalized accuracy, we prove sparse-output lower bounds of $\tilde{\Omega }(N)$ randomized classical queries, even with unrestricted output size, and $\tilde{\Omega }(\sqrt{Nn})$ quantum queries for outputs with at most $n\mathrm{polylog}(n)$ atoms. Hence, for $\kappa \le \mathrm{polylog}(n)$, MOT has tight query complexities $\tilde{\Theta }(N)$ classically and $\tilde{\Theta }(\sqrt{Nn})$ quantumly.