acceptodds
Under review as a conference paper at ICLR 2027

Higher-Order Token Interactions via Quantum Attention

Abstract

A single self-attention layer scores token pairs and aggregates them linearly over values, and known lower bounds put specific order- tasks out of reach for one such layer at budget . We introduce Quantum Higher-Order Attention (QHA), a shallow, hardware-realizable quantum attention head that — via data re-uploading and an all-to-all non-Clifford entangler — synthesizes order- token interactions inside the circuit and exposes them on a local single-qubit read-out. We prove two complementary results, deliberately not billed as a separation theorem because they concern different targets: no budget-limited attention layer computes the order- matching family, while a circuit in the QHA gate set realizes every order- monomial at depth ; and a barren-plateau-free trainability guarantee for the shallow local-design variant — the all-to-all variant we benchmark does show exponentially decaying gradients. Empirically we tune the classical head's learning rate, width and training length to maximize its own accuracy, an advantage we do not grant QHA, and find the gap is graded in : a tuned attention layer learns order-3 parity (), so no separation holds there; from order 4 QHA ( parameters) leads against at ; and at order 6 every attention-paradigm model we test — explicit high-order attention and a larger two-layer Transformer included — sits at chance, the only classical model in our suite that solves it being a larger MLP. A trained order-3 head runs on IBM Heron at accuracy through qubits under a disclosed shot budget, and QHA is the most compact detector on genetic epistasis, learning-parity-with-noise and graph triangle detection. Our claim is an inductive-bias advantage and an empirical learning separation against classical attention, not an exponential speedup.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
quantum machine learning, quantum attention, higher-order interactions, expressivity, barren plateaus

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_pwqdOpenReview ↗
Rating
4(+2)
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper exposes a really interesting but conceptually niche strength in a very specific type of quantum circuit over a very specific type of classical machine learning layer.

The authors present a shallow and simple quantum circuit consisting of stacked layers a) data-reupploading, b) learned ising entanglement, and c) learned local rotations. The circuit is simultaneously proven, demonstrated, and hypothesized about, but for three slightly different statements. To the authors' credit, they are unusually explicit about where those statements do and do not overlap.

A major motivation and result is that classical transformers have a hypothetical order limitation prior to the softmax. This makes sense, and I can fully understand how someone in quantum ML could notice this, given the constant contention we muddle in between quantum circuits being linear and also highly expressive. Their method performs quite well on several tasks following this regime.

The paper has clearly stated limitations in theory and results woven together with defensible claims making for a coherent and tame set of claims.

Critical strengths
  1. The circuit is simple, well studied, and easily realisable. Results on simulation and real-world hardware reflect expected differences, aside from the oddly satisfying and surpising coherence of the ising gates.
  2. The result sits in a niche that may seem unusual on the surface, but studying the mechanisms that make the well founded classical models strong and weak, especially in terms of linearity and expressivity, is critical to clawing our way towards a better understanding of how both classical and quantum systems work. Higher Order function approximation from ising layers is exciting.
  3. It was buried pretty heavily, but seeing that entanglement is necessary to get this advantage is a bigger result than you present
Critical weaknesses

This paper does not seem to necessary know what it is trying to say. A lot of the text reads defensively, like it is mostly about what it is not about, which limits the novelty. I can see a world where this paper is called "Higher Order Reupploading Ising Mixer" or something, and it becomes easier to defend and justify the stronger evidence and claims buried in the paper. Though I really do understand that metaphor to classical methods may make the nuanced ideas more digestible.

Questions for authors

What really is your strongest claim, that you absolutely wanted us readers to leave the paper having understood, and where in the paper is this claim directly supported?

This commitment to "attention," is it directly necessary to present the strengths of this paradigm, and if so, why is the connection between this "attention" and entanglement presented in 5.1.c not more confidently relevant?

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

The paper introduces Quantum Higher-Order Attention, a quantum attention head with characteristics similar to a classical attention head. It improves upon classical limitations in representingteractions by exploiting the Fourier properties of data-reuploading circuits. The authors provide theoretical evidence for local readout and a trainability guarantee for shallow circuits. Empirically, they show an increasing accuracy gap relative to classical models as the order increases. higher-order in

Critical strengths

The paper investigates a concrete intersection point between quantum computing and machine learning and its potential viability for improving upon current limitations. The authors propose a thoughtful integration of quantum hardware that exploits its advantages. Although the theoretical results seem mostly limited to the general representational advantage of data reuploading quantum routines through their connection to Fourier series, I appreciate that the authors are explicit and transparent about the scope of their theoretical claims.

Critical weaknesses

Overall, the paper's writing does not feel final and would have benefited from re-reading and thorough revision, e.g., to eliminate incomplete bullet-point-like sentence structures and overly verbose formulations, which make the current form of the paper feel more like a draft than a polished paper ready for publication.

While the motivation for the approach is briefly elaborated in the introduction, a simple (potentially graphical) example might have helped convey the necessity and importance of the proposed approach. It would also offer an opportunity for the authors to present a (potentially even drafted) very simple proof-of-concept-like result, where the precision that cannot be reached by limited classical implementations would be required. approach to the reader. This wo

Furthermore, I have concerns about the authors' claims regarding the approach's hardware realizability, which, especially for the proposed hybrid setup, does not seem accurate given current hardware capabilities and limitations.

While the theoretical results provide helpful intuition about the intended advantage of the proposed approach, a closer link to the experimental results would have been appreciated. In particular, the trainability guarantee hinging on shallow circuits, while representability of arbitrary orders seems to correlate with circuit depth, may be contradictory.

The budget definition that the comparison of classical and quantum approaches is based upon seems fundamentally flawed, especially as long as classical compute is required to simulate quantum circuits involved. Also, comparing the number of parameters might not be a fair objective to assess classical vs quantum approaches, as the parameters compared differ vastly and their implementation yield large differences in computability (a quantum parameter might be indecisively more difficult to compute than a classical parameter; reasons for this in this specific case might include the intended hybrid setup introducing overhead of repeatedly encoding and measuring data from quantum hardware, potentially over multiple shots).

Questions for authors
  • The representability of higher-order quantum circuit interactions depends on circuit depth. Yet current hardware is limited in reliability, especially as depth increases. Do the authors have any intuition or indication of this tradeoff, i.e., how deep circuits can grow and to what order current hardware can realistically represent interactions? In general, more detail on the required depth to achieve the reported result would be appreciated.
  • Are the reported results obtained on real hardware, or are they simulated for training and then transferred to hardware for final test inference only?
  • What is the anticipated advantage of restricting the approach to local readout?
  • How do the authors envision integrating their hybrid approach into current large-scale models, in the short term and in the longer term?
Reviewer_Xg3AOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies a quantum token mixer with data re-uploading, trainable all-to-all RZZR_{ZZ} couplings, local RYR_Y rotations and single-qubit readouts. It reports better learning of hidden-subset parity than several classical attention baselines at n=12n=12, particularly k=6k=6, together with synthetic epistasis/LPN experiments and hardware inference of order-3 models. Its theoretical results concern a classical MATCHk\mathrm{MATCH}_k lower bound, a basis-input Clifford parity construction in the circuit's gate set, and a local-design trainability variant. The manuscript explicitly acknowledges that these results neither form a separation theorem nor certify the trained all-to-all ansatz.

Critical strengths
  1. The benchmark contains useful controls and reports unfavorable findings: The parity/junta contrast, removal of the entangler, depth/topology comparisons and epoch-matched runs help characterize the observed effect. Table 2 includes a degree-matched HOFM that outperforms QHA at k=6k=6, while the paper discloses attribution failure, corrected data overlap and the negative triangle result. These disclosures make the empirical scope easier to assess.

  2. The hardware experiment tests a concrete trained model: Table 7 reports simulator/hardware accuracy, expectation correlations and transpiled depth for order-3 inference on 8–14 qubits, with the input count and nominal shot setting disclosed. This is useful evidence about small-scale inference robustness, although it does not validate the k=6k=6 comparative result or hardware training.

Critical weaknesses
  1. The theoretical and mechanistic interpretations still exceed the results despite the stated caveats: Section 3.3, lines 227–228, asserts order-kk terms after O(log⁡k)O(\log k) blocks, while Appendix F.2, lines 1147–1149, claims exact monomial representation in that many QHA blocks. Generating some degree-kk terms is weaker than exactly realizing a chosen parity. The gate-set witness does not establish the latter for the trained encoder and fixed block structure, as the manuscript itself acknowledges. Directly scheduling all pairwise gates of a generic dense RZZR_{ZZ} block also requires at least n−1n-1 two-qubit gate layers under the usual disjoint-gate scheduling model; LL such blocks cannot simply be reported as physical depth LL. This scheduling observation concerns the dense trained blocks, not the sparse Clifford witness.

    Theorem 2 and Appendix F.4 omit conditions needed for a positive gradient lower bound. In particular, for C=⟨Zw⟩C=\langle Z_w\rangle, a parameter θμ\theta_\mu outside the observable's backward light cone satisfies ∂C/∂θμ=0\partial C/\partial\theta_\mu=0 identically. Cerezo et al., Theorem 2 and Corollary 2, Eqs. (18)–(19) include causal-cone restrictions and require at least one input-state/observable factor to remain inverse-polynomial for the claimed bound. Furthermore, the ring experiment is not shown to satisfy the local-22-design hypothesis, so its fitted variance does not “confirm” that theorem.

    The same issue affects the empirical explanations. Appendix F.3, lines 1184–1187, claims that the classical bound responds to high-degree Fourier mass. Neither its preceding norm-based construction heuristic nor the MATCHk\mathrm{MATCH}_k lower bound establishes this relationship for parity learning. Appendix D.3 attributes failed mean-absolute-gradient attribution to missing first-order Fourier mass. Yet, for the multilinear parity extension χS(x)=∏j∈Sxj\chi_S(x)=\prod_{j\in S}x_j and every i∈Si\in S,

    =\prod_{j\in S\setminus\{i\}}x_j,\qquad \left|\frac{\partial\chi_S(x)}{\partial x_i}\right|=1 \quad\text{for }x\in\{-1,1\}^n.$$ Thus, zero first-order Fourier mass alone does not imply failed absolute-gradient attribution. The learned circuit need not realize this particular continuous extension, so the reported attribution failure may be real; it needs a different explanation. These gaps matter because an explanation of higher-order learnability is a central contribution, not just supplementary motivation.
  2. The remaining empirical advantage is too narrowly identified to establish the claimed novelty and parameter efficiency: QHA is explicitly an input-independent token mixer (Section 3.3), yet the headline conclusion is a separation “within the attention paradigm.” A matched standard data-re-uploading VQC or fixed classical token mixer is needed to isolate what the proposed architecture adds. Merely removing all entangling gates also removes cross-token communication and does not isolate a specifically quantum advantage.

    Table 2's degree-6 HOFM already achieves 1.00 versus QHA's 0.92, and the 692-parameter implementation is not a lower bound on the necessary HOFM size. From the ANOVA formulation in Blondel et al., Eqs. (5)–(6), a rank-one degree-kk component with vi=1{i∈S}v_i=\mathbf{1}_{\{i\in S\}} and ∣S∣=k|S|=k gives

    \prod_{i\in T}v_i x_i=\chi_S(x).$$ This uses $n$ weights in the degree-$k$ component with other degrees omitted; it is a representation fact, not proof that training finds an unknown support. A rank/budget sweep is therefore important for the parameter-efficiency claim. The attention baselines also need a precise implementation audit. In [Omranpour et al., Definition 3.1 and Section 4](https://arxiv.org/html/2412.02919), HOT's order is tensor-mode order, not Boolean Fourier degree; the manuscript does not specify how its 634-parameter “HOT-style” baseline maps the sequence into that construction. [Bhattamishra et al., Section 5 and Figures 5–6](https://aclanthology.org/2023.acl-long.317.pdf) report successful Transformer learning of sparse parity at $n=40$, $k=4$, including training-label noise, under different budgets and protocols. This does not refute the present $n=12$ results, but requires a more careful comparison than citing that work as evidence for an order-dependent failure threshold. The current evidence establishes a result for the tested implementations and training budgets, not a general attention limitation.
Questions for authors
  1. Please reconcile the O(log⁡k)O(\log k) block claims with the gate-set-only theorem, and give a corrected trainability statement specifying the parameter locations, initialization distribution and nonvanishing conditions. Which theoretical conclusion then applies to the exact ansatz and loss used in Table 1?
  2. Please provide the exact HOT/Performer/polynomial-attention definitions, tensorization, feature counts, kernel degrees, ranks, initialization and all selected sweep configurations. Do the k=6k=6 and parameter-efficiency conclusions survive a matched generic VQC/fixed token mixer and a HOFM rank/budget sweep?
  3. Can the eight per-seed parity records and an independent validation/test selection protocol confirm the Table 1–2 conclusions? Please also explain the Table 3 versus Table 4 k=3k=3, noise 0.10.1 discrepancy for HOFM/MLP, and substantiate the attribution explanation with a controlled probe rather than Fourier degree alone.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.