量子计算（三）

基于该定理的量子绝热算法的关键在于用某个哈密顿量对给定决策问题的特定实例进行编码的可能性（这可以通过利用众所周知的事实来完成，即任何决策问题都可以导出通过将数值界限作为附加参数纳入优化问题）。然后，我们在另一个易于构造的哈密顿量的基态下启动系统，并及时缓慢地演化系统，将其变形为所需的哈密顿量。根据量子绝热定理并给定间隙条件，这种物理过程的结果是另一个能量基态，它编码了所需决策问题的解。因此，绝热算法是一种相当“悠闲”的算法：只需在基态下启动系统，使其绝热变形，并测量其最终基态即可获得所需的结果。但该算法是否能产生所需的加速关键取决于随着系统自由度数量增加而能隙的行为。如果这个差距随着输入的大小呈指数级减小，那么算法的进化时间将呈指数级增加；如果间隙按多项式减小，则可以有效地解决如此编码的决策问题。近一个世纪以来，物理学家一直在研究光谱间隙，但他们最近才开始考虑计算问题。现在已知，在给定任意量子多体系统的哈密顿量的情况下，不存在可以确定它是有间隙还是无间隙的算法（Cubitt、Perez-Garcia 和 Wolf 2015）。在实践中，绝热量子计算机采用间隙放大技术，以确保整个计算过程中间隙的存在（Albash & Lidar 2018，sec. F）。

量子绝热算法前景广阔（Farhi et al. 2001）。它已被证明（Aharonov 等人，2008）与电路模型多项式等效（即，每个模型都可以通过量子位数量和计算步骤上的多项式开销来模拟另一个模型），但有时会留下警告没有提到的是，它在解决棘手的计算问题时有时可能需要解决另一个棘手的任务（这种普遍的担忧首先由一位哲学家提出；参见 Pitowsky 1990）。事实上，Reichardt (2004) 已经表明，存在一些简单的问题，算法将陷入局部最小值，其中存在指数数量的特征值，所有特征值都以指数方式接近基态能量，因此应用绝热定理，即使对于这些简单的问题，需要指数级的时间，然后我们又回到了原点。有关最新技术水平的最新调查，请参阅 Albash & Lidar (2018)。

3.3 基于测量的算法

基于测量的算法与电路算法的不同之处在于，这些算法不是采用单一进化作为信息操作的基本机制，而是在计算过程中而不只是在读出阶段充分利用测量。它们分为两类。第一个是隐形传态量子计算，基于 Gottesman 和 Chuang (1999) 的想法，并由 Nielsen (2003) 和 Leung (2004) 发展成计算模型。第二个是“单向量子计算机”，也称为“簇态”模型（Raussendorf & Briegel 2002）。这些模型的有趣特征是，它们可以使用非酉测量有效地模拟酉量子动力学，它们在多项式上等价于电路模型（Raussendorf、Browne 和 Briegel 2003）。这是通过对一组高度纠缠的量子系统进行测量来实现的（参见 Duwell 2021，5.2），以便通过经典计算机使用早期测量的结果来计算执行每次测量的标准正交基。

从基础角度来看，基于测量的模型很有趣，原因有很多。首先，在这些模型中，计算的经典部分（即下一个测量基础的计算）和量子部分（即对纠缠量子位的测量）之间存在明显的分离，这可能使得更容易查明负责加速的量子资源。此外，它们还可以深入了解纠缠在量子计算中的作用。它们还可能产生有趣的与工程相关的后果，表明一种不同类型的容错能力更强的计算机架构（Brown & Roberts 2020；Nielsen & Dawson 2005）。

3.4 拓扑量子场论（TQFT）算法

量子计算的另一种模型引起了很多关注，尤其是来自微软公司的关注。 （Freedman 1998），是拓扑量子场论模型（Lahtinen & Pachos 2017）。与易于可视化的电路模型相比，该模型属于理论物理学最抽象的领域。 TQFT 描述的奇异物理系统是物质的拓扑状态。 Witten (1989) 证明了 TQFT 的形式可以应用于计算问题，并且这个想法后来被其他人发展。该模型的主要优点之一与电路模型多项式等价（Aharonov, Jones, & Landau 2009; Freedman, Kitaev, & Wang 2002），在于它对实现中不可避免地引入的错误有很高的容忍度大型量子计算机（见下文）。拓扑在这里特别有用，因为根据定义，许多全局拓扑属性在变形下是不变的，并且考虑到大多数错误都是局部的，拓扑属性中编码的信息对它们来说是鲁棒的。

4 实现

量子计算机可能是理论家的梦想，但就实验家而言，它的完全实现，其中涉及解决如何将构建量子计算机所需的元素组合成可扩展系统的仍然悬而未决的问题（参见 Van Meter & Horsman 2013 ），是一场噩梦。 Shor 的算法可能会破解 RSA 加密，但如果它能分解的最大数字是 21，这仍然是一个轶事（Martín-López et al. 2012；Skosana & Tame 2021）。在基于电路的模型中，问题是实现一个可扩展的量子系统，同时允许人们（1）稳健地表示量子信息，（2）退相干时间明显长于计算长度，（3 ）实现酉变换的通用族，（4）准备基准初始状态，（5）测量输出结果（这些是 DiVincenzo (2000) 的五个标准）。替代范式可能会与其他范式交换其中一些要求，但要点将保持不变，即，人们必须以这样一种方式实现对自己的量子系统的控制，即该系统将保持“量子”，尽管是宏观的或至少是介观的它的尺寸。

为了应对这些挑战，人们设计了几种巧妙的解决方案，包括量子纠错码和容错计算（Aharonov & Ben-Or 1997；de Beaudrap & Horsman 2020；Horsman, Fowler, Devitt, & Van Meter 2012；Raussendorf） ，哈林顿和戈亚尔 2008 年；肖尔和迪文森佐； 1996；Steane 1996）这可以显着减少“嘈杂”量子计算期间的错误传播。然而，对这些主动纠错方案的一个重要批评是，它们是为非常不切实际的噪声模型而设计的，该模型将计算机视为量子，将环境视为经典（Alicki、Lidar 和 Zinardi 2006）。一旦允许使用更现实的噪声模型，大规模、容错和计算优越的量子计算机的可行性就不太清楚了（Hagar 2009；Tabakin 2017）。

短期内，在有限数量的问题领域实现量子优势的一个有希望的途径是噪声中尺度量子（NISQ）范式（Lau、Lim、Shrotriya 和 Kwek 2022；Preskill 2018）。 NISQ 范式不采用任何纠错机制（将问题推迟到将来实现这些机制的可扩展版本），而是专注于构建计算组件并解决计算问题，这些组件本质上对噪声更具弹性。例如，其中包括某些类别的优化问题、量子半定规划和数字量子模拟（Tacchino、Chiesa、Carretta 和 Gerace 2020）。这里需要注意的是，随着电路对噪声的弹性增加，它的行为就越经典。

正如刚才提到的，NISQ 计算的设想应用之一是数字量子模拟（即使用基于门的可编程量子计算机进行模拟）。然而，模拟量子模拟有一种古老的传统，其中使用的量子系统的动力学类似于感兴趣的特定目标系统的动力学。尽管人们相信数字量子模拟最终会取代它，但模拟量子模拟领域自首次提出以来这些年来已经取得了长足的进步，并且模拟量子模拟器已经被用来研究被认为超出了量子模拟范围的量子动力学。经典模拟器的范围（例如，参见 Bernien 等人，2017 年；有关所涉及的哲学问题的进一步讨论，请参见 Hangleiter、Carolan 和 Thébault，2022 年）。

5 个哲学问题

在本节中，我们回顾了哲学和物理文献中讨论过的与量子计算相关的一些重要哲学问题。有关非专业人士仍然可以了解的其中一些问题的更详细调查，请参阅 Cuffaro (2022) 和 Duwell (2021)。

5.1 量子计算中的量子是什么？

抛开实际实现和实施大规模量子计算机的问题，一个关键的理论问题仍然悬而未决：哪些物理资源（量子力学的哪些基本特征）决定了量子计算机超越经典计算机的假定能力？已经提出了一些候选人。 Fortnow (2003) 将干涉视为关键，尽管有人认为这并不是真正的量子现象 (Spekkens 2007)。 Jozsa (1997) 和许多其他人都指出了纠缠，尽管该论文有据称的反例（参见，例如，Linden & Popescu 1998 [其他互联网资源]，Biham, Brassard, Kenigsberg, & Mor 2004，以及关于哲学关于其重要性的讨论参见 Cuffaro 2017）。 Howard、Wallman、Veitch 和 Emerson (2014) 诉诸量子语境。对于 Bub (2010) 来说，答案在于量子力学的逻辑结构（参见 Dalla Chiara, Giuntini, Leporini, & Sergioli 2018），而 Duwell (2018) 则主张量子并行性。对于 Deutsch (1997) 和其他人来说，“平行世界”就是资源。

“量子计算中的量子是什么？”这个问题看似具有推测性。具有重大的实际影响。几乎可以肯定的是，实际发现的量子算法很少的原因之一是缺乏对量子计算机量子化的充分理解。量子计算怀疑论者（Levin 2003）高兴地利用了这一点：如果没有人知道为什么量子计算机优于经典计算机，我们如何确定它们确实优越？

5.1.1 关于并行性和多世界的争论

主导量子计算流行文献的答案是由以下演变推动的：

Σx|x⟩|0⟩→Σx|x⟩|f(x)⟩,

这对于许多早期的量子算法来说都很常见。请注意，f 的每个可能输入同时​​被评估。我们应该从表​​面上理解这一点，即量子计算机实际上可以同时计算许多不同输入值的函数，这就是杜威尔（Duwell，2018，2021）所说的量子并行论（QPT）。对于接受它为正确的多伊奇来说，对 QPT 的唯一合理解释是量子力学的多世界解释（MWI）也是正确的。对于多伊奇来说，叠加态的量子计算机就像任何其他量子系统一样，在某种意义上同时存在于许多经典宇宙中。它们提供了计算机进行并行计算的物理场所。 Hewitt-Horsman (2009) 和 Wallace (2012) 也捍卫了这一结论。然而，华莱士指出，QPT——以及因此对许多世界的解释性需求——可能并不适用于所有甚至大多数量子算法。

对于 Pitowsky (2002) 和 Steane (2003) 来说，量子加速的解释不能在量子并行性中找到。 Pitowsky (2002) 要求我们考虑一个给定的解决方案，该解决方案是使用基于量子电路的算法找到的，以解决诸如可满足性之类的问题。量子算法似乎可以通过“一次”测试指数级的许多分配来解决这个问题，如（1）所示，但这个量子“奇迹”对我们帮助甚微，因为如前所述，对输出状态执行的任何测量都会使其崩溃，如果存在一个可能的真值分配来解决这个决策问题，则检索它的概率不会大于经典概率图灵机猜测解决方案然后检查它的概率。 Pitowsky的结论是，实现量子加速要求我们构建“聪明”的叠加，从而增加成功检索结果的可能性远远超过了纯粹的猜测（另请参见Aaronson 2022 [其他Internet资源]）。 Steane（2003）除其他外，认为，如果我们比较量子和古典算法实际产生的信息，那么我们应该得出结论，量子算法的性能不多，而是比古典算法更少，更聪明的计算（另请参见第5.1节，，也要说，，也更聪明，请参见第5.1节。 .2下面）。 Steane还认为，QPT的动机至少部分是由于标准量子形式主义的误导性方面。

MWI方法的另一个批评家是Duwell，他（Contra Pitowsky和Steane）接受了QPT（Duwell 2018），但仍然否认（Contra Deutsch），它独特地支持MWI（Duwell 2007）。在评估量子算法的计算效率时，考虑到叠加中的术语之间的相位关系至关重要。但是，阶段关系是状态的全球属性。因此，杜威尔认为，量子计算不仅由局部并行计算组成。但是在这种情况下，QPT并不能唯一支持MWI而不是其他解释。

Hewitt-Horsman（2009）捍卫MWI，认为量子计算机实际上并未生成（1）中代表的每个评估实例的量子计算机，这是错误的：原则上，具有足够先进的技术。此外，休伊特·霍斯曼（Hewitt-Horsman）强调，MWI并不是仅仅由暗示性的数学代表来激励。 MWI上的世界是根据其解释性实用性来定义的，特别是由于它们在与计算相关的时间尺度上的稳定性和独立性所表现出来。华莱士（Wallace）（2012）也同样论证。

Aaronson（2013b）和Cuffaro（2012，2022）指出，量子计算的许多世界解释（MWX）与MWI之间存在表面上的张力。后者通常采用反融合作为将宏观世界彼此区分的标准。但是，量子电路模型算法使用相干叠加。因此，要区分彼此的计算世界，人们需要以某种方式修改矫正标准，但是Cuffaro质疑这是否可以成功地与先前对MWI的承诺无关。此外，Cuffaro认为，MWX出于所有实际目的与基于测量的计算不相容的所有实际目的，即使是为了授予修改后的世界识别标准的合法性，该模型没有自然的方式来识别所需的稳定和独立的世界。 。

5.1.2 加速的难以捉摸的本质

即使我们可以排除MWX，确定负责量子加速的物理资源仍然是一个困难的问题。除其他方面，问题提出了有关如何衡量给定量子算法的复杂性的重要问题，以及关于我们实际上希望能够实施哪些量子操作的问题（Geroch 2009，ch。18； Schmitz 2023）。答案根据所考虑的特定模型而有所不同。在绝热模型中，只需要估计能量差距行为及其与输入大小的关系（编码在系统的哈密顿自由度的数量中）。在基于测量的模型中，一个人计算了揭示隐藏在输入群集状态中的解决方案所需的测量数（由于群集状态的制备是多项式过程，因此它不会增加计算的复杂性）。但是在电路模型中，事物并不那么简单。毕竟，整个基于量子电路的计算可以表示为从输入状态到输出状态的单个统一转换。

可以说，这表明量子计算机的力量（如果有的话）本身不在于其动力学（即schrödinger方程），而是在量子状态的某些特征或“波函数”本身。还考虑到，希尔伯特子空间在量子计算过程中“访问”是在任何时候都是由整个希尔伯特空间中的所有向量跨越的线性空间，直到那一刻，这是由计算过程创建的。但是，这个希尔伯特子空间是由多项式矢量跨越的子空间，因此最多是总希尔伯特空间的多项式子空间。对具有多项式尺寸数量的希尔伯特空间上的量子演化的经典模拟（即，在计算中涉及的量子数中是多项式的许多基础向量跨越的希尔伯特空间），但是可以执行在多项式的经典计算中。是量子动力学完全负责量子计算的功能，可以使用经典计算机以多项式的步骤模仿后者（参见，例如Vidal 2003）。

这并不是说量子计算不比经典计算强大。当然，关键点是，没有一个任意叠加的量子计算，而是要使用Pitowsky的术语来实现非常特殊的“聪明”状态。量子计算并不总是在经典上有效地模拟，因为某些量子状态的计算子空间的表征很困难。因此，在量子电路模型中，应该不是通过计算状态的变换数来计算计算步骤数的数量，而是通过计算创建''''所需的一或两Q级局部变换的数量来计算计算步骤的数量。巧妙的叠加确保了所需的加速。 （请注意，例如，Shor的算法在此上下文中涉及三个主要步骤：首先，一个通过一组单一的转换创建了“聪明”的纠缠状态。计算的结果 - 函数的全局属性 - 现在是'隐藏在此状态下，为了检索此结果，一个人在希尔伯特空间的子空间上投射，最后一个人执行了另一组统一转换，以使结果可以在原始计算的基础上进行测量就算法的效率而言，步骤算作计算步骤。可以找到量子计算的物理力量。