Abstract
Given the query, key and value matrices Q, K, V∈ R^n× d, the attention module is defined as Att(Q, K, V)=D⁻¹AV where A=exp(QK/√d) with exp(·) applied entrywise, D=diag(A 1_n). The attention module is the backbone of modern transformers and large language models, but explicitly forming the softmax matrix D⁻¹A incurs Ω(n²) time, motivating numerous approximation schemes that reduce runtime to 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 O( ε⁻¹ n^0.5 ( s_λ^2.5 + s_λ^1.5 d + α^0.5 d ) ) 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/ srank(V), the stable rank of V. Each row query can be answered in O(s_λ² + 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.