Faster Algorithms for Multimarginal Optimal Transport

arXiv:2608.09513v2 Announce Type: replace 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.

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.

Quantum Physics (quant-ph); Data Structures and Algorithms (cs.DS); Optimization and Control (math.OC)

arXiv:2608.09513 [quant-ph]

(or arXiv:2608.09513v2 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2608.09513 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.

analiza aiqbench

Faster Algorithms for Multimarginal Optimal Transport

Subiecte conexe