美国实验室诞生两个新量子算法，量子计算应用范围正式扩大

量子计算有望利用量子力学特性，构建出性能强大的机器。但事实证明，人们对于它的应用范围还比较模糊。

为了充分发挥量子计算的潜力，科学家们需要从零开始，为量子计算机开发程序或算法，以执行简单任务，比如分解质因数。然后，这些简单的算法可以充当更为复杂的计算构件。

美国能源部 (DOE) 费米实验室量子研究所的博士后研究助理Prasanth Shyamsundar，在其发表的论文中宣布了两种新算法[2]。这两个算法在该领域现有工作的基础上，进一步丰富了量子计算机能够解决的问题类型。

Shyamsundar表示，量子计算机可以更快完成一些特定任务，而他对于这些特定任务具体是什么十分感兴趣。他开发的两个新的算法可以执行通用任务，他也希望人们可以围绕它们设计出更多算法。

Shyamsundar的量子算法，在未排序的数据集合中搜索特定条目时非常有用。假设有一叠100张黑胶唱片，要求计算机在这叠唱片中，找到一张爵士乐唱片。

经典计算中，计算机需要根据给定的一组搜索条件，检索每一张单独的唱片，然后决定是否是我们需要的唱片。

如果该爵士乐唱片是在这叠唱片的前列，那么可能几次检索之后就可以找到它。但如果在底部，那就需要近100次检索。平均来看，一台经典计算机需要通过大约50次检索以找到正确的唱片。

而量子计算机更快，因为它有能力利用量子叠加效应，一次性检索所有唱片。在这种特性下，量子计算机仅需大约10次检索就能找到爵士乐唱片 (这叠唱片数量的平方根)。这种现象被称为“量子加速”，是量子计算机独特的信息存储方式的结果。

量子叠加是单个状态的组合，每个状态在测量时都有自己的显示概率。但测量的过程不一定会将叠加态坍缩为我们寻找的值，取决于与正确状态相关联的概率。

图1｜处于叠加态的量子比特（来源：Jerald Pinson）

也就是说，如果创造一个叠加态并对其进行测量，不一定会得出想要的正确答案，它只会提供一个唱片的信息。

为了充分利用量子计算机提供的加速效果，科学家们必须以某种方式提取出他们正在寻找的正确唱片。如果他们不能，那么量子计算机就会丧失所谓的量子优势。

幸运的是，科学家们在近25年前就开发出了一种算法，会根据一组给定的搜索标准，在叠加态上执行一系列操作，从而放大某些单个状态的概率，抑制其他状态的概率。这意味着在测量时，叠加态很有可能会坍缩成他们正在寻找的状态。

但这种算法的局限性在于，它只能应用于布尔 (Boolean) 类型的数据，或者是可以用是/否输出进行查询的情况，例如在一叠唱片中搜索爵士乐专辑。

图2｜布尔方案（来源：Prasanth Shyamsundar）

非布尔输出的场景下就颇具挑战性，由于音乐流派并没有精确的定义，所以只能让计算机根据专辑的“爵士程度”来给它们打分。也就是说，科学家需要先设定一个阈值，假定阈值为5，那么低于5的专辑都不是爵士乐，而5-10之间的专辑都是爵士乐。

图3｜非布尔方案（来源：Prasanth Shyamsundar）

而在此之前，科学家们不得不将这样的非布尔问题转换为布尔输出问题。但Shyamsundar扩展了这种计算方式，无需再进行布尔转换，他将这种新算法称为“非布尔量子幅度放大算法”(non-Boolean quantum amplitude amplification algorithm)。

Shyamsundar表示，如果一个问题需要是/否的答案，那么新的算法和之前的就没有任何区别。但现在许多问题可以更自然地以分数方式来解决，无需依赖于是/否。

论文中介绍的第二种算法，被称为量子平均值估计算法。这种算法允许科学家估计所有唱片的平均等级，也就是说，可以评估这一叠唱片整体的“爵士程度”。

这两种算法都不用把场景还原成只有两种类型输出的计算，而是允许一系列的输出，以比经典计算方法更快的量子速度更准确地描述信息。Shyamsundar还计划在量子机器学习中利用这些新算法。

这样的过程看似原始而抽象，但它们为量子未来更复杂、更有用的任务奠定了重要基础。在物理学领域，新引入的算法最终可能会让科学家在某些实验中更快地达到目标灵敏度。

封面：

Quanta Magazine

引用：

[1]https://news.fnal.gov/2021/04/new-computing-algorithms-expand-the-boundaries-of-a-quantum-future/

[2]https://arxiv.org/abs/2102.04975

声明：此文出于传递更多信息。若有错误或侵权，请联系

---

延 伸 阅 读