摘要

萌生于上世纪70年代的量子信息技术被寄予突破现有信息技术的物理极限的厚望，在信息处理速度、信息容量、信息安全性、信息检测精度等方面均能够发挥极大作用，进而显著提升人类获取、传输和处理信息的能力，为未来信息社会的演进和发展提供强劲动力。量子计算理论在20世纪初风光无限，Google, IBM等巨人入场，量子计算资源成为国家战略资源，但2017年后，随着Google高管离职，学术界也发出了“量子计算是一场骗局”的声音。本论文希望梳理量子计算发展阶段，对并行算法思想在各个发展阶段成果的整理和总结。同时对量子计算现今的境况进行合理化分析。

前言

量子计算是一种遵循量子力学规律调控量子信息单元进行计算的新型计算模式。对比传统的通用计算机的理论模型，通用图灵机。通用的量子计算机的理论模型是用量子力学规律重新诠释的通用图灵机。可计算角度来看，量子计算并不能解决传统计算机理论上无法求解的问题。但是由于量子力学叠加性的存在某些已知的量子算法在处理问题时速度要快于传统的通用计算机。论文将按照量子计算发展概述、并行思想发展路线、量子计算发展现状及展望三方面进行讲解。

一、量子计算发展综述

（一）量子计算的内涵

量子计算是量子信息科学的一条重要分支。量子信息科学是量子物理与信息科学交叉的新生学科，其物理基础是量子力学。量子力学就是研究和描述微观世界基本粒结构、性质及相互作用的一门科学。量子信息技术借助量子叠加和量子纠缠等独特物理现象，以经典理论无法实现的方式获取、传输和处理信息的一类技术。

量子计算的内涵与量子比特、量子叠加和量子纠缠等几个量子态受控的基本概念息息相关。

量子比特是量子计算中的最小信息单位。一个量子比特可以表示0、1或0和1的叠加，因此其搭载的信息量远超智能表示0或1的经典比特。

量子叠加是指一个量子系统可以处在不同量子态的叠加态上。在量子系统中，量子态是指微观粒子所处的一系列不连续的恒稳运动状态。在无外界观测干扰时，量子系统可处于一系列量子态叠加态上。

量子纠缠是指微观粒子在由两个或两个以上粒子组成系统中相互影响影响的现象。在量子系统中，存在量子关联的多个粒子即使在空间上被分隔开，也能够相互影响运动状态。

从本质上看，量子计算是基于量子态受控演化的一类计算技术。量子计算具有经典计算无法比拟的巨大信息携带和超强并行处理能力，有望成为未来几乎所有科技领域加速发展的“新引擎”。

（二）量子计算的基本原理与特征

从技术角度，量子计算以量子比特为基本单元，通过量子态的受控演化实现数据的存储计算。据此制造的量子计算机就是遵循量子力学规律，基于上述原理进行信息处理的一类物理装置。

一般而言，量子计算机的计算过程可以分为数据输入、初态制备、 量子逻辑门操作、量子测算和数据输出等步骤。其中，量子逻辑门操作是一个幺正变换，这是一个可以人为控制的量子物理演化过程。对量子计算机的可用性而言，需要从量子比特数、长相干时间保护、高保真度量子操作等多个维度进行综合衡量。

与经典计算相比，量子计算具有以下特点：

(1)并行计算能力更强。

一般地，描述 n 个量子比特的量子计算机需要 2n 个系数数字，但由于量子叠加效应[2]，量子计算过程中的幺正变换可以对处于叠加态的所有分量同时进行操作（也即量子并行性）。因此，量子计算机可以同时进行多路并行运算，这也是量子计算机超强信息处理能力的源泉。

(2)量子信息的存储量大。

根据量子叠加态原理，2个经典比特有4种情况，00，01，10，11，但是这两个比特只能处于其中一个态，就只能存1种的信息；但是量子比特（qubit）可以处于这四种情况的叠加态，就可以存储4种信息。类似的，量子信息存储的量就是经典信息的指数倍。

（3）能耗更低。

当前，经典计算中运算速度遇到的一大瓶颈就是能耗问题对芯片集成度的制约。直观而言，传统芯片的特征尺寸很小（数纳米）时， 量子隧穿效应开始显著，电子受到的束缚减小，使得芯片功能降低、 能耗提高。因此，必须将不可逆操作改造为可逆操作，才能大大提高芯片的集成度。有研究表明，能耗产生于计算过程中的不可逆操作。相较之下，量子计算中的幺正变换属于可逆操作，因而信息处理过程中的能耗较低，应用场景广阔。

（三）量子计算理论发展阶段总览

迄今为止，量子计算的发展可分为三个阶段。20 世纪 90 年代以前的理论探索阶段、20 世纪 90 年代的编码算法研究阶段、21 世纪以来的技术验证和原理样机研制的阶段。

基础理论探索阶段的成就主要集中于量子算法的设计和研究。1982 年，Benioff 提出量子计算机概念， Feynman 也提出利用量子系统进行信息处理的设想。1985 年，Deutsch 算法首次验证了量子计算并行性。

编码算法研究阶段提出了许多真正有价值的量子算法，引起了学术圈的震动。1994 和 1996 年，Shor 算法和 Grover 算法分别提出。前者是一种针对整数分解问题的量子算法，后者是一种数据库搜索算法。 这两种量子算法在特定问题上展现出优于经典算法的巨大优势，引起了科学界对量子计算的真正重视。

技术验证和原理样机研制的阶段则聚焦于量子芯片的研发，以实现通用量子计算机为最终目标。2019 年，IBM 发布最新 IBM Q System One 量子计算机，提出衡量量子计算进展的专用性能指标——量子体积，并据此提出了 “量子摩尔定律”，即量子计算机的量子体积每年增加一倍。若该规律成立，则人类有望在 10 年内实现量子霸权。实现量子霸权后，通用量子计算机的研发计划就会提上日程了。

二、并行思想发展路线

并行思想在我看来是量子计算的一大核心思想。如果没有同步性的加持，量子计算机也不可能真正替代电子计算机。

所以说并行思想是时刻伴随在量子技术发展的路线上的。量子芯片即为量子计算机的物理实现与硬件系统，量子算法则是将量子计算机计算效率最大化的软件系统。我们也就可以承接上文，从量子算法和量子芯片两方面阐述并行算法的优异之处。

（一）量子算法研究

量子算法角度的研究有很多很有价值的问题，比如著名的NP难问题。如果说量子算法可以让我们的算力空前提高，那很多密码也就称不上安全了。

在量子计算的物理实现方面，最重要的莫过于DJ算法，因为它能非常简单地证明量子计算的加速能力。在应用前景方面，莫过于可以破解RSA公钥体系的Shor算法，和可以解决大部分问题的Grover搜索算法。而量子计算算法的并行特征，可以从DJ算法中窥见一二。

DJ算法的目标是已知未知的黑盒f

，判断函数f是常函数还是均匀的函数。这里均匀指的是：f(x)对于恰好一半的x得0，而对另恰好一半的x得1。

对于这个问题，传统解决方法很简单：做多次访问，若做k次访问，输出结果不完全相同，则必为平衡函数；若做k次访问，输出结果都相同，则可能为常数函数。要想做出准确的判断，这个k必须超过2^(n-1)，这个算法的复杂度是随着n的增大而指数增多的。

量子算法的解决方法则依赖“并行“，只需要一步就可以判断是常数函数还是平衡函数，其逻辑门操作如图：

有两条很明显的线路，上方的那条线路实际上表示n个比特|0>,下方那条表示辅助比特|1>，作Hadamard变换，然后经过Uf变换，再对输出比特（不包括辅助比特）进行Hadamard变换即可得到一个可以判断是常数函数还是平衡函数的等式。

最能体现这一思想的是通过uf前后和最后的测量部分。

这是通过uf前的两条路：

n个比特集中在一条路上，而Uf对于|x相当于单位矩阵In一样，为什么这样出来的结果为什么会大大减少工作量呢？

问题出在“Uf对于|x相当于单位矩阵In”这句话上。事实上，Uf并不能写作InUf′的形式，也就是说Uf并不能分成两个矩阵分别影响上下两条线路。从物理层面上讲，经过Uf门之后，上下两条线路（|x和|y⊕f(x)发生了纠缠，所以Uf门输出的“两条线路”也无法分成“|x(|y⊕f(x))”这样的“张量积”形式，因而不能分开单独考虑了。

最后进行实验测量部分的检查是看对应的量子数。我们以 |0x^{\otimes n} 为基进行测量，落到这个基上的概率是

.如果f(x)是常数函数，这个概率就是1；如果是平衡函数，这个概率就是0.也就是说对于最后的测量，如果落在

为上，就是常数函数；如果不落在|0x^{\otimes n}上，就是平衡函数，实现了一步解决问题，同时也说明了量子计算相对于经典计算的强大之处。

量子算法精妙无比，后文由基于量子云平台的演示，可以从中一窥并行计算的精妙所在。

（二）量子芯片研究

将量子力学理论与计算机技术相结合的概念由美国物理学家 Feynman 于 1982 年首次提出。3 年后，英国牛津大学的 Deutsch 团队 10 对量子计算机的概念进行了进一步阐述，并提出研究如何由量子逻辑门构成逻辑网络是实现通用量子计算机的核心。

目前，量子计算的各类物理体系虽都取得了较大进展，有多种量子芯片已经初见雏形。但未来哪种物理实现系统最终可研制成通用量子计算机尚无定论。

（1）超导量子算法

超导量子计算利用超低温“冻结”粒子的运动进而实现粒子状态的控制，量子比特有超导相位、超导磁通和超导电荷三种形式。超导量子计算的核心单元是约瑟夫森结，约瑟夫森结是一种“超导体—绝缘体—超导体”的三层结构。

（2）半导体量子点

半导体量子点也是基于现有半导体工艺的一种量子计算物理实现方法。在平面半导体电子器件上制备出的单电子晶体管，其电子服从量子力学运动规律，电子自旋的向上和向下组成的系统可作为一个量子比特。根据电子的泡利不相容原理，通过自旋和电荷之间的关联，可以通过普通的电子开关（门）对电子自旋进行控制，完成包括单量子比特操作、两量子比特操作及结果的读出等在内的对电子自旋编码 的量子比特的各种操作①。

（3）光学量子计算

光学量子计算（OQC）是基于测量的量子计算方案，利用光子的偏振或其他自由度作为量子比特，光子是一种十分理想的量子比特的载体，以常用的量子光学手段即可实现量子操作。

光学量子计算根据 其物理架构分为两种：KLM 光学量子计算以及团簇态光学量子计算。 KLM 光学量子计算仅使用单光子、线性光学和测量，允许通过和可扩展光学量子计算，目前已经实现了光子-光子之间的两量子位的逻辑操作。

团簇态光学量子计算由一个高度纠缠的成为团簇态的多粒子态组成，与单量子测量和前馈相结合，实现可扩展的通用量子计算， 具有降低整体复杂性和放宽测量过程的物理需求，以及物理资源的更有效利用等技术优势。 由于光子与环境相互作用很小，光学量子计算具有相干时间长、 操控手段简单、与光纤和集成光学技术的相容性，以及简单的资源可 14 扩展性等优点。

也就是说，从本质上，这三点都是基于量子的三大特点进行的研究。看起来虽然和量子计算的并行性关系不大，但是基于量子交缠等基本物理原理，时间这一重要的物理因素绝对被考虑了进去。特别是我国技术领先的光量子研究，光的相干性更是和“时间”密不可分。

三、量子计算发展现状及展望

量子计算的宏观发展集中在量子云平台和量子芯片的研发。量子芯片的研发上文已经做出阐述，相信不难理解。我国的量子芯片研发主要在超导量子和光量子两部分。

在光电子技术进展方面，目前中国研究团队已经在实验室产生了同时具备高系统效率（33%）、高纯度（97%）和高全同性（90%）的高品质单 光子源和基于参量下转换的 10 光子纠缠。在此基础上，光学量子计算的基本操作（如概率性的控制逻辑门）和各种算法（大数分解算法、 数据库搜索、线性方程组求解算法、机器学习、波色取样）的简单演示验证也已经实现。但也正是由于光子之间相互作用微乎其微，导致两量子比特之间的逻辑门操作难以实现。 所以我们现在的实用性量子计算机还是基于超导的。

下图为如今我国自研的量子云计算平台的量子算法实例化演示。

实验非常简单，只是为了展示量子计算逻辑门使用以及最终成果展示的奇妙。

量子比特的选择是随机的，我们能够通过在某个取值的频率进行选择。

量子计算的应用前景光明，在多个领域都能有一席之地。

从中短期来看，量子计算主要可在量子模拟、量子优化和量子增强人工智能等方面发挥作用。 量子模拟。在传统计算中，由于难以精确求解方程，当前的计算化学方法严重依赖近似值。相比之下，量子计算所依赖的量子力学是自然界最基本的物理原理，因此量子计算天然适于模拟各类物理、化学过程，能够在更长时间范围内准确模拟分子行为，因此能够大幅提升建模精度，在生物药物、化工材料等领域提升研发效率、 缩短产品开发周期。例如，在生物医药领域，药物研发的前、中、后期都需要大量数据计算，尤其在中期环节，需要极高的计算能力以支撑分子性质模拟和药品功能设计。

量子优化。优化问题需要从诸多解决方案中找到最优解，对传统计算而言，在大规模物流网络等复杂系统中，设计满足各种需求的最优路线的计算量很大。例如，对仅有数百个集散地的物流网络而言， 而穷尽所有可能性，传统计算机需要数十亿年时间。量子计算则能大幅提升计算效率，从而在物流运输、金融资产管理、网络基础设施等领域中提升运营效率、减少碳排放等。

量子增强人工智能。人工智能对算力需求的一大特征即海量异构 数据的并行计算，这也是传统 CPU 芯片难以胜任，从而导致 GPU、 FPGA、ASIC 等芯片在人工智能领域大受欢迎的原因。

如上文所述， 量子计算的超强算力源自量子并行性，因而其十分适于进行人工智能所需的并行计算。当前，量子计算已经开始用于提升机器学习在数据聚类等领域的能力，但目前成果方面还有不太充足。像老师所说的，量子算法考虑其复杂性也应当考虑制造量子计算机的复杂性，如果没有很强力的算法能够设计出量子计算器，量子计算中短期恐怕要蒙上一层阴影。

参考文献

[1]Neven H, Denchev V S, Rose G, et al. Training a large scale classifier with the quantum adiabatic algorithm[J]. arXiv preprint arXiv:0912.0779, 2009.

[2]Neven H, Denchev V S, Rose G, et al. QBoost: Large Scale Classifier Training with Adiabatic Quantum Optimization[C]//ACML. 2012: 333-348.

[3]Denchev V S, Ding N, Vishwanathan S V N, et al. Robust classification with adiabatic quantum optimization[J]. arXiv preprint arXiv:1205.1148, 2012.

[4]Babbush R, Dnchev V, Ding N, et al. Construction of non-convex polynomial loss functions for training a binary classifier with quantum annealing[J]. arXiv preprint arXiv:1406.4203, 2014.

[5]Boixo S, Smelyanskiy V N, Shabani A, et al. Computational role of collective tunneling in a quantum annealer[J]. arXiv preprint arXiv:1411.4036, 2014.

[6]Smelyanskiy V, Boixo S, Shabani A, et al. Collective disispative tunneling during quantum annealing on D-Wave II device[J]. Bulletin of the American Physical Society, 2015, 60.

[7]Kafri D, Quintana C, Chen Y, et al. Tunable inductive coupling of superconducting qubits in the strongly nonlinear regime[J]. Physical Review A, 2017, 95(5): 052333.

[8]Dunsworth A, Megrant A, Quintana C, et al. Characterization and reduction of capacitive loss induced by sub-micron Josephson junction fabrication in superconducting qubits[J]. Applied Physics Letters, 2017, 111(2): 022601.