Sublinear Time Quantum Algorithm for Attention Approximation

Zhao Song, Jianfei Xue, Jiahao Zhang +1

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 (Q{K}^{\top }/\sqrt{d})$ wi…