量子计算（二十）：量子算法简介

​量子算法简介

一、概述

量子算法是在现实的量子计算模型上运行的算法，最常用的模型是计算的量子电路模型。经典（或非量子）算法是一种有限的指令序列，或一步地解决问题的过程，或每一步指令都可以在经典计算机上执行。

量子算法是一个逐步的过程，每个步骤都可以在量子计算机上执行。虽然所有经典算法都可以在量子计算机上实现，但量子算法这个术语通常用于那些看起来是量子的算法，或者使用量子计算的一些基本特性，如量子叠加或量子纠缠。

使用经典计算机无法判定的问题，使用量子计算机仍然无法来确定。量子算法有趣的是，它们可能能够比经典算法更快地解决一些问题，因为量子算法所利用的量子叠加和量子纠缠可能不可以在经典计算机上有效地模拟。

最著名的算法是Shor分解算法和Grover的搜索非结构化数据库或无序列表的算法Shor算法运行速度比最著名的经典因式分解算法（一般的数域筛选算法）快得多（几乎是指数级），对于同样的任务，Grover算法运行速度比最好的经典算法（线性搜索）要快得多。

二、量子经典混合算法

量子计算机究竞什么时候能够真正实现？没有人能给出确切的答案，不过在这条路上探索的人们非常明白，建立一个容错的、具有足够多的逻辑比特的系统，是一个非常漫长的任务。

然而，一个具有50个比特的量子系统，或者一个50个比特能模拟的量子系统，已经难以被传统计算机所模拟，它具有非常巨大的计算潜力。为了解决这个问题，Johm Preskill教授提出了一个全新的概念：含噪声的中等规模的量子计算机（Noise Intermediate-ScaleQuantum），它被定义为未经纠错的，具有50个到数百个量子比特的量子计算机，简称为NISQ量子计算机。在NISQ上设计的算法可能和以往假设的容错量子计算机上设计的算法完全不同，NISQ算法本身需要能容忍噪声所造成的影响。

量子霸权在最初提出的时候，代表超过50个量子比特的量子计算机在生成特定分布（distribution）上超过了传统计算机，但是研究表明，在这些问题上可以巧妙地选取模拟算法，使得经典计算机也可以产生相同的分布。取代”量子霸权”（Quantum Supremacy）这个称呼的，是量子优势”（Quantum Advantage）。量子优势意味着量子计算机在处理某些领域问题上，超过了传统计算机的表现，相对于霸权而言，量子优势更注重量子算法以及实际的领域应用。可以说，量子优势是NISQ量子计算机领域的皇冠，谁夺取了皇冠，谁就证明了量子计算机可以投入到现实应用中。相比为了制造出一个逻辑比特可能需要数万个物理比特的容错量子计算机而言，NISO计算机被认为可以在短期的未来中被实现。因此，这个领域成为了量子计算研究的热门。

量子经典混合算法是一类近期提出的，适用于NISQ量子计算机上的算法。它的特点是量子计算机只处理整个算法中的一个部分，经典计算机负责处理其他部分。绝大多数量子经典混合算法中都会存在一个类似于机器学习中的参数优化过程，其中，量子计算机处理一个包含多个参数的量子线路，并且对这些参数进行随机的初始化，量子计算机执行的结果会进一步被计算成一个损失函数，这个损失函数被输入到经典计算机的优化器中，从而修改这些参数，之后再通过量子计算机进行计算，如此循环，直到达到优化终止条件。例如损失函数收敛，达到最大优化步数等。

第一个提出的量子经典混合算法是变分本征求解器（Variational Quantm Eigensolver），即VQE算法，它可以被用于求解化学分子的基态，因此，这个算法可以被用于解决各类涉及化学计算的相关问题。对于经典计算机而言，要表示N个分子轨道的占据状态，需要用2”维的线性空间去计算，因此，在计算具有超过50个轨道的分子时就无法进行精确计算；而量子计算机的N个轨道正好需要N个量子比特完成模拟过程听以这个问题可以在量子计算机上被有效的求解。现在，针对组合优化问题、机器学习问题，都有各种各样的量子-经典混合算法被提出，它们被认为是有希望在NISQ计算机上实现。

由于量子经典混合算法的框架类似于在经典计算机上执行的机器学习算法，因此可以利用类似于机器学习框架的系统去进行编程。本源量子所开发的VQNet框架XanaduAI公司开发的PennyLane框架，都是在原有机器学习框架上扩展支持量子计算的部分。VQNet是基于符号运算的机器学习框架，它设置了“含参量子线路”（Variational Quantum Circuit），可以通过变量生成一个量子线路。通过含参量子线路可以进一步构建成量子算符（Quantum Operator），量子算符相当于对变量的运算，这种运算等价于一个普通的算符，支持求值和偏微分操作，因此，量子算符就可以容纳到机器学习这个框架中。利用VQNet可以实现目前绝大多数的量子-经典混合算法，包括VQE，QAOA，QCL等等。