acceptodds
Under review as a conference paper at ICLR 2027

Faster Algorithms for Multimarginal Optimal Transport

Abstract

We study constructive discrete multimarginal optimal transport (MOT) among distributions on points, where the cost tensor has entries. Let . Classically, we give two algorithms that return exactly feasible additive- couplings. A deterministic box–simplex method with rounding runs in time, while an exact reduction to positive packing followed by rank-one completion runs in randomized time . At fixed , both match the cost of writing a dense coupling, up to factors in and logarithms. Quantumly, in the general entry-access model, tensor Sinkhorn followed by sparse recovery returns an exactly feasible additive- coupling as a classical list of atoms, using coherent cost queries without materializing the tensor. Finally, for fixed and constant normalized accuracy, we prove sparse-output lower bounds of randomized classical queries, even with unrestricted output size, and quantum queries for outputs with at most atoms. Hence, for , MOT has tight query complexities classically and quantumly.

Primary area:
optimization
Keywords:
optimal transport, linear programming, quantum computing

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_FrCoOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies classical and quantum algorithms for discrete multimarginal optimal transport. It presents two classical approaches based on box–simplex optimization and positive packing, improving the dependence on approximation accuracy while ensuring exact marginal feasibility. The quantum approach combines tensor Sinkhorn iterations with a trim–sample–complete procedure to construct an explicit sparse coupling without materializing the full tensor. The paper also gives classical and quantum cost-query lower bounds matching the upper-bound exponents up to logarithmic factors, for a fixed number of marginals and constant normalized accuracy in the sparse-output setting.

Critical strengths
  1. The paper improves the dependence on approximation accuracy in classical MOT algorithms while ensuring exact marginal feasibility.
  2. The paper addresses a well-motivated theoretical problem: recovering an explicit sparse coupling with exact marginals from implicit scaling potentials.
Critical weaknesses
  1. The abstract and introduction introduce substantial notation and numerous complexity bounds before clearly explaining the main technical obstacles and ideas. This makes the contributions difficult to assess for readers outside the MOT literature.
  2. Section 3 identifies noisy convergence analysis and sparse recovery as the main quantum contributions. However, the comparison with the cited quantum matrix-scaling work remains brief, particularly regarding the treatment of adaptive estimation errors. I found it difficult to assess which parts of the convergence proof require new arguments beyond extending the existing analysis to multiple marginals.
  3. Remark D.5 accounts for ordinary-table access and gives conditions for a sublinear gate count. The remaining limitation concerns the classical comparison: efficient cost evaluation relies on structure that may also benefit classical algorithms, as Section 5 acknowledges. A gate count below the dense tensor size therefore does not by itself establish a runtime advantage over classical methods using the same input representation.
Questions for authors
  1. How does the treatment of estimation errors in Lemma C.4 and the subsequent convergence argument differ from that in the cited quantum matrix-scaling algorithms? Identifying the specific step that needs a new argument, and its role in obtaining the final query bound, would help clarify the technical contribution.
  2. Is there a concrete cost family satisfying the efficient-evaluation assumptions of Remark D.5 for which the compiled quantum runtime improves on a known classical runtime bound under the same input representation? Such a comparison would help assess the significance of the query separation beyond the general oracle model.
3 comments
AuthorsOpenReview ↗

Response to FrCo (part 1)

Thank you for the specific questions. The answers changed the paper: answering Q1 led to the sharper bound in the general response.

W1 (presentation). The quantum part of the revised introduction now states the question first. Next it describes the two obstacles: estimating fibers of nm−1n^{m-1} entries under adaptively dependent noise, and producing an explicit, exactly feasible output without writing the tensor. It then gives the ideas that address them, and only then the bounds. The access model is stated at the start of Section 3.

Q1 / W2 (what is new in the convergence analysis). In short: since the matrix analysis does not cover noisy updates on mm blocks (general response, item 3), we prove convergence for random blocks, and two steps of that proof are new: a second-order one-step bound (Lemma C.4), which allows log-accuracy Θ(δ/m)\Theta(\delta/m) instead of Θ(δ2/m2)\Theta(\delta^2/m^2), and an occupation estimate (Lemma C.8), which gives the fast rate without certifying any iterate. Together they give O~(m7/2Nn κ5/2)\widetilde O(m^{7/2}\sqrt{Nn}\,\kappa^{5/2}) queries, against O~(m4Nn κ3)\widetilde O(m^4\sqrt{Nn}\,\kappa^3) with a first-order bound. The details follow.

Lemma C.4 versus the robust Sinkhorn lemma. The robust Sinkhorn lemma of van Apeldoorn et al., in the form of Nieuwboer's thesis (Lemma 14.1.2), bounds the decrease of the potential after a δ\delta-accurate update by D(r∥r(A))−2δD(r\|r(A))-2\delta. That error term is first order. Lemma C.4 gives KL(μk∥qk)−α2/2\mathrm{KL}(\mu_k\|q_k)-\alpha^2/2 for the normalized potential, by Hoeffding's lemma. The sharpening is elementary, since the exact remainder ∑lrl(ezl−1−zl)\sum_l r_l(e^{z_l}-1-z_l) is already second order, but it changes the precision the algorithm needs. In expectation over the random block, progress at residual EE is at least E2/(2m2)E^2/(2m^2) minus the error term. With the error term α2/2\alpha^2/2, log-accuracy α=Θ(δ/m)\alpha=\Theta(\delta/m) suffices down to residual δ\delta. A first-order term forces α=Θ(δ2/m2)\alpha=\Theta(\delta^2/m^2).

Lemma C.8 versus testing or basic random stopping. The fast rate comes from the gap bound Φ−Φ⋆≤(R+α)E\Phi-\Phi^\star\le(R+\alpha)E (Lemma C.7, the tensor analogue of the thesis's Lemmas 14.2.2–14.2.3). The thesis reaches this rate with a halving argument that calls TestScaling (Section 14.2), and it uses random stopping only with the basic rate (Section 14.3). Lemma C.8 is a variable-drift occupation estimate. It combines the fast rate with a random output time, so no marginal is tested during the run. Basic random stopping, with the initial gap Φη(0)−Φη⋆≤log⁡N+ΔC/η\Phi_\eta(0)-\Phi_\eta^\star\le\log N+\Delta_C/\eta, needs O~(m3κ3)\widetilde O(m^3\kappa^3) updates, against O~(m3κ2)\widetilde O(m^3\kappa^2) with Lemma C.8. A fast-rate route that certifies a few candidate iterates would also reach O~(m3κ2)\widetilde O(m^3\kappa^2) updates, since each test costs only mm marginal estimations; against such a route, the advantage of Lemma C.8 is that no iterate is certified.

Role in the final bound. The table gives Sinkhorn-stage cost queries with the common factor O~(Nn)\widetilde O(\sqrt{Nn}) omitted, using the sharper log-sum-exp cost d/α\sqrt{d/\alpha}. The revision adds it to Appendix C.4 as Table 3.

one-step error termoccupation argumentcost queries
first orderbasic random stoppingm4κ4m^4\kappa^4
second order (Lemma C.4)basic random stoppingm7/2κ7/2m^{7/2}\kappa^{7/2}
first ordernonlinear (Lemma C.8)m4κ3m^4\kappa^3
second order (Lemma C.4)nonlinear (Lemma C.8)m7/2κ5/2m^{7/2}\kappa^{5/2}

Lemma C.4 thus contributes a factor mκ\sqrt{m\kappa}, and Lemma C.8 a factor κ\kappa relative to basic random stopping. The submitted bound m4κ3m^4\kappa^3 is the last row computed with the conservative cost d/α\sqrt d/\alpha (general response, item 1). The revision states O~(m7/2Nn κ5/2)\widetilde O(m^{7/2}\sqrt{Nn}\,\kappa^{5/2}), and only the resource counts change.

The estimation errors depend adaptively on the past. We handle this by coupling the run to a "safe process" (proof of Theorem C.9). This is one standard way to account for estimator failures, and we do not claim it as new.

AuthorsOpenReview ↗

Response to FrCo (part 2)

Q2 / W3 (a concrete cost family). We agree with W3, and the revision says it explicitly: a gate count below NN does not by itself show a runtime advantage under the same input representation. Our classical lower bound of Ω(N/log⁡2n)\Omega(N/\log^2n) queries (for fixed mm and constant accuracy) implies that, in the entry-access model, a classical algorithm can save more than polylogarithmic factors over NN only by exploiting structure. Two kinds of structured families illustrate the point.

  • Families with polynomial-time classical algorithms. These include graphical costs of bounded treewidth, set-optimization costs, and costs of constant rank plus sparse corrections (Altschuler and Boix-Adserà), and we claim no advantage for them. Low-dimensional geometric costs can also admit fast classical algorithms.
  • Dense pairwise interactions. These are costs Ci=∑k<lgkl(zk,ik,zl,il)C_{\mathbf i}=\sum_{k<l}g_{kl}(z_{k,i_k},z_{l,i_l}) with each gklg_{kl} computed from the support points by a small circuit. Here the Gibbs kernel factorizes over pairs of modes. Grouping the modes into three blocks turns each marginal into a weighted triangle sum, which fast matrix multiplication evaluates. Exact Sinkhorn, sampling and our trim-and-complete step then give a constructive classical algorithm with work

O~(poly(m) κ2 nω⌊m/3⌋+(m mod 3)).\widetilde O\bigl(\mathrm{poly}(m)\,\kappa^2\,n^{\omega\lfloor m/3\rfloor+(m\bmod3)}\bigr).

Our compiled bound with ordinary table lookup (Remark D.5) is O~(poly(m) κ5/2 n(m+3)/2)\widetilde O(\mathrm{poly}(m)\,\kappa^{5/2}\,n^{(m+3)/2}). Its exponent is smaller for every m≥5m\ge5; at m=6m=6, for example, it is 4.54.5 against 2ω≈4.742\omega\approx4.74.

This example compares two upper bounds, and for small mm the margin is modest; it is not a lower bound for classical algorithms on this family. The revision adds it to Section 5 with these caveats.

Thank you for the response and the revisions. The revised manuscript clarifies the technical contributions and the scope of the speedup, and also makes the main technical ideas easier to follow. The revision improves the dependence of the quantum query bound on the target accuracy and provides a concrete classical baseline for dense pairwise costs.

However, my concern about the extent of the technical novelty remains. The proof of Lemma 3.3 in van Apeldoorn et al. already contains the cancellation that gives a second-order error term, and the new stopping analysis combines a standard variable-drift argument with the existing idea of returning a randomly chosen iterate. These refinements strengthen the complexity analysis for multimarginal Sinkhorn, but I still find their methodological novelty limited. Therefore, I will keep my original score.

Reviewer_QPLUOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies constructive multimarginal optimal transport (MOT) and proposes faster classical and quantum algorithms. On the classical side, it presents two nearly-linear-time algorithms based on box–simplex optimization and positive packing LPs. On the quantum side, it develops a quantum Sinkhorn-based algorithm that outputs an explicitly represented, exactly feasible sparse coupling. The paper also establishes classical and quantum query lower bounds that match the upper bounds up to polylogarithmic factors in the relevant parameter regimes.

Critical strengths

The complexity bounds are clearly stated. The paper improves the complexity bounds for constructive MOT in both classical and quantum settings. The proposed classical algorithms achieve nearly-linear dependence on both the tensor size N=nmN=n^m and the normalized inverse accuracy κ\kappa, with complexities O~(m3Nκ)\widetilde O(m^3N\kappa) and O~(m2Nκ)\widetilde O(m^2N\kappa), respectively. The quantum algorithm achieves O~(m4Nnκ3)\widetilde O(m^4\sqrt{Nn}\kappa^3) coherent cost queries. The paper also establishes matching quantum query lower bounds of Ω~(Nn)\widetilde\Omega(\sqrt{Nn}), demonstrating the tightness of the query complexities under the considered access and output models.

Critical weaknesses
  1. The classical algorithms in Section 2 appear to rely heavily on existing techniques. In Section 2.1, the approach of incorporating marginal constraint violations through an ℓ1\ell_1 penalty and reformulating OT as a box–simplex game has already been studied in Revisiting Area Convexity: Faster Box-Simplex Games and Spectrahedral Generalizations, which also applies the box–simplex solver to OT. Similarly, the reduction of OT to a positive packing LP in Section 2.2 was already developed in Towards Optimal Running Times for Optimal Transport. The proposed methods seem to mainly extend these existing approaches from two marginals to mm marginals, without introducing substantially new algorithmic techniques.

  2. The quantum algorithm in Section 3 also appears to be largely based on existing approaches. The use of entropic regularization to reduce OT to a matrix scaling problem has been extensively studied, for example in Towards Optimal Running Times for Optimal Transport. Furthermore, Quantum Algorithms for Matrix Scaling and Matrix Balancing already developed a quantum implementation of Sinkhorn iterations, including convergence analysis under approximate marginal estimation.

    The proposed algorithm appears to follow essentially the same framework, extending quantum Sinkhorn from matrix scaling to multimarginal tensor scaling. Although the paper additionally introduces a sparse recovery procedure using quantum sampling, its trimming and completion steps are also closely related to existing rounding techniques. Overall, the genuinely new technical contributions beyond combining and extending known methods are not sufficiently clear.

Questions for authors

Could the authors clarify the genuine technical difficulties in extending the existing classical and quantum algorithms from the two-marginal setting to the multimarginal setting? In particular, which steps require fundamentally new techniques or analyses that cannot be directly generalized from previous work? As currently presented, the proposed algorithms appear to be relatively straightforward extensions or combinations of existing approaches. A more explicit explanation of the technical novelty would help assess the significance of the contributions.

2 comments
AuthorsOpenReview ↗

Response to QPLU

Thank you for the careful reading. We agree with much of this characterization and will state it plainly in the paper. For each part, below we separate what is inherited from what is new.

Classical algorithms.

  • Box–simplex route. This is a direct application of Jambulapati and Tian (Theorem 1) together with the rounding of Lin et al. (Theorem 4.4). The paper presents it that way, and the route serves as a deterministic counterpart with explicit dimension dependence.
  • Packing route. It extends the bimarginal reductions of Blanchet et al. and Quanrud. The tensor-product deficit correction is also known (Lin et al., Algorithm 2). The multimarginal case requires one exact optimization fact. For arbitrary mm, every packing-feasible partial plan completes to a coupling without lowering the shifted benefit. Hence P⋆=U−MOT(C,μ)P^\star=U-\mathsf{MOT}(C,\boldsymbol\mu), and a (1−δ)(1-\delta)-approximate packing solution gives additive MOT error at most δΔC\delta\Delta_C with no further rounding loss.
  • What we claim. We agree that the ingredients are known and that the extension is short once one sees that the completion argument survives for mm marginals; we regard that simplicity as a strength. But the result was not known, although the complexity of MOT has received considerable attention. The bimarginal packing reductions appeared in October 2018 (Blanchet et al., arXiv:1810.07717; Quanrud, arXiv:1810.05957). The MOT algorithms that followed obtained O~(m3Nκ2)\widetilde O(m^3N\kappa^2) and O~(m3Nn1/3κ4/3)\widetilde O(m^3Nn^{1/3}\kappa^{4/3}) (Lin et al., arXiv:1910.00152) and O~(m3Nn κ)\widetilde O(m^3N\sqrt n\,\kappa) (Tupitsa et al., arXiv:2004.02294). Lin et al. explicitly left extending the framework of Blanchet et al. to MOT as future work (their Remark 5.6), writing that "such extension is challenging since we are not clear whether these frameworks heavily depend on the minimum-cost flow structure of the OT problem or not". To our knowledge, for m≥3m\ge3 our routes are the first constructive MOT algorithms whose work is linear in both NN and κ\kappa. The gain is polynomial, not only in mm: for fixed mm and κ=n1/4\kappa=n^{1/4}, the best earlier bound in Table 1 is O~(Nn1/2)\widetilde O(Nn^{1/2}), against O~(Nn1/4)\widetilde O(Nn^{1/4}) for packing. These bounds also set the classical baseline against which the quantum result is measured.

Quantum Stage I. We agree that it follows the quantum Sinkhorn framework of van Apeldoorn et al. and Nieuwboer. Two steps of the analysis differ, and they determine the final exponent; our reply to Reviewer FrCo gives the details.

  • One-step bound. The bound in Lemma C.4 has a second-order error term α2/2\alpha^2/2. The robust Sinkhorn lemmas in those works have a first-order term 2δ2\delta.
  • Occupation estimate. Lemma C.8 combines the fast convergence rate, obtained from the gap bound Φ−Φ⋆≤(R+α)E\Phi-\Phi^\star\le(R+\alpha)E, with random stopping. As a result, no marginal is tested during the run.

Lemmas C.5–C.7 are noisy tensor analogues of the range and gap arguments of Kalantari et al. and Dvurechensky et al., in the robust form of Nieuwboer's thesis (Section 14.2). Random stopping appears in its Section 14.3, and the revision credits both. Using the sharper cost of the log-sum-exp primitive (see the general response) improves the bound to O~(m7/2Nn κ5/2)\widetilde O(m^{7/2}\sqrt{Nn}\,\kappa^{5/2}). That improvement requires the second-order bound: with a first-order bound, the same primitive gives only m4κ3m^4\kappa^3.

What changes for m≥3m\ge3.

  • Block selection. Lin et al. choose the block greedily, which needs all mm marginal residuals at every iteration. Implemented with quantum estimates, that means mm marginal estimations per step. Random blocks together with Lemma C.8 remove this cost.
  • Output. For m≥3m\ge3 the standard rounding (Lin et al.) writes the dense tensor, and its rank-one correction ∏kerrk/∥err1∥1m−1\prod_k\mathrm{err}_k/\|\mathrm{err}_1\|_1^{m-1} can have up to nmn^m nonzeros. As you note, our trim and completion reuse ideas from rounding. What is new is making them work on an implicit tensor and on a sample, which keeps the algorithm sublinear in NN while restoring the marginals exactly. Item 4 of the general response compares the two procedures step by step.
  • Lower bounds. For fixed mm and constant accuracy, the constructive lower bounds are Ω(N/log⁡2n)\Omega(N/\log^2n) classical queries for any output size and Ω(Nn/log⁡n)\Omega(\sqrt{Nn}/\log n) quantum queries for outputs of at most n polylog(n)n\,\mathrm{polylog}(n) atoms (Theorem 4.1). Their proof needs almost-perfect matchings in random mm-partite mm-uniform hypergraphs (Pippenger's theorem); for m=2m=2 a bipartite random-graph matching would suffice. Together with our upper bounds, they give query complexity Θ~(N)\widetilde\Theta(N) classically and Θ~(Nn)\widetilde\Theta(\sqrt{Nn}) quantumly for fixed mm and κ≤polylog(n)\kappa\le\mathrm{polylog}(n) (Corollary 4.2), so the exponent n(m+1)/2n^{(m+1)/2} is optimal in that regime.

Thank you for the helpful response and clarifications. I appreciate the improvements achieved, though I still view the contributions as primarily extending and combining existing frameworks. Therefore I will maintain my original score.

Reviewer_GvVkOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

In this paper, the authors present three key contributions related to compute an approximate multimarginal optimal transport plan over mm distributions with support size nn each and a cost tensor CC whose elements have a range of max⁡iCi−min⁡jCj=κ\max_i C_i - \min_j C_j = \kappa. First, the authors describe a classical, randomized algorithm which runs in O(m2Nκ)O(m^2N\kappa) time where N=nmN = n^m. The classical algorithm reduces the multimarginal optimal transport problem to a packing LP and applies a randomized packing LP solver. Next, the authors present a quantum algorithm which runs in O(m4Nnκ3)O(m^4 \sqrt{Nn} \kappa^3) time. Their quantum algorithm exploits the sparse representation of a transport plan that is admitted by the dual Gibbs potentials.

Critical strengths

The claimed first sublinear time quantum algorithm with respect to the size of the cost tensor for multimarginal optimal transport and matching lower bound is a theoretically interesting and potentially strong result.

Critical weaknesses

My major issue with the paper is the lack of clarity in presentation. It seems that the major technical contributions of the paper are in the first sublinear quantum algorithm and the nearly matching lower bounds (up to polylog(N)\mathrm{polylog}(N) factors). Yet much of the paper was focused on getting a m=polylog(N)m = \mathrm{polylog}(N) improvement in the running time for classical algorithms which already take Ω(N)\Omega(N) time. What this meant is that there was not enough space for the authors to fully detail how the quantum algorithm works or how to construct the lower bounds. It was quite hard for me to parse through these sections, and I admittedly still do not fully understand the details from the main text (which should be the goal of the main text). See the questions below for my concerns regarding the clarity of the presentation.

I am also noting that the quantum algorithm and lower bound are both entirely AI generated, as claimed in the ethics statement. This means that the potentially interesting results had no substantive contributions from the authors, raising potential ethics issues to be addressed by the conference.

Questions for authors

High level questions:

  • What is the significance of a classical algorithm running in roughly m2nmm^2 n^m time when the previous best algorithm runs in roughly m3nmm^3 n^m time? The nmn^m term already dominates any polynomial terms in mm.
  • Relatedly, why did the authors choose to put more emphasis on the classical algorithm which makes a marginal improvement in the dependence on mm over the claimed quantum algorithm which makes a significant improvement in NN?

Technical questions (which I wish could be addressed in the main text if the authors had enough space to do so):

  • Line 323: Do you need to know what Z is explicitly? How do you get around not knowing the value of Z?
  • Line 339: What is this fiber? How would you design it and how does it imply the quadratic speedup? This seems to be the crux of the entire algorithm! It was glossed over in a single line of the description.
  • Line 344: How do you interpret the Sinkhorn algorithm itself now if you have errors in the marginals? Sinkhorn typically works by iteratively projecting so that the marginal of one distribution is always satisfied. We now project in a way so that the marginal is only almost satisfied?
  • Line 373: What does the phrase "we estimate each marginal of QβQ_\beta from above and scale its entries downward, one correction factor per mode" mean, at a detailed level? How do you do this precisely? What is a "correction factor"? How do you estimate the marginal?
  • Line 382: Can you give a self-contained explanation of how you would intend to use amplitude amplification to resolve the issue of low sampling success probabilities?
  • Line 388: If trimming is again used in this phase, as described on line 373, then intuitively how do we guarantee that the result is feasible when the marginals are only estimated in the process of trimming (I'm guessing for the sake of saving time)?
  • Line 402: The O(m5nm+1κ3)O(m^5 n^{m+1} \kappa^3) working-cost vector lookups does not appear anywhere else in the introduction. Is there a reason why only the cost queries were considered relevant in the introduction?
  • Line 471: I agree that writing a dense solution will require Ω(N)\Omega(N) time. The quantum algorithm avoids this by instead maintaining the dual Gibbs potential. However, even though we know there exists a solution with size O(mn)O(mn) by bounding the rank of the constraint matrix, the corresponding entropy regularized solution necessarily has a complexity of Ω(N)\Omega(N) (since sparse solutions are heavily penalized by the regularization term). Does this mean that only an approximate cost can actually be computed in roughly N\sqrt{N} time using your quantum algorithm?
4 comments
AuthorsOpenReview ↗

Response to GvVk (part 1)

Thank you for the close reading and the precise questions. Several of them point to places where Section 3 was too terse, and the revision now answers each one in the main text.

The classical goal is linearity in both NN and κ\kappa. We believe the review misreads the classical result and its motivation. The two high-level questions describe the packing algorithm as a marginal improvement in the dependence on mm, which the N=nmN=n^m term would dominate. Improving the dependence on mm was never our aim. The introduction sets the goal of linear dependence on both NN and κ\kappa (lines 69–75: "Existing MOT bounds trade dependence on NN against dependence on κ\kappa ... Is there a constructive algorithm for MOT with O~(poly(m)Nκ)\widetilde O(\mathrm{poly}(m)N\kappa) arithmetic cost?"), answers it at line 77 ("We give two routes linear in both NN and κ\kappa"), and the first sentence of Section 2 repeats it (line 188).

For m≥3m\ge3, no earlier MOT algorithm achieves this; for m=2m=2, the packing reductions of Blanchet et al. and Quanrud already do, and our packing route extends them. In Table 1, multimarginal Sinkhorn costs O~(m3Nκ2)\widetilde O(m^3N\kappa^2), accelerated alternating minimization O~(m3Nn κ)\widetilde O(m^3N\sqrt n\,\kappa), and accelerated Sinkhorn O~(m3Nn1/3κ4/3)\widetilde O(m^3Nn^{1/3}\kappa^{4/3}), whereas packing costs O~(m2Nκ)\widetilde O(m^2N\kappa). Beyond a common factor of mm, the savings are factors of κ\kappa, n\sqrt n and n1/3κ1/3n^{1/3}\kappa^{1/3}, respectively. The revised abstract now states the goal explicitly ("in time linear in both NN and κ\kappa").

The positioning of the classical result. In addition to the above, the classical bound also calibrates the quantum result. A first step in most work on quantum algorithms is to check whether the classical bounds can be improved, so as not to overstate a quantum speedup. The revised quantum algorithm uses O~(m7/2n(m+1)/2κ5/2)\widetilde O(m^{7/2}n^{(m+1)/2}\kappa^{5/2}) cost queries. That is fewer than the O~(m2nmκ)\widetilde O(m^2n^m\kappa) classical operations roughly when κ<n(m−1)/3/m\kappa<n^{(m-1)/3}/m. This comparison sets queries against arithmetic operations; Remark D.5 accounts for gates. Measured against existing classical bounds, the quantum advantage would look larger than it is.

Emphasis. We agree that the quantum algorithm and the lower bounds deserve more of the main text. The revision moves the box–simplex route to Appendix B.5, where it is now Theorem B.8, and uses the space for the explanations in our technical answers below. The quantum part of the introduction now states the two obstacles and our ideas before any bound.

AuthorsOpenReview ↗

Response to GvVk (part 2)

Technical questions

Line 323: do we need ZZ? No. In Stage I, adding a constant cc to block βk\beta_k multiplies every entry of K(β)K(\beta) by ece^c. The normalized tensor, its marginals and Φη\Phi_\eta do not change. In the update

βk,a←βk,a+log⁡μk,a−log⁡Sk,a(β)+log⁡Z(β),\beta_{k,a}\leftarrow\beta_{k,a}+\log\mu_{k,a}-\log S_{k,a}(\beta)+\log Z(\beta),

the term log⁡Z\log Z is the same for every aa. It is a gauge shift that the recentering step removes, so it could even be omitted. We estimate it with the same routine at lower cost (nm/2n^{m/2} versus n(m+1)/2n^{(m+1)/2} queries). In Stage II the sampler needs only an upper estimate Zˉ≥Z\bar Z\ge Z within a constant factor, so that acceptance probabilities are at most one. This estimate changes the acceptance rate but not the distribution of accepted samples. The normalizer's estimation error matters only in the trim, which compares normalized marginals with μ\mu, and there it is part of the accuracy budget α\alpha (Lemma D.2).

Line 339: what is a fiber, and where does the speedup come from? For mode kk and point aa, the fiber is the preimage {i∈[n]m:ik=a}\{\mathbf i\in[n]^m:i_k=a\} of aa under the kkth coordinate projection. It consists of the nm−1n^{m-1} entries that contribute to the marginal coordinate qk,aq_{k,a}. The revision defines the term explicitly. The fiber's mass is Sk,a(β)=∑i:ik=aewi(β)S_{k,a}(\beta)=\sum_{\mathbf i:i_k=a}e^{w_{\mathbf i}(\beta)}, where wi(β)=∑ℓβℓ,iℓ−Ci/ηw_{\mathbf i}(\beta)=\sum_\ell\beta_{\ell,i_\ell}-C_{\mathbf i}/\eta. Each exponent costs one cost query and mm potential lookups (Lemma C.1).

The quantum log-sum-exp routine works in three steps. It finds an approximately largest term by quantum maximum finding. It then divides every term by that one, so the largest term is of order one. Finally it estimates the normalized sum with the improved quantum approximate summation of van Apeldoorn, Gribling and Nieuwboer (Quantum 2024), which sums the largest terms exactly and applies amplitude estimation to the rest. This yields log⁡Sk,a\log S_{k,a} to additive accuracy α\alpha with O~(d/α)\widetilde O(\sqrt{d/\alpha}) queries for d=nm−1d=n^{m-1} terms [Nieuwboer 2024, Thm 13.3.2].

A classical algorithm needs Ω(d)\Omega(d) queries in the worst case, because the costs can make one dominant term hide among d−1d-1 negligible ones. Over the nn fibers of one mode, the quantum routine uses O~(n(m+1)/2α−1/2)\widetilde O(n^{(m+1)/2}\alpha^{-1/2}) queries against n⋅nm−1=nmn\cdot n^{m-1}=n^m classically. As Remark D.7 explains, this square root on fiber sums, together with the same square root on rejection loops, is the entire source of the speedup.

Line 344: what is Sinkhorn when the marginals have errors? Yes, after a noisy update the selected marginal is only almost satisfied: with log-marginal errors at most α\alpha, it lies within a factor e±2αe^{\pm2\alpha} of μk\mu_k. An exact Sinkhorn update satisfies the selected marginal exactly, but it generally changes the other marginals, so a run stopped after finitely many steps generally satisfies the marginals only approximately. The Sinkhorn-based OT and MOT algorithms of Altschuler, Weed and Rigollet (m=2m=2) and Lin et al. (m≥3m\ge3) therefore stop once the marginal error is below a tolerance, and then apply a separate rounding step that enforces all marginals exactly. Our convergence proof never uses exact satisfaction of a marginal. It views Sinkhorn as block-coordinate minimization of the convex dual Φη\Phi_\eta in (9), and a noisy update as an inexact block minimization. By Lemma C.4, a noisy update decreases Φη\Phi_\eta by at least KL(μk∥qk(β))−α2/2\mathrm{KL}(\mu_k\|q_k(\beta))-\alpha^2/2, at most α2/2\alpha^2/2 less than the progress of an exact update. By Pinsker's inequality, this bound can be negative only when the kkth marginal is already within ℓ1\ell_1 distance α\alpha of μk\mu_k. Exact feasibility comes from Stage II (Line 388 below).

AuthorsOpenReview ↗

Response to GvVk (part 3)

Line 373: what exactly does the trim do? It is a variant of the first step of the classical rounding procedures above, which scale slices of the tensor down until no marginal exceeds its target. Classical rounding does this one mode at a time with exact marginals; the trim does all modes at once, with upper estimates of the marginals of QβQ_\beta. For each mode kk and point aa, the log-sum-exp routine estimates the marginal

νk,a=projk(Qβ)a,\nu_{k, a } = proj_k ( Q_{\beta} )_a,

a fiber sum divided by the normalizer, to within a factor e±α/2e^{\pm\alpha/2}. Multiplying the estimate by eα/2e^{\alpha/2} gives an upper estimate νˉk,a\bar\nu_{k,a} with νk,a≤νˉk,a≤eανk,a\nu_{k,a}\le\bar\nu_{k,a}\le e^{\alpha}\nu_{k,a}, where α≤δ/(8m)\alpha\le\delta/(8m). The correction factors and the trimmed tensor are

\qquad Q^\downarrow_{\mathbf i}=Q_\beta(\mathbf i)\prod_{k=1}^m f_{k,i_k}.$$ All factors are at most one and $\bar\nu_{k,a}\ge\nu_{k,a}$, so $$proj_k ( Q^{\downarrow} )_a \leq \mu_{k,a}$$ for all $k$ and $a$ at once, and the removed mass is at most $5\delta/8$. Up to normalization, the trimmed tensor is again a Gibbs tensor, with potentials $\beta_{k,a}+\log f_{k,a}$, so we never write it down and each entry still costs one cost query. **Line 382: how does amplitude amplification fix the low acceptance rate?** Without amplification, the sampler is ordinary rejection sampling. It proposes $\mathbf i$ by drawing $i_1$ from $\mu_1$ and the other coordinates uniformly, and accepts with probability $A_{\mathbf i}=W^\downarrow_{\mathbf i}/(\bar Z\,\mu_{1,i_1})$, where $W^\downarrow=Z\,Q^\downarrow$ is the unnormalized trimmed tensor. Evaluating $A_{\mathbf i}$ costs one cost query and $O(m)$ lookups, and $A_{\mathbf i}\le1$ because the trim gives $Q^\downarrow_{\mathbf i}\le\mu_{1,i_1}$ and $\bar Z\ge Z$. An accepted index is distributed as $Q^\downarrow/\|Q^\downarrow\|_1$. However, a proposal is accepted with probability between $1/(3n^{m-1})$ and $1/n^{m-1}$, so repeating until acceptance takes $\Theta(n^{m-1})$ trials per sample in expectation. Amplitude amplification is the quantum version of repeating until acceptance, and it needs only the square root of the number of repetitions. The proposal and the acceptance test form a reversible circuit. Amplification (Brassard et al., with the exponential search of Boyer et al. since the acceptance probability is unknown) reaches an accepted index after $O(n^{(m-1)/2})$ applications of this circuit in expectation. The accepted index keeps its distribution, up to a small total-variation error from finite-precision arithmetic (Lemma D.1). The revised Section 3 explains this step.
AuthorsOpenReview ↗

Response to GvVk (part 4)

Line 388: why is the result feasible if the marginals are only estimated? The second trim involves no estimation. It acts on the explicit classical list of NsampN_{\rm samp} sampled atoms with weights s0/Nsamps_0/N_{\rm samp}, where s0=1−5δ/8s_0=1-5\delta/8 is a known lower bound on the trimmed mass. We compute the list's marginals exactly, in O(mNsamp)O(mN_{\rm samp}) time. For k=1,…,mk=1,\dots,m and each aa, we remove exactly the excess (projk(V)a−μk,a)+(\mathrm{proj}_k (V)_a-\mu_{k,a})_+ from atoms with ik=ai_k=a. Entries only decrease, so modes already processed stay below their targets. The deficits dk=μk−projk(X0)d_k=\mu_k-\mathrm{proj}_k(X_0) are then nonnegative and have equal mass. Greedy completion couples them exactly with at most mn−m+1mn-m+1 new atoms, and all weights lie on a common finite rational grid.

Exact feasibility is therefore enforced by exact classical steps on every run. If a quantum estimate fails, only the cost guarantee can fail. If a subroutine aborts, the algorithm falls back to the greedy coupling of the marginals, so the output is still exactly feasible (Proposition D.4(i)). The revision states this fallback explicitly in Algorithm 3.

Line 402: why does the introduction count only cost queries? We think the lookup count in the question may contain a typo, since as written, the referee states the working-cost vector lookups as O~(m5n(m+1)κ3)\widetilde O(m^5n^{(m+1)}\kappa^3). Theorem 3.3 gives O~(m5n(m+1)/2κ3)=O~(m5Nn κ3)\widetilde O(m^5n^{(m+1)/2}\kappa^3)=\widetilde O(m^5\sqrt{Nn}\,\kappa^3) working-vector lookups, and O~(m9/2Nn κ5/2)\widetilde O(m^{9/2}\sqrt{Nn}\,\kappa^{5/2}) with the sharper summation cost in our general response. This is the same Nn\sqrt{Nn} scaling as the cost queries, up to one extra factor of mm. The factor arises because each Gibbs exponent wi(β)=∑ℓβℓ,iℓ−Ci/ηw_{\mathbf i}(\beta)=\sum_\ell\beta_{\ell,i_\ell}-C_{\mathbf i}/\eta uses O(1)O(1) cost queries and O(m)O(m) potential lookups (Lemma C.1). Every coherent evaluation pairs its cost queries with O(m)O(m) lookups, so the number of lookups exceeds the number of cost queries by at most a factor of mm.

Lookups are reads of the algorithm's own O(mn)O(mn) classical working data: potentials, trimming factors and marginal masses. A quantum circuit has to read these coherently, so they are a separate resource from cost-entry queries. The lower bounds, and hence the tightness statements, concern cost-entry queries, which is why the introduction reports those. Lookups do enter the gate count: Remark D.5 compiles each one without qRAM at O~(n)\widetilde O(n) gates. The revised introduction states the lookup count alongside the query count.

Line 471: is only an approximate cost computed? No: the algorithm returns a coupling as well as a value. It returns an explicit classical list of O~(m2nκ2)\widetilde O(m^2n\kappa^2) atoms. The list describes a coupling with exactly the prescribed marginals on every run, and with probability at least 2/32/3 its cost is within ε\varepsilon of the unregularized optimum MOT(C,μ)\mathsf{MOT}(C,\boldsymbol\mu) (Theorem D.3). The classical algorithms in Table 1 give the same type of guarantee.

The dense entropic tensor serves only as a sampling distribution. The list is an empirical sample from its trimmed version. By Hoeffding's and McDiarmid's inequalities, with high probability sampling raises the cost by at most θΔC\theta\Delta_C and moves the marginals by at most θ\theta in total ℓ1\ell_1 distance (Lemma D.2). The second trim and the completion then restore exact feasibility. Optionally, Proposition D.4 reduces the list to at most mn−m+1mn-m+1 atoms, a vertex of the LP restricted to the listed support, using only the costs of the listed atoms and polynomial classical time. The cost of the returned coupling is computed exactly with one cost query per atom.

The ethics flag

The AI Use Statement is the disclosure that ICLR requires. It says that generative AI tools were used as research assistants: in developing and checking proof arguments, in exploring proof strategies, and in editing text. It also says that the authors reconstructed and independently verified every AI-assisted argument and take full responsibility for the paper. The statement does not say that the results were entirely AI generated. It also does not say that our role was limited to reconstruction and proofreading. ICLR's policy permits this use, requires disclosure, and makes the authors accountable for every claim. We followed that policy. We welcome scrutiny of the mathematics and will answer any further technical question about the proofs.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General response to all reviewers (1/2)

We thank the reviewers for detailed and specific reviews. We have uploaded a revision with the following changes, and the individual replies give the details. To make the revision easy to check, every change in the revised PDF is shown in blue (deleted text does not appear). The deletions are the box–simplex subsection of Section 2, which moved to Appendix B.5 (marked there by a blue note), the original quantum paragraphs of the introduction, which were rewritten, three sentences of Section 3 that the new explanations replace, and the sentence after Theorem 3.3 listing the error budget, which remains in the proof of Theorem D.3.

  1. Sharper quantum bound. While answering Reviewer FrCo's question on the convergence analysis, we revisited the cost of the log-sum-exp routine in Lemma C.2. The submission used the conservative bound of O(d/δ)O(\sqrt d/\delta) queries, which is what a straightforward application of amplitude estimation gives. That bound remains valid, but the routine we cite [Nieuwboer 2024, Thm 13.3.2] needs only O(d/δ)O(\sqrt{d/\delta}) queries, because it uses the improved approximate summation of van Apeldoorn, Gribling and Nieuwboer (Quantum 2024). The revision uses this sharper cost, which changes only the resource counts. The query bound of Theorems 3.1 and 3.3 improves from O~(m4Nn κ3)\widetilde O(m^4\sqrt{Nn}\,\kappa^3) to O~(m7/2Nn κ5/2)\widetilde O(m^{7/2}\sqrt{Nn}\,\kappa^{5/2}), with O~(m9/2Nn κ5/2)\widetilde O(m^{9/2}\sqrt{Nn}\,\kappa^{5/2}) lookups. The convergence and recovery proofs, the parameters of Algorithm 2, the output size, the lower bounds and Corollary 4.2 stay the same. The improvement relies on the second-order descent bound of Lemma C.4; see the reply to FrCo.

  2. Section 3 made self-contained (GvVk, FrCo). It now defines fibers, explains the role of Z(β)Z(\beta) and of lookups, gives the trimming formulas and the amplitude-amplification step, and explains why the final list is exactly feasible on every run. Algorithm 3 now states its fallback explicitly. To make room, the box–simplex route moved to Appendix B.5; it keeps a short description in the introduction and its row in Table 1.

  3. Relation to quantum matrix scaling (FrCo, QPLU). Our algorithm differs from quantum matrix scaling in both stages.

    Stage I (noisy Sinkhorn). We build on the quantum Sinkhorn framework of van Apeldoorn et al. and Nieuwboer's thesis, but neither their algorithm nor their analysis applies to MOT as it stands. Both are written for matrices: two marginals, updated alternately. A multimarginal Sinkhorn method must choose among mm blocks, and each update leaves the other m−1m-1 marginals uncontrolled. The complexity analysis of multimarginal Sinkhorn by Lin et al. handles this with a greedy choice of block and exact updates. Implemented quantumly, the greedy choice would need estimates of all mm marginals at every step, and their analysis does not allow for estimation errors. Neither analysis covers noisy updates on mm blocks. We choose the block at random, so each step estimates one marginal, and prove convergence of this noisy random-block scheme (Lemmas C.4–C.8). The proof adapts the range, gap and random-stopping arguments of the thesis (Sections 14.2 and 14.3) and uses the variable drift theorem, which the revision credits. Two of its steps are new: the second-order one-step bound (Lemma C.4) and the occupation estimate (Lemma C.8). The reply to Reviewer FrCo explains both, and Table 3 in Appendix C.4 shows how each affects the final bound.

    Stage II (recovery). Quantum matrix-scaling algorithms output scaling vectors and have no counterpart of Stage II. Some recovery step is unavoidable, since MOT asks for a coupling with exact marginals, and the standard rounding procedures (Altschuler, Weed and Rigollet; Lin et al.) write all NN entries of the tensor. With them, the quantum algorithm would lose its speedup in NN just to write down the answer (Section 3). Item 4 explains how Stage II avoids this.

AuthorsOpenReview ↗

General response to all reviewers (2/2)

  1. What Stage II does, and why it is distinct from classical rounding procedures (QPLU, GvVk). Sinkhorn, classical or quantum, does not return a solution to MOT. It returns a probability distribution over all NN index tuples, the Gibbs tensor QβQ_\beta, described by mnmn potentials, whose marginals match μ\mu only approximately. MOT asks for a coupling with exact marginals and near-optimal cost. Stage II turns the distribution into such a coupling, written as a sparse list of O~(m2nκ2)\widetilde O(m^2n\kappa^2) atoms.

    Classical rounding (Altschuler, Weed and Rigollet; Lin et al.) reaches the same end goal, but at cost Ω(N)\Omega(N). It first scales slices of the tensor down until no marginal exceeds its target, which needs exact marginals and hence all NN entries, and then adds a rank-one tensor that can have NN nonzeros. For a classical algorithm, which already spends Ω(N)\Omega(N) on Sinkhorn, this cost is harmless. For the quantum algorithm, it would erase the speedup in NN. Trim–sample–complete reaches the same end goal with O~(Nn)\widetilde O(\sqrt{Nn}) cost queries, up to factors polynomial in mm and κ\kappa, so the speedup survives:

    • Trim. Instead of exact marginals, we use one-sided quantum estimates and scale all modes of the implicit tensor at once. Every marginal ends up below its target, and μ1\mu_1 becomes a valid proposal for rejection sampling. Up to normalization, the trimmed tensor is again a Gibbs tensor, so it is never written down.
    • Sample. Instead of keeping all NN entries, amplified rejection sampling draws O~(m2nκ2)\widetilde O(m^2n\kappa^2) atoms from the normalized trimmed tensor. Their cost and marginals concentrate around those of that tensor.
    • Complete. On this explicit list, an exact trim removes the remaining excess. Instead of the dense rank-one tensor, a greedy coupling of the deficits adds at most mn−m+1mn-m+1 atoms.

    Feasibility is enforced by these exact classical steps on the list, so the output is exactly feasible on every run; estimation errors can affect only the cost.

  2. Scope of the separation (FrCo). The Discussion and a new paragraph in Remark D.5 work through dense pairwise costs and state what is and is not claimed.

  3. Introduction (FrCo, GvVk). The abstract now states the classical goal (time linear in both NN and κ\kappa), and the quantum part of the introduction states the obstacles and our ideas before the bounds.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.