量子科技中心_量科网

给定查询矩阵Q、键矩阵K和值矩阵V∈ℝ^(n×d)，注意力模块定义为Att(Q,K,V)=D^(-1)AV，其中A=exp(QK^⊤/√d)（逐元素应用指数函数），D=diag(A𝟙_n)。该模块是现代Transformer和大语言模型的核心组件，但显式构造softmax矩阵D^(-1)A需要Ω(n²)时间复杂度，这促使研究者提出多种近似方案——通过稀疏化或低秩分解将运行时间降至Õ(nd)。该研究团队提出一种量子数据结构，仅需对Q、K、V进行行查询即可近似获取Att(Q,K,V)的任意行。该算法预处理这些矩阵的时间复杂度为Õ(ϵ^(-1)n^(0.5)(s_λ^2.5 + s_λ^1.5d + α^0.5d))，其中ϵ为目标精度，s_λ是由Q和K定义的指数核的λ统计维度，α衡量V的行失真度（其上限为d/srank(V)，即V的稳定秩）。每次行查询可在Õ(s_λ^2 + s_λd)时间内完成。据研究人员所知，这是首个能以相对于n的亚线性时间复杂度近似注意力矩阵各行的量子数据结构。该工作基于三项关键技术：针对指数核的量子Nyström近似、用于计算D的量子多元均值估计，以及与V相乘时的量子杠杆得分采样。