量子计算机有望以比传统计算机快得多的速度解决某些问题，但只有少数几个例子能实现如此显著的加速，例如Shor 的因式分解算法和量子模拟。在这几个例子中，大多数涉及模拟本质上是量子力学的物理系统——这是量子计算机的自然应用。但是模拟本质上不是量子的系统呢？量子计算机能为此提供指数级优势吗？
在《物理评论 X》（PRX）上发表并在计算机科学基础研讨会（FOCS 2023）上发表的 “模拟耦合经典振荡器的指数量子加速”中，我们报告了一种新的量子算法的发现，该算法为模拟耦合的经典谐振子提供了指数优势。这些是自然界中最基本、最普遍的系统，可以描述无数自然系统的物理特性，从电路到分子振动再到桥梁力学。我们与麦考瑞大学的 Dominic Berry 和多伦多大学的 Nathan Wiebe 合作，发现了一种映射，可以将任何涉及耦合振荡器的系统转换为描述量子系统时间演化的问题。在某些约束条件下，用量子计算机解决这个问题的速度比用传统计算机快得多。此外，我们使用这种映射来证明任何可以通过量子算法有效解决的问题都可以重新转化为涉及耦合振荡器网络的问题，尽管它们的数量呈指数级增长。除了解锁量子计算机以前未知的应用之外，这一结果还提供了一种通过纯粹推理经典系统来设计新量子算法的新方法。
模拟耦合振荡器
我们考虑的系统由经典谐振子组成。单个谐振子的一个例子是附在弹簧上的物体（例如球）。如果你将物体从其静止位置移开，则弹簧将产生一个恢复力，将物体推向或拉向相反方向。该恢复力使物体来回振荡。
谐振子的一个简单例子是通过弹簧连接到墙壁的质量。
现在考虑耦合谐振子，其中多个质量块通过弹簧相互连接。移动一个质量块，它将引发一波振荡，脉冲通过系统。正如人们所预料的那样，在传统计算机上模拟大量质量块的振荡变得越来越困难。
可以用量子算法模拟的由弹簧连接的质量示例系统。
为了能够模拟大量耦合谐振子，我们提出了一种映射，将所有质量和弹簧的位置和速度编码到量子比特系统的量子波函数中。由于描述量子比特系统波函数的参数数量会随着量子比特数量的增加而呈指数增长，我们可以将N 个球的信息编码到仅约 log( N ) 个量子比特的量子力学系统中。只要对系统有一个紧凑的描述（即质量和弹簧的属性），我们就可以演化波函数以在以后了解球和弹簧的坐标，而这比我们使用简单的经典方法模拟球和弹簧所需的资源要少得多。
我们证明了，某一类耦合经典振荡器系统可以在量子计算机上高效模拟。但仅凭这一点并不能排除存在某种尚未知晓的巧妙经典算法的可能性，这种算法在资源利用方面同样高效。为了证明我们的量子算法比任何可能的经典算法实现了指数级加速，我们提供了另外两个证据。
胶合树问题和量子预言机
对于第一个证据，我们使用映射来证明量子算法可以有效地解决一个著名的图形问题，该问题被称为胶合树问题，该问题已知很难用经典方法解决。该问题需要两棵分支树（一个图，其每个节点都分支到另外两个节点，类似于树的分支路径）并通过一组随机边将它们的分支粘合在一起，如下图所示。
粘合树问题的直观表示。这里我们从标记为 ENTRANCE 的节点开始，并允许本地探索图，该图是通过随机粘合两个二叉树获得的。目标是找到标记为 EXIT 的节点。
胶合树问题的目标是尽可能高效地找到出口节点——第二棵树的“根”。但胶合树的节点和边的确切配置最初对我们是隐藏的。要了解系统，我们必须查询一个oracle，它可以回答有关设置的具体问题。这个 oracle 允许我们探索树木，但仅限于本地。几十年前，人们已经证明，在传统计算机上找到出口节点所需的查询次数与N的多项式因子（即节点总数） 成正比。
但将其重新定义为球和弹簧的问题，我们可以将每个节点想象成一个球，将两个节点之间的每个连接想象成一个弹簧。拔掉入口节点（第一棵树的根），振动就会在树中脉动。到达出口节点只需要与树的深度成比例的时间——比N指数小。因此，通过将粘合树的球和弹簧系统映射到量子系统并在该时间内演化它，我们可以检测到出口节点的振动，并以比使用传统计算机快得多的速度确定它。
BQP完备性
我们的算法比任何可能的经典算法效率高出指数级的第二个也是最有力的证据是通过检查量子计算机可以有效解决的问题集（即可在多项式时间内解决）而揭示的，这些问题集称为有界误差量子多项式时间或 BQP。BQP 中最难的问题称为“BQP 完全”。
虽然人们普遍认为，有些问题量子算法可以有效解决，而经典算法却不能，但这一点尚未得到证实。因此，我们能提供的最好证据是，我们的问题是 BQP 完全的，也就是说，它是 BQP 中最难的问题之一。如果有人能找到一种有效的经典算法来解决我们的问题，那么量子计算机有效解决的每个问题都可以用经典算法解决！即使是因式分解问题（寻找给定大数的素因数），它构成了现代加密的基础，并由 Shor 算法解决了，也不可能是 BQP 完全的。
该图显示了 BPP 和 BQP 类的信任关系，它们分别是可以在经典计算机和量子计算机上有效解决的问题集。BQP 完全问题是 BQP 中最难的问题。
为了证明我们的模拟球和弹簧的问题确实是 BQP 完全的，我们从模拟通用量子电路的标准 BQP 完全问题开始，并证明每个量子电路都可以表示为由许多球和弹簧耦合而成的系统。因此，我们的问题也是 BQP 完全的。
启示和未来工作
这项研究还为 2002 年的研究提供了启示，当时理论计算机科学家 Lov K. Grover 和他的同事 Anirvan M. Sengupta 使用了耦合摆的类比来说明 Grover 著名的量子搜索算法如何能够在无序数据库中找到正确元素，其速度比传统算法快二倍。在适当的设置和初始条件下，系统经过仅 ~√( N)的时间演化后，就有可能判断N个摆中是否有一个与其他摆不同（类似于在数据库中找到正确元素）。虽然这暗示了某些经典振荡系统与量子算法之间的联系，但它不足以解释为什么 Grover 的量子算法具有量子优势。
我们的结果使这种联系更加精确。我们表明，任何经典谐振子系统的动力学实际上都可以等效地理解为相应指数级较小量子系统的动力学。通过这种方式，我们可以在 log( N ) 量子比特的量子计算机上模拟 Grover 和 Sengupta 的钟摆系统，并找到可以在 ~√( N )时间内找到正确元素的不同量子算法。我们在经典系统和量子系统之间发现的类比可用于构建提供指数级加速的其他量子算法，其中加速的原因现在从经典波的传播方式中更加明显。
我们的工作还表明，每个量子算法都可以等效地理解为经典波在耦合振荡器系统中的传播。这意味着，例如，我们原则上可以构建一个经典系统，该系统在演化时间比任何已知的解决因式分解的经典算法的运行时间小得多之后，可以解决因式分解问题。这看起来像是一种高效的经典因式分解算法，但问题是振荡器的数量呈指数级增长，因此它不是一种解决因式分解的实用方法。
耦合谐振子在自然界中无处不在，可以描述从电路到分子链再到桥梁等结构的广泛系统。虽然我们的工作重点是这类问题的根本复杂性，但我们希望它能指导我们寻找现实世界中谐振子问题的例子，在这些例子中量子计算机可以提供指数级的优势。
致谢
我们要感谢我们的量子计算科学传播者凯蒂麦考密克 (Katie McCormick) 帮助撰写这篇博文。
评论