量子科技中心_量科网

该团队识别出了一个尖锐的交互度阈值，用于经典模拟具有 \(2\)-局域代价函数的量子近似优化算法（QAOA）。在度为 \(3\) 时，从深度为 \(1\) 的 QAOA 中以较小的乘法误差进行经典采样，会将多项式层级坍缩至其第三层。在度为 \(2\) 时，对 \(n\) 个量子比特上深度为 \(p\) 的 QAOA 进行精确经典采样，其运行时间为 \(n^{O(1)}\)，只要 \(p = O(\log n)\)。这些困难的度为 \(3\) 的实例具有可轻易优化的代价函数，因此采样困难性本身并不意味着量子优化优势。