Sublinear Time Quantum Algorithm for Attention Approximation

Given the query, key and value matrices Q, K, Vin mathbb{R}^{ntimes d}, the attention module is defined as Att(Q, K, V)=D^-1AV where A=exp\(QK^→p/sqrt{d}\) with exp\(cdot\) applied entrywise, D=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^-1A incurs Ω\(n²\) 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 widetilde{O}left\(ε^-1 n^0.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 widetilde{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öm approximation of the exponential kernel, quantum multivariate mean estimation for computing D, and quantum leverage score sampling for the multiplication with V.