量子科技中心_量科网

网络协同问题——如交通信号同步、列车调度、通信时隙分配等——需要最小化耦合系统间的成对成本。这类问题虽属NP难解，却共享一种可被量子算法利用的傅里叶稀疏结构。该研究团队提出傅里叶网络协同问题（Fourier-NC），统一了八个应用领域。对于阿贝尔群和二面体群，经典稀疏傅里叶变换在相同预言机模型下与量子算法性能相当，量子优势最多为多项式级。真正的性能分离出现在对称群Sk场景：当类函数成本存在非平凡极小值时，可获得条件性k!→poly(k)的超指数级加速。若极小化共轭类的结构可确定，则该问题属于NP∩BQP且条件性不在P内（推论6.5），使其与整数分解和图同构问题同处中间复杂度层级。研究人员将阿贝尔指数α(G)=[G:Amax]形式化为调控量子-经典差距的结构不变量，并识别出三阶段复杂度分类：阿贝尔（α=1，经典sFFT足够）、近阿贝尔（α=dmax，多项式优势）和强非阿贝尔（α>>dmax，超指数优势）。