

什么是量子算法

量子创投界

2021-09-02

导读：量子算法专题报告，本文总结了几种量子计算的主要算法，对量子算法的发展趋势做出了预测。

（正文共5390字，预计阅读时间14分钟）

算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。无论是狭义还是广义，算法都是用来处理相应问题，因此计算机算法，就是用计算机来解决问题的方法和步骤，在现实中，解决不同的问题，需要不同的算法。我们知道，计算机的本质上是计算器，加、减、或以其他方式操作1和0来完成从处理文本文档到流的所有事情。这是由处理器，软件，计算机的硬件，和各种输入及输出设备，构造的一个复杂的过程，其核心是计算机围绕着一个简单的任务通过在他们的状态和他们想要的问题之间架起桥梁来解决一个问题。

算法以编程的方式工作，按指令进行操作，精确地构建门电路，我们通过运行复杂的高级软件，使得计算机执行算法操作，在运算底层迅速执行指令，来实现我们期望的运算结果。原理总体来说可以用图1来表示：

图1 经典算法基本原理

Google搜索是由算法提供支持的，Google搜索实际上是基于许多其他算法之上的数十种算法的算法，所有算法都解决了较大问题的特定子问题，并在单个进程或程序中协同工作以返回查询的搜索结果。Facebook的新闻源, Instagram, YouTube它们都是由算法构建的，解决彼此之间的问题，以产生我们想要的功能。

量子算法是什么

从概念描述来看，量子计算机（quantum computer）是一类遵循量子力学规律进行高速数学和逻辑运算、存储及处理量子信息的物理装置。当这个装置处理和计算的是量子信息，运行的是量子算法时，就是量子计算机。在量子计算中，一切都是变化的，不管是从我们经常理解信息比特的物理层还是操作他们的设备都完全不同。我们制造这种设备的方法是不同的，需要新材料、新的设计规则和新的处理器架构。同时，我们编写这些系统的方法也完全不同。

从数学层面看，即使是最强大的超级电脑也没有办法突破序列任务设定的障碍，但量子计算机可以，因为它是基于量子的量子叠加、纠缠和干涉特征。因此量子计算最本质的特征就是量子叠加性和量子相干性。量子叠加是指一个量子系统可以处于多个基态的线性组合形式，例如一个量子比特可以处于叠加态。由此，一次操作U可以并行作用于两个态和上得到，即所谓的“一次操作同时完成多次计算”。然而，这里在并行性前面加了定语“潜在的”，即这种并行性并非直接就解决了问题，还需要后续算法设计。

简单讲，量子计算机是通过运行量子算法来实现量子信息处理，量子算法通过利用量子叠加性和量子相干特性来实现计算，是量子计算机的必要软件支撑，同时量子算法的研究也是推动量子计算发展的强大动力，其运行环节原理如下：

图2 量子算法运行原理

要保证算法的每一步骤符合量子力学的要求，并最终保证其求解速度比经典算法更快。能发挥量子计算并行性快速解决的问题在数学上通常是关于函数的某种全局属性，所谓全局属性即依赖于函数在某个区间中多个点处的函数值，例如函数的周期。科学家研究至今发现，应用量子算法的领域包括密码学、搜索和优化、量子系统的模拟以及解决大型线性方程系统，而潜在的应用，跨越了从基因组学到金融的各个行业。

主要的量子算法

Shor算法

Shor算法：采用现有计算机对数 N（二进制长度为logN）做因子分解，其运算步骤（时间）随输入长度（logN）指数增长。

Shor于1994年发现第一个量子算法，它可以有效地用来进行大数因子分解。大数因子分解是现在广泛用于电子银行、网络等领域的公开密钥体系 RSA安全性的依据。采用现有计算机对数 N（二进制长度为logN）做因子分解，其运算步骤（时间）随输入长度（logN）指数增长。迄今在实验上被分解的最大数为129位，1994年在世界范围内同时使用1600个工作站花了8个月时间才成功地完成了这个分解。若用同样计算功能来分解250位的数则要用80万年，而对于1000位的数，则要有10^25年[ii]。与此相反，量子计算机采用 Shor算法可以在几分之一秒内实现1000位数的因子分解，而且操作时间仅随输入数的3次方增长。可见 Shor量子算法将这类“难解”问题变成“易解”问题。在量子计算机面前，现有公开密钥RSA体系将无密可保。

最早的量子算法可以追溯到1985年的Deutsch算法。1985年DavidDeutsch在其关于量子图灵机的开创性论文中给出了一个简单问题，并为之设计了一个量子计算过程，通过利用量子叠加和干涉现象展现出了量子计算可能超越经典计算的优势，这为后续量子算法设计埋下了思想的种子。Shor算法源于Simon算法，而Simon算法源于那些看似没用的Deutsch-Jozsa算法和Deutsch算法。这个过程正好体现了科学研究的魅力，同时，Shor的开创性工作有力地刺激了量子计算机和量子密码术的发展，成为量子信息科学发展的重要里程碑之一。

应用：Shor算法在量子计算机上的实验实现一直是国际公认的难题。2001年，美国IBM公司和斯坦福大学合作，利用核磁共振技术演示了分解15的实验。但是由于核磁共振的固有缺陷，他们的实验不能显示该算法的量子属性，也无法扩展到更多比特，限制了进一步的应用。

2008年伊始，中国科学院公布，中国科技大学教授潘建伟和他的同事杨涛、陆朝阳等，与英国牛津大学的研究人员合作，在国际上首次利用光量子计算机实现了Shor量子分解算法，研究成果发表在当年1月出版的美国权威物理学期刊《物理评论快报》上，标志着我国光学量子计算研究达到了国际领先水平。

量子搜寻算法

Grover算法：每查询一次可以同时检查所有100万个号码。由于100万量子比特处于叠加态，量子干涉的效应会使前次的结果影响到下一次的量子操作，这种干涉生成的操作运算重复1000（即 N √）次后，获得正确答案的几率为1／2。但若再多重复操作几次，那么找到所需号码的几率接近于1。

第一个(有实用价值的)量子算法。1997年Grover发现了另一种很有用的量子算法，即所谓的量子搜寻算法，它适用于解决如下问题：从 N个未分类的客体中寻找出某个特定的客体。经典算法只能是一个接一个地搜寻，直到找到所要的客体为止，这种算法平均地讲要寻找 N／2次，成功几率为1／2,而采用Grover的量子算法则只需要Nkk√次。例如，要从有着100万个号码的电话本中找出某个指定号码，该电话本是以姓名为顺序编排的。经典方法是一个个找，平均要找50万次，才能以 1／2几率找到所要电话号码。Grover的量子算法是每查询一次可以同时检查所有100万个号码。由于100万量子比特处于叠加态，量子干涉的效应会使前次的结果影响到下一次的量子操作，这种干涉生成的操作运算重复1000（即 √N）次后，获得正确答案的几率为1／2。但若再多重复操作几次，那么找到所需电话号码的几率接近于1。

Grover算法的用途很广，可以寻找最大值、最小值、平均值等，也可以用于下棋。最有趣的是可有效地攻击密码体系，如DES体系，这个问题的实质是从256＝7×1016个可能的密钥中寻找一个正确的密钥。若以每秒100万密钥的运算速率操作，经典计算需要1000年，而采用Grover算法的量子计算机则只需小于4分钟的时间。难怪 Grover以“量子力学可以帮助在稻草堆中寻找一根针”这样的题目在PRL上公布他的算法。

量子退火

量子退火（QA）是用于通过使用量子波动的过程在给定的一组候选解（候选状态）上找到给定目标函数的全局最小值的元启发式。量子退火常用于搜索空间是离散的（组合优化问题）与许多局部最小值的问题。

量子退火算法的提出者是西森教授，量子退火算法是模拟退火算法的进阶，模拟退火算法用的是热力学的退火思想找minimum。而量子退火的中心思想是，量子力学的隧穿效应可以在寻找global minimum的时候更快地穿过局域极值点旁的势垒。

量子退火应用：

量子退火主要用于组合优化问题与局部最小值问题。组合优化问题，在应用数学和理论计算机科学领域，指的是在一个有限的对象里集中找出最优对象的一类课题。这类问题特征是可行解的集是离散或者可以简化到离散结果，并且目标是要找到最优解。当前，常见的组合优化问题通用版上包括旅行商问题和最小生成树，行业场景领域上涉及极大规模的集成电路设计、药物设计和财务组合管理等问题。显然，无论是金融、制药或是财务等领域，组合优化问题都是最贴近科技赋能日常生活与工作的实用问题之一，而退火算法是经过了实验和市场论证的最优解算工具。

量子退火的商业应用——量子退火机。量子退火机就是通过超导电路、相干量子计算（CIM）实施激光脉冲等方式、以及基于模拟退火（SA）的相干量子计算，与数字电路，如现场可编程门阵列（FPGA）等一起实现的量子算法。量子退火先从权重相同的所有可能状态（候选状态）的物理系统的量子叠加态开始运行，按照含时薛定谔方程开始量子演化。根据横向场的时间依赖强度，在不同的状态之间产生量子穿隧，使得所有候选状态不断改变，实现量子并行性。当横向场最终被关闭的时候，预期系统就已得到原优化问题的解，也就是到达相对应的经典伊辛模型(Ising Model)基态。这就是量子退火机的应用原理。

说到量子退火机，就不得不提到加拿大的一家量子计算机公司D-Wave。D-Wave商业销售的量子计算机原理是用金属铌制成的微小电流环形成量子比特，直接实现量子退火现象，可以模仿量子计算中单一比特存储大量数值的效果。值得注意的是，在商业应用落地上，量子退火方法可以通过使用叠加状态搜索各种可能性来有效地解决优化问题，有效满足各大企业对于实际工作方案的提效与加速需求。

D-Wave的架构不同于传统的量子计算机，不能等价于通用量子计算机，不能执行Shor算法，因为Shor算法不是爬山过程，需要通用的量子计算机。因此D-wave并不是通用型量子计算机，只能运行量子退火（Quantum Annealing）算法这一种算法而已。因为它的构造就是为基于量子退火设计的，没办法做其他量子计算。所以很多人并不觉得这是真正的量子计算机，只认为这是一种具有特定计算功能的量子结构。不过量子退火算法用处广泛，截至目前，D-Wave已在物流、人工智能、材料科学、药物发现、网络安全、故障检测和财务建模等各个领域，构建了250多款早期应用程序。

量子算法的发展趋势

现阶段，算法可独立于硬件研发。未来，要想充分发挥量子计算机的优势，必须使用具有量子叠加和纠缠特性的量子算法，来解决一些经典算法难以处理的问题。而目前很多人疑问的是：量子计算机还没造出来，现在有必要研究量子算法吗？我们认为现阶段，算法可独立于硬件发展，抽象层次的算法设计从来不依赖于具体硬件平台，在经典计算领域就是如此。算法本质上是解决问题的一种方法，量子算法是遵循量子力学规律的一种方法，硬件平台只是实现这种方法的一个工具。同时，从算法与复杂性研究的角度来看，算法的好坏由复杂度衡量，依赖于严格的数学证明，而不是在具体硬件平台上的测试。

具有代表性的量子算法有限，但研究较为活跃。量子算法只在特定问题上具有理论优势，并不能适用于所有问题，因此研究更多有使用价值的算法，将会为更多领域的应用实践提供支撑。从目前科学界的研究进展来看，按照 AshleyMontanaro 的介绍性综述 Quantumalgorithms: an overview，以及Stephen Jordan 等人维护的 QuantumAlgorithmZoo，我们看到，除了本文介绍的几个主流的量子算法，研究者在这方面做了很多努力，也取得了一系列成果，针对不同应用场景的量子算法已有上百个，一定程度上展现了量子算法领域研究较为活跃。

量子算法的外延随应用问题而发展。上述几个具有代表性的量子算法均是基于量子特性而在专用量子计算机或通用量子计算机上运行的量子算法，而在当前的学术研究中，利用量子特性与相关学科的相结合的算法也有较为深入的研究进展。量子遗传算法是量子计算与遗传算法相结合的智能优化算法，由K.H.Han等人提出，其将量子态、量子门、量子状态特性、概率幅等量子概念引入到遗传算法当中。量子遗传算法也是一种概率搜素算法，它采用量子位来表示基因。遗传算法的基因所表达的是某一确定的信息，而量子遗传算法中，由于量子信息的叠加性使量子位所表达的基因包含所有可能的信息。

什么是量子算法

量子算法是什么

主要的量子算法

Shor算法

量子搜寻算法

量子退火

量子算法的发展趋势