量子科技中心_量科网

图同构问题探究的是两个图在顶点重标号后是否相同。尽管该精确问题存在拟多项式时间经典算法，但分子比较、噪声网络分析和模式识别等众多应用需要更灵活的结构相似性定义。该研究团队针对源自Erdős-Rényi分布𝒢(n,1/2)的n顶点图，研究近似图同构测试的量子查询复杂度——若两图最多通过k次边编辑即可成为同构图，则视为近似同构。 该工作提出基于MNRS量子行走搜索的算法，通过在输入图的乘积图Γ(G,H)上进行搜索。当图近似同构时，量子行走能检测出属于稠密近同构匹配集的顶点对；候选配对通过局部一致性传播重建，并借助Grover加速的一致性检验进行验证。该团队证明该方法可实现𝒪(n³/²logn/ε)查询复杂度，其中ε控制近似阈值。研究同时给出常数近似情况下Ω(n²)的经典下界，确证了查询模型中真实的量子多项式加速优势。 该框架可拓展至基于图拉普拉斯特征值的谱相似性度量，以及加权图和属性图。在量子模拟器上对20顶点以内图结构的小规模仿真实验表明，该方案与近期量子设备具有兼容性。