# Higher-Order Token Interactions via Quantum Attention

arXiv: https://arxiv.org/abs/2606.11673 · HTML: https://mlsanity.com/paper/2606.11673/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 24 references that are in the map.
- First posted on arXiv 10 Jun 2026.

## Builds on (most cited first, 18 of 18)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Barren plateaus in quantum neural network training landscapes](https://mlsanity.com/paper/1803.11173/) (2018)
- [The effect of data encoding on the expressive power of variational quantum machine learning models](https://mlsanity.com/paper/2008.08605/) (2020)
- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Transformer Dissection: A Unified Understanding of Transformer's Attention via the Lens of Kernel](https://mlsanity.com/paper/1908.11775/) (2019)
- [Inductive Biases and Variable Creation in Self-Attention Mechanisms](https://mlsanity.com/paper/2110.10090/) (2021)
- [The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks](https://mlsanity.com/paper/2202.08658/) (2022)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [Absence of Barren Plateaus in Quantum Convolutional Neural Networks](https://mlsanity.com/paper/2011.02966/) (2020)
- [Better than classical? The subtle art of benchmarking quantum machine learning models](https://mlsanity.com/paper/2403.07059/) (2024)
- [Does provable absence of barren plateaus imply classical simulability?](https://mlsanity.com/paper/2312.09121/) (2023)
- [Transformers, parallel computation, and logarithmic depth](https://mlsanity.com/paper/2402.09268/) (2024)
- [A quantum-inspired classical algorithm for recommendation systems](https://mlsanity.com/paper/1807.04271/) (2018)
- [Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functions](https://mlsanity.com/paper/2211.12316/) (2022)
- [Quantum Vision Transformers](https://mlsanity.com/paper/2209.08167/) (2022)
- [Quantum Doubly Stochastic Transformers](https://mlsanity.com/paper/2504.16275/) (2025)
- [Do Quantum Transformers Help? A Systematic VQC Architecture Comparison on Tabular Benchmarks](https://mlsanity.com/paper/2604.23931/) (2026)

## Abstract (arXiv)

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 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/loglog 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 Omega(1/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× smaller parameter budget, QHA generalizes hidden-subset parity of every order k≤6 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.