{
  "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 $κ=\\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κ\\log N)=\\widetilde O(m^3Nκ)$ time, while an exact reduction to positive packing followed by rank-one completion runs in randomized time $\\widetilde O(m^2Nκ)$. At fixed $κ$, both match the $Ω(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κ^2)$ atoms, using $\\widetilde O(m^4\\sqrt{Nn}\\,κ^3)$ coherent cost queries without materializing the tensor. Finally, for fixed $m$ and constant normalized accuracy, we prove sparse-output lower bounds of $\\widetildeΩ(N)$ randomized classical queries, even with unrestricted output size, and $\\widetildeΩ(\\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Θ(N)$ classically and $\\widetildeΘ(\\sqrt{Nn})$ quantumly.",
  "abstract_shown": true,
  "affiliations": [],
  "article_type": null,
  "arxiv": "2608.09513",
  "author_total": 7,
  "authors": [
    {
      "name": "Brandon Augustino"
    },
    {
      "name": "Yue Sun"
    },
    {
      "name": "Atithi Acharya"
    },
    {
      "name": "Shouvanik Chakrabarti"
    },
    {
      "name": "Junhyung Lyle Kim"
    },
    {
      "name": "Shree Hari Sureshbabu"
    },
    {
      "name": "Charlie Che"
    }
  ],
  "bibtex": "https://research.draconitic.com/paper/ax0mq2b3swqpr.bib",
  "cited_by": 0,
  "doi": "10.48550/arxiv.2608.09513",
  "fulltext_url": null,
  "id": "ax0mq2b3swqpr",
  "issns": [],
  "landing_url": "https://arxiv.org/abs/2608.09513",
  "language": null,
  "licence": "LicenseRef-arXiv-nonexclusive-1.0",
  "licence_label": "arXiv licence",
  "licence_source": "article",
  "licence_url": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
  "metadata_licence": "CC0-1.0",
  "native_subjects": [
    [
      "arxiv",
      "cs.DS"
    ],
    [
      "arxiv",
      "math.OC"
    ],
    [
      "arxiv",
      "quant-ph"
    ],
    [
      "openalex",
      "2604|Geometric Analysis and Curvature Flows"
    ]
  ],
  "openalex": "W7202197514",
  "pdf_url": "https://arxiv.org/pdf/2608.09513",
  "pmcid": null,
  "pmid": null,
  "published": "2026-10-06",
  "publisher": null,
  "ris": "https://research.draconitic.com/paper/ax0mq2b3swqpr.ris",
  "sources": [
    {
      "first_seen": "2026-10-30T12:27:22Z",
      "native_id": "2608.09513",
      "source": "arxiv",
      "url": "https://arxiv.org/abs/2608.09513"
    }
  ],
  "subjects": [
    {
      "field": "mathematics",
      "origin": "arxiv:math.OC",
      "subfield": "optimisation-control"
    },
    {
      "field": "physics",
      "origin": "arxiv:quant-ph",
      "subfield": "quantum"
    }
  ],
  "title": "Faster Algorithms for Multimarginal Optimal Transport",
  "title_text": "Faster Algorithms for Multimarginal Optimal Transport",
  "type": "preprint",
  "updated_at": "2026-10-30T12:27:26Z",
  "url": "https://research.draconitic.com/paper/ax0mq2b3swqpr",
  "venue": "arXiv",
  "versions": []
}