{"id":"arxiv/2602.00874","url":"https://arxiv.org/abs/2602.00874","tags":["quant-ph","cs.DS","cs.LG"],"score":0,"title":"Sublinear Time Quantum Algorithm for Attention Approximation","domain":"quant-ph","source":"arxiv","authors":["Zhao Song","Jianfei Xue","Jiahao Zhang","Lichen Zhang"],"reviews":0,"subject":"quant-ph","summary":"Given the query, key and value matrices $Q, K, V\\in \\mathbb{R}^{n\\times d}$, the attention module is defined as $\\mathrm{Att}(Q, K, V)=D^{-1}AV$ where $A=\\exp(QK^\\top/\\sqrt{d})$ with $\\exp(\\cdot)$ applied entrywise, $D=\\mathrm{diag}(A{\\bf 1}_n)$. The attention module is the backbone of modern transformers and large language models, but explicitly forming the softmax matrix $D^{-1}A$ incurs $Ω(n^2)$ 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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-01-31","reactions":{}}