量子计算 | 从计算机科学讲起

量子计算作为量子信息技术的一个重要领域，在生物医药、化学材料、大数据分析优化、人工智能等领域有广泛的应用前景。近年来，我国在量子计算领域取得了不少世界级的重要成果，在产业化方面也正在迅速起步。

为帮助大家更好地了解量子计算的行业发展前景，中国信息协会量子信息分会官方微信公众号正式上线“量子计算专栏”，聚焦量子计算的应用，同大家分享量子计算发展历史、基本原理介绍、产业现状等内容。

本期将对量子计算的早期发展进行梳理汇总。

邱奇-图灵论题

为了理解量子计算的起源，首先需要回顾一下计算机科学的发展。一般认为，阿兰·图灵1936年那篇著名的文章宣告了现代计算机科学的诞生，文章中提出了如今被称为图灵机的计算模型。

在此基础上，图灵与阿隆佐·邱奇相互独立地提出了所谓邱奇-图灵论题：在任何硬件上实现的算法过程都能用通用图灵机等价实现。

之后各种其他计算模型被陆续提出来。60年代末70年代初人们意识到，这些计算模型相比图灵机并没有计算能力上的显著提升。从而诞生了强邱奇-图灵论题：任何算法过程都能用图灵机有效仿真。这里的“有效”是计算复杂度里的一个特定词汇，大致可以理解为“在随问题尺度多项式增长的时间内”。

70年代中期，强邱奇-图灵论题首次面临挑战：有人提出用随机算法来概率性地解决问题。通过多次重复提升概率，有望超越决定性图灵机的计算效率。这一挑战可以通过修正强邱奇-图灵命题来应对：任何算法过程都能用概率性图灵机有效仿真。

那么，有没有可能彻底打破强邱奇-图灵论题呢？这就是人们在80年代初提出量子计算的主要动机。

量子计算的提出

一般认为，量子计算是由贝尼奥夫、曼宁以及费曼在80年代初先后独立地提出的。曼宁和费曼都是从仿真量子系统的角度出发的：

也许【……】我们需要量子自动机的数学理论。【……】量子态空间的容量远远大于经典的：对于具有N 个态的经典系统，它的量子版本因为允许叠加，可以容纳cᴺ个态。当我们将两个经典体系合并时，它们的态数N₁与N₂会相乘，而在量子的情形我们会得到指数增长Cᴺ₁ᴺ₂【……】这些粗略的估计表明系统的量子行为可能比它的经典仿真复杂得多。

——尤里·曼宁（1980）

物理能用通用计算机仿真吗？【……】物理世界是量子力学的，因此合理的问题是量子物理的仿真【……】对一个R个粒子的大系统的量子力学的完整描述【……】包含太多变量了，用正比于R那么多个元件的常规计算机是无法仿真的。【……但它可以用量子计算机元件来仿真。】量子系统能用经典（假定是概率性的）通用计算机来概率性地仿真吗？如果你采用我之前描述的经典类型计算机【……】答案肯定是，不能！

——理查德·费曼（1982）

他俩的思路是类似的：量子体系的态数目是指数式增长的，因而很难用经典计算机（哪怕是概率性的）来有效仿真。但用量子体系构建的量子计算机是有可能的，因为至少每个量子体系都可以有效地仿真其自身！

量子计算模型

1980年，保罗·贝尼奥夫在他的文章提出了量子图灵机的初步构想。

1985年，多伊奇推广经典计算机的逻辑门电路，提出了量子电路模型。进一步研究发现，二者实际上是等价的。量子电路因为简单形象，现在被普遍接受。

本世纪初，人们提出了另一种通用量子计算模型，称作“基于测量的量子计算”。这一模型完全脱离了对量子门的依赖，只通过初态制备、单比特测量和前馈来实现所有运算，又称“单向模型”。值得一提的是，量子电路和单向模型都可以用ZX-演算来重新表述。（关于ZX-演算，我们之后会详加介绍。）

肖尔算法

90年代初，人们已经可以在一些人为问题上揭示出量子算法的优越性。这些发展最终促成了彼得·肖尔1994年在大数分解问题上的突破。

我们稍微介绍一点肖尔算法背后的原理。量子比特可以处于叠加状态：|ψ>=α|0>+β|1>.因此，一次单比特操作就可以实现长度为2的离散傅里叶变换。这其实是所谓的阿达马门H：H|0>= (|0>+|1>)/√2,    H|1>= (|0>−|1>)/√2.

对n个量子比特都作用H门，可以实现n重长度2的离散傅里叶变换。这会在一些特殊的计算问题上体现出指数级的优越性——正如多伊奇-乔萨算法和西蒙算法所展示的。

肖尔的独创之处在于，他指出可以利用一系列n比特门直接实现长度为2ⁿ的离散傅里叶变换。相比于傅里叶变换的经典算法，这一实现方案达到了指数级的加速。在此基础上，肖尔给出了大数分解以及离散对数问题的高效算法，在理论上证实了量子计算在实际应用方面的巨大潜力。同时，这也在一定程度上实现了人们早期发展量子计算的预期目标。肖尔算法后来被推广到一大类隐子群问题中，至今仍属于热门研究。

硬件实现方式

哪怕局限于以量子比特为基本单元的量子电路模型上，量子计算的硬件实现方式依然非常丰富。例如，中科大的“祖冲之号”用的是超导电路，而“九章”则用的是光量子。原则上任何包含两个量子态的体系都可以用来实现量子比特。不同的硬件体系有各自的优劣，目前还很难有定论。

本文将它们简单分成两类：拓扑实现和非拓扑实现，然后加以对比。作为朗道范式的推广者，文小刚及其合作者在1989年提出了多体系统的“拓扑序”。拓扑序由体系的长程量子纠缠决定，因而不受局域扰动的影响。1997年，阿列克谢·基塔耶夫进一步提出，利用拓扑序体系的拓扑激发——任意子，可以实现容错量子计算。拓扑量子计算后来成为微软公司的主要发展方向。然而，拓扑序体系至今为止仍未在实验中证实，给拓扑计算的发展带来了巨大的困难。

非拓扑的实现方式则相对比较容易，但同时也更容易受到环境的影响，所以必须对物理量子比特进行纠错，最终实现容错计算。近十年来，多种硬件方案在门保真度和纠错性能方面都取得了大幅的进步。

事实上，这两种实现方式并非毫无关联。在纠错中广泛采用的表面码，就是一种特殊的拓扑序模型“环面码”在平面上的形式。而利用当前的超导量子电路，人们已经能仿真出简单拓扑序体系的一些性质。或许在不远的将来，二者可以融为一体，共同形成一种实用的容错量子计算机。

本文作者：

上海微观纪元数字科技有限公司左芬博士。

参考文献：

迈克尔·尼尔森,艾萨克·庄:《量子计算与量子信息》;

鲍勃·科克,亚里克斯·基辛格:《图解量子过程：量子理论与图形化推理入门》。