- 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
- The paper improves the dependence on approximation accuracy in classical MOT algorithms while ensuring exact marginal feasibility.
- The paper addresses a well-motivated theoretical problem: recovering an explicit sparse coupling with exact marginals from implicit scaling potentials.
Critical weaknesses
- 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.
- 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.
- 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
- 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.
- 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
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 does not by itself show a runtime advantage under the same input representation. Our classical lower bound of queries (for fixed and constant accuracy) implies that, in the entry-access model, a classical algorithm can save more than polylogarithmic factors over 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 with each 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
Our compiled bound with ordinary table lookup (Remark D.5) is . Its exponent is smaller for every ; at , for example, it is against .
This example compares two upper bounds, and for small 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.
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−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 m 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) instead of Θ(δ2/m2), and an occupation estimate (Lemma C.8), which gives the fast rate without certifying any iterate. Together they give O(m7/2Nnκ5/2) queries, against O(m4Nnκ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 δ-accurate update by D(r∥r(A))−2δ. That error term is first order. Lemma C.4 gives KL(μk∥qk)−α2/2 for the normalized potential, by Hoeffding's lemma. The sharpening is elementary, since the exact remainder ∑lrl(ezl−1−zl) is already second order, but it changes the precision the algorithm needs. In expectation over the random block, progress at residual E is at least E2/(2m2) minus the error term. With the error term α2/2, log-accuracy α=Θ(δ/m) suffices down to residual δ. A first-order term forces α=Θ(δ2/m2).
Lemma C.8 versus testing or basic random stopping. The fast rate comes from the gap bound Φ−Φ⋆≤(R+α)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)−Φη⋆≤logN+ΔC/η, needs O(m3κ3) updates, against O(m3κ2) with Lemma C.8. A fast-rate route that certifies a few candidate iterates would also reach O(m3κ2) updates, since each test costs only m 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) omitted, using the sharper log-sum-exp cost d/α. The revision adds it to Appendix C.4 as Table 3.
Lemma C.4 thus contributes a factor mκ, and Lemma C.8 a factor κ relative to basic random stopping. The submitted bound m4κ3 is the last row computed with the conservative cost d/α (general response, item 1). The revision states O(m7/2Nnκ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.