# Sublinear Time Quantum Algorithm for Attention Approximation

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 64 of its 86 references that are in the map.
- First posted on arXiv 31 Jan 2026.

## Builds on (most cited first, 30 of 64)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [End-to-End Object Detection with Transformers](https://mlsanity.com/paper/2005.12872/) (2020)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [XLNet: Generalized Autoregressive Pretraining for Language Understanding](https://mlsanity.com/paper/1906.08237/) (2019)
- [Informer: Beyond Efficient Transformer for Long Sequence Time-Series Forecasting](https://mlsanity.com/paper/2012.07436/) (2020)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [TinyBERT: Distilling BERT for Natural Language Understanding](https://mlsanity.com/paper/1909.10351/) (2019)
- [Efficiently Scaling Transformer Inference](https://mlsanity.com/paper/2211.05102/) (2022)
- [Efficient Content-Based Sparse Attention with Routing Transformers](https://mlsanity.com/paper/2003.05997/) (2020)
- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [Attention-Based Models for Speech Recognition](https://mlsanity.com/paper/1506.07503/) (2015)
- [Random Feature Attention](https://mlsanity.com/paper/2103.02143/) (2021)
- [Attention Mechanisms in Computer Vision: A Survey](https://mlsanity.com/paper/2111.07624/) (2021)
- [Reducing Transformer Key-Value Cache Size with Cross-Layer Attention](https://mlsanity.com/paper/2405.12981/) (2024)
- [Keyformer: KV Cache Reduction through Key Tokens Selection for Efficient Generative Inference](https://mlsanity.com/paper/2403.09054/) (2024)
- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [HyperAttention: Long-context Attention in Near-Linear Time](https://mlsanity.com/paper/2310.05869/) (2023)
- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [q-means: A quantum algorithm for unsupervised machine learning](https://mlsanity.com/paper/1812.03584/) (2018)
- [LoRC: Low-Rank Compression for LLMs KV Cache with a Progressive Compression Strategy](https://mlsanity.com/paper/2410.03111/) (2024)
- [SMYRF: Efficient Attention using Asymmetric Clustering](https://mlsanity.com/paper/2010.05315/) (2020)
- [RocketKV: Accelerating Long-Context LLM Inference via Two-Stage KV Cache Compression](https://mlsanity.com/paper/2502.14051/) (2025)

## Built on by (most cited first, 1 of 1)

- [Structured Redundancy Modeling for Efficient Visual Token Pruning in High-Resolution MLLMs](https://mlsanity.com/paper/2607.23046/) (2026)

## Abstract (arXiv)

Given the query, key and value matrices Q, K, V∈ ℝn× d, the attention module is defined as Att(Q, K, V)=D-1AV where A=exp(QK^top/√d) with exp(·) applied entrywise, D=diag(Abf 1n). The attention module is the backbone of modern transformers and large language models, but explicitly forming the softmax matrix D-1A incurs Omega(n2) time, motivating numerous approximation schemes that reduce runtime to widetilde O(nd) via sparsity or low-rank factorization. We propose a quantum data structure that approximates any row of Att(Q, K, V) using only row queries to Q, K, V. Our algorithm preprocesses these matrices in widetildeOleft( ε-1 n0.5 left( sλ2.5 + sλ1.5 d + α0.5 d right) right) time, where ε is the target accuracy, sλ is the λ-statistical dimension of the exponential kernel defined by Q and K, and α measures the row distortion of V that is at most d/rm srank(V), the stable rank of V. Each row query can be answered in widetildeO(sλ2 + sλ d) time. To our knowledge, this is the first quantum data structure that approximates rows of the attention matrix in sublinear time with respect to n. Our approach relies on a quantum Nystr"om approximation of the exponential kernel, quantum multivariate mean estimation for computing D, and quantum leverage score sampling for the multiplication with V.