其他
NISQ时代的混合量子-经典算法：现状、展望及未来 | 综述荐读
在计算领域，量子技术有望改变各行各业，解决目前经典计算机无法解决的复杂问题。在叠加和纠缠等原理的驱动下，量子计算机的能力使量子比特（qubit）能够加速特定计算。
然而，要全面了解这一领域，就必须从细微处着眼，认识到量子系统和经典系统固有的独特能力和局限性。
基于量子力学原理创建计算资源的最初提议出现于1980年代。这很快导致人们在整个二十世纪九十年代发现了许多针对“玩具问题”的量子算法，这些算法旨在展示量子计算与经典计算在复杂性理论上的分离。
然而，在上世纪90年代中后期，彼得·肖尔（Peter Shor）开发出了多项式时间量子算法，用于对大素数乘积进行因式分解，该算法现在被广泛认为是第一个有用的量子算法，其速度超过了纯经典算法。
由于肖尔的工作，人们对量子计算的兴趣大增，这也是早期量子实验硬件迅速发展的部分原因，这些硬件可以运行小型、有噪声的量子算法实例。然而，随着这些对计算规模和质量有严格限制的实验平台的出现，人们很快意识到，要想让量子计算机在近期和中期发挥作用，量子计算界需要为这个量子计算时代（后来被称为 “含噪声的中等规模量子计算”（NISQ）时代）量身定制算法：不仅包括在门模型量子设备上运行的算法，还包括通过量子退火进行的模拟优化、模拟和机器学习。
目前出现的混合变分量子算法体现了集成方法的力量。通过经典计算和量子计算之间的交替，这些算法解决了复杂的问题，让我们得以一睹经典和量子资源无缝协作的未来。
在适合门模型NISQ的量子算法领域，最具影响力的发展或许是变分量子算法（VQA）框架，它是随着变分量子本征求解器（VQE）而引入的。这些算法利用短深度参数化量子电路（特别适合NISQ硬件），嵌入到原本经典的变分环路中，这种结构显然是混合量子-经典结构。
虽然之前发现的其他一些量子算法也是混合型的，但VQA清晰地展示了将量子和经典资源耦合在一起的潜在组合能力。因此，由于VQA的出现，量子-经典混合算法从此成为量子算法研究中不可或缺的一部分，将NISQ设备应用于量子化学、机器学习和组合优化等问题的实验演示。
除了VQA，在模拟量子计算中实现混合技术的关键进展是偏向搜索概念，这一系列技术允许在更广泛的算法中将系统作为子程序调用，并借助先前的结果。这些技术可以以简单的方式使用，例如偏向于经典贪婪搜索中预先找到的好解，也可以以更复杂的方式使用，例如遗传算法。
总之，计算的未来在于利用量子和经典系统优势的协作、集成环境；混合方法不仅是最实用的，也是最有前途的前进道路。
要开始对量子-经典混合算法进行有意义的讨论，首先需要理解量子算法被视为混合算法的含义，以及混合算法与其他量子算法的不同之处。为此，必须对“混合”一词进行有效定义。
一个公认的、有意义的和有用的定义有助于促进交流，并允许对类似算法进行有用的分组。有一种观点很有诱惑力，认为“重复直到成功”等简单技术在几乎所有量子算法中都发挥着重要作用，因此几乎所有量子算法都应被视为混合算法。虽然这种观点有可能是正确的，但这种方法并不能得出有用的定义：如果一切都是混合算法，那么“混合量子算法”一词就没有什么意义了。
与其说任何量子算法都是混合算法，不如说量子-经典混合算法的突出特点是经典处理的使用与计算模型从根本上不可分割。
因此，我们提出以下量子-经典混合算法的定义：一种算法需要同时使用非量子计算和经典计算的量子和经典计算量，而且在不影响经典计算的情况下，无法对量子和经典计算量进行描述，甚至无法对量子和经典计算量进行描述。
量子纠错（QEC）提供了一个经典计算机支持量子算法的简单例子，但其中的经典计算与计算模型并无根本联系。在采用QEC的设备中，量子计算只发生在副机希尔伯特空间的一小部分，即逻辑子空间；选择逻辑子空间时，几乎所有的物理误差都会将系统带出子空间；也就是说，子空间内的误差是不可能发生的。
通过精心选择的测量方法，可以在不破坏量子信息的情况下检测状态是否离开了逻辑子空间（更正确地说，误差会导致逻辑子空间和误差子空间的位置变化，但测量会迫使状态坍缩到其中一个子空间上，这种机制被称为“误差去数字化error digitization”）。对这些测量结果的经典分析可用于诊断错误，并确定将状态旋转回逻辑子空间所需的量子操作，这种机制被称为解码。
就经典计算资源而言，量子纠错的解码可能非常密集；然而，（无噪声）门模量子计算的基本模型并不取决于如何纠错。同样，解码的分类策略也不取决于运行的量子算法，而只取决于解码架构。容错算法可以是混合算法，因为算法的量子部分可以以容错方式运行，但算法依赖QEC这一事实本身并不能使其成为混合算法。
要解决量子计算何时是混合计算的问题，我们不妨先看看在理解物理系统何时进行计算方面已经完成的工作。计算的抽象-表征理论正是由这个问题引发的。抽象表征理论在正在计算的物理系统和没有计算的物理系统之间划出的关键区别是，正在进行计算的系统拥有编码在其中的信息，以及与之相对应的计算抽象模型。换句话说，计算与其说是系统在做什么，不如说是系统在做什么。
根据抽象表示理论，物理系统需要与它正在进行的计算的抽象模型（可能不完美）配对。例如，门模式量子计算机可以用量子电路（可能包括来自噪声的随机元素）来抽象表示，相干量子退火器可以用薛定谔方程来表示，耗散量子退火器可以用主方程来表示。
要理解计算是否是混合的，就必须考虑经典计算在这个模型中扮演什么角色。回到QEC的例子，容错量子计算的模型已经是一个（无噪声）量子电路，经典计算只是起到辅助作用，确保模型足够精确。相比之下，我们可以考虑变分算法；在这种情况下，经典计算直接参与了计算模型，它提供了门参数的更新，从根本上说，不能从计算模型中移除。
格罗弗（Grover）算法是解决“非结构化搜索”问题的著名量子算法。在本节中，我们只讨论Grover算法的“纯粹”实现，即整个问题被表述为非结构化搜索。
简单地说，这是一个在知道M和N的情况下，在一组N≥M的标签中找到任意M个标记标签的问题。许多计算问题都可以表述为非结构化搜索，例如数据库搜索和某些形式的约束满足。由于无法获取标签间的额外结构，解决非结构化搜索的唯一方法就是随机或按特定顺序重复选择标签、 其时间复杂度为
虽然算法的单次运行并不能保证以单位概率获得标记状态），但可以通过Oracle检查结果，并重复少量次算法，直到确认标记状态，而不会影响二次加速。将具有这种微不足道的经典后处理水平的量子算法视为混合算法是没有用的，因为很难想象任何有用的量子算法不包含至少这些经典控制元素。
肖尔的多项式时间算法用于对两个大素数p1和p2的乘积N=p1p2进行因式分解，被认为是第一个有用的量子算法。鉴于肖尔算法的实际应用会给现代计算机安全带来很大风险，因此它可能是影响最大的量子算法——它被视为量子计算能力的典型例子。
然而，肖尔算法远非“纯粹的”量子算法；当然，它应该被视为一种混合算法。该算法的基础是将因式分解问题多项式时间还原为计算周期函数阶数T的问题。通过上图可以看出，几乎所有步骤都是完全经典的：包括第2步和第9步中通过经典欧几里得算法计算最大公约数，以及第6步中的经典续分展开。算法中唯一的量子部分是第5步中对量子相位定时电路的调用，它构成了阶调子程序的核心。
虽然肖尔算法的量子部分确实比最著名的纯经典方法速度更快，但在第5步调用量子子例程之前和之后，还进行了大量的经典处理（但却是多项式的），以便将问题转化为量子处理器可以轻松处理的特定形式。这种经典处理包括调用可识别的经典算法，如欧几里得算法；换句话说，如果没有周围的经典步骤，量子计算机正在计算的东西就不会直接有用。
在讨论了两种可能最具代表性的量子算法之后，我们将更详细地讨论混合算法的其他重要实例。
需要说明的是，这并不是一份详尽无遗的清单，而是为了开始讨论在不同情况下混合算法的含义，并提供有助于将这些算法扩展到其他算法的例子。
1）量子退火和连续时间量子计算
量子退火（QA）是利用量子系统的连续时间动力学，通过量子波动搜索空间来解决优化问题。我们今天所熟知的QA是由kadawaki和Nishimori在上世纪90年代末提出的（尽管更早之前就有人针对化学相关问题提出过类似建议）。
自问世以来，QA已发展到包括各种协议，但典型的结构包括实现一个随时间变化的横向伊辛模型哈密顿量：
关于连续时间量子计算中混合算法的大部分工作都集中在协议上，这些协议允许在协议中加入对计算结果的启发式猜测。
其中，s是一个起始于s(O) = O、止于s(1) = 1并在两者之间单调递增的附表函数，横向磁场驱动在退火过程中打开，然后关闭。
退火协议的目的是将非微量的振幅转移到问题哈密顿Hp的真正基态，横向磁场先上后下，以通过量子波动帮助这种转移。值得注意的是，由于逆向退火(reverse annealing)运行的目的是在已知合理解的基础上进行改进，因此可以将逆向退火嵌入经典循环中，将一次运行测得的输出状态作为下一次运行的初始状态（具有适当的初始哈密顿）。
例如，一种逆向退火的哈密顿形式为：
其中s(O)、λ(O)=O，s(1)、λ(1)=1，两者之间均为单调递增。由于系统在t=O时开始处于瞬时基态，并在t=T时进入瞬时基态，因此原则上可以绝热运行，这就是所谓的绝热逆向退火。
由于逆向QA和偏置驱动QA都以解法的先前知识形式将经典信息纳入协议本身，因此任何利用它们的算法都必然是混合算法。早期的许多论文都关注封闭系统量子纠错如何纳入先验知识，但后来的工作则探讨了如何将这些想法用于将QA作为子线的更复杂算法中。
上图显示了利用逆向退火进行局部搜索的实验演示数据。这些实验是通过构建一个具有已知病理行为的伊辛系统来进行质量保证的。这是通过创建一个“宽泛的”假最小值来实现的，在这个假最小值中，强量子波动被降低了。然后，将该系统初始化到一个“窄得多”的真实最小值附近（从位点数的意义上来说）。
结果表明，从“好的猜测”出发，通过逆向退火只访问适度的波动，从容地搜索解决方案，可以避免宽假最小值，从而验证了逆向退火是局部搜索解决方案空间的工具，而这正是混合量子算法的关键要素。
总体而言，逆向退火被认为是通过退火技术最终实现量子优势的关键技术，尤其是在相干性较低的情况下。
2）变分算法
量子计算NISQ时代的特点是设备的空间（如量子比特数量）和时间（如可实现的相干时间）资源有限。因此，近期的量子算法设计必须侧重于从这些有限的资源中提取尽可能多的性能。混合算法是实现这一目标的自然途径，它可以用普通硬件完成大部分计算，只在量子处理器特别适合的小问题上调用量子处理器。
变分量子本征求解器(Variational Quantum Eigensolver，VQE)就是一个著名的示例，它是一类针对NISQ设备的算法，结合了小型量子电路和经典运算技术，可以逼近哈密顿量H的特征状态（通常是地面状态）和相关特征能。
在VQE中，量子处理器用来准备一个状态：
其中，“亚初始状态”（
量子近似优化算法（QAOA）是一种用于组合运算的算法，并迅速启发了其他一些进一步发展该思想的工作。虽然某些形式的QAOA可被视为纯量子算法，但它通常是混合形式的。事实上，QAOA最常见的形式可以看作是将VQE算法应用于组合阶乘优化的一个例子，其解析式受到QA的启发。
解析式的形式通常为：
其中，P是QAOA层数，a=(a1 , ... , ap ), β=(β1 , ... , βp )是2P变量参数。
实际上，为了接近QA极限，在运行QAOA算法时需要大量的层数p，这很快就会变得不切实际，尤其是在NISQ时代。因此，QAOA算法通常只考虑少量层数，甚至有时p=1。对于较少的层数，参数a、β的数量是可控的，可以像其他变分算法一样在经典变分循环中进行优化。
最后，变分算法（包括QAOA）的性能将严格取决于PQC U(θ)的解析式选择。
3）量子振幅估计
量子振幅估计 (QAE) 算法是解决一些问题的量子方法集合。
研究表明，QAE算法的实际应用有可能加快各种重要应用的速度；特别是，有文献指出，QAE可以通过提高采样收敛速度，实现蒙特卡罗算法的四次方（最高达对数）加速。鉴于蒙特卡罗算法在化学、统计物理和计算数学等广泛领域的重要性，QAE算法的实际应用将产生重大影响。
QAE算法是一种纯粹的量子算法，依赖于类似前文所示的相位估计方法，其中包含了许多复杂的受控单元操作，实现起来可能很困难。在展示了QAE的潜在用途之后，许多新形式的QAE被开发出来，它们将相位估计程序与经典相位估计程序重新组合在一起，但算法的核心工作原理保持不变。所有形式的QAE都涉及构建类似Grover的迭代算子：
这些算法通过对Grover迭代算子进行不同次数的迭代来放大振幅a，并检测哪些迭代次数能产生较大概率的测量“良好”状态。
4）量子化学和材料模拟中的量子子程序
早期量子算法的一个有前途的研究方向是开发用于解决量子化学问题的量子方法。
在一般情况下，必须考虑量子力学才能计算重要属性的系统往往难以用纯经典技术处理；这是由于与系统大小相比，希尔伯特空间的大小呈指数增长。直接利用量子计算机的量子特性，可以为这些问题带来非常自然的技术。
通过选择VQE循环中使用的哈密顿量H作为所研究化学体系的哈密顿（以及合适的VQE方 法），VQE程序可以用来计算哈密顿的基态（或其他特征态），并由此计算出其他重要性质 （如格林函数或各种化学性质）。
虽然直接的VQE方法可能适用于那些小到足以在近期量子设备上使用（但仍然大到对经典方法来说很困难）的问题，但对于更大的问题（如相关物质模拟），必须采取更复杂的方法。科学家们提出的一项建议是，将一个完整的系统分成一个具有有效量子哈密顿的小活动空间及其环境，后者可以通过密度泛函理论（DFT）进行较不精确的处理。然后可以用VQE处理小的活性空间，从而了解整个系统的电子特性。
许多用于量子化学和材料的纯经典算法都依赖于量子蒙特卡罗，这是一个经典算法系列，可以在一定程度上模拟热平衡中的量子系统。然而，对于费米子系统来说，量子蒙特卡罗受到了所谓符号问题的限制：即在特定温度以下，精确采样在计算上是不可行的。这些算法的优势在于提供了现成的经典部分来添加量子成分，因此是早期量子-经典混合算法的天然候选者。
不过，为了克服经典方法固有的计算难题，科学家提出将绝热态预处理（使用AQC计算哈密顿特征态的近似值）和量子相位估计相结合来制备基态，并由此测量格林函数。
1）在更小的硬件上进行更大的计算：纠缠锻造
由于近期量子处理器可用的量子比特数量有限，因此值得考虑如何利用经典处理将混合算法应用于小型设备上可能无法解决的问题。例如，利用纠缠锻造（以及一些启发式改进），通过十量子比特映射，在真实量子硬件上仅使用5个超导量子比特，就能高精度地计算出水分子各种几何形状的基态能量。
2）附加控制
在QA和其他非通用模拟处理器中，有时混合技术需要额外的控制。
这里最典型的例子就是逆向退火，它允许采用混合技术。这些控制措施非常重要，因为它们允许使用更丰富的技术，而这些技术在实验中已经取得了实实在在的成果。特别是，在这个例子中，这些控制实际上在底层设备中已经存在，但还没有提供给外部用户。
因此，考虑如何在计算中将现有实验技术用于不同于其初衷的目的是非常重要的。
3）将量子计算能力与经典计算能力合二为一
虽然目前主流的量子计算机云访问模式非常适用于概念验证实验，但量子和经典组件之间通过互联网发送信号所需的时间可能会成为一大障碍。目前已经有人在努力将量子计算资源与强大的经典高性能计算共同定位，例如通过于利希超级计算中心的JUNIQ计划。
有些计算可能需要量子和经典部件之间更快的通信；对于超导量子比特等量子比特技术来说，它们可以在超低温的芯片基板上运行，这意味着在低温下（尽管可能不如量子计算机那么冷）进行经典计算可能是有益的。受量子计算用例的启发，已经有许多这方面的研究。
另外，还有许多类型的经典处理器，它们各有优缺点；任何一种都有可能成为与量子计算机共址的有用候选者。
在前述文章中，我们列举了许多实例，展示了如何将经典处理器和量子处理器结合使用，以比单独使用经典处理器更高效的方式完成计算任务。
虽然量子处理器在实践和理论上肯定与任何类型的经典处理器大相径庭，但不同类型的处理器协同工作已经是纯经典计算中的常见结构；有许多经典的专用协处理器实例，特定类型的处理被加载到这些协处理器上，这种情况有时被称为异构或异质。
经典异构计算最明显的例子是计算机的中央处理器（CPU）与图形处理器（GPU）协同工作。除其他外，典型的GPU由比典型CPU多得多的内核组成，这些内核特别适合图形处理所需的三维向量矩阵运算，如空间中的平移和旋转。
例如，三维物体上的每个点都需要以相同的方式移动，只是每个点的起始条件不同。与CPU上相对较少（更通用）的内核相比，GPU上大量的小型内核可以大大加快处理速度。通常情况下，计算安排为CPU在需要时将这些特定任务交给GPU。
最近，GPU技术已被用于图形处理以外的应用，这些应用同样需要对小型数值运算进行大规模并行化，例如机器学习计算（如TensorFlow）。
应用专用集成电路（ASIC）也可被视为一种处理器，其设计和制造目的是以比CPU等通用处理器更快的速度和更高的能效执行特定的计算任务。英特尔的快速同步视频技术就是具有这些特性的ASIC的一个实例；这些电路用于在不同格式之间快速转换视频，并与英特尔CPU集成以处理这些特定的工作负载。
1）神经网络
许多现代经典算法都是通过使用软件定义的神经网络来模仿人脑的行为。虽然这种方法在许多领域都取得了成功，但标准处理器却受到了特别大的瓶颈限制，例如内核与内存之间的通信。为了避免这些限制，新出现的神经形态处理器旨在直接在硬件层面模拟人脑的行为，从而开发出可以比标准处理器更高效地运行人工智能应用的硬件。
2）作为专用协同加速器的量子计算器
这里描述的专用加速器都展示了为特定类型的计算工作而设计和优化的硬件如何与标准处理器（如CPU）协同运行，以提高整体计算效率。
混合量子-经典算法，包括本研究中描述的算法，天然就属于这一框架；量子处理单元（QPU）可被通用经典CPU调用，以加速特定的计算子程序，例如肖尔算法的相位估计部分或VQE算法的解析准备部分。
从这个角度看，量子-经典混合算法是计算机技术发展中传统模式的延续。虽然量子计算机的运行原理与经典计算机的运行原理有很大不同，但从根本上说，量子计算机与更大的体系结构的结合方式（以及与之相关的问题）并不是以前从未遇到过的。
混合算法的发展路径并不普遍，并不总是涉及非混合前身；虽然混合形式的QAE是由最初的纯QAE发展而来的（也可以说是由格罗弗搜索这种纯量子算法发展而来的），但许多其他算法的产生方式却各不相同：与许多高桥材料和化学算法类似，都是从经典算法发展而来，用量子计算呼叫取代了经典方法，如量子蒙特卡罗。在变分算法以及量子纠错的混合形式中，硬件的能力推动了算法的发展。
从这些故事中得出的一个重要教训是，开发混合算法的方法并非只有一种：它们可以以多种不同的方式出现。
这一讨论带来的一个直接问题是，混合算法是否只是量子计算发展过程中的一个阶段？随着新的、先进的协处理器的发展，它们并没有取代旧有的模式，而是被添加到旧有模式中以执行专门的任务。量子计算机在数字加法这样的简单应用上本质上并不更快，即使大量高质量的量子比特可以随时读取，它们在所有指标上都比经典比特更好也是值得怀疑的，在这种情况下，异构计算将是最明智的范例，就像目前在经典计算领域一样。
事实上，一旦量子硬件发展到真正有用的阶段，非混合算法就不太可能被部署到“生产”环境中，原因很简单，加入混合组件很可能会带来进一步的改进。
从迄今为止的讨论中，我们已经看到，混合算法最有意义的分类方式不是它们使用了多少经典计算能力，而是计算如何融入整个模型。Grover算法和随后的QAE技术，以及量子退火和随后的混合版本，都出现了一种模式，即非混合算法经常演变成更丰富、更强大的混合变体。
这种模式很可能不是偶然的，因为首先在更“纯粹”的环境中想象算法，然后让它们进化，往往会更容易。这表明混合算法和非混合算法之间存在一种有趣的关系：非混合环境是混合技术的孵化器，而混合技术将在日后得以实现。
因此，我们并不是说混合算法是唯一一类值得研究的量子算法，而是认为，将非混合算法视为有待开发的新算法的基础可能是最合适的。
参考链接：[1]https://samithp.medium.com/embracing-a-hybrid-future-the-symbiotic-relationship-between-quantum-and-classical-computing-08be66c19e65[2]https://journals.aps.org/pra/abstract/10.1103/PhysRevA.106.010101
相关阅读：毕马威、微软、霍尼韦尔合作开发「量子-经典混合算法」
亚马逊Braket宣布支持混合量子-经典算法，并将接入首个欧洲系统
混合集成的光量子电路 | 综述荐读
计算的未来是“混合”的：为什么量子计算机将与经典系统一起工作？
Nature：激光冷却原子，实现混合量子系统
#光子盒视频号开通啦！你要的，这里全都有#
每周一到周五，我们都将与光子盒的新老朋友相聚在微信视频号，不见不散！
|qu|cryovac>你可能会错过：|qu|cryovac>