量子算法在补集采样任务上胜过经典工具

Source: Slashdot

量子算法在补集抽样任务上优于经典方法

来自 Quantinuum（英国）和 QuSoft（荷兰）的研究团队开发了一种量子算法，在 补集抽样 任务上比任何已知的经典算法都要高效得多。该工作展示了在样本复杂度——解决问题所需的样本数量——上的可证明且可验证的 量子优势。

关键发现

• 该算法针对一种特定的抽样问题，称为 补集抽样。
• 它所需的样本数量远低于任何经典方法，确立了明确的量子优势。
• 这种优势既是 可证明的（理论保证），也是 可验证的（可通过实验确认）。

发表详情

研究结果已发表在 Physical Review Letters 上。
阅读论文请点击此处: https://journals.aps.org/prl/abstract/10.1103/q55v-wm7y

合著者 Harry Buhrman 的评论

“我们在进行另一个项目时偶然发现了这项工作的核心结果，”论文合著者 Harry Buhrman 在接受 Phys.org 采访时说。 “我们有一组项目和两种量子态：一种由一半的项目构成，另一种由剩余的一半构成。尽管这两种状态本质上是不同的，我们却证明量子计算机很难判断它们到底是哪一种。令人惊讶的是，我们随后意识到，将一种状态转换为另一种状态始终很容易，因为一个简单的操作就能在它们之间切换。”