Quantum Doubly Stochastic Transformers

Thank you for the feedback, please find our responses below. We're glad to discuss further during the discussion period if there are other questions!

• (Q1): The paper is written in a slightly quantum-agnostic manner...

  • Answer: Thank you for this feedback. It is difficult to hit the right tone addressing both quantum and classical AI researchers but we will revisit the QontOT section to make it more clear.

• (Q2): First, the error rate for each quantum computation...

  • Answer: Note that these $\Omega()$-type lower bounds are generally pessimistic, as they aim to capture the worst-case instances, which are rarely met in practice. Recall that the classical complexity of attention is also $\Omega(n^2)$ (see e.g., Alman and Song, NeurIPS 2023), which matches the quantum lower bound with respect to $n$. However, these lower bounds are not very informative, since there exist many efficient approximation algorithms and heuristics that surpass the quadratic dependence. Our quantum hardware experiment points in the same direction. Instead of the theoretical lower bound of $640K$ shots, we obtained high information preservation with as little as 10K shots, a reduction by a factor of 64.

• (Q3): On that same note, findings like Figure A1 worry me a bit...

  • Answer: The quantum hardware result in Figure A1 suggests two things. First, the Frobenius distance between the exact DSM and the one obtained from a noisy quantum computer does not improve much beyond a shot count of 10K. This might be due to a multitude of factors but is most likely explained by high noise in existing quantum hardware. While this is indeed not ideal, we argue that Frobenius Distance is not the most meaningful measure to compare real and noisy attention matrices. Attention is not about absolute values, but about relative values. Does token A or token B get more attention from the source token? Panel B of Appendix Figure A1 shows that the ordering of the attention scores is preserved extremely well. With as little as 10K shots, we obtain a spearmn rank correlation above 0.9. In practice, this means that QDSFormer preserves peak attention scores but alters their absolute value by adding additional entropy. This entropy might indeed help to mitigate known issues with Softmax like attention entropy collapse (Zhai et al, ICML 2023) and thus act as regularization.

• (Q4): Because the experiments are performed with really small values of $n$ ...

  • Answer: This is a great point and we agree that more experiments are always better. We take this as an opportunity to invite you to revisit our experiment on the Eureka dataset (Figure 4). This Figure evidently shows that a plain ViT obtains an accuracy of around $55\%$ while the QDSFormer achieves above $80\%$ in almost all settings. This is a large step forward on this challenging compositional image classification task. Moreover, regarding small gains and statistical significance: the performance gain in Table 1 is well above the standard deviation in almost all cases. Indeed, we ran an two-sided Wilcoxon signed-rank test between all ViT and QDSFormer results in Table 1 ($n=40$) and obtained a clearly significant improvement ($p<0.017$). While our improvements in Table 1 are often below $1\%$, the absolute numbers are not very meaningful for accuracies above $90\%$, indeed, the gain translates to reductions in error rate by around $10\%$ which is substantial.

• (Q5): I am still a bit unsure about the value of having doubly-stochastic matrices...

  • Answer: There is a huge body of literature discussing limitations of attention in Transformers, many of which tend to be naturally fixable with doubly stochastic attention (e.g., entropy collapse [22] or rank collapse [23]). Since the Sinkformer, many papers have refined the idea of doubly stochastic attention, e.g., the concurrent work of the ESPFormer at ICML this year. Ultimately, time will show how practically useful this stream of research will be.

• (Q6): How does QontOT exactly transform the input to the output? How is the result interpretable in terms of $M$?

  • Answer: QontOT is a variational quantum circuit that performs a unitary transformation as described in Section 2.3.3. The actual transformation is obtained by the ansatz realization through various two-qubit gates (mostly ECR gates) that provably yields a DSM. Due to the difficulty of interpreting this, Section 3 provides extensive empirical experiments. We find that Sinkhorn often produces collisions (i.e., different attention score matrices $M$ yield the same DSM $D$) whereas QontOT remains injective. Moreover, the Frobenius Distance between $M$ and $D$ is lower for QontOT than for Sinkhorn attention and the entropy is slightly higher which is generally regarded beneficial (see e.g., ref [22]).

• (Q8): Are there issues of numerical stability by applying QontOT to the exponentiated output? Otherwise, what other methods of ensuring positive matrices would you consider?

  • Answer: That is a beautiful question. One advantage of QontOT over Sinkhorn attention is that it does not require exponentiation of inputs. As we found in a new experiment for Reviewer 1 (gGX6), Sinkhorn's algorithm produces collisions whenever $M$ is low-rank and has essentially constant rows. For example, Sinkhorn fails to differentiate attention score matrices $\mathbf{e}_2 \mathbf{1}^T$ from $\mathbf{e}_4 \mathbf{1}^T$ (where $\mathbf{e}_2$ and $\mathbf{e}_4$ are the second and forth column of the identity). Sinkhorn maps these matrices to the center of the Birkhoff polytope. Instead, the QDSFormer avoids collisions which is critical because it implies that it does not confuse cases where attention matrices are row-wise constant but each row has a unique value.

Thank you for the positive feedback, below we elaborate on the raised concerns.

• (Q1): Scale and domain scope. All positive results are on small images, ImageNet-1K...

  • Answer: Thanks for this suggestion. While larger scale would indeed always be desirable, we emphasize that among the reported experiments we already included the infrared-spectral dataset of Alberts et al., (NeurIPS 2024) which includes almost one million samples. Having covered object recognition (images) as well as multi-label time-series classification from small-scale (MNIST) up to 1M samples, we hope to have shown sufficient evidence on versatility and scalability.

• (Q2): Ablation. No experiment shows that trainability of the quantum operator, as opposed to simply using a richer classical layer (e.g., Mixture‑of‑Softmaxes), is essential for the observed gains.

  • Answer: Indeed, an end-to-end training of the quantum circuit parameters jointly with the ViT revealed no significant benefit over a more rigid scheme (see Appendix Figure A8). We believe that this is due to the presence of Barren plateaus, a ubiqitious challenge in quantum ML (for review see Larocca et al, Nature Reviews Physics 2025). Due to (1) the empirical superiority of doubly stochastic attention as reported in the Sinkformer (AIStats 2022) and the ESPFormer (ICML 2025) and the richness of the literature on the softmax in general, we have limited our comparisons largely to flavors of doubly stochastic attention. Among those, QDSFormer consistently performs better than competing methods like Sinkformer or the QR decomposition.

Thank you for your positive comments about novelty and writing. Below we provide responses for specific questions.

• (Q1): There are no experiments in the specific settings of quantum computing. The experiments are limited to small-scale datasets.

  • Answer: These are two separate points. First, we do provide experiments on quantum hardware. This is rare for quantum ML papers as there are only around a hundred functional quantum computers globally. Our 14-qubit experiment is described in Section 5 (L 322ff, p. 9) and demonstrates that even on noisy hardware, the ordering of the attention scores is preserved, implying that the same tokens would receive high attention as in a noise-free simulation. Secondly, we have provided experiments on datasets with almost one million samples which is not considered "small-scale" for quantum circuits (indeed it is pretty large-scale). Of course, there are scaling limitations in existing quantum hardware, but we unfortunately have no control over this. If there are specific follow-up questions regarding our paper we are happy to discuss further.

• (Q2): The improvement in the performance of the proposed model is not significant. Specifically,...

  • Answer: Regarding Table 1, the performance gain is well above the standard deviation in allmost all cases. It would be helpful if you could clarify which statistical measure you refer to when you say "not significant". We ran an two-sided Wilcoxon signed-rank test between all ViT and QDSFormer results in Table 1 ($n=40$) and obtained a clearly significant result ($p<0.017$). Our accuracy improvements in Table 1 are often below $1\%$ but absolute numbers are not very meaningful for accuracies above $90\%$, indeed, the gain translates to reductions in error rate by around $10\%$ which is substantial. Regarding Table 2, it is clearly mentioned in the paper that our performance gain is above the standard deviation for 5 out of 7 datasets with an average improvement of 1.3%. Also, please do not forget our experiment on the Eureka dataset shown in Figure 4. This Figure evidently shows that a plain ViT obtains an accuracy of around $55\%$ while the QDSFormer achieves above $80\%$ in almost all settings. This is a large step forward on this challenging compositional image classification task.

• (Q3): The theoretical analysis in Section 4 is unclear. Although...

  • Answer: As noted in Section 4, the expressivity is related to counting the number of DSMs, which is an open problem in mathematics (see e.g. ref [47]). A full theorem is beyond the scope of this work, as solving this would be worth a standalone paper in a prestigious mathematics journal (we highlight this already in Section 4). Therefore a fully theoretical comparison of the operators is unfeasible. Note that we obtained a partial result of the discrete size of the Birkhoff polytope. We also provide a thorough empirical comparison based on existing results and techniques in Section 3.

• (Q4): Can you empirically provide a comparison of the computation efficiency between the proposed method and baselines in Table 1?

  • Answer: The speed of QontOT is determined entirely by the underlying quantum hardware. Since the clock time of quantum computers is in the KHz range, unlike the GHz range of even personal silicon devices, a runtime comparison will always discourage the integration of any quantum technique. Appendix Figure A1 shows performance of QontOT as a function of circuit execution time, which reveals that with less than 10K shots (i.e., several seconds for one pass) good performance can be obtained. In simulation, the QDSFormer runs much faster, at a speed roughly 5x of a conventional ViT. Again, we emphasize that quantum ML methods are generally not compared to classical ML in terms of runtime due to incredible differences in hardware maturity.

The responses addressed my questions well. I have increased my score to 4.

We thank the reviewer for the very solid feedback and good questions. Below we provide responses point by point.

• (Q1): Line 42 states that “It [Sinkhorn’s algorithm, SA] can guarantee to find a DSMs only if...

  • Answer: QontOT produces a DSM given an arbitrary matrix while Sinkhorn's Algorithm (SA) requires a non-negative input. While exponentiation is indeed used as a trick to enable application of SA to negative matrices, it generally remains inapplicable to negative matrices. This has important practical implications: a large subset of DSMs cannot be produced, namely the faces of the Birkhoff polytope. This is because, in practice no input entry can ever be 0 due to the exponentiation. QontOT avoids this limitation.

• (Q2): Line 43 to 44 states that “It [Sinkhorn’s algorithm] is non-parametric. Thus,...

  • Answer: This is a great and subtle point. The major difference is that QontOT is naturally a parametric model which aids its expressivity, while, for Sinkhorn, even if the input is learnable, the actual algorithm is always fixed.

• (Q3): Figure 3 left: In particular, different operators do not follow the same mathematical definition, so taking the input to be the same discretized n-dimensional hypercube may not be optimal and fair to all the operators.

  • Answer: We agree. But it is not trivial to find a more fair way to compare all algorithms than exhaustively iterating over an isotropic and equidistantly-spaced grid of all possible matrices (ideally, as fine-grained as computationally possible).

• (Q4): Have you tried taking discretized points from the unit sphere?

  • Answer: Yes, Sinkhorn produces collisions, while QontOT remains injective (there is no proof that the map is injective, but it appears to be experimentaly). In detail, with a discretization of $m=3$ (i.e., $a_{ij} \in$ {$0, 0.5, 1$}), our sphere discretization contains 625 $4 \times 4$ matrices whose columns all have unit lengths. Sinkhorn yields collisions by mapping all rank-1 matrices with constant rows to the center of the Birkhoff polytope: E.g., it fails to differentiate matrix $\mathbf{e}_2 \mathbf{1}^T$ and $\mathbf{e}_4 \mathbf{1}^T$, where $\mathbf{e}_2$ and $\mathbf{e}_4$ are the second and forth column of the identity, and thus produces only 621 unique DSMs whereas QontOT yields 625 DSMs (QR: 381). This is critical because it implies that Sinkhorn confuses cases where attention matrices are row-wise constant but each row has a unique value. We will highlight this in the final manuscript.

• (Q5): What if you scale the hypercube/sphere by some constant, say $2$, 5, 10?

  • Answer: All algorithms are scale invariant. Thus we refrained from analysing vectors above unit length.

• (Q6): Figure 3 right: it does not make sense to me that birkhoff projection by definition minimizes Frobenius distance between an output doubly stochastic matrix and the input doubly stochastic matrix, yet it gets the largest distance.

  • Answer: Thanks a lot, good observation, indeed you are correct and we identified an incorrect rescaling before calculating the Frobenius distance. We repeated the analysis. The updated Frobenius distance reflect a slightly new trend: Among all operators, the Birkhoff projection now correctly shows by far the lowest Frobenius Distance (avg. $1010$) between the unnormalized QK matrix and the produced DSM ($||D-QK||_F$). Sinkhorn and QontOT show roughly the same avg. Frobenius Distance ($1050$). Interestingly, a vanilla Softmax, that is not constrained to produce a DSM, also obtains an avg. Frobenius Distance of ca. $1050$, indicating that the QontOT transformation does not largely alter the numerical values, yet yields a doubly stochastic attention matrix with higher entropy. We will include the new plot in the final manuscript (note that, at this year's NeurIPS, unlike in the past, authors are unfortunately not allowed to provide links to artifacts/images during the rebuttal period). Thank you for your understanding!

• (Q7): Figure 3: it appears that the QDS former uses multiple quantum circuit layers, whereas for ViT only one (Figure 3a) or two (Figure 3b) layers are used. Is that what the figure is showing? If so, why don’t we vary the layers of ViT as well?

  • Answer: We did this already. Indeed, Figure 3 shows how increasing the complexity of QontOT (by adding circuit layers) yields better DSMs while keeping the number of ViT layers fixed. Instead, Table 1 shows excessive ablations on varying the ViT layers. More results on ViT layers are in Appendix Table A3 and Figure A5, A6.

• (Q8): Tables 1 and 2: If QontOT can have parameters, what if we also give Sinkhorn’s algorithm parameters as mentioned above?

  • Answer: Covered in (Q2) above.

• (Q9): There are many works related to the current paper...

  • Answer: Thank you for pointing out this related literature. It is challenging to keep track of all related work. The work by [1] on spectral clustering builds upon Zass and Shashua (NeurIPS 2006) who proposed Frobenius distance to project onto the Birkhoff polytope, just like we do. The work by [2] on Hadamard parametrization can enforce right-stochasticity without a projection or a Sinkhorn step which might help to mitigate the issues of Sinkhorn with low rank matrices that we reported above. Yet, it is not immediately obvious how such Hadamard parametrization could give rise to a parametric doubly stochastic operator. We will highlight this related work in the final manuscript.

• (Q10): I could not find the definitions of some notations. ...

  • Answer: Yes, in L123 $\odot$ refers to the Hadamard product. Yes, $\overline{U}=\left(U^\dagger\right)^\top$ defines the complex-conjugate. Sorry for the brevity.

• (Q11): Assuming the answers are yes, I can agree that is doubly stochastic when is unitary. What is U(p; $\theta$) and how is it computed? ...

  • Answer: We agree that it would be great to include more details on QontOT. We opted for a high-level description and pointed in many places to the QontOT paper by Mariella et al. (ICML 2024) since its quantum theory goes well beyond the scope of our paper. In essence, QontOT leverages the Operator Schmidt decomposition and the unitarity principle ($U \odot \bar{U}$ is a DSM) to propose an ansatz $U(p; \theta)$ for amortized optimization of conditional optimal transport. The ansatz is realized by a variational quantum circuit which provably yields a DSM through a checkerboard structure with various two-qubit gates (mostly ECR) gates. Since QontOT is the first quantum circuit for optimal transport, it is impossible to compare to previous work in quantum ML (see Mariella et al., ICML 2024).

Q1: Your explanation makes sense, but it is different than what the original sentence in the paper said “It [Sinkhorn’s algorithm] can guarantee to find a DSMs only if the input matrix is non-negative”. The sentence needs to be revised for precision.

Q5: “All algorithms are scale invariant” l2 projection onto the birkhoff polytope is not scale invariant. For example: X=[.8, .2; .2, .8], so P(X) = X; but 2X = [1.6, 0.4; 0.4, 1.6] and P(2X) = I_2.

Q6: I am glad to see that the comment helped and the issue is resolved!

Q9: “It is challenging to keep track of all related work” Agreed! I am simply pointing out a few. “Frobenius distance to project onto the Birkhoff polytope, just like we do…” This is why [1] sounds related; it complements Zass and Shashua with theoretical grounds.