Faster Algorithms for Multimarginal Optimal Transport
The study develops classical and quantum algorithms for approximating multimarginal optimal transport (MOT) distance between discrete distributions. Classical methods yield polynomial runtime, while quantum approaches offer speedups in dimension, though accuracy dependence is different. Lower bounds establish the required query complexity for both regimes.