科学家们打破了谷歌的量子算法的神话

谷歌正在竞相开发量子增强处理器，利用量子力学效应来提高数据处理的速度。在短期内，谷歌已经设计出新的量子增强算法，可以在真实的噪声中工作。所谓的量子近似优化算法(简称QAOA)，是现代朝着容错量子增强算法发展的基石。

谷歌在QAOA采用的著名方法已经引起了广泛的商业兴趣，并点燃了全球研究社区探索新应用的热情。然而，我们对谷歌的QAOA算法的最终性能限制知之甚少。

来自Skoltech深量子实验室的一组科学家接受了这一当代挑战。由Jacob Biamonte教授领导的all-Skoltech团队发现并量化了谷歌广泛采用的方法的一个基本限制。

在《物理评论快报》的报道中，作者详细描述了所谓的可达性缺陷的发现——作者表明，这些缺陷对QAOA的能力造成了根本的限制，甚至无法近似地解决某个问题，例如。

Skoltech团队的发现报告了变分QAOA量子算法的明显局限性。QAOA和其他变分量子算法已经被证明是非常困难的分析使用已知的数学技术，由于内部量子到经典的反馈过程。也就是说，一个给定的量子计算只能运行一段固定的时间。在这个固定的时间内，可以执行固定数量的量子操作。QAOA试图通过形成一个不断优化的近似序列来迭代地利用这些量子运算来最小化一个目标函数。这项研究对这一过程提出了新的限制。

作者发现QAOA对于任何固定深度量子电路的近似最优解的能力从根本上依赖于问题的“密度”。在MAX-SAT问题中，所谓的密度可以定义为问题约束与变量计数之比。这有时被称为子句密度。

作者发现了存在问题的高密度实例，这些实例的最优解无法近似地保证成功，无论算法的运行时间如何。