第1章引言和预备知识

量子软件工程的挑战在于如何对传统的软件工程进行重新设计和扩展，使得程序员可以像操纵传统程序一样对量子程序进行操纵。
--Grand Challenges in Computing Research (2004)
量子编程主要研究如何在未来的量子计算机上编程，包括下面两个问题：

现有的编程方法和技术如何扩展到量子计算机上？
什么样的编程方法和技术可以有效利用量子计算的特有能力？

因为量子系统中存在奇异的特征，如量子信息的不可克隆性、量子进程之间的纠缠、观测结果不可交换等均深植于程序变量之中，所以许多在传统计算机编程领域取得极大成功的技术难以迁移到量子计算机上。更重要也更具挑战性的问题是：如何寻找抽象的编程范式和编程模型等才能最大化地利用量子计算的特有能力——并行性？这个问题并不能从传统的编程经验中获得启示。

1.1量子编程研究简史

量子编程的概念最早是Knill在1996年提出的。他设计了量子随机访问机；(QRAM)模型，并提出一系列编写量子伪代码的规定。在接下来的20年中，量子编程的研究继续如火如荼地进行，主要包括以下几个方向。

1.1.1量子编程语言的设计

早期研究主要集中在量子编程语言的设计方面。20世纪90年代末和21世纪初，有几种高级量子编程语言被设计出来。例如，Omer设计了第一个量子编程语言QCL,此外,他还实现了该语言的模拟器。Sanders和Zuliani基于Dijkstra卫式命令语言提出了量子编程语言qGCLo。Bettelli等人对C++进行了扩展，并实现了一个用于量子编程的C++库。将经典程序控制流与量子数据相结合，Selinger定义了第一个函数式量子编程语言QPL。随后，Altenkirch和Grattage回引入量子控制流设计了量子函数式编程语言 QML。Tafliovich和Hehner对一种谓词编程语言进行了量子化的扩展，该扩展语言可以为这样的程序开发技术提供支持，即用它开发出来的程序所执行的每一步都可以被证明是正确的。
最近，Green等人和Abhari等人分别设计了两个通用的、可扩展的量子编程语言Quipper和Scaffold,并开发了它们的编译器。Lapets等人设计了领域专用的量子编程语言QuaFL。除此之外，Wecker和Svore开发了量子软件体系结构LIQUi|），并提供了内置于F#的量子编程语言。

1.1.2量子编程语言的语义

编程语言的形式语义是对该语言的严格数学描述，以便能够对该语言语法之下的本质有精确而深刻的理解。一些量子编程语言的操作语义或指称语义在定义的时候就已经提供了，比如 qGCL、QPL和QML。
人们提出了两种量子程序谓词转换语义的思路。第一种是Sanders和Zuliani在设计qGCL的时候提出的：通过观测（测量）步骤，将量子计算归约为概率计算，这样为概率程序开发的谓词转换语义就可以移植到量子程序中来。第二种是DHondt和Panangaden设计的，它将量子谓词定义为由特征值所属单位区间内的厄米算子所表示的物理可观测量。针对一类称为投影算子的特殊量子谓词，文献［225］对量子谓词转换语义做了进一步研究。人们将注意力集中于投影谓词，是因为它允许使用Bitkhoff-von Neumann量子逻辑中丰富的数学工具去建立各种量子程序的健壮性条件。
人们还对一些量子计算的技术进行了研究，这些技术往往是抽象的，与具体的编程语言无关。Abramsky和Coeck提出了一种基于量子力学基本假设的范畴论公式，我们可以用它来对量子程序和通信协议（比如隐形传态）进行优美的描述。
该领域近来的进展如下。基于Girard发明的，并由AbramskyHaghverdi和Scott 进一步范式化的交互几何，Hasuo和Hoshino提出了一种包含递归的函数式量子编程语义模型。Pagani. Selinger和Valiron为这种函数式编程语言设计了一种指称语义，这类量子编程语言带有递归特性，以及根据线性逻辑量化语义构造出来的无限数据类型。Jacobs对量子编程中的块状结构进行了范畴式的公理化描述。Staton提出了一种可以对量子程序进行公式化推理的代数语义框架。

1.1.3量子程序的验证和分析

与量子世界相比，人类的直观感受与经典世界更加契合。而这恰恰意味着，相比在经典计算机上进行编程，人们在量子计算机上进行编程可能会出现更多的错误。因此，对量子程序的验证技术进行研究至关重要。Baltag和Smets的对量子系统中的信息流进行了动态逻辑的形式化描述。Brunet和Jorrand介绍了一种使用Bitkhoff-von Neumann量子逻辑对量子程序进行推理的方法。Chadha、Mateus和Sernadas提出一种Floyd-Hoare体系的证明系统来对那些只允许边界迭代的命令式量子系统进行推理。Feng等人提出了一些有用的证明法则用于对纯粹的量子程序进行推理。文献［221］开发了满足完备性的量子程序中局部和整体正确性的Floyd-Hoare逻辑。
在实现和优化程序的过程中，程序分析技术非常有用。文献［227］率先对量子程序终止性分析进行了研究，它研究了以幺正变换作为循环体的基于测量的量子循环。文献［234］使用量子马尔可夫链的语义模型对一般性量子循环的可终止性进行了研究。文献［234］也证明了，可以通过量子态和可观测量之间的Schr6dinger-Heisenberg对偶性将证明概率性程序属性的Sharir-Pnueli-Hart方法进行扩展，使其在量子程序中也同样适用。这一研究思路在文献［152-153,235-236,238］中得以延续，它们均基于量子马尔可夫决策过程的可达性分析对不确定性和并发性量子程序的可终止性进行了研究。Jorrand和Perdrix提出了另一类量子程序分析技术，他们揭示了如何将抽象解释技术应用到量子程序中。

1.2量子编程的方法

很自然地，对量子编程的研究是从将经典程序设计模型、方法和技术扩展到量子领域开始的。正如1.1节所述，相关研究人员已经设计了命令式和函数式量子编程语言，并对许多经典程序的语义模型、验证和分析技术进行了扩展，使其可以适用于量子编程。
量子编程的最终目的是最大限度地发挥量子计算机的计算能力。相较于现有的计算机, 量子计算机的主要优势来源于它的并行性——量子叠加态，以及由此衍生出来的诸如量子纠缠的概念。所以，量子编程中的一个关键问题就是如何将量子并行性的优势与现有的传统编程模型进行结合。在我看来，可以通过如下两种叠加范式来解决这个问题。

1.2.1数据叠加——带经典控制的量子程序

数据叠加范式的主要思路是引入一类可以操控量子数据的程序结构，比如幺正变换、量子测量等。但是，使用这类范式的量子程序的控制流与经典编程中的控制流非常相似。举例来说,在经典编程中，一般用于定义控制流的基本程序结构是条件语句(if…then . . • else - .fi), 或者更具一般性的case语句：

对于任意的2,子程序Pi由布尔表达式Gi所控制，且只有当e是true的时候才会执行 Pi.对公式(1.1)的一个很自然的量子化扩展是基于测量的case语句：

其中q是量子变量，M是对q进行的测量操作，mi,••• ,mn是测量M所有可能的结果。对于任意的i, Pi都是一个量子子程序。该语句会根据测量M的结果选择一条命令去执行: 如果输出是血分，那么会执行相应的程序因为是根据经典信息 —— 量子测量的结果来选择需要执行的程序的，所以我们将上述过程称为使用经典控制的量子编程。因此，可以基于这类case语句对量子编程中其他的程序结构(比如循环和递归)的控制流进行定义。
因为输入的数据和程序计算的都是量子数据，即数据叠加，但程序本身不允许叠加，所以我们将上述编程范式称为数据叠加范式。因为程序中的数据流是量子的，但是控制流仍然是经典的，所以Selinger将这类范式精准地描述为“量子数据，经典控制”。
目前关于量子编程的主要研究方向是数据叠加范式，该范式使用经典控制流对量子编程进行处理。

1.2.2程序叠加——带量子控制的量子程序

受量子游走的结构启发，人们发现还可以用一类在本质上与数据叠加范式完全不同的方法定义量子编程中的case语句 —— 由量子“硬币"控制的量子case语句：

其中是外部“硬币”系统c的状态希尔伯特空间的一组标准正交基，根据“硬币”空间的基态来选择子程序Pi去执行。因为态是可以叠加的，所以这是量子信息而非经典信息。此外，我们可以定义量子选择：

直观上而言，量子选择(1.4)通过“掷硬币”程序C构造子程序3, • • •,耳的执行路径的叠加态，然后再执行量子case语句。在量子case语句的执行过程中，每一个子程序Pi都在自己的执行路径上独立运行，且它们各自的执行路径都包含于Pi,・・・R 所组成的叠加态中。我们可以基于这类量子case语句和量子选择对一些新的量子程序结构进行定义，比如量子递归。
我们将这类量子编程方法称为程序叠加范式。从量子case语句和量子选择中可以发现，程序叠加范式中的控制流具有天然的量子特性。所以，可以将这类范式描述为“量子数据，量子控制”。
必须承认，这种范式还处于发展的初级阶段，还有一系列基础性的问题没有解决。但另一方面，我坚信这种范式引入了一种新的考虑量子编程的方法，这种方法可以帮助程序员进一步开拓量子计算强大的计算能力。

1.3全书结构

这本书以从数据叠加到量子叠加为线索，对量子编程理论基础进行了系统的论述。本书主要介绍命令式函数编程，但是大多数的观点和技术也同样可以推广到函数式量子编程中。
本书分为以下四个部分：

第一部分包括本章和第2章(预备知识)。阅读本书首先需要对量子力学、量子计算和编程语言有大致的了解。第2章对量子力学和量子计算所需的基础知识进行了介绍。至于编程语言理论，建议读者查阅标准教科书，[21,158,162,200]。
第二部分研究数据叠加范式中带经典控制的量子程序，共分为三章。第3章详细地介绍了带经典控制（条件语句、循环和递归）的量子程序的语法、操作语义和指称语义。第4章介绍了对带经典控制的量子程序的正确性进行推理论证的逻辑基础。第5章设计了一系列用于分析带经典控制的量子程序的数学工具和算法技术。
第三部分研究程序叠加范式中带量子控制的量子程序，分为两章。第6章定义了量子case语句和量子选择及其语义，并建立了一套可以对包含量子case语句和量子选择在内的量子程序进行推理的代数法则。第7章举例说明了如何使用量子case语句和量子选择来定义带量子控制的递归。此外，还通过二次量子化（即一类处理可能包含不同数量粒子的量子系统的数学框架）对这类递归的语义进行了定义。
第四部分由独立的一章组成，列举了几个在量子编程方面很重要却没有在上述部分提及的问题，并指出下一步计划研究的几个方向。

关于阅读本书：从图1.1中，我们发现可以通过以下三种路径完成对本书的阅读：
- 路径1：第2章-第3章一第4章。这条路径针对对量子程序的逻辑感兴趣的读者。
- 路径2：第2章-第3章一第5章。这条路径针对对量子程序的分析感兴趣的读者。
- 路径3：第2章一第3章一第6章一第7章。这条路径针对想要学习数据叠加范式和程序叠加范式的量子程序结构的读者。

当然，从头到尾读完本书，读者才能得到一幅关于量子编程的全景画面。

教学建议：关于量子编程的短期课程可以基于第2章和第3章来进行教学。此外，本书的第一部分和第二部分可以作为本科生或者研究生一个学期或者两个学期的课程内容。如果是一个学期的课程，那么教学安排可以根据前面介绍的前两条路径之一进行设计。因为带量子控制的量子编程理论（程序叠加范式）仍处于发展的初级阶段，所以最好将第6章和第7章的内容作为研讨班的材料而非教学课程内容。
练习：本书中有一些引理和命题的证明留作练习。它们通常都不太难，通过完成这些练习，读者可以更好地理解相关内容。
研究问题：本书第二部分和第三部分每章的最后都会给出一些未来有待研究的问题。
文献注解：第2章到第7章的最后一节都是文献注解，给出了引用和参考文献，并为接下来的阅读提供建议。本书最后提供了完整的参考文献，包括按照首字母排序的引用文献和推荐阅读书目的列表。

带你读《量子编程基础》之一：量子编程研究简史

第1章引言和预备知识