Faster Algorithms for Multimarginal Optimal Transport

Abstract

We study constructive discrete multimarginal optimal transport (MOT) among $m$ distributions on $n$ points, where the cost tensor $C$ has $N=n^m$ entries. For additive accuracy $\varepsilon$, let $\kappa=\max\{1,(\max C-\min C)/\varepsilon\}$. Classically, we give two algorithms that return exactly feasible additive-$\varepsilon$ couplings. A deterministic box--simplex method with rounding runs in $O(m^2N\kappa\log N)=\widetilde O(m^3N\kappa)$ time, while an exact reduction to positive packing followed by rank-one completion runs in randomized time $\widetilde O(m^2N\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-$\varepsilon$ coupling as a classical list of $\widetilde O(m^2n\kappa^2)$ atoms, using $\widetilde 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 $\widetilde\Omega(N)$ randomized classical queries, even with unrestricted output size, and $\widetilde\Omega(\sqrt{Nn})$ quantum queries for outputs with at most $n\operatorname{polylog}(n)$ atoms. Hence, for fixed $m$ and normalized accuracy between $(\log n)^{-O(1)}$ and a sufficiently small constant, explicit sparse MOT construction has query complexity $\widetilde\Theta(N)$ classically and $\widetilde\Theta(\sqrt{Nn})$ quantumly.