Sublinear Time Quantum Algorithm for Attention Approximation

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.