Higher-Order Token Interactions via Quantum Attention

A single self-attention layer scores token pairs and aggregates them linearly over values, and known lower bounds put specific order-$k$ tasks out of reach for one such layer at budget $mHp=o(N/\log \log N)$. 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-$k$ 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-$k$ matching family, while a circuit in the QHA gate set realizes every order-$k$ monomial at depth $O(\log k)$; 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 $k$: a tuned attention layer learns order-3 parity ($0.93$), so no separation holds there; from order 4 QHA ($296$ parameters) leads $1.00/1.00/0.92$ against $0.74/0.58/0.49$ at $k=4/5/6$; and at order 6 every attention-paradigm model we test — explicit high-order attention and a $16\times$ larger two-layer Transformer included — sits at chance, the only classical model in our suite that solves it being a $31\times$ larger MLP. A trained order-3 head runs on IBM Heron at $\ge 95\%$ accuracy through $14$ 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.