Higher-Order Token Interactions via Quantum Attention

Jian Xu; Chao Li; Delu Zeng; John Paisley; Qibin Zhao

quant-phJun 10, 2026

Higher-Order Token Interactions via Quantum Attention

Authors: Jian Xu, Chao Li, Delu Zeng, John Paisley, Qibin Zhao

Organizations: 1RIKEN iTHEMS · 2RIKEN AIP · 3South China University of Technology · 4Columbia University

Abstract

Standard dot-product self-attention computes, in a single layer, only pairwise (order-2) interactions between tokens; representing a generic order- $k$ interaction is known to require either super-quadratic resources in one layer or composition across depth. We introduce \textbf{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- $k$ token interactions inside the circuit and exposes them through a local single-qubit read-out. We prove (i) an expressivity separation: any single standard self-attention layer with embedding dimension $m$ , $H$ heads and $p$ -bit precision satisfying $mHp=o(N/\log\log N)$ cannot represent the order- $k$ correlation family that one QHA head represents with circuit depth $O(\log k)$ ( $O(k)$ two-qubit gates); and (ii) a trainability guarantee for its local-design instantiation: with a local read-out and $O(\log n)$ depth the gradient variance is $Ω(1/\mathrm{poly}(n))$ (no barren plateau), which we confirm empirically -- while being explicit that the more expressive all-to-all instantiation we benchmark is trained empirically and shows exponentially decaying gradients. Empirically, at a $6.5\times$ smaller parameter budget, QHA generalizes hidden-subset parity of every order $k\le6$ from disjoint inputs, whereas the larger classical attention head collapses past order~2; consistent with theory, the size of the advantage tracks the target's Fourier degree - largest for parity and shrinking when low-order structure is present. As an application, QHA serves as a compact high-order interaction detector across three domains - genetic epistasis, learning-parity-with-noise, and graph triangle detection - reaching the noise ceiling at the smallest parameter budget where field-standard linear methods fail.

Explore similar work

Sep 3, 2026cs.CC

The Head Complexity of Boolean Functions in Single-Layer Attention

What can a single layer of self-attention compute? We study head complexity: the minimum number of attention heads required to compute a function in a one-layer attention-only model. We establish an exact hierarchy under this measure:

k

heads compute

k

-bit parity but cannot compute

(k+1)

-bit parity. The lower bound is unconditional in the two resources a transformer might otherwise exploit; it holds at unbounded embedding dimension and unbounded numerical precision. The proof rests on an alternating-sum obstruction: after clearing the softmax denominators, every monomial in the resulting decision polynomial omits at least one of the

k+1

input bits, forcing its correlation with parity to vanish. The same obstruction yields lower bounds for related tasks, including the well-studied multi-hop induction-head task. We also establish compactness bounds for embedding dimension and numerical precision. Specifically, a compactness theorem shows that any function computable at all can be computed with embedding dimension and precision bounded by the discrete data of the task, namely, head count, alphabet size, and length. Thus, potentially unbounded dimension or precision provably cannot substitute for heads. Finally, we derive nearly matching universal bounds for general binary functions:

2^n

heads suffice to compute every

n

-bit binary function, with one head per monomial in its multilinear expansion, while a counting argument shows almost all such functions require

Ω(2^n/n^2)

heads. This lower bound matches the upper bound to within a

\operatorname{poly}(n)

factor, even when dimension and precision are unbounded. Together, these results characterize head requirements for Boolean computation in this model.

Rajmohan Rajaraman, Ravi Sundaram, Amanuel Tesfaye

Multi-Head Self-Attention Model Complexity Universality

Ask PDF

Aug 7, 2026cs.LG

Faster Query-Key Learning Sharpens Attention in Self-Attention Models

A standard self-attention layer consists of two interacting circuits: the query-key circuit that governs attention allocation, and the output-value circuit that maps attended representations to predictions. Collapsed and factorized parameterizations of the query-key and output-value circuits lead to qualitatively different attention patterns. In particular, some parameterizations give sharper attention to task-relevant tokens, at a similar training loss. We analyze how the parameterizations of these circuits shape the parameter trajectories in single-layer self-attention models trained for next-token prediction. Through gradient-flow analysis, we show that factorization induces implicit rescaling of the two circuits' learning rates. We derive closed-form dynamics showing that output-value and query-key parameters move along a line, with relative speeds determined by their learning rates. Faster query-key learning relative to output-value learning thus produces sharper attention, as the model compensates for slower output-value learning by increasing attention mass on relevant tokens. Experiments show that differences in the relative learning rates of the two circuits govern attention concentration. This improves attention interpretability proxies while maintaining comparable predictive performance.

Rahul Vashisht, Harish G. Ramaswamy

Softmax Attention Model Interpretability

Ask PDF

Jun 18, 2026cs.LG

Grouped Query Experts: Mixture-of-Experts on GQA Self-Attention

Self-attention is central to Transformer performance and is often the most expensive part of the Transformer at long context lengths because its pairwise token interactions scale quadratically with sequence length. Standard dense attention also applies the same set of attention heads to every token regardless of token difficulty or information content. This uniform activation can waste compute, especially as sequences grow longer and attention cost increases rapidly. We propose Grouped Query Experts (GQE), a mixture-of-experts layer on top of grouped-query attention (GQA). Within each GQA group, a router selects k query-head experts per token while all key-value (KV) heads remain dense and unchanged. Thus, GQE keeps the KV cache benefits of GQA and reduces only the active query-head computation. On a fixed 30B token budget at the 250M parameter scale, GQE matches the all-active GQA baseline in downstream accuracy while activating half the query heads per token.

Vishesh Tripathi, Abhay Kumar

Transformer Architectures Mixture-of-Experts Models Experts

Ask PDF