量子科技中心_量科网

该论文介绍了一种针对图着色问题中特殊图类的高效量子计算方法。所研究的特殊图类包括对称轴仅穿过节点、仅穿过边以及同时穿过节点和边的对称与非对称图。该方法将着色矩阵数量从K^N缩减至K^(N+m)/2（对于具有m个节点对称轴的单次对称约简而言），这对实现所需量子态数量至关重要，其中K为所需颜色数，N为总节点数。其他类型图也实现了量子态数量的类似缩减。通过针对具有m个节点对称轴图类的单次对称约简，量子比特数量复杂度降低了δC_q = (9N²/8 - 3m²/8 - 3Nm/4 - N/4 + m/4)。相较于现有最优量子算法，该工作还大幅减少了门操作数量和迭代次数——例如对于含20个节点且对称轴穿过2个节点的图，迭代次数从5157次降至67次。因此，该研究提出的图着色问题求解方案所需量子比特数量显著减少。对于具有m个节点对称轴的特殊图类，算法运行时间从O(1.9575^N)降至O(1.9575^(N+m)/2)，其他类型图也获得相应改进。