量子科技中心_量科网

社区检测是数据科学中的基础性问题。将其自然扩展到超图可捕捉超越成对交互的高阶相关性。该研究团队开发了一种超图社区检测的量子算法，相比最先进的经典算法实现了四次方量子加速，并在空间复杂度上获得超多项式优势。该算法基于Kikuchi方法，研究人员将其应用范围从张量主成分分析、p-XORSAT等已有研究问题，扩展至广义随机块模型这一更广泛的领域。为证明该方法的（近似）最优性，研究者在低阶框架中证明了匹配的对数因子下界，表明该算法实现了平滑的统计-计算权衡饱和。量子加速源于Kikuchi方法的量子化实现，其核心在于高效制备与底层社区结构相关的引导态。该工作表明，基于Kikuchi方法的量子加速具有超出预期的鲁棒性，可适用于更广泛的问题类别；研究者推测，被称为“边际阶”的参量可能是这类量子加速存在的关键特征量。