Quantum Doubly Stochastic Transformers
Authors: Jannis Born
Filip Skogh
Kahn Rhrissorrakrai
Filippo Utro
Nico Wagner
Aleksandros Sobczyk
Venue: NeurIPS 2025 spotlight ()
Keywords: Quantum Machine Learning
Transformers
Self-Attention
Computer Vision
Primary area: other
TL;DR: A hybrid quantum-classical Transformer model with quantum-induced doubly-stochastic attention that stabilizes and improves small-scale vision transformers

Abstract: At the core of the Transformer, the softmax normalizes the attention matrix to be right stochastic. Previous research has shown that this often de-stabilizes training and that enforcing the attention matrix to be doubly stochastic (through Sinkhorn’s algorithm) consistently improves performance across different tasks, domains and Transformer flavors. However, Sinkhorn’s algorithm is iterative, approximative, non-parametric and thus inflexible w.r.t. the obtained doubly stochastic matrix (DSM). Recently, it has been proven that DSMs can be obtained with a parametric quantum circuit, yielding a novel quantum inductive bias for DSMs with no known classical analogue. Motivated by this, we demonstrate the feasibility of a hybrid classical-quantum doubly stochastic Transformer (QDSFormer) that replaces the softmax in the self-attention layer with a variational quantum circuit. We study the expressive power of the circuit and find that it yields more diverse DSMs that better preserve information than classical operators. Across multiple small-scale object recognition tasks, we find that our QDSFormer consistently surpasses both a standard ViT and other doubly stochastic Transformers. Beyond the Sinkformer, this comparison includes a novel quantum-inspired doubly stochastic Transformer (based on QR decomposition) that can be of independent interest. Our QDSFormer also shows improved training stability and lower performance variation suggesting that it may mitigate the notoriously unstable training of ViTs on small-scale data.

Quantum Doubly Stochastic Transformers
Jannis Born
Filip Skogh
Kahn Rhrissorrakrai
Filippo Utro
Nico Wagner
Aleksandros Sobezyk"
IBM Research
Correspondence to: jabszurich, com
Abstract
At the core of the Transformer, the softmax normalizes the attention matrix to be right stochastic. Previous research has shown that this often de-stabilizes training and that enforcing the attention matrix to be doubly stochastic (through Sinkhorn' s algorithm) consistently improves performance across different tasks, domains and Transformer flavors. However, Sinkhorn's 's algorithm is iterative, approximative, non-parametric and thus inflexible w.r.t. the obtained doubly stochastic matrix (DSM). Recently, it has been proven that DSMs can be obtained with parametric quantum circuit, yielding a novel quantum inductive bias for DSMs with no known classical analogue. Motivated by this, we demonstrate the feasibility of hybrid classica doubly stochastic Transformer (QDSFormer) that replaces the softmax in the self-attention layer with a variational quantum circuit. We study the expressive power of the circuit and find that it yields more diverse DSMs that better preserve information than classical operators. Across multiple small-scale object recognition tasks, we find that our QDSFormer consistently surpasses both a standard ViT and other doubly stochastic Transformers. Beyond the Sinkformer, this comparison includes a novel quantum-inspired doubly stochastic Transformer (based QR decomposition) that can be of independent interest. Our QDSFormer also shows improved training stability and lower performance variation suggesting that may mitigate the notoriously unstable training of ViTs on small-scale data.
Introduction
The Transformer [1] continues to be a dominant building block in natural language processing [2]. computer vision [3, 4] and biology [5]. Quantum computing (QC), instead, is novel paradigm with the potential to become practically useful in ML [6-10] and fuel applications across disciplines [11, 12]. Many attempts have been made build Transformers with quantum gates, either entirely [13-15] or only the attention blocks [16-18]. However, rather than merely migrating, recent work in quantum ML identified constraints in specific flavors of neural networks (NN) and successfully mitigated those through quantum e.g., fourier NNs [19], graph NNs [20] or input-conver NNs [21]. Some known limitations of Transformers are due to the softmax in the attention block, e.g., entropy collapse [22],
rank collapse [23], token uniformity [24], eureka moments [25] and more [26-30]. Applying softmax enforces the attention matrices to be right-stochastic (i.e., rows sum to 1) while its temperature controls the distribution entropy and is often adjusted to stabilize training [25, 23].
'The author contributed to this work while at IBM Research.
Spotlight at 39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

Concurrently, it was discovered that Transformer attention naturally converge to doubly stochastic matrices (DSMs) over training, i.c. their rows and columns sum [31]. Motivated by this, the Sinkformer [31] enforces bistochasticity which boosts Transformer performance across different modalities (text, images, point clouds). Intuitively, doubly stochastic attention has similar effect to increasing temperature (entropy) attention becomes more "democratic", less interactions are missed and all tokens are being attended more equally. The Sinkformer [31] is a generalization of Transformers that leverages Sinkhorn's 's algorithm (SA) and has been widely adopted and extended [32- 34J. Among various techniques to obtain DSMs [35-38], SA the most obvious choice, however has some disadvantages:
an iterative approximation procedure which reaches a DSM only in the limit. is thus empirical how many iterations Sinkformer needs and poor initialization can drastically deteriorate performance [39].
2. It can guarantee to find a DSMs only if the input matrix is non-negative, which is generally not the case within Transformer (in practice non-negativity enforced via exponentiation but we show that this hampers expressivity).
Backpropagating through SA often yields ill-conditioned and exploding/vanishing gradients when is small. In practice, under early stopping, SA is a sublinearly convergent mirror-descent fixed-point solver rather than a simple, well-conditioned layer [40]. 4. It is non-pornnnn ponmmeramtrric. Thus, in contrast to e.g., NN layer, it cannot be optimized regarding which
DSM should be returned.
Given the empirical superiority of the Sinkformer to vanilla Transformers, it is natural to study different techniques to make attention doubly stochastic. Strikingly, it was recently proven (in
Temperature
Attention
Vdd
Matmul
Matmul
Operator
a(QN)
Sinkhorn
Sottmax
CentoT
Figure 1: Doubly Stochastic Transformers. Standard scaled dot oot-product attention applies a Softmax activation on the query-key matrix (top). We study different techniques make attention doubly stochastic attention by replacing the softmax operation (bottom). Our proposed Quantum Doubly Stochastic Transformer (QDSFormer) leverages QonOTT, variational quantum circuit with high expressivity.
different context) that DSMs can be obtained naturally with a variational (i.e., parametric) quantum cireuit, dubbed QontOT [21]. They emphasize that there exists classical learning (i.e., parametric) method that can produce a DSM, akin to QontOT. Here, we demonstrate that this opens the door for hybrid quantum-classical doubly-stochastic Transformer (QDSFormer) which offers more flexibility than the Sinkformer. To that end, we extend QontOT to emit DSMs for an equally-sized matrix. The resulting quantum layer may replace the softmax within any standard (i.e., non-local, non-sparse) self-attention block. We focus on replacing the softmax inside the scaled dot-product self-attention of a Vision Transformer (ViT) for three reasons:
1. ViTs [3] suffer from unstable training [22, 25]
2. Unlike in NLP, the attention matrix size is constant, which eases quantum circuit application
3. The attention matrix in Transformer encoder is unconstrained (unlike in decoders)
We empirically analyse expressivity of the quantum circuit, finding that it yields more diverse DSMs than Sinkhorn's algorithm both on synthetic and real data. also preserves information better and induces higher entropy. We then train various flavors of doubly stochastic Transformers (see Figure 1) on more than ten object recognition datasets. comparison the ViT [3] and Sinkformer [31], the QDSFormer shows competitive performance, consistently surpassing both. In compositional image

---

recognition task [25], we find that they stabilize Transformer training and accelerate learning as they antedate the Eureka moment in compositional problem solving.
In concurrent work, Shahbazi et al. have proposed the EPSFormer [34] and the LOTFormer [41] Two doubly stochastic Transformers that, just like QDSFormer, overcomes the dependence Sinkhorn's s algorithm to reach doubly stochastic attention. The ESPFormer [34] achieves this with sliced OT which is faster than SA but still slower than standard attention. Their improvement, the LOTFormer [41] marries doubly stochastic and linear attention via conditional OT, yielding better performance and scaling than softmax attention. Due their concurrent nature, a performance comparison to ESPFormer and LOTFormer is not included in this work.
2 Methods
2.1
Doubly Stochastic Matrices (DSMs)
We denote the n--dimensional vector of by 1, and the identity matrix In. The Birkhoff polytope 22 == N (In, In) [42] defines the convex set of n x doubly stochastic matrices (DSMs). DSM 92 non-negative matrix with row/column sum of i...
PI, = In, P = Ia P.j 2.
(I)
right stochastic matrix R. has now sums of 1, i.e. R1, = 1,: R,, 2 0, and a left stochastic matrix L has column sums of 1, i.e. L1 In. L, 2 0. Hence, DSM is left and right stochastic. Moreover, the Birkhoff-von Neumann theorem states that the n! vertices (i.e., extreme points) of the Birkhoff polytope Ωt are permutation matrices, so their entries belong to {0, 1). Notably, every DSM P E 2n can be decomposed as a convex combination of permutation matrices: P= EE III Here X E An is some probability vector in the probability simplex (denoted as AN) [ are the X n permutation matrices and N < n² denotes the extreme points. While the decomposition is not unique, each DSM can be represented by at most n² permutation matrices [43]. Due to the linear equality constraints, the Birkhoff polytope 22 lies within (n ( dimmdmmensi affine subspace of the space of R matrices.
2.2 Attention
We study extensions of dot product attention [1]
QK
Attention Q, V) = AV = Softmax
V
(2)
where Q = XW : XW K and V = XWv map the input X to query Q, key K and value through their respective weight matrix W; s.t. Q, K, E Rxd Moreover, 7 is called the "tem- perature" and canonically set to ddz [1]. It controls the entropy of the output: low temperature yields a peaky distribution emphasizing differences, High temperature attenuates differences thus increasing so the unnormalized attention matrix quadratic. Applying exp(x,)
entropy. Note that -KK E Tx the softmax operator, denoted S(z), Σ e over the rows makes A right-stochastic, i.e.,
each row contains a probability distribution denoting the amount of "attention" token i pays to the other tokens. The temperature T,
2.3 Doubly-Stochastic Operators
Below define non-exhaustive of operators that transform M E R2 TxT DSM P E QT. The operators be integrated into Transformer by M QK thus yielding Doubly Stochastic Transformer ("DSFormer").
2.3.1 Sinkhorn's algorithm
The most natural approach to obtain doubly stochastic Transformer was pursued in the Sink- former [31] and leverages Sinkhomn' 's algorithm [35]. Sinkhorn's 's algorithm is based on Sinkhorn's

---

RTTxT, there exist (strictly) positive diagonal matrices P = D, D2 s.t., D,MD2 Ωr. Sinkhorn's algorithm, also known as iterative proportional fitting [44], is an approximation procedure that iteratively normalizes the mass of the rows and the columns of M which has been proven to converge to DSM by minimizing Kullback-Leibler (KI.) divergence [45]. The sole hyperparameter of this procedure is K, the number of iterations, which we enforce to be odd, following [31]. to ensure the resulting matrix is at least numerically row-stochastic, like for the canonical Softmax operator. Moreover, we study and compare two implementations of Sinkhorn's s algorithm (SA), Naive and OT. Mai ve alternates between column- and now-normaiizaiio: at even iterations (f), each column is normalized ((t+1) = P /E2 P
theorem, stating that for any square strictly positive matrix M E R," TxT,
and at odd iterations, each row is normalized as p((+1) = P /E P Instead, the OT flavor is the operator used in the Sinkformer [31] which relies on the more robust and generalized version to compute optimal transport distances [37]. Note that, both flavors may not converge with few iterations, especially if QK' contains large numeric values. Therefore, the Sinkformer is only an approximately doubly stochastic Transformer.
2.3.2 Projection on the Birkhoff polytope
Previous work studied different approaches to project matrices onto the Birkhoff polytope [46, 47], and the most established scheme leverages Frobenius distance [48]. Alternatively, one can project M directly on Ω2r via P = arg min|| X M p.p where the set for X and the objective are convex. We Xeft
chose to minimize the Frobenius norm here but note that different distances could be explored. The resulting problem is positive-definit convex quadratic program and can be rewritten
min
X x q qxx, x,
A =
X: X:20
S.t.
0
Ax=12a
I
where x = vec(X") ), q vec and A E 1R2uxn", The last (or any other) row of A can be removed without losing information, since it is a linear combination of the other rows (A has rank 2n - 1) [42, Thm. 8.1.IJ. We solved the quadratic program with OSQP [49].
2.3.3 QontOT
QontOT' is a parameterized (variational) quantum circuit that was conceived for conditional prediction of optimal transport plans [21] but can be extended to many combinatorial problems [50]. The circuit naturally emits DSMs and while [21] do not find signs of quantum advantage for their main task of optimal transport plan prediction, they report accuracy surpassing their classical baselines for the prediction of DSMs. This is likely a consequence of the choice of the ansatz which explores previously unreported link between unitary operators and DSMs. Indeed, they first proved that DSMs can be obtained naturally with quantum computers thus constructing a quantum inductive bias for DSMs. Notably, as the authors state, currently unknown whether a similarly natural classical approach exists to produce DSMs parametrically.
Let @ be the Hadamard product and U (Ut) the complex conjugate. For any unitary matrix U: U o U E 9ng Given the circuit parameters 0 (typically in the hundreds) and p E R, QontOT obtains DSM via U(p: 8) U(p 0). This matrix is dlock-decomposed before the classical rescaling. notable detriment of QontOT is the data injection which is limited to scalar p. Therefore. we extend
the multiplicative data injection f(0.p) p) = p- from scalars to tensors, such that (0, = 0 M. If M has less items than A we repeat its values to obtain a vector of length identical to 0. Furthermore, QontOT requires the DSM dimension n to be a power of 2. While this may be prohibitive within Transformer (because sequence length T may differ), it can be mitigated by padding. Padding to powers of two common technique to maximize hardware efficiency. Here, we focus our experiments on ViT's because 7 is function of patch size. In general, the circuit size scales favorably in O Ologg(() (T)). It needs at least 4 4(log, + 1) qubits, i.e., 2(ga + qa 1) where qa is the number of data qubits (log(TT) and ga is the number of auxilliary qubits (2 (Tg)(T)) + 1).

---

2.3.4 QR Decomposition
As highlighted above, any unitary U can provide DSM by taking U O U. For any input matrix M, we can obtain a unitary by computing an orthonormal basis for its column space. While there are many ways to obtain a basis, choose QR decomposition M UR, in which case R. is upper triangular. When implemented with Gram-Schmidt, QR is differentiable if M is full-rank, but for long-context applications that is rarely the case because query and key matrix have d dembed rows Rkoads
and typically M Txx has rank mi, T). implying that M only has full rank when d 2 T. In practice, if the rank is defective, we inject additive Gaussian noise (0, 1e-7) 7) to obtain full ranks. In the ViTs studied in our experiments, M often has close to, full-rank since the dimension d is greater than the number of patches P. where P R T. Moreover, QR has time complexity (n1)) for dense matrices, thus to scale up, approximation techniques may be needed [51].
3 Expressivity of Doubly-Stochastic Operators
Given the empirical superiority of the Sinkformer to the vanilla (i.e., right-stochastic) Transformer, natural question is which operator chose to obtain DSMs. Before training the DSFormers, we compare the expressivity of the o especially QontOT and Sinkhorn's algorithm - in isolation on synthetic data. We focus on two aspects.
1. Soundness does the operator always produce DSM? Given that U U E D QontOT always yields DSM. Similarly for the QR decomposition. Instead, Sinkhorn's algorithm (SA) may fail to produce a DSM if the input matrix not positive. Within the Transformer where M == QK T, the positivity requirement is generally not fulfilled which is mitigated by input exponentiation. Thus, following Sinkhorn's theorem, SA always converges given enough iterations k. But in practice the iterative procedure is limiting. When passing 8 QK' matrices from trained Sinkformer, we observe that SA does not converge for the common choices of & (3 and 21). Indeed, the Frobenius distance to the Birkhoff polytope 0.84+0.3 for k = 3 and 0.23 2.. for 21. This is in contrast to the QR, QontOT and the Birkhoff projection which all yield distances 2e-4, QontOT even < 5e-6. Instcad. the vanilla Softmax operator yields a right-stochaste matrix with distance 0.33 Hence Sinkformer attention is only approximately doubly stochastic.
Completeness can the operator produce all possible DSMs? Sinkhorn's 's algorithm reaches all DSMs of the form P D,MD2- However, due to the entry-wise exponentiation of M in the Sinkformer, the input matrix never contains any zero, thus the boundaries of the polytope cannot be reached. Regarding QontOT, the resulting DSM is a convex combination of unistochastic matrices [21, Eq. 11b]. Unistochastic matrices are a non-convex proper subset, covering a large amount of the Birkhoff polytope (albeit the exact amount is unknown [52]). In theory, if all unistochastic matrices could be reached, then by their convex combinations QontOT could cover the entire Birkhoff polyope. In practice, reaching all unistochastic matrices (especially all permutation matrices) with the same circuit parametrization is unfcasible as it requires fault- tolerant quantum hardware and high circuit depth (entanglement), But over the parameter space of QontOT, the Birkhoff polytope can be approximated more closely.
3.1 Empirical analysis
To empirically assess the completeness of the operators w.r.t. the Birkhoff polytope, we performed a brute-force analysis over a discretized grid of the unit hypercube. For a n X n matrix and a discretiztion step d 44, we sample each column from discretized n-dimensional hybercube with d" points, yielding d unique matrices. We refrain from analysing vectors above unit length because all operators are scale-invariant, i.c., fAAA) = f(A). For = 4 and d = 3 we obtain 316 x 43M matrices and computed the DSM for each input, before rounding to third decimal place. Across all operators, QontOT yielded by far the most unique DSMs (see Figure 2A), behaving nearly injective when 8 or more circuit layers are used. This is important, because, none of the other operators is injective thus some information is lost when using it inside neural network. A closer inspection of the empirical cumulative distribution function all DSMs reveals that QR often emits the same DSMs and that with only 2 layers (i.e., 98 parameters), QontOT surpasses all other methods (see Appendix Figure A3). Furthermore, whereas all the classical techniques are non-parane non-parametric, QontOT yields different set of DSMs for each parameter configuration. We repeated above experiment by
5

---

sampling from discretized grid of the unit hypersphere (instead of the hypereube). In this case, Sinkhorn also produces collisions, while QontOT remains injective (there is no proof that the map is injective, but it appears to be experimentaly). With discretization of d = 3, our sphere contains 625 matrices where all columns have unit lenghhs. Sinkhorn yields collisions by mapping all rank-1 matrices with constant rows to the center of the Birkhoff polytope, i.e., it fails to differentiate matrix ee1 and e; 1 (e2 and ey 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. In general, Sinkhorn's 's algorithm and the direct Birkhoff projection are both permutation and rotation equivariant. Instead, QR and QontTT do not possess this characteristic. Moreover, SA and the QR are scale-invariant whereas, again, QontOT is not. Note that such invariances or equivariances within a Transformer are not generally beneficial or detrimental.
Beyond approximate injectivity, powerful operator needs to possess two further characteristics: First, information has to preserved. Obtaining unique DSMs is useless they destroy information from the input matrix. To assess this, measured the Frobenius norm of the residuals between input
DSMs obtained from QK matrices of Sinkformer
Projecting discrete hypercube Birkhoff polytope
1.8
Unique Inpute (43M)
1.4
35M
of unique
20M
Shannon Encros
29M
3.0
Stnshrm
20M
8.8
15.2M
Sottmas
28.1M
0.6
Orchot Proection
10M
6.1M
8.4
SM
3.4M
1.1M
0M
QcntOT
Laaerss
GonIDT
Layers
Sinkhom Naive
Method
Sinkhom
OT
QR
Birkhoff Projection
1010
Froberius distance to QK 1B0SM OK]
1020
1:30
1040
1050
Figure 2: Left: Number unique DSMs obtained after exhaustively iterating over a discretized unit hypercube. With only layers. QontOT produces a unique DSM for every possible input, unlike all other methods. Right: Entropy vs. iitancc-preeervatioon tradcoff. Shannon entropy of different doubly stochastic attention against the Frobenius norm of the difference between unnormalized attention QK and the obtained DSM P.
and output matrix?. Secondly, low entropy has to be avoided because it causes vanishing gradients and destabilizes Transformer training [22, 28] for which various mitigation techniques have been suggested [53, 25). This so-called "entropy collapse" arises if attention is too spiky and is induced by low temperature in the softmax. Our analysis in Figure 2B reveals that QontOT possesses comparable information preservation to Sinkhorn while having higher entropy on realistic unnormalized attention matrices. QR decomposition showed superior entropy, but its cubic scaling limits applicability beyond small-scale Transformers.
Next, assessed which combination of circuit layers and auxiliary qubits yields the best speed- expressivity compromise. In general, a single circuit execution is in the three-digit millisecond range but can be efficiently parallelized. Increasing the number of layers causes sub-linear runtime increase, whereas adding more qubits causes a exponential increase (Appendix Figure A2). Regarding expressivity, adding more layers has a higher impact than adding more qubits (Appendix Figure A4). In detail, we passed the same matrix 10, 000 times, sampled the circuit parameters 0 ~ (-11, 1) and then measured the average range of values covered within each cell of the DSM. This shows that adding more auxiliary qubits is only useful if even more layers are added simultaneously.
4 Theoretical result on number of DSMs
The optimal way of studying the expressivity of a doubly-stochastic operator empirically would enumerate all DSMs in given Birkhoff polytope Ω, and assess for each DSM whether it can be reached (or how closely). The exact volume of the Birkhoff polytope is an open problem in
Otter metries like measuring preservation of ranks or pairwise ratios are possible but yielded similar results.

---

mathematics [54] which limits our ability to study expressivity theoretically. In practice, one can e.g.. if p 2 then Pú E {0. 1}. In that case there are n! DSMs. In Appendix we provide a partial derivation for the combinatorial problem of identifying the function f(n, p) + N returning the number of DSMs. The basic idea is that a n n DSM has (n - 1)² degrees of freedom. thus there are p(n-1) candidate matrices. Not all of these can be turned into DSMs because of two constaints, (1) the sum of any row or column must not exceed and (2) the sum of the n X n submatrix must not be below n 2 [54]. This allows to decompose f into (n, p) = p p'n pnn=1)² 1] - Cj - C2 + C12 where ej and 02 measure the constraint violations and 212 discounts cases where both constraints are violated. For details see Appendix E.
assume a certain discretization p E N. s.t., P. E {0, p-r.... .... 1}.
5 Quantum Doubly Stochastic Transformer
5.1 Experimental Setup
We evaluate different flavors of DSFormers obtained through replacing the Softmax function with any of the DSM operators described above. When integrating our QontOT-derived operator into a ViT we obtain our hybrid crantum-classicas doubly stochastic Transformer (QDSFormer). In the following, we refer to QontOT as the attention flavor which contains the quantum circuit whereas ODSFrrmer denotes, more broadly, any Transformer with quantum -ttbhy-stochastic attention. To date, the only realization of QDSFormer is through QontOT. Among all operators, the classical ones are non-parametric whereas this quantum operator can be optimized during training. Therefore, one could theoretically optimize circuit parameters concurrently with Transformer training. However, the ViTs we study contains up to 4 attention layers, with a batch size of 512, yielding 2048 samples to optimize in a single forward pass. We predict, unless mentioned otherwise, 8 x 8 DSMs, use 16 circuit layers and 4 auxiliary qubits (16 qubits in total). Running the circuit on quantum hardware requires 22n² /En2/=²) shots to obtain satisfactory sampling error [21]. Assuming precision of e 0.01, this is in the order of 640k shots per sample. Since quantum hardware operates on kHz frequency, execution and online optimization on hardware is unfortunately not (yet) feasible. Therefore, perform exact statevector simulation with Qiskit [55] and implement three circuit training strategies:
1. Differentiable: Joint optimization of circuit and Transformer parameters through backpropagation, akin to integrating the circuit as a neural network layer. This is by far the slowest given the difficulty of gradient propagation through quantum circuits [56].
Mixed: A mixed strategy where Transformer training interleaved with 200 steps of gradient-
circuit optimization with Nevergrad [57] on per-epoch basis.
3. Static: The circuit is used in pure inference mode with parameters obtained from a 24-qubit DSM prediction experiment on quantum hardware [21].
From the operators studied in Section 3.1, we discard the Birkhoff projection due to its non- differentiability and low DSM-diversity (Figure 2A). For comparison, we further include the Norm- Softmax [58], here denoted as Softmax,, that attenuates attention by taking the minimum of the
QK expected standard deviation := Vdz and the empirical one: A Softmax min (a(QK ).TT)
This was found to stabilize ViT training [58, 25]. Moreover, replacing the standard deviation with the empirical variance, denoted as Softmax,z, improved the performance and stabilized training even more. Note that both Softmax, and Softmax,= yields a right-stochastic but not a doubly-stochastic attention matrix. We did not perform hyperparameter optimization for any experiment (for details see Appendix D. We adapted the Sinkformer's ViT implementation of and simply reduced the number of layers and attention heads [31].
5.2 Data sets
We evaluate all VITs on MNIST [59], Fashion MNIST [60], seven datasts from the MedMNIST benchmark [61] and compositional task requiring multistep reasoning [25]. that task, a x grid contains two MNIST digits (upper left and lower right) and two FashionMNIST items (upper right and lower left). If the digits have equal value, the label is the upper right fashion item, otherwise is the bottom left fashion item. Performance typically ramps up quickly to ~ 50% because the model learns to attend one (and only one) of the FashionMNIST images. Upon continued training with a long saturation phase, ViT suddenly grasps the relationship of the MNIST digits to the classification
7

---

task and then climbs rapidly to 90 - 95% accuracy. The moment of abrupt improvement is called "Eureka moment" [25]. The dataset is split into 60K (10K) training (validation) examples. To accommodate the 8 x 8 attention matrix, each image from MNIST, FashionMNIST and MedMNIST split into horizontal stripes and a CLS token is pre-pended the patch sequence. For the Eureka dataset we use patch size of 14 x 28 pixels and mean-pooling.
5.3 Empirical results
First, we compare the QDSFormer directly with a standard VIT. The ViT uses softmaxed attention whereas the QDSFormer employs VIT with static (i.e., noo-trrainable) instantiation of QontOT to make attention doubly stochastic. Figure clearly indicates that on both datasets, the QDSFormer exceeded the ViT by significant margin. This confirms the finding that doubly stochastic attention
100
QDSFormer
Validation accuracy (%)
95
VIT
Validation accuracy
89.5
90
89.0
85
88.5
88.0
QDSFormer
VIT
75
87.5
16
16
Quantum circuit layers
Quantum circuit layers
(a) 1-ViT-Layer on MNIST.
(b) 2- 2-ViT-Layer on FashionMNIST.
Figure 3: Comparison of VIT and QDSFormer while varying the circuit depth. Mean/std from 5 trainings are shown. Within (a) and (b) all models use the same number of trainable parameters.
can improve ViTs [31]. J. Moreover, in both cases, adding more circuit layers increases performance logarithmically and with or 8 eircuit layers the ViT performance is surpassed. Exact numerical results are provided in Appendix Table A3. Next, we varied the number of ViT layers between I and 4, comparing to softmaxed attention, Softmax,a [25] and two classical doubly stochastic attention types: Sinkhorn as used in the Sinkformer [31] and a QR decomposition, a quantum-inspired alternative to QontOT. All flavors used the same number of parameters and training steps. On FashionMNIST (Table I left) the QDSFormer exceeded all other models for 2, 3 and 4 VIT layers with a performance delta larger than the standard deviation. The same result was obtained on MNIST and, this time, QontOT outperformed softmaxed attention also for one ViT layer (see Table 1 right).
Table 1: Validation accuracy of L-layered VIT on FashiouMNIST and MNIST different attention methods. QontOT uses 16 circuit layers. Mean/std computed from trainings.
FaSHionMNIST
MNIST QR
I. Softmax Softmax,2
QR
QontOT Sinkhorn
Softmax
Softmax,2
QontOT Sinkhorn
86.52
75.3+4.6
87.1
85.6.o.1
84.2=a.s
80.1-12.5
66.7-22.5
96.6.0.1
93.9+o.1
94.3
88.920.
84.612.1
89.3
90.010.
89.1
18.1
93.024.6
98.3
98.4
98.240.
3
19.3
86.342.7
89.4go1
90.3
80.4
98 98.6 g
97.7
98.6
98.7
98.610.1
89.7
87.1
89.5.0.1
90.3
89.1.11
98.8
97.9
98.7
98.8
97.9+1.
In further experiments with more ViT layers performance assimilated and plateaued due to the simplicity of the datasets. But we saw scant further improvement for more than 16 circuit layers. For a barplot visualization of Table see Appendix Figure A5/A6. Notably, QontOT offers great flexibility in the type of ansatz for the quantum circuit [21]. We observed only minor differences between four different ansatz types, with three of them outperforming the VIT, underlining the generality of the finding (Appendix Table A1). A compelling aspect is that the static version of the QontOT-attentiin did perform as good or even better than the optimized one (see Appendix Figure A8). We tested an end-to-end optimizable QDSFormer where circuit and ViT parameters are jointly optimized. Such end-to-end training is not only slower, but also had lower accuracy than the static configuration, for both MNIST and FaShionMNIST and and 8 circuit layers (Figure A8). This may be caused
8

---

by Barren plateaus [62] (i.e., gradients are largely constant along most directions), a widespread phenomenon variational quantum circuits that slows down learning. We further experimented with a "mixed" training strategy where the circuit is trained every n-th epoch. This did not reveal a clear benefit for more frequent cireuit optimization (see Appendix Figure A7), potentially due to higher volatility of the circuit. We therefore use the static, faster configuration in all remaining experiments. Next, we repeated the comparison to the four classical attention types on larger datasets
Table 2: Test accuracy for MedMNIST datasets across 5 attention types in 2-layer VIT.
MedMNIST dataset
Softmax Softmax,,
QR
QontOT
Sinkhorn
OCT 64.4_1.6
43.643.0
62.540.9
61.64u.6
55.1
Pneumonia
84.2+0.8
84.7+2.0
84.3+0.7
86.1+1.
83.041.5
Tissue
60.0+0.2
49.4+1.2
59.040.1
60.610.1
56.942.0
OrganA
78.8
73.611.7
81.2 78.4
77.012.5
OrganC
79.810.5
71.717.3
79.610.3
82.7 10.5
79.7
OrganS
64.4
59.310.9
62.610.8
68.1 10.6
63.510.9
Breast
79.642.0
78.2+2.2
81.342.9
80.0+1.1
80.1
Mean
73.0
65.8
72.5
74.3
70.8
(up to 240k images) from the MedMNIST benchmark [61]. In 5 out of 7 datasets, the QDSFormer obtained significantly better results than all other methods (Table 2). with mean accuracy increase of 1.3% compared to standard ViT. Notably, none of the other attention types can improve upon the standard ViT. Another important advantage of the QDSFormer is its stabilizing effect. Among repeated training runs, the performance variation (i.e., test accuracy variance) is consistently lower than for all classical methods (e.g.. Table or Table 2). Notably, with ViT-layer and softmax- based attention some trainings on MNIST failed to converge.
Furthermore, study training stability more systematically, we used compositional object recog- nition task with 10 classes, referred to as "Eureka" dataset. ViTs are very unstable to train on this task [25]. The random seed may determine whether the model saturated at 50% accuracy or experienced a Eureka moment (EM) after hundreds of epochs and would finally converge to 90% accuracy. As mitigation strategy, Hoffmann al. [25] tame the attention by replacing the Softmax with the NormSoftmax. In practice, temperature is often tuned manually to find sweet spot between too low temperature (causing vanishing gradients by low entropy) and too high temperature (causing vanishing gradients by uniform attention). We speculated that doubly stochastic attention might, en passant, antedate the Eureka moment (EM) because it increases attention entropy without making it uniform [31], thus cireumventing temperature tuning. Our experiments confirmed that the stan- dard ViT implementation from [25] achieves its Eureka moment only after a few hundred epochs. While the same holds true for their proposed mitigation strategies (Softmax, and Softmax,=), the QDSFormer consistently Icarned within 100 epochs to solve this task, resulting in a 30% accuracy improvement over standard ViT (Figure 4b). This major improvement, achieved with extremely lightweight quantum circuit (1 layer) also consolidated across different learning rates (Figure 4a).
Next, to assess the potential of the QDSFormer beyond image data and simultaneously study the scalability of the QDSFormer, we applied it on a novel dataset for time-series classification of InfraRed (IR) spectra of molecules into 37 functional groups [63]. This dataset contains almost 1M samples and we scale up the circuit to produce 4x larger attention matrices (16 x 16). On this dataset, the performance differences are marginal and the QDSFormer performs par with standard ViT (for details see Appendix Table A2). This shows that the QDSFormer can meaningfully generalize to domains like scientific data and tasks like multi-label classification.
Since all above results were obtained through statevector simulation, we conducted final experiment to understand the detrimental effect of quantum noise induced by real quantum hardware via the publicly available IBM Quantum Platform. We used the three machines Torino (Heron R1, 133 qubits, error per layered gate: 1.3%), Brisbane (Eagle R3, 127 qubits, EPLG: 2.2%) and Cusco (Eagle R3, 127 qubits, EPLG: 6.8%). This 14-qubit experiment tests the potential for a hybrid hardware training. Despite various light error mitigation techniques, the obtained doubly stochastic attention matrices consistently show high entropy (i.e., a tendency toward more uniform distributions), even for larger shot counts. Experimental details and plots are given in Appendix A). As Appendix Figure AIB

---

LR
Metric Softmax Softmax,2 Sinkhorn
QR
QontOT
Validaaioo accuracy (%)
80
Acc.
1
48.6
49.0.0.9
61.2 61.2
70.0
13.9
1c-3
EM@Ep
72.2=14.2
74.8.a.4
EM
0/5
0/5
0/5
2/5
2/5
8
Acc.
53.920.2
50.9
20.9
12.0
82.3 57.7+110
14.0
7e-4 Ep@
43.3=2.0
40
EM
0/5
0/5
0/5
4/5
4/5
QDSFormer
Sinkformer
Acc.
61. 111.0
51.0
51.6 51.6.0.2
66
66.4
89.4.0.1
20
QR
Softmax,
5e-4
EM@Ep
61.0
22.6,22.
72.6
43.6-8.3
EM
1/5
0/5
0/5
2/5
5/5
40
80
100
(a) Results the Eureka dataset across different models and (b) Validation accuracy per epoch, highlight- learning rates. EM @p denotes the average epoch of the EM: ing the Eureka Moment on the compositional dataset. Confidence bounds from runs.
runs without EM are set to epoch 100.
Figure 4: (a) Eurcka results across attention methods. (b) QDSFormer antedates the Eureka Moment (EM).
shows, when comparing to noise-free ground truth attention matrix, the ordering of the values in the attention matrix was preserved with high precision (spearman p >> 0.9 even for moderate shot count). Since the circuit runs within a ViT, successfully preserving the ordering will be key (to not destroy signal). Instead, numerical exactness (cf. Appendix Figure AlA) may be compromised: embedding a noisy quantum attention block (which preserves peak attention scores but also increases entropy) into Transformer could even be advantagcous. The additional entropy may avoid vanishing gradients and act as a form of regularization. This effect is particularly notable compared to its noise-free analog, which remains classically intractable if sufficient qubits used.
Conclusion
Here, we proposed the Quantum Doubly Stochastic Transformer. We conceived this method by connecting the centerpiece of novel variational quantum circuit [21] with the Transformer, fa- cilitated through the empirical observation that doubly-stochaste attention improves performance Transformers [31]. By extending the QontOT circuit from scalars to matrices we enabled its Transformer. Notably,
integration into a VIT, thus providing the first parametric, doubly-stochasee the QDSFormer presents meta-class of Sinkformers because it estimates DSMs parametrically, i.e., it can be optimized to learn arbitrary transformations onto the Birkhoff polytope. Moreover, to knowledge, there is no classical, parametric approach to estimate DSMs, thus the QDSFormer is a promising candidate for hybrid quantum claassccal neural networks trained on quantum hardware.
Our empirical expressivity analysis revealed that the quantum circuit produces DSMs that are more diverse, preserve information better and have higher entropy than DSMs from Sinkhorn's 's algorithm. On multiple simple object recognition tasks, the QDSFormer exhibited significantly higher accuracy, outperforming VIT and Sinkformer in most cases. Our usage of quantum attention substantially stabilizes the notoriously unstable ViT training on small-scale data, as evidenced by the performance on compositional object recognition task (Figure 4b), previously used to study ViT training dynamics [25]. Albeit these results are promising, all experiments were performed on comparably small-scale, due to the currently poor scaling of quantum computers in general (which is expected to improve). Notably, by leveraging QR decomposition, we also proposed a novel, quantum-inspired attention flavor. Broadly speaking, outsourcing the activation function to a parametric quantum circuit might be seen a computational overhead, however, we envision that this may reveal potential benefits (typically in small-data, small-model and short-training settings [10]) that are out of reach for classical hardware. To that end, future work could explore concurrent optimization of ViT and circuit parameters via the parameter-shift rule real quantum hardware.
Funding Declaration
This project received no external funding.
10

---

Competing Interests
The authors declare no competing financial or non-financial interests.
Author Contributions.
Conceptualization: J.B.; Data curation: J.B., F.S: Formal analysis: J.B., ES; Investigation: J.B.,
F.S, K.R, F.U., N.W., A.S.; Methodology: J.B., A.S.; Project administration: J.B.; Software:
J.B., FS; Supervision: J.B.; Validation: J.B.; Visualization: J.B., F.S, K.R; Writing original
draft: J.B., F.S. N.W., A.S.; Writing review & editing: J.B., E.S. K.R, F.U., A.S.
J.B. F.
K.R.
F.U.
N.W.
A.S.
Conceptualization
Data curation
Formal analysis
Investigation
Methodology
Project administration
Software
Supervision Validation
Visualization
Writing- Priting-originall original draft
Writing review & editing
References
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakoh Uszkoreit, Llion Jones, Aidan N Gomez, Attention you need. Advances in neural information processing systems, 30(1):261-23 2017, 1,
[2] Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The llama 3 herd of models. arXiv preprint arXiv:2407.2178. 2024.
[3] Alexey Dosovitskiy. Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai Thomas Unterthiner, Mostafa Dehghani. Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image worth 16x16 words: Transformers image recognition scale. In International Conference on Learning Representations, 2021. URL https: / //oprreee/////ee/e/// net/ id=YicbFaNTTy. 1,2
Alexander Kirillov, Fric Mintun, Nikhila Ravi, Hanzi Mao, Chloe Rolland, Laura Gustafson, Tete Xiao, Spencer Whitehead, Alexander C Berg, Wan-Yen Lo, et al. Segment anything. In Proceedings of JEFF/CVF International Conference on Computer Vision, pages 4015-4026, 2023.
Josh Abramson, Jonas Adler, Jack Dunger, Richard Evans, Tim Green, Alexander Pritzel, Olaf Ronncherger, Lindsay Willmore, Andrew Ballard, Joshua Bambrick, et al. Accurate structure prediction biomolecular interactions with alphafold 3. Nature, pages 1-3, 2024.
Maria Schuld and Nathan Killoran. Is quantum advantage the right goal for quantum machine learning? Prx Quantum, 3(3)003010,, 2022.
[7] Vojtéch Havlfček, Antonio D Córcoles, Kristan Temme, Aram W Harrow, Abhinav Kandala, Jerry M Chow, and Jay M Gambetta. Supervised learning with quantum-enhanee feature spaces. Nature, 567 (7747)2209 212, 2019.
[8] Yunchao Liu. Srinivasan Arunachalam, and Kristan Temme. A rigorous and robust quantum speed-up in supervised machine learning. Nature Physics, 2021. ISSN 1745-2481.

---

[9] Hsin- Yuan Huang, Michael Broughton, Masoud Mohseni. Ryan Babbush, Sergio Boixo, Hartmut Neven, and Jarrod R. McClean. Power of data in quantum machine learning. Nature Communications, 12(1))2631, 2021.
[10] Amira Abbas, David Sutter. Christa Zoufal, Aurélien Lucchi, Alessio Figalli,, and Stefan Woerner. The power of quantum neural networks. Nature Computational Science, 1(6):403-400 2021. 1, 10
[11] Saugata Basu, Jannis Born, Aritra Bose, Sara Capponi, Dimitra Chalkia, Timothy A Chan, Hakan Doga, Mark Goldsmith, Tanvi Gujarati, Aldo Guzman-Saenz, et al. Towards quantum-enabled cell-centric therapeutics. arXiv preprint 2307.00000.5773 2023. 1
[12] Alberto Di Meglio, Karl Jansen, Ivano Tavemelli, Constantia Alexandrou, Srinivasan Arunachalam, Christian W Bauer, Kerstin Borras, Stefano Carrazza, Arianna Crippa, Vincent Croft, et Quantum computing for high-energy physics: State of the art and challenges. PRX Quantum, 5(3)0037011, 2024. 1
[13] Nikhil Khatri, Gabriel Matos, Luuk Coopmans, and Stephen Clark. Quixer: A quantum transformer model. arXiv preprint 2406::24006043000 2024. 1
[14] Xuan-Ba Bac Nguyen, Hoang- Quan Nguyen, Samuel Yen-Chi Chen, Samee U Khan, Hugh Churchill, and Khoa Luu. Qclusformer: A quantum transformer-bas based framework for unsupervised visual clustering. arXiv preprint arX.v:2405.19722. 2024.
[15] Naixu Guo, Zhan Yu, Matthew Choi, Aman Agrawal, Kouhei Nakaji. Alán Aspuru-Guzik, and Patrick Rebentrost. Quantum linear algebra is all you need for transformer architectures. arXiv preprint arXiv:2402.167 16714, 2024. 1
[16] Iordanis Kerenidis, Natansh Mathur, Jonas Landman, Martin Strahm, Yun Yvonna Li, et al. Quantum vision transformers. Quantum, 8:1265, 2024. 1
[17] Ethan N Evans, Matthew Cook, Zachary P Bradshaw, and Margarite L LaBorde. Learning with sasquatch: novel variational quantum transformer architecture with kernel-bar -aadd self-attention. arXiv preprint arXiv:2403. 14753, 2024,
[18] Eyup B Unlu, Marçal Comajoan Cara, Gopal Ramesh Dahale, Zhongtian Dong, Roy T Forestano, Sergei Gleyzer. Daniel Justice, Kyoungchul Kong, Tom Magorsch, Konstantin T Matchev, et al. Hybrid quantum vision transformers for event classification in high energy physics. Axioms, 13(3):187, 2024. 1
[19] Jiaming Zhao, Wenbo Qiao, Peng Zhang, and Hui Gao. Quantum implicit neural representations. In Forty-first International Conference on Machine Learning, 2024. 1
[20] Slimane Thabet, Mehdi Djellabi, Igor Olegovich Sokolov, Sachin Kasture, Louis Pouus Henry, and Loic Henriet. Quantum positional encodings for graph neural networks. In Forty-first International Conference on Machine Learning, 2024.
[21] Nicola Mariella, Albert Akhriev, Francesco Tacchino, Christa Zoufal, Juan Carlos Gonzalez-Espitia, Benedek Harsanyi, Eugene Koskin, Ivano Tavernelli, Stefan Woerner, Marianna Rapsomaniki, Sergiy Zhuk, and Jannis Born. Quantum theory and application of contextual optimal tranpoort. Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research. PMLR, 2024. 1,2, 5, 7, 8, 10, 19
[22] Shuangfei Zhai, Tatiana Likhomanenko, Etai Littwin, Dan Bushridge, Jason Ramapuram, Yizhe Zhang, Jiatao Gu, and Joshua M Susskind. Stabilizing transformer training hy preventing attention entropy collapse. In International Conference Machine Learning, pages 10770-40801 PMLR, 2023. 2. 6
[23] Lorenzo Noci, Sotiris Anagnostidis, Luca Biggio, Antonio Orvieto, Sidak Pal Singh, and Aurelien Lucchi. Signal propagation in transformers: Theoretical perspectives and the role of rank collapse. Advances in Neural Information Processing Systems, 35:27198-27211 2022.
[24] Yihe Dong. Jean- Sran-Baptiste Cordonnier, and Andreas Loukas. Attention is not all you need: pure attention loses rank doubly exponentially with depth. In Marina Meila and Tong Zhang, editors. Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 2793-2803. PMLR, 18-24 Jul 2021.
[25] David Hoffmann, Simon Schrodi, Jelena Bratulic, Nadine Behrmann, Volker Fischer, and Thomas Brox. Eureka moments in transformers: Multi-step tasks reveal softmax induced optimization problems. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 18409-1843 PMLR, 21-27 Jul 2024. 1, 2, 3. 6, 7, 8, 9, 10, 19, 25, 27
12

---

[26] Zhilin Yang, Thang Luong, Russ R Salakhutdinov, and Quoe V Le. Mixtape: Breaking the softmax bottleneck efficiently. Advances in Neural Information Processing Systems, 32, 2019.
[27] Haw-Shiuan Chang and Andrew McCallum. Softmax bottleneck makes language models unable represent multi-mode mode word distributions. Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics, volume 1, 2022.
[28] Kai Shen, Junliang Guo, Xu Tan, Siliang Tang, Rui Wang, and Jiang Bian. A study on relu and softmax in transformer. arXiv preprint urXiv:2302.0646) 2023. 6
[29] Xiangyu Chen, Qinghao Hu, Kaidong Li, Cuncong Zhong, and Guanghui Wang. Accumulated trivial attention matters in vision transformers on small datasets. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 3984-3399 9992, 2023.
[30] Shen Yuan and Hongteng Xu. Towards better multi-head attention via channel-wist sample permutation. arXiv preprint arXiv:2410. 10914, 2024.
[31] Michael E. Sander, Pierre Ablin, Mathieu Blondel, and Gabriel Peyré. Sinkformers: Transformers with doubly stochastic attention. In International Conference on Artificial Intelligence and Statistics, pages 3515-3530. PMIR, 2022. 2, 3, 4, 7, 8, 9, 10, 19, 27
[32] Borjan Geshkovski, Cyril Letrouit, Yury Polyanskiy, and Philippe Rigollet. The emergence of clusters in self-attention dynamics. Advances in Neural Information Processing Systems, 36, 2024. 2
[33] Jong Chul Ye, Yujin Oh, et al. Otseg: Multi-promph sinkhorn attention for zero-shot semantic segmen- tation. In The 18th European Conference Computer Vision, ECCV 2024. European Computer Vision Association (ECVA), 2024.
[34] Ashkan Shahbazi, Elaheh Akbari, Darian Salehi, Xinran Liu, Navid NaderiAlizadeh, and Soheil Kolouri. ESPFormer: Doubly-stochastic attention with expected sliced transport plans. In Forty-second International Conference on Machine Learning, 2025. 2,
[35] Richard Sinkhorn. A relationship between arbitrary positive matrices and doubly stochastic matrices. The annals of mathematical statistics, 35(2):876-879 1964. 2,
[36] Nikitas Rontsis and Paul Goulart. Optimal approximation of doubly stochastic matrices. In International Conference Artificial Intelligence and Statistics, pages 3589-33 -598.. PMLR, 2020.
[37] Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26, 2013. 4
[38] Fei Wang, Ping Li, and Arnd Christian Konig. Learning bi-stochastic data similarity matrix. In 2010 IEEE International Conference on Data Mining, pages 551-5601 IEEE, 2010.
[39] James Thornton and Marco Cuturi. Rethinking initialization the sinkhorn algorithm. In International Conference on Artificial Intelligence and Statistics, pages 1698.869.. PMLR, 2023. 2
[40] Flavien Léger. A gradient descent perspective on sinkhorn. Applied Mathematics & Optimization, 84(2): 1843-1855, 2021.
[41] Ashkan Shahbazi, Chayne Thrash, Yikun Bai, Keaton Hamm, Navid NaderiAlizzdehh and Sohcil Kolouri. Lotformer: Doubly-stochastic linear attention via low-rank optimal transport. arXiv preprint (tti:255092233360 2025. 3
[42] Richard A. Brualdi. Combinatorial Matrix Classes. Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2006. 3.4
[43] Garrett Birkhoff. Tres observaciones sobre algebra lincal. Univ. Nac. Tucuman, Ser: A, 5:147-154, 1946.
[44] Michael Bacharach. Estimating nonnegative matrices from marginal data, International Economic Review, 6(3):294-310, 1965. 4
[45] George W Soules. The rate of convergence of sinkhorn balancing. Linear alyebra and its applications, 150:3-40, 1991. 4
[46] Derek Lim, René Vidal, and Benjamin D Haeffele. Doubly stochastic subspace clustering, arXiv preprint arXiv:2011.1485, 2020. 4
13

---

[47] Tianjiao Ding, Derek Lim, Rene Vidal, and Benjamin D Haeffele. Understanding doubly stochastic clustering. In International Conference Machine Learning, pages 5153-5165. PMLR, 2022. 4
[48] Ron 7ass and Amnon Shashua. Doubly stochastic normalization for spectral clustering. Advances in neural information processing systems, 19, 2006. 4
[49] B. Stellato, G. Banjac. P. Goulart, A. Bemporad, and S. Boyd. OSQP: operator splitting solver for quadratic programs. Mathematical Programming Computation, 12(4))637-672, 2020. doi: 10.1007/ s $12532-020-0011944 URL https: / //oii. org/10. 0ttp:/00...000//2222220000111110 -20-0009---
[50] Dylan Laplace Mermoud, Andrea Simonetto, and Sourour Elloumi. Variational quantum algorithms for permutation- based combinatorial problems: Optimal ansatz generation with applications to quadratic assignment problems and beyond. arXiv preprint urXiv:2505.05995 2025.
[51] Nathan Halko, Per-Gunnar Martinsson, and Joel A Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM review, 53(2):117-288, 2011. 5
[52] Charles Dunkl and Karol Zyczkowski. Volume the set unistochastic matrices order and the mean jarlskog invariant. Journal of mathematical physics, 50(12), 2009. 5
[53] Shulun Wang, Feng Liu, and Bin Liu. Escaping the gradient vanishing: Periodic alternatives of softmax in attention mechanism. IEEE Access, 11865749-168759,1 2021. 6
[54] Clara S Chan and David P Robbins. On the volume of the polytope of doubly stochastic matrices.
Experimental Mathematics, 8(3)22113300, 1999. 7, 23
[55] Ali Javadi-Abhari, Matthew Treinish, Kevin Krsulich, Christopher! Wood, Jake Lishman, Julien Gacon, Simon Martiel, Paul D Nation, Lev S Bishop, Andrew W Cross, et al. Quantum computing with qiskit. arXiv preprint arXiv:2405. 08810, 2024. 7
[56] Amira Abbas, Robbie King, Hsin-Yuan Huang, William J Huggins, Ramis Movassagh, Dar Gilhoa, and Jarood McClean. On quantum backpropagation, information reuse, and cheating measurement collapse. Advances in Neural Information Processing Systems, 36, 2024.7
[57] Pauline Bennet, Carola Doerr, Antoine Moreau, Jeremy Rapin, Fabien Teytaud, and Olivier Teytaud. Nevergrad: black-box optimization platform. ACM SIGEVOlution, 14(1):8-15, 2021. 7
[58] Zixuan Jiang, Jiaqi Gu, and David Z Pan. Normsoftaax: Normalizing the input of softmax to accelerate and stabilize training. In 2023 IEEE International Conference on Ommi-layer Intelligent Systems (COINS), pages 1-6. IEEE, 2023. 7
[59] Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann.ler lecuw.com/exdd//miss. 2, 2010. 7,
[60] Han Xiao, Kashif Rasul, and Roland Vollgraf. bishion-mnistt a novel image dataset for benchmarking machine learning algorithms, 2017. URL https::/ //arxii wrg//bs///////////oo wwsaaa/ss 2bb/1708.00747. 7.25
[61] Jiancheng Yang, Rui Shi, and Bingbing Ni. Medmnist classification decathlon: A lightweight automl benchmark for medical image analysis. In IEEE 18th International Symposium on Biomedical Imaging (ISBI), pages 191-195, 2021. 7, 9, 25
[62] Jarrod R McClean, Sergio Boixo, Vadim Smelyanskiy, Ryan Babbush, and Hartmut Neven. Barren plateaus in quantum neural network training landscapes. Nature communications, (1)4812,, 2018. 9
[63] Marvin Alberts, Oliver Schilter, Federico Zipoli, Nina Hartrampf, and Teodoro Laino. Unraveling molecular structure: A multimodal spectroscopic dataset for chemistry. Advances in Neural Information Processing Systems, 37:125880-125808, 2025. 9, 25
[64] Nic Fzzell, Bihek Pokharel, Lina Tewala, Gregory Quiroz, and Daniel A Lidar. Dynamical decoupling for superconducting qubits: performance survey. Physical Review Applied, 20(6):064027,, 2023. 16
[65] Joel J Wallman and Joseph Emerson. Noise tailoring for scalable quantum computation via randomized compiling. Physical Review A, 94(5):052325, 2016. 16
[66] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. CoRR, ab2/141 2014. URL ptatps://ap1. semanticscholar .rg. http/Corps.D::eee20
19
[67] Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations, 2019. URL https: httpss:/ http://www...eeeee/ommmm////aaaa 19
14

---

[68] Ross Wightman. Pytorch image models. https://github.comm http:///wgggaaaaa/oooorraaaeeeee 2019. 19
[69] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang. Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017. 19
[70] Sumeet Khatri, Ryan LaRose, Alexander Poremba, Lukasz Cincio, Andrew T Sornborger, and Patrick J
Coles. Quantum-assisted quantum compiling. Quantum,, 3:140, 2019. 19
[71] Liam Madden and Andrea Simonetto. Best approximate quantum compiling problems. ACM Transactions Quantum Computing, 3(2):1-29, 2022. 19
[72] Adam Smith, MS Kim, Frank Pollmann, and Johannes Knolle. Simulating quantum many-body dynamics current digital quantum computer. npj Quantum Information, 5(1): 106, 2019. 19
15

---

A Quantum hardware experiment
We measured the extent and the effect of quantum hardware noise on DSM produced by our quantum circuit. To that end, we picked shallow circuit (1 layer) with 14 qubits and computed the ground-trute 8 DSM for a random input matrix through statevector simulation. We then transpiled the circuit three different quantum computers (Cusco, Brisbane and Torino) available to the public via the IBM Quantum Platform. After using transpilation optimization level we obtained circuit with a 2-qubit-depth of 15 and and a total of 52 two-qubit gates. As error mitigation techniques, we used dynamical decoupling [64], Pauli twirling [65] and a projection the Birkhoff polytope of the approximate- Moooximate-DMMMM obtained from the quantum circuit (see Section 2.3.2). The results, shown in Figure AI, indicate that, consistently, Cusco was the noisiest machine and Torino yielded the best results. Moreover, in general, beyond shot count of 10, 000 little performance improvement can be observed. This a positive finding because it substantially below the theoretical minimum given by the shot noise limit (640, 000). However, the deviation from the exact DSM, measured in Frobenius Distance, was substantial (Figure A1A). We analyzed the root cause of this and found that the deviation can be largely attributed to increase in entropy. DSMs obtained from noisy quantum hardware converge toward the center of the Birkhoff polytope (1/n in every cell). The relative ordering of the absolute values instead is largely preserved (Figure A1C).
Deviation from exact DSM
Preservation of ordering
C
Duration by shots
Backend
Cusco
1.50
Spearman rank correlation
0.8
Frobenius Distance
1.25
Runtime (seconds)
0.7
1.00
0.6
0.75
0.5
0.50
0.4
Backend
Backend
Statevectorsampler
30
Brisbane
Brisbane
Cusco
0.3
Cusco
Torino
0.00
0.2
20
10K
50K100K
10K
50K 100K
1K
10K
SOK 100K
Shots (log scale)
Shots (log scale)
(log scale)
Figure A1: Hardware experiment on different quantum computers available IEM Quantum Platform. The Frobenius distance between the hardware-obtained DSM to its noise-free equivalent. B: The spearman rank correlation between the 64 values in the noise-fre free and hardware obbaiind DSMs show that the ordering of values is largely preserved. Statevectorsampler here denotes finite sampling from ideal, noise-fre free statevector.
16

---

B Circuit execution times
In Figure A2 we report detailed runtimes for the QontOT algorithm for different combinations of circuit layers and auxiliary qubits.
Fanortion time
C
Circuit for Bub DOVe
6,03
133
0.340
6..0
5.24
2014
0.11
128
6.00
2-
6464
6,992
L004
1236
Descction thee for tull D5Ws
Croutt for Bud DSVs
R.I.X
1.0M
3.14
290
33
Numorr Luy
201
6.30
6571
1,00
2.58
635
8331
23.508
2:
123
15
Figure A2: QontOT circuit execution times for DSM of size 4 (A) and 8 for different combinations of qubits and circuit layers. C and show the relative increase execution time as function inereasing the number of layers (C), and qubits (D). Adding more layers has sublinear effect on runtime, adding qubits requires exponential more runtime. The minimal number of auxiliary qubits is log,(n) + 1 and the total number of qubits is 2(qa + (o) where qa and Ja are data and auxilliary qubits respectively.
17

---

C
Empirical circuit expressivity
Cumulative Number of DSMs by Frequency (ECDF)
Cumulative Number of DSMs (in millions)
QR
40M
Birkhoff
Projection
Sinkhorn
30M
Naive
Sinkhorn
OT
QontOT
20M
8 Layers
QontOT
2 Layers
10M
0M
10
10
10
10
10
10
10
10
10
Rank of DSM (most frequent to least frequent)
Figure A3: DSM counts ranked descendingly and plotted against their cumulative count. QontOT generally produces more diverse DSMs than Sinkhorn's 's algorithm.
Range of values within DSMs
16
0.26
0.31
0.47
0.52 20.13
0.43
Total Qubits
18
0.24
0.29
0.43
0.47
+3.21
=0.17
20
0.26
0.35
1
2
8
16
Number of Layers
Figure A4: Mean range observed values in the DSM obtained a single, random input matrix, when randomly sampling 1000 circuit parametrizations.
18

---

D QDSFormer results
D.1 Hyperparameters
For experiments on MNIST. FashionMNIST and the seven MedMNIST datasets, the ViT was configured with a hidden dimension of 128 and an MLP dimension expansion factor of The model was tested with I to 4 Transformer layers, each containing a single attention head. No dropout was applied, and the batch size was set to 100. For the optimizer, Adam [66] was used, and the learning rate schedule followed the setup in Sander et al. [31], with an initial learning rate of 5e-4, decreasing by factor of 10 at epochs 31 and 45. For the more complex Eureka dataset, comprised of 56x56 RGB images, the hidden dimension was increased to 256, and a larger batch size of 512 was used. The MLP expansion factor was also doubled to 2. A cosine learning rate schedule was used with the optimizer Adam W [67]. The scheduler uses 5 warmup epochs with warm-up learning rate of le-6, the decay rate is set to 0.1 and the minimum learning rate is le-5, the other parameters follows the default TIMM settings [68]. For the optimizer the weight decay is 0.05 and betas (0.9, 0.999). All studied imaging datasets (MNIST, FaShionMNIST and seven types of MedMNIST datasets) come with predefined train/validationteest splits. On the infrared spectral data of molecules from Alberts et al. [63] we performed a 5-fold cross validation with 80%/20% train/test split. Hyperparameters were kept identical to previous experiments. For the Eureka dataset, no Exponential Moving Average (EMA) is used. Experiments were conducted on POWERS infrastructure in Python 3.9 with PyTorch [69] 1.13.1 machines with 16 cores of 32GiB RDIMM DDR4 2.7 GHz. Due to the small size of the ViTs, training took between few hours and a day (for the slowest, i.e., anddto-endddifffeenntable configuration of the QDSFormer). The Sinkformer [31] and the standard ViT implementation are taken from the original author's repository: https: htt//gittuu thub. camub.comm com/mi chaelsdr/ wwweeeddrsiinffroeeeeec sinkformers. The results on the compositional Eureka dataset [25] were generated with the ViT implementation of the original authors: https: //github. com//bocchreseacch hethh/ureeallaa eurekaMoments, The implementation of the QontOT eircuit was implemented as described in Mariella et al. [21] and, as described in the main text, adapted to digest matrix (or vector) inputs rather than scalars only.
D.2 QontOT ansatz types
Table A1: Ablation study for 2-layer QDSFormer with different circuit ansatz types and varying number of layers on FashionMNIST. Mean/std of runs.
Circuit I.
Simple
Parted
Centrosymmetric
Trotter
1
88 38.040.10 87. 87.720.22
86.420.23
87.7
8
89.9 89.8
89.4
88.420.20
Simple: This ansatz is the most generic and resembles a checkerboard structure formed by 4- parameter unit-blocks acting two qubits each [70, 71]. If all parameters are zero, it falls back to the identity. This ansatz is convenient because it is shallow in simulation but whose depth may vary depending qubit layout of the quantum hardware.
Parted: This ansatz partitions the Simple ansatz into two parts: U = U1 @ U2, where U2 operates normally, and U, is transposed and placed around the initial Bell state. This design reduces the original Simple ansatz circuit depth nearly by half, which may be more efficient on certain quantum hardware. However depending the qubit layout of the quantum hardware, it carries the potential of increased transpiled circuit depth, as the two-qubit gates may act on distant qubits necessitating additional swap gates upon transpilation, which we observed on IBM Eagle and Heron quantum processing units. Unless mentioned otherwise, we used this ansatz in all our experiments as it yields shallower circuits in simulation and the increased depth compared the Simple ansatz was negligible at tested system sizes.
Centrosymmetric: This was the predominantly used ansatz by Mariella al. [21]. is less generic, biasing toward properties of centrosymmetric matrices. Trotter: This ansatz implements a second-order Trotter decomposition [72]. Each circuit layer corresponds to a Trotter step.
D.3 Time series classification
19

---

Table A2: Micro-FI on spectra dataset 5-fold cross-validation with I-layer ViT. QDSFormer 16 circuit layers for both DSM sizes.
DSM
Softmax
Softmax,
QR
QDSFormer
Sinkhorn
8
20.30
+1.41
80.68 18
81.70 81.0640.27
81.38 80.98
16 x 16
81.55
80.9440.13
81.48
D.4
Ablation studies
Table A3: QDSFormer ablation varying the circuit layers. Exact numbers corresponding to Figure 3.
Validation Accuracy (%) MNIST
Configuration
FashionMNIST
QDSFormer- IL
73
87.7 87.7+0.22
QDSFormer-21
85.7+0.60
88.5+0..7
QDSFormer-4L
80.7
89.3
QDSFormer-8L
91.8
89.8 89.8
QDSFormer- 16L
93.8
90.0+t.115
QDSFormer-321 94.2
90.0++0.13
Baseline
VIT
92.943.76
88.9+0.12
Validation accuracy (%)
85
Operator
Softmax,*
80
Softmax,
QontOT
75
Sinkhorn
Softmax
70
1
3
VIT layers
Figure A5: MashionMNIST results of different ViT layers for different attention types.
100
Validation accuracy (%)
90
Operator
80
Softmax,2
Softmax,
70
QontOT
Sinkhorn
60
Softmax
50
ViT layers
Figure A6: MNIST results of different VIT layers for different attention types.
20

---

84.2
Validation loss (%)
84.0
83.8
83.6
83.4
1
2
3
Training interval
Figure A7: Ablation different number of QontOT trainings on MNIST in the mixed circuit optimization strategy.
D.5
Differentiable circuit
80
85
75
Validation accuracy (%)
80
Validation accuracy (%)
70
75
70
FashionMNIST
FashionMNIST
Static
Static
Differentiable
Differentiable
60
65
MNIST
MNIST
Static
Static
Differentiable
Differentiable
55
2
3 Epoch
4
5
1
3
5
7
11
Epoch
(a) QDSFormer 8 circuit layers.
(b) QDSFormer circuit layers.
Figure A8: Differentiable QontOT training the static circuit.
21

---

E
Counting DSMs
In Section E.1 we provide full analytical solution count the number of 3 x DSMs for given discretization p E N. In Section E.2 we strive to extend the analytic solution to an arbitrary E N but only provide a partial solution. Finally, in Section D.3 we provide numerical results from brute-force calculation of the number of DSMs that verified the explicit analytical solution in Section E.I.
E.1 Analytical solution for = 3
Intuition. By systematically testing all combinations from the discretized range of values, starting with an initial 2 x 2 zero matrix, each element is incrementally increased in the order Fo,0; 21,0, 20 #1,1 with the next highest value in the discretized range. Once an element reaches its maximum value, the next element is increased, and the preceding elements are reset to 0. This cycle repeats, starting again with the first element.
Explanation. Assume that n 3 and a specific discretization p E N2 are given. In this scenario, the corresponding 3 matrix possesses 4 degrees of freedom, implying that the associated submatrix has dimensions x 2. The first constraint requires that the sum of the elements in each row and each column of the matrix must exceed 1.
a specific element Gjj with i E {0, }} is chosen and assigned a value 2;, the possible values for the remaining elements in the same and column be determined.
Given that each element can assume exactly p distinct values, the total number combinations computed as sum over all p values:
f(3. p)
The possible values for the elements in the same row and column are restricted to the subset As result, the amount of submatrices that satisfy the first constraint can be expressed as:
p p-i+1
p p-i
s(3,p)
Σ
Cafk
To determine the possible values for the last element, it is necessary consider the elements eyy, The minimum number of possible values derived from these elements defines the number of candidates for the last element:
V p-1+1 1-1 min(p j+I. k+1)
1(3, Σ
Σ
Σ I
1(,j,,,1,p))
(6)
Up this point, only the first constraint has been considered. To fully satisfy the problem require- ments, matrices that violate the second constraint must be excluded. The second constraint is satisfied when the sum of the indices of all elements does not exceed p. Instead of subtracting ki,,j,,,l,p) the condition is captured using indicator function I(i, k, p), defined as:
{
ifitit 32P.
1i, k,,
(7)
otherwise.
By incorporating 1(i,j,k, k,,,,,,,,)) (),, the expression extends to:
min(p- j+1. 1+1)
f(3.p) Σ
Σ
1(1.j,,,4,p)
(8)
22

---

This can be summarized as follows:
f(3.p) = Σ
1(i,j,,l.p)
(9)
where D(p)
p. | -
1,1
5
This equation has been validated computationally for values up 43, demonstrating alignment with our empirical results.
E.2 General approximation
To determine the number of unique DSMs for a given n. E N we try to solve
[(n, p) = - Ci C2 + 612
(10)
where the first term calculates the number of DSM-candidate matrices, ei and 02 measure how often the constraints are violated and 612 is small correction term counting cases where both constraints are violated.
Generally, is very small, yet difficult to compute, thus a tight lower bound can be given with the remaining three terms. Below, we provide derivation for Cg. We leave the derivation of o₁ future work.
E.2.1 Constraint 2
Constraint 2. The sum of the n 1 inner matrix must not be below [54].
We aim to find function c2 that computes the number of violations to Constraint 2 for given n. P when exhaustively looping over all ((n-1)² candidate matrices that uniquely determine X n DSM.
An n - 1 x n matrix where each cell Fiy can take p values has
unique possible sums. These |u| (n 1) 1) +
(11)
regularly spaced from t (n- with step size of p- 1, i.e., F - i e (0.1,...,/uuu /.////// This allows conversion to integer problem (by multiplication of p - 1) and apply Stars Bars Theorem 2.
Theorem D.1. For any s,k N. the number of k-tuples (rr, ... F&k where 2e No with is equal to the number of multisets of cardinality taken from a set of size k:
( k 1-1
(
(12)
Specifically, set k = (n 1)2 and then define the set of sums that violate the constraint as
S = {s E No 0 < $ I (p 1)}. Thus [S] = (n (p 1ipp-11 1) We then compute the violations via:
(n (n-2)(p-1)
+ 102- (n (n-1)² 1)2 -
(n,p)
Σ
(13)
Unfortunately, this is only approximately correct because Theorem D.I assumes Iy No, instead we require x; E (0..,...,, 1}. Therefore, we exclude solutions where any >> p 1 through the inclusion exclusion principle as follows.
Assume that some v, p 1. We set c.j =x; (p- 1 1). Since 3; 0, we can rewrite the original sum
Σ 54
(6) p)
(14)
iET
23

---

where I is the set of indices where 2; > >p-1. 1.
Now let [ be the number of violating variables, then
mp
Σ
Σ
Zi
(15)
RET
To find the number of non-negative integer solutions to Equation 15, we can again leverage Theo- rem D.I, but now in corrected form:
( (e-mpt (=-mpt(n-1)22) if - mp > 0, (n-1))-11-
d(n, p. m, s)
(16)
otherwise.
This gives a solution for a specific sum E S and number of violations m. However, since 0 S S (n 1)?, we have all options of m and apply the to avoid over//undercountingg
principle
Thrs number of bise
100
Figure A9: Number of DSMs of fixed size with given number of discretization steps ps up to values of 4 and p 30.
1)2
(2,n,, 8)
Σ
(-1)m²
d(n. m. 8)
(17)
m
where ((n-1)²) accounts for the number of ways to choose m out of (n 1)2 variables that exceed p
Plugging Equation 17 back into the initial summation over all values s violating the constraint (see Equation 13), obtain the final formula:
(n-2) pn-2)(p-1)
2(n, Σ
s2
[8| (n- 1)²
(n (n-1)²) 1)3) 10
if mp S 0,
(-1)
(s-mpta² 2m else.
s=0 m==
m
n2 =2-2n
where [S] (n (p
D.3 Empirical results
To empirically determine the solutions f p) we implemented a brute-force algorithm by iterating over all 1)² candidate matrices of size (n - 1) x (n (n-11 1) and verifying whether the two constraints violated (see section 4).
The results are given Figure A A10 and Figure A9. Interestingly, f(n,, 2) = n!, but in general ((, p)
scales super-factorial]] in for a given

---

Tatal number of DSMs
10
66.6
24
282
2K
10K
40K
188K
381K
982K
2M
120
6X
153K
2M
22M
164M
976M
58
218
9M
40K
545M
363K
Points per Dimension
Figure A10: Number of DSMs of fixed size with a given number of discretization steps pı to values of = 10 and 10. Empty cells require >> 5 days of compute time machine with 128 cores and 128GB RAM.
Checklist information
Dataset
Reference
License
Size
MNIST
[59]
GNU
70,000
Fashion-MNIST
[60]
MIT
70,000
OCTMNIST
[61]
CC BY 4.0
109,000
PneumoniaMNNIST
[61]
CC BY 4.0
5,856
TNSST
[61]
CC BY 4.0
236,386
OrganAMNIST
[61]
CC 4.0
58,830
OrganCMNIST
[61]
CC BY 4.0
23,583
OrgASSMNIST
[61]
CC 4.0
25,211
BreastMNIST
[61]
BC 4.0
780
Compositional
[25]
GNU MIT
70,000
IR Spectra
[63]
CDLA
790,000
Table A4: Summary of datasets used, with references, licenses, and sizes.
25

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope?
Answer: [Yes]
Justification: We report empirical evidence for all claims in the abstract and introduction. Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contribu- tions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine include aspirational goals motivation long as it is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The conclusion discusses limitations of our approach imposed by the noisy nature of
current quantum hardware well as the limited scaling to large-scale datasets.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to vi- olations of these assumptions (c.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with a few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution low or images taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by review- ers grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: In the appendix, we provide full analytical solution count the number of 3 x DSMs for given discretization. We then we strive to extend the analytic solution to an arbitrary V but only find a partial solution.
Guidelines:
The answer NA means that the paper does not include theoretical results.
26

---

All the theorems, formulas, and proofs in the paper should be numbered and cross
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experi- mental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Experimental details are described in detail in the Hyperparameter subsection and the main body of the paper. Our VIT implementations relied on previous, publicly available implementations (Sinkformer [31] and Eureka [25]).
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible important, regardless of whether the code and data are provided or not.
If the contribution
dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g., in the of large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) If the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution be a way to access this model for reproducing the results or a way reproduce the model (e.g., with an open-souree dataset or instructions for how to construct the dataset).
new model (e.g., a large language model), then there should either
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access the model limited in some way (e.g.. to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: While the entire development codebase for this project unfortunately cannot be made public this point, specific parts of the code are available upon justified request.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines guides/Codeen muiless/Codeeuubiisiiiolll......
for more details.
27

---

While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:// nips. cc httpi///ggidee//Cceeeeeee wwweesuubisssionii. wwweiissssspoooioioiooo for more details.
The authors should provide instructions data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only a subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs data and code is permitted. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: There is a dedicated section about hyperparameter choices in the appendix. Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: All empirical experiments on the QDSFormer were repeatedly performed. Error bars are shown in all plots and standard deviations are given in all tables.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates). If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experi- ments?
Answer: [Yes]
28

---

Justification:
Quantum circuit execution times are explicitly studied. Moreover we provide compute resource details the hyperparameter section.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experi- mental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (c.g., preliminary or failed experiments that didn' make into the paper).
Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code Ethics https: /ttees///euurpspe httppc//pppcccccccccccco..eeee
Answer: [Yes]
Justification: Code respected.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there a special consideration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
This is piece of foundational research quantum machine learning that currently only applicable to relatively small-scale data (i.e., small images). Beyond the general societal implications of advances in quantum computing hardware, which will be vast and potentially disruptive, certainly for cryptography but potentially also for machine learning, we do not feel that there anything specific about this paper. Guidelines:
Justification:
The answer NA means that there is no socictal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address socictal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deploy- ment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
29

---

Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators. or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: A table with all datasets, citations, size and license terms are explicitly given in appendix. No data is re-distributed, license terms are respected.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use the packuge should be provided. For popular datasets, paperswithcoe licenses for some datasets. Their licensing guide can help determine the license of dataset.
com/ datasets has curated
For existing datasets that are re-packaged, both the original license the license of derived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged reach out the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the detaset/code/model part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA] Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
30

---

for Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, other labor should be paid least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non- standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required. Answer: [NA]
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https://net http://cc/ecooooeeoo/////////// what should or should not described.
31


Reviews:
[{"review_id": "FUwJxBPTZH", "reviewer": "Reviewer_gGX6", "summary": "The paper is motivated by the observation that doubly-stochastic attention is often better than row-stocahstic attention made by prior works. As there are many different ways to obtain an attention matrix, there is a question of which one is the best, which is the topic of study of the paper. A few variants are described and benchmarked: sinkhorn approximation, projecting onto the birkhoff polytope, QontOT, QR decomposition, where the metrics are expressitivity and performance on down-stream machine learning tasks.", "questions": "The reviewer would love to see the concerns in the above addressed and revise the rating.", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "### Significance\n\n1. The authors listed several motivations regarding why sinkhorn’s algorithm is not sufficient, but I do not agree with the arguments.   \n- Line 42 states that “It \\[Sinkhorn’s algorithm\\] can guarantee to find a DSMs only if the input matrix is non-negative, which is generally not the case within a Transformer”. However, in Sinkhorn’s algorithm, often included is a step that replaces each entry of the input matrix with its exponential so that we have a non-negative matrix. Notably, it is already part of the softmax operation in transformer.   \n- Line 43 to 44 states that “It \\[Sinkhorn’s algorithm\\] is non-parametric. Thus, in contrast to e.g., a NN layer, it cannot be optimized regarding which DSM should be returned.” Isn’t it standard to apply some learnable parametric operations to the input matrix before passing it to the Sinkhorn’s algorithm?   \n  - For one example, in transformers, the $XW\\_Q W\\_K^\\\\top X$ already has learnable parameters $W\\_Q, W\\_K$.   \n  - As another example, given a matrix $Y$, one can do $W \\\\odot Y$ or $W\\_1 @ Y @ W\\_2$ where the $W$’s are learnable, and pass the output to sinkhorn’s algorithm.  \n2. Experiments in section 3.1: I am not sure figure 3 is conclusive.   \n- 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.   \n- Have you tried taking discretized points from the unit sphere $\\\\{x: \\\\|x\\\\|\\_2=1\\\\}$?   \n- What if you scale the hypercube/sphere by some constant, say 2, 5, 10?  \n- 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.   \n3. Experiments in section 5:  \n- 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?   \n- Tables 1 and 2: If QontOT can have parameters, what if we also give Sinkhorn’s algorithm parameters as mentioned above? \n\n### Novelty\n\n1. There are many works related to the current paper. Clarifying connections with them or giving links to related ones would help readers better appreciate the paper.  \n   1. Obtaining a doubly stochastic matrix by projecting a matrix on the birkhoff polytope, there are existing papers on understanding the solution of such a projection as well as efficient sparse-support solvers; see \\[1\\] and references therein.  \n   2. Regarding parameterizing a doubly stochastic matrix via the element-wise squares of a unitary matrix, there are works characterizing the geometry and optimality condition in the vector case \\[2\\].\n\n### Clarity\n\n1. I do not quite understand the QontOT approach in the following sense.   \n   1. I could not find the definitions of some notations. Perhaps the paper has them but somehow i missed them. For example, on line 123, does $\\\\odot$ mean element-wise multiplication? Does $\\\\bar$ mean conjugate?   \n   2. Assuming the answers are yes, I can agree that $U \\\\odot \\\\bar{U}$ is doubly stochastic when $U$ is unitary. What is U(p; θ) and how is it computed? Since QontOT is one of the main things that the paper advocates, it would be great if the paper can be self-contained by having basic descriptions on the architecture, efficiency, benefits.   \n   3. Minor typo on line 115\\.\n\n\\[1\\] Understanding doubly stochastic clustering. ICML, 2022  \n\\[2\\] From the simplex to the sphere: faster constrained optimization using the Hadamard parametrization. Information and Inference, 2023\\.", "was_revised": true, "final_justification": "On one hand, multiple revisions have been made as a result of the rebuttal, which is productive. On the other hand, there are many corrections: For example, the correction on experiments (Q6), mathematical claims on algorithms in their paper (Q5, Q1). As a result, my confidence of the authors understanding what they claim decreases (especially when it comes to baselines). Therefore, I maintain my initial rating.", "rebuttal": "We thank the reviewer for the very solid feedback and good questions.\nBelow we provide responses point by point.\n- (Q1): Line 42 states that “It [Sinkhorn’s algorithm, SA] can guarantee to find a DSMs only if...\n    - **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.\n    This has important practical implications: a large subset of DSMs cannot be produced, namely the faces of the Birkhoff polytope.\n    This is because, in practice no input entry can ever be 0 due to the exponentiation.\n    QontOT avoids this limitation.\n\n\n- (Q2): Line 43 to 44 states that “It [Sinkhorn’s algorithm] is non-parametric. Thus,...\n    - **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.\n\n- (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.\n    - **Answer**: \n    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). \n- (Q4): Have you tried taking discretized points from the unit sphere?\n    - **Answer**: \n    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). \n    This is critical because it implies that Sinkhorn confuses cases where attention matrices are row-wise constant but each row has a unique value.\n    We will highlight this in the final manuscript.\n\n- (Q5): What if you scale the hypercube/sphere by some constant, say $2$, 5, 10?\n    - **Answer**: All algorithms are scale invariant. \n    Thus we refrained from analysing vectors above unit length.\n\n- (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.\n    - **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.\n    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.\n    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!\n    \n- (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?\n    - **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.\n- (Q8): Tables 1 and 2: If QontOT can have parameters, what if we also give Sinkhorn’s algorithm parameters as mentioned above?\n    - **Answer**: Covered in (Q2) above.\n- (Q9): There are many works related to the current paper...\n    - **Answer**: Thank you for pointing out this related literature. It is challenging to keep track of all related work. \n    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.\n    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.\n    Yet, it is not immediately obvious how such Hadamard parametrization could give rise to a parametric doubly stochastic operator.\n    We will highlight this related work in the final manuscript.\n- (Q10): I could not find the definitions of some notations. ...\n    - **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.\n- (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? ...\n    - **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.\n    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. \n    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.\n    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*)."}, {"review_id": "eXpb56cyRJ", "reviewer": "Reviewer_hvSm", "summary": "This paper proposes a hybrid classical-quantum doubly stochastic Transformer, which modifies the attention layer. Then, the authors study the expressive power and show that the proposed model can preserve more information than classical operators. This model can also match or surpass ViT on some real-world datasets. I am not an expert in this area. I will consider the review from other reviewers and the AC to make a final decision.", "questions": "Can you theoretically compare the expressive power of the proposed model and any other baseline method or models in Table 1? \nCan you empirically provide a comparison of the computation efficiency between the proposed method and baselines in Table 1?", "limitations": "NA", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths And Weaknesses:\nStrengths:\n1. The proposed method looks interesting and novel.\n2. The paper is overall well-written and easy to follow.\n\nWeaknesses:\n1. There are no experiments in the specific settings of quantum computing. The experiments are limited to small-scale datasets.\n\n2. The improvement in the performance of the proposed model is not significant. Specifically, the improvement in Table 1 is generally below 1%. In Table 2, the performance gain is clearly beyond the error bar on only three out of seven datasets.\n\n3. The theoretical analysis in Section 4 is unclear. Although the discussion there is about expressive power, there is no complete theorem presented in this section.", "was_revised": true, "final_justification": "The responses addressed my questions well. I have increased the score to 4.", "rebuttal": "Thank you for your positive comments about novelty and writing. Below we provide responses for specific questions.\n\n- (Q1): There are no experiments in the specific settings of quantum computing. The experiments are limited to small-scale datasets.\n    - **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.\n    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.\n- (Q2): The improvement in the performance of the proposed model is not significant. Specifically,...\n    - **Answer**: \n    Regarding Table 1, the performance gain is well above the standard deviation in allmost all cases. \n    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$).\n    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.\n    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\\%.\n    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.\n    \n- (Q3): The theoretical analysis in Section 4 is unclear. \n    Although...\n    - **Answer**: \n    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]).\n    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.\n    \n- (Q4): Can you empirically provide a comparison of the computation efficiency between the proposed method and baselines in Table 1?\n    - **Answer**:\n    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. \n    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."}, {"review_id": "thygMP98Gm", "reviewer": "Reviewer_3Xrp", "summary": "This paper proposes the Quantum Doubly Stochastic Transformer (QDSFormer), which replaces the standard softmax in self-attention with a variational quantum circuit (QontOT) that directly outputs doubly stochastic matrices (DSMs).\n\nUnlike Sinkhorn-based methods, which are non-parametric and approximate, QontOT is parametric and theoretically guarantees DSM outputs. The authors demonstrate improved expressivity (more diverse DSMs) and higher entropy in attention, which stabilizes training. Empirical results on small-scale vision tasks (e.g., MNIST, FashionMNIST, MedMNIST) show QDSFormer consistently outperforms standard Vision Transformers (ViT) and Sinkformers, particularly improving training stability on difficult tasks like the Eureka dataset.", "questions": "NA", "limitations": "NA", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n- Novel parametric DSM layer. Prior work enforced bistochasticity with iterative, non‑learnable operators such as Sinkhorn in Sinkformers or entropic OT; the proposed quantum circuit is the first trainable alternative and therefore enlarges the design space of attention normalisers.\n\n- Theoretical grounding: Clear analysis of expressivity advantages over Sinkhorn and QR methods (e.g., Figure 2).\n\n- Training‑stability benefit. The proposed model avoids “entropy collapse’’ and triggers Eureka moments significantly earlier than soft‑max or NormSoftmax baselines\n\n**Weaknesses**\n\n- Scale & domain scope. All positive results are on small images or 1‑D spectra; no evidence is given for ImageNet‑level problems where ViTs excel. It would be very interesting to study the proposed method on a slightly larger scale setting such as ImageNet-1k (the model size could be small scale).\n\n- 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.", "was_revised": true, "final_justification": "I would like to thank the authors for their rebuttal, and I will keep my original score.", "rebuttal": "Thank you for the positive feedback, below we elaborate on the raised concerns.\n\n- (Q1): Scale and domain scope. All positive results are on small images, ImageNet-1K...\n    - **Answer**: \n    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.\n\n- (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.\n    - **Answer**: \n    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*).\n    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."}, {"review_id": "ifeC5NK4pe", "reviewer": "Reviewer_F6sD", "summary": "This paper presents a novel way of modifying the Attention Mechanism in Transformers by replacing the softmax operator with a quantum algorithm for generating a doubly-stochastic matrix. The quantum method is a new finding in the theory of optimal transport and it is used here in the context of Transformers to achieve more stable training and increased expressiveness. Numerous experiments studying the effect of the method are performed showcasing its promise and limitations.", "questions": "1. How does QontOT exactly transform the input to the output?\n2. Are there issues of numerical stability by applying QontOT to the exponentiated output? Otherwise, what other methods of ensuring positive matrices would you consider?\n3. How do you explain that the Frobenius distance in Figure A1 does not increase with the number of shots?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths \n1. The paper addresses an important and impactful question in modern AI - the quest for a a more expressive and easily trainable Transformer. \n2. The paper's application of a DSM generating method is novel in this space and showcases the potential of using quantum algorithms in machine learning. \n3. The paper thoroughly tests the proposed ideas experimentally, exploring different connections and caveats carefully, even at the absence of well-developed theory.\n4. I liked the inclusion of a counting argument for DSMs in the quantized space. It is valuable to have theoretical insights, despite the lack of a complete understanding of the DSM generation problem either in the classical or quantum space.\n5. The experimental results seem promising - this method could suggest that striving for a DSM transformation of the attention score matrix is an important future area of research. \n\n### Weaknesses\n1. The paper is written in a slightly quantum-agnostic manner, which makes it a bit hard to read for a non-expert in quantum computing. This primarily shows up when the QontOT method is explained. I think a primer of the method and a quick explanation of how it works would be a good addition to the paper to improve clarity. Beyond affecting the flow of the paper though, it is also a matter of soundness - I would have liked to see a formal statement (maybe in the form of a lemma) of what the QontOT method guarantees in terms of input-output relationship and why it is applicable to use it with attention scores.\n2. Practically, the method has a few weaknesses, which, while acknowledged by the authors, make it difficult to tell how far the method is from actually being applicable, even in the presence of quantum-capable hardware. \n    - First, the error rate for each quantum computation is really high. The authors do mention that around $\\Omega(n^2 / \\varepsilon^2)$ samples need to be taken for reducing the error, which ultimately forces them to consider really small values of the input length $n$. \n    - On that same note, findings like Figure A1 worry me a bit: is it suggesting that the error does not diminish even when the number of shots is increased exponentially?\n    - Because the experiments are performed with really small values of $n$, I worry about the statistical significance when compared with softmax. It seems like in many experiments the method is only marginally better than softmax, which could not be the case when $n$ is larger. This could be a positive for the method also, but it means that more experiments will have to be ran somehow with larger values of $n$. Exploring algorithmic ways to reduce the effect of noise and maintain desirable qualities of the output matrices seems like an important question to suggest. \n3. I am still a bit unsure about the value of having doubly-stochastic matrices over row-stochastic matrices only in attention. The authors cite the Sinkformer paper as a justification of this, but I'm wondering if double stochasticity is widely verified as a desirable property. What does it gain us? Is it expressiveness? Stability? Of course, studying this might fall beyond the scope of the paper, but it makes for an important point on the paper's claim: \"double-stochasticity is better than row-stochasticity\". Is this actually the case?\n4. QontOT is a parametric method for double-\"stochastifying\" a matrix. But how does the result relate to the input. As far as I understand, the method starts with attention score matrix $M = QK^T$ and then applies QontOT on the exponentiated version $e^M$. How is the result interpretable in terms of $M$? For softmax the intuition is that each row is a categorical distribution on the similarity scores. Now, since QontOT is a black-box in terms of presentation, it's hard to tell what the output actually is.", "was_revised": true, "final_justification": "This paper finds an interesting connection between quantum computing and Transformer architectures, presenting a novel technique for having a doubly-stochastic matrix in the attention module. Though I was initially skeptical about the value of such a transformation, the rebuttal discussion allowed me to dive into some concurrent and recent works that further support the claim that doubly-stochastic attention matrices are desirable. Also, the paper does a good job of exploring their proposed method via a large number of empirical experiments and ablation studies.\n\nAt the same time however, I remain slightly unsatisfied in terms of the clarity of presentation of the paper. Furthermore, I remain unsure about the scalability of this approach (or approaches similar to it) to large or even moderately large context lengths, given the known volatility of quantum hardware to errors. At its current state, the method still appears impractical to me.", "rebuttal": "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!\n\n- (Q1): The paper is written in a slightly quantum-agnostic manner...\n    - **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.\n- (Q2): First, the error rate for each quantum computation...\n    - **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.\n    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.\n    \n- (Q3): On that same note, findings like Figure A1 worry me a bit...\n    - **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.\n- (Q4): Because the experiments are performed with really small values of $n$ ...\n    - **Answer**: This is a great point and we agree that more experiments are always better. \n    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.\n    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$).\n    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.\n- (Q5): I am still a bit unsure about the value of having doubly-stochastic matrices...\n    - **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.\n- (Q6): How does QontOT exactly transform the input to the output? How is the result interpretable in terms of $M$? \n    - **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. \n    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]).\n    \n- (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?\n    - **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.\n    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."}]

Author rebuttal:

Meta-review: The paper is motivated by the destabilization effect of the softmax normalization on the attention matrix and based on previous works showing that doubly stochastic can improve performance. Due to the limitation of the classic implementation of doubly stochastic matrix  (DSM) and the possibility of approximating it on a parametric quantum circuit, the paper proposes Quantum Doubly Stochastic Transformer a hybrid quantum classic transformer with variational quantum circuit for attention layers, and empirically shows that the Doubly Stochastic attention improves performance. 
Experiments are of good scale with respect to the known Quantum limitations along with a hardware implementation.

All concerns were addressed during rebuttal and non of the reviewers recommended rejection. We ask the authors to  improve the clarity of the paper based on the rebuttal and reviewers suggestions.
Decision: Accept (spotlight)