量子科技中心_量科网

设G是一个素阶p的强正则图，其连接度k≥6。该团队证明量子游走特征多项式χq(G,λ):=det(λI−UG)——其中UG是G上的铸币量子游走算子——能在同阶强正则图类中完全确定G的同构类。 证明过程分为三步：首先，该团队展示UG在ℤp上的离散傅里叶变换下呈块对角化，产生p个k×k大小的块UG(j)；其次，该团队推导出显式公式 χq(UG(j),λ)=(λ−1)(k−2)/2(λ+1)(k−2)/2(λ2−2ÂG(j)kλ+1), 由此傅里叶系数ÂG(j)可作为UG(j)中不同于±1的特征值唯一实部被还原；最后，通过离散傅里叶逆变换还原图G的连接集S，结合Turner定理（1967）即可在同构意义下识别G。这一结果表明，借助量子游走谱可在多项式时间内判定该类图的同构问题，而无需依赖Babai（2016）提出的拟多项式通用算法。