量子程序设计研究进展丁圣超2005年10月11日0引言正式量子计算的研究应该认为从1982年R. Feynman的论文《Simulating Physics with Computers》[1]开始，在这篇开创性的论文中，Feynman认为构造基于量子机制的计算机可能能够有效模拟量子系统或其他物理系统，而这种模拟对于传统计算机来说是相当困难的。

在1985年，Deutsch[2]讨论了量子计算机可能的计算能力，并相对于经典图灵机提出了量子图灵机(Quantum Turing Machine, QTM)的概念。

随后，在20世纪90年代中期，发现了Shor[3]量子因子分解算法和Grover[4]量子搜索算法，这两类算法展示了量子计算从根本上超越经典计算机计算能力和在信息处理方面的巨大潜力。

与此同时，量子计算机和量子信息处理装置的物理实现的研究，成为继并行计算、生物计算之后的又一研究热点。

另一量子计算研究领域的热点是量子密码技术，但不是我们感兴趣的。

这里关注的是量子程序设计的相关技术的研究。

一般认为，量子计算的几个基本要求是[5]：鲁棒地表示量子信息完成酉变换的通用性族制备基准初态测量输出结果事实上，目前量子计算机的物理实现相当有限，最多的是IBM在实验室实现的7个量子位的量子设备。

然而，对于量子程序设计的前瞻性研究还是很有必要的，至少这样做可以摆脱缺乏严格的理论基础的尴尬，在传统计算机上的程序设计就曾广泛存在这样的问题。

我认为量子程序设计的相关研究领域可以大致分为如下几个方面：量子计算机体系结构量子程序设计语言的研究语法语义的研究量子程序编译量子计算模拟而且这些方面彼此之间有关联，或是有部分重叠。

1 量子计算机体系结构1.1 QRAM(Quantum Random Access Machine)由Knill[6]提出，在这篇论文中作者没有给出QRAM形式化的定义，但是作者指出QRAM是一种主从式机器，应由量子寄存器组成，由传统计算机进行的传统计算，对量子计算进行预处理，并控制量子寄存器的状态演化，最后获得量子系统的测量结果，而且该机器具有在量子寄存器上进行状态制备、酉转换和测量等量子操作的能力。

1.2 SQRAM(Sequential Quantum Random Access Machine)[7]在QRAM的基础上提出了一种量子计算SQRAM体系结构。

这种结构是一个传统计算机和量子计算机的混合体。

作者描述了一个合适的指令集，实现了量子门的一个通用集，并通过运行Deutsch的量子算法[5]证明了SQRAM操作的有效性。

其体系结构和操作周期如下图所示。

图1. SQRAM的体系结构图2. SQRAM的操作周期2 量子程序设计语言的研究量子程序设计语言的研究是一项艰巨的工作。

因为目前我们仅发现了极其有限的量子算法，而且我们尚不清楚未来的量子计算机是否拥有一个象传统计算机一样的中央处理器。

目前量子程序设计语言的研究都是基于上述的QRAM和SQRAM量子计算机体系结构的。

[6, 8, 9, 7]讨论了量子程序设计语言应该具有的几个特征：Classical Characteristics：多年的传统程序设计语言的研究可对量子程序设计语言的研究给予很多启发。

Completeness：一种量子程序设计语言应该是通用的，应该能够描述所有的量子算法，具有与量子线路模型相同的表达能力。

Expressivity：该语言应该给程序设计者提供充足的操作指令，并提供能够方便构造量子程序的机制。

Separability ：应该易于分离程序中的量子部分和传统部分，这样可以简化编译器的设计，并易于程序的执行。

Hardware Independence ：一种高级程序设计语言应该与特定的机器实现无关，应尽可能将量子图灵机(Quantum Turing Machine, QTM)作为其执行平台。

Extension of Classical Languages ：量子程序设计语言如果能够从已广泛使用的传统设计语言进行扩展，应该比一种全新的语言更受欢迎。

本文借鉴了文献[10]对程序设计语言的分类方法。

2.1命令式语言(imperative languages)最早的形式化的量子程序设计语言可能是Knill[6]的量子程序设计伪代码语言，这种语言适合在QRAM 上实现。

在这种语言中，量子寄存器被视为具有不确定状态的传统寄存器，在伪代码中用带下划线的字母表示。

Knill 给出了如何在伪代码中引入量子寄存器、量子寄存器和传统寄存器如何转换等问题的建议。

例如，一个寄存器不能同时以量子形式出现在一条语句两边；出现在语句左边的寄存器要么是传统的，要么是从未定义过的新的寄存器（量子的或传统的）；等等。

同时，Knill 也意识到，这种量子伪代码语言本身并不精确，并不是一种可实现的量子程序设计语言；然而，这毕竟在如何叙述量子操作和测量的应用上迈出了重要的一步。

经过几年的发展，Ömer 在C 语言的语法启发下，第一次提出了一种真正实现的量子程序设计语言，QCL(Quantum Computing Language)[11, 12, 13, 14, 15]。

他也实现了该语言的一种模拟器，可以从http://tph.tuwien.ac.at/~oemer/qcl.html 免费获得。

QCL 是一种结构化量子程序设计语言，它将传统程序设计中的如变量、数据类型、循环、条件分支、子程序、局部变量、动态内存分配等概念进行量子化，设计了相应的量子形式。

QCL 的主要特征包括：具有函数、流控制、交互式I/O 、各种传统数据类型（int, real, complex, boolean, string ）的传统控制机制，语法接近于C 语言；除传统程序设计语言的过程和函数两种结构外，提供两种量子操作类型：通用酉操作(operator)和可逆的伪标准门(qufunct)；为编译器提供各种量子数据类型(qubit 寄存器)：qureg, quconst, quvoid, quscratch ； 方便操作量子寄存器：q[n]-qubit, q[n:m]-substring, q&p-combined register ；为局部量子变量提供量子内存管理机制，采用的是“量子堆”(quantum heap)的方法，所有未分配的量子寄存器都为空1。

QCL 允许子程序（函数或过程）中使用从量子堆中分配的临时空间，称为scratch space 。

为保证量子堆能正常工作，要求这些空间在分配前、释放后都为空，QCL 使用如下过程进行处理：设F 是一个量子函数，具有参数寄存器x （quconst ），目标寄存器y （quvoid ）和scratch 寄存器s （quscratch ），定义为：s y x s y x i j i f i i s y x F >>>→>>>)(|)(||0|0|:|),,(s 在计算过程中的状态变为)(i j 。

释放s 时，QCL 自动分配一个辅助寄存器空间t （也是从量子堆中分配的，故而也要求使用后为空），将F 转换为如下定义的F ’操作：),,(),(),,(),,,(s t x F y t fanout s t x F t s y x F +=′1 空寄存器(Empty Registers)：量子寄存器s 为空，当且仅当满足:|00|,||)(00〉〈=〉Ψ=〉ΨP s P .其中fanout 操作定义为：i i i fanout →0:最后的结果是x 的计算结果保存在y 中，同时恢复了s 和t 。

如下所示：0,0),(,)(),(),(,)(),(,0,0,0,0,i f i i f i j i f i i f i j i i →→→QCL 没有结合盖然论和非确定论，没有程序精练的概念，也没有语义，而且只允许标准观测，只适合量子算法的数值模拟[16]。

Sanders 和Zuliani[16, 17]定义了qGCL 语言，该语言基于guarded-command language ，用pGCL 表达，因而继承了pGCL 的refinement calculus 。

qGCL 在pGCL 基础上进行了如下扩展：变换：将一个传统的位寄存器变换为一个量子位寄存器；初始化：为量子计算初始化量子位寄存器；演化：由量子寄存器上的酉操作序列构成；结束（观测）：从量子寄存器读取数据。

qGCL 拥有严格的语法和语义，有程序精练、数据精练的概念，包含有高级控制结构。

而且，它将酉变换抽象为赋值，将量子门抽象为酉变换的执行。

qGCL 的语法除了包括变量声明、赋值、条件语句、循环语句外，还包括非确定性语句P Q I 和概率语句r P Q ⊕。

由于qGCL 具有严格、抽象的语义和相关的refinement calculus ，可能比QCL 更适于程序的推导、正确性证明和教学。

Zuliani 在文[18, 19]中还研究了qGCL 中非确定和混和态条件下的程序设计问题。

Bettelli 等人定义了一种基于C++和低级原语的高级程序设计语言[8]，一般称之为Q 语言。

由于量子计算过程中不能对量子位进行测量，运行过程中不能对量子寄存器进行读操作，因此量子寄存器(Qreg)应该当作访问量子设备的一个部分的接口，而不是一个象传统寄存器那样保存数值的器件（除非决定对其进行测量）。

所有对量子寄存器的操作由高级原语（HLP, High Level Primitives ）和低级原语（LLP, Low Level Primitives ）构成，其中HLP 包括操作合成、操作变换、可控操作、传统函数的操作等等不直接与量子设备交互的操作，LLP 是基于QRAM 模型的，包括量子寄存器初始化与分配、寄存器测量、低级酉门等与量子设备相关的操作，但是尽可能设计成与体系结构无关。

他们给出了编译的细节，提供了自动对高级原语进行优化并转换成低级原语的方法，并用C++库实现了该语言。

系统实现可以从http://sra.itc.it/people/serafini/qlang/获得。

Gough[20]实现了一种提供叠加和测量的Perl 模块，由于整合了支持复数的模块，该实现可模拟一般的量子计算。

Tafliovich[21]定义了一种基于或然的、肯定的程序设计的量子程序设计语言。

这种语言本身是命令式的，其关键的一个特点是程序和规范之间有紧密的联系，并强调实现上的精练。

2.2函数式语言与λ-演算(Functional Languages and Lambda-Calculus)Van Tonder [22]定义了一种量子λ-演算，λp ，该演算具有可操作的语义和方程式理论。