俄罗斯科学家打破了谷歌的量子算法

来自Skolkovo科技学院(Skoltech)的科学家,莫斯科,俄罗斯私营研究生研究所,发现和量化了谷歌发起的狂野采用的量子方法中似乎是一个基本限制。

谷歌正在赛车开发使用量子机械效应的量子增强处理器,从而大大提高了可以处理数据的速度。

在近期,谷歌已经设计了新的量子增强算法,该算法在存在现实噪音时运行。所谓的量子近似优化算法或QAOA短,是现代驱动抗噪声量子增强算法开发的基石。

谷歌采取的庆典方法引发了巨大的商业利益,并点燃了全球研究界探索了新颖的应用。然而,实际上仍然符合谷歌Qoa算法的最终性能限制。

来自Skoltech的深量实验室的一个科学家团队,占据了这一当代挑战。由Jacob Biamonte教授领导的全Skoltech团队发现并量化了谷歌发起的疯狂采用的方法中所似乎是一个基本限制。

该图表表示随机生成的MAX-SAT情况下的固定深度Qoa电路的性能(QAOA Optima和精确Optima之间的差异,随着问题密度的增加。虽然更高的深度版本实现了更好的表现,但它们仍然表现出可达性缺陷。

报告物理审查信件,作者详细介绍了所谓的可达性赤字的发现 - 作者展示了这些缺陷如何对Qoa甚至近似问题的能力来实现基本限制。

SKOLTECH团队的调查结果报告了对变分QAOA量子算法的清晰限制。由于内部量子到典型反馈过程,QAOA和其他变分量子算法已经证明极难分析了使用已知的数学技术。即,给定的量子计算只能运行固定的时间。在该固定时间内,可以执行固定数量的量子操作。QAOA寻求通过形成越来越好的近似的序列来迭代地利用这些量子操作以最小化目标函数。该研究在此过程中讨论了新的限制。

作者发现,QAOA对任何固定深度量子电路近似最佳解决方案的能力基本上取决于“密度”问题。在称为MAX-SAT的问题的情况下,所谓的密度可以定义为问题约束与可变计数的比率。这有时被称为子句密度。

作者发现了高密度的问题实例,其最佳解决方案无法近似,无论算法的运行时,不管算法。

参考:“量子近似优化的可达性缺陷”,V.Pherathong,M.E.S.S. Morales和J.D. Biamonte,3月5日2020年3月5日,物理评论信件.DOI:
10.1103 / physrevlett.124.090504

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。