量智信息中心_量科网

该研究工作评估了对称局部算法在环图上的割表现。在深度 \(p\) 下，无法观测整张图的此类算法预期最多切割 \((2p+1)/(2p+2)\) 比例的边。该工作证明了量子近似优化算法（QAOA）能够达到这一数值，从而证实了Farhi、Goldstone和Gutmann长期以来的猜想。有趣的是，该工作并未通过寻找最优参数来完成证明，而是展示了该问题等价于寻找一对次数至多为 \(2p-1\) 的最优洛朗多项式。这一进展得益于将单量子比特上的QAOA问题重新表述为量子信号处理的语言。