基于量子傅里叶变换算法的量子乘法器*

钱俊恺 ，朱家良 ，叶 宾

(1.中国矿业大学 计算机科学与技术学院，江苏 徐州 221116；2.中国矿业大学 信息与控制工程学院，江苏 徐州 221116)

0 引言

基于量子逻辑的量子算法设计是目前量子计算和量子信息研究的热点方向之一[1]。由于量子算法具有并行处理量子叠加态的能力，一些经典算法在量子计算环境下能够获得指数级的加速。Grover 于1996 年提出的量子搜索算法[2]将搜索问题从经典的N 步缩小到步，体现了量子算法的强大加速能力。1997 年，Shor 因子分解算法[3]使用量子傅里叶变换在多项式时间内实现对整数的因子分解，其采用模块化的算数运算更是奠定了量子计算领域模块化的算法设计基础。近年来，随着量子调控技术的发展以及众多量子仿真平台的推出，量子算法的研究得到快速的发展[4-5]。

乘法运算是许多量子算法中的基本运算之一，它在量子人工智能算法、量子信号处理等领域有着广泛的应用[6-7]。量子乘法器通常以量子加法器为基础。最初的量子加法器一般由量子门实现经典布尔逻辑运算规则[8]，但是将经典进位思想引入量子算法的做法并未带来运行效率的大幅提升，反而占用了大量辅助量子比特。文献[9]中提出了一种基于carry-save 的量子加法器，在增加量子位的前提下提高了算法的运行效率，但仍未超越经典数字逻辑的设计范畴。对于两个n 位二进制数字的加法运算，这些量子加法运算都至少需要3n 个量子比特。2014 年，Kotiyal 等设计了一种基于二叉树优化的量子乘法器[10]，实现了较高的运行效率，但仍未跳出经典电路的设计范畴，因此未能很好地体现量子电路的优势。文献[11]在carry-save 量子加法器的基础上设计了量子移位电路实现了量子乘法器，虽然算法结构较为简单，但也继承了carry-save 加法器的缺陷。这些基于经典布尔逻辑的量子电路验证了量子加法器和乘法器的理论可行性，但过高的空间复杂度使得这些算法无法在当前小规模的量子计算硬件平台上展现量子计算的优势。

与基于经典布尔逻辑的设计思路不同，Draper 提出了一种基于量子傅里叶变换的加法器[12]，它使用量子傅里叶变换从而更好地利用了量子态的叠加和纠缠特性，在量子计算机上可以获得更高的性能提升。Lidia 等在Draper 所提出加法器的基础上设计了量子乘法器[13]，在保证运行效率的前提下使用了较少的辅助量子位。然而，其算法过程中实际存在着两个问题：(1)在对部分积做相位加法的过程中并未考虑到量子相位变换的周期性，而是沿用加法电路中的相位，因此最终得到的结果与实际会存在较大的误差；(2)提出了通过移位循环相加的方法，却并未给出其量子移位电路的实现。以上所提出的所有方法受限于其提出时间的量子计算发展水平的限制，都缺乏相应的实验支撑。

本文在量子傅里叶加法器以及量子移位电路的基础上，设计并实现了基于量子傅里叶变换算法的乘法器电路，并使用IBM Q 量子计算平台[14]进行了实验验证。与基于经典布尔逻辑以及基于二叉树的量子乘法器相比，该量子乘法器结构简单，且使用了更少的量子比特资源。与Draper 提出的量子傅里叶变换的乘法器相比，该乘法器通过循环调用加法器避免了其在加法过程中的错误，且给出了包括移位电路在内的完整的量子电路。

1 量子加法器

早期的量子加法器基于经典布尔逻辑进行量子电路设计，效率较为低下。Draper 提出的基于量子傅里叶变换的加法器消除了对临时进位的需要，从而减少了加法所需的量子比特的数目。尽管这种量子加法器在计算复杂度上并未体现出很大的优势，但是却利用量子态的叠加性，将所需的量子比特数目缩减到2n。以下简要介绍量子傅里叶变换以及基于该变换的量子加法器。

1.1 量子傅里叶变换

量子傅里叶变换(QFT)是在波函数振幅上实现的离散傅里叶变换。一个由n 个量子比特构成的量子寄存器A，状态|a〉可表示为由基态{|0〉，|1〉，…，|2n-1〉}构成的一个叠加态，即，其中N=2n，复数ax满足归一化条件。QFT 将量子态通过式(1)映射为

QFT 量子电路如图1 所示，图中H 和Rn分别表示Hadamard 量子门和量子相位门：

图1 量子傅里叶变换电路

对于一般形式的量子态|a〉=|an-1an-2…a1a0〉，QFT 电路实现可分解为以下步骤：

(1)对于量子寄存器最高位A[n-1]施加H 门：

其中，⊗为张量积运算[15]，其运算规则为：

(2)对量子比特A[n-1]施加受控相位门R2，控制位为A[n-2]：

(3)类似地，依次对量子比特A[n-1]施加受控相位门Rn，控制位分别为A[n-3]至A[0]，可得量子态：

因为a=an-12n-1+an-22n-2+…+a020，式(7)可化简为：

(4)依次对A[n-2]至A[0]施加类似的变换，其最终结果为：

(5)QFT 逆变换可定义为：

其中，k 为十进制累加变量，当以向量形式|k〉出现时实际需要变换为二进制形式，a 亦是如此。向量|k〉代表了0 到N-1 的各量子态。此时，式(10)的结果相当于各量子态的叠加。这种形式的相位编码是所有使用QFT 算法的基本共同要素[16-17]。

1.2 QFT 加法器

QFT 提供了在量子计算机上进行算数运算的另一种方式，其核心是通过酉变换将任意单量子态制备成叠加量子态以达到指数加速的目的。

假设两个数a 和b 分别用n 位量子比特表示：

考虑到加法运算时进位问题，需要对a 增加1 位量子比特表示，如图2 所示，且a 的这个最高位初始化为0。首先对|a〉施加QFT 得：

图2 QFT 加法电路

然后使用受控量子相位门Rn对|a〉和|b〉进行加法：

该受控旋转门由|b〉的第j 个量子位控制，仅在bj为1时作用于结果寄存器的第s 个量子位。当j+s-n＞0 时，受控量子相位门为Rj+s-n，当j+s-n≤0 时，其相位为1，此时ai状态保持不变。

随后对|a〉施加量子傅里叶逆变换得到|a+b〉。整个电路需要使用到2n+1 个量子位。

2 量子乘法器

量子乘法器以量子加法器为基础。假设a 为被乘数，且用n 个量子位表示；b 为乘数，也用n 个量子位表示。通过调用n 个连续的受控加法门来实现被乘数的逐步相加，最后使用一个2n 位的量子位寄存器存储ab 相乘的结果。

2.1 量子右移

在量子乘法器中需要使用到右移操作，其量子电路图如图3 所示，电路中的X 为非门：

图3 右移位运算量子电路

该量子电路通过两个受控非门交换相邻两个量子位，这样的组合在图3 中有n+1 组。电路将引入一个辅助量子位|0〉作为右移后的最低位，受控非门在相邻两个量子位间将|0〉由低位逐步向高位置换，最终实现整体右移的操作。不同于寻常右移操作过程中舍弃最低位的性质，该右移操作将保留最低位的|x0〉，因此每进行一次右移操作实际效果等同于在高位添加一个|0〉。左移算法只需参考右移算法，将辅助量子位添加在高位即可。

2.2 QFT 乘法

QFT 乘法器由n 次连续可控的加法运算构成，电路如图4 所示。图中有n 个相似的受控算数块，依次由|b〉的低位至高位控制。将这样的受控算数块命名为移位求和块。|sum〉负责记录部分积结果，共有2n 个量子位，被初始化为|0〉，经过n 个移位求和块后存储ab 信息。理论上整个乘法电路需要使用4n 量子位，在实际编码中使用了4n+1 量子位。

图4 QFT 乘法电路

对于第一个移位求和块，由|b1〉控制。其进行的运算为20a+sum，由于此时sum 为0，因此实际相当于将被乘数a 增加到部分积，此时|sum〉的结果为：

随后第二个移位求和块由|b2〉控制，进行的运算为21a+sum，则运算后的|sum〉结果为：

以相同步骤处理直至b 的最高位，其结果为：

下面考虑更一般的情况，对于第k 个移位求和块(图4 中虚线框的部分)，其进行的运算为2ka+sum。

图4 中受控的移位求和块可进一步分解为图5 所示电路。图5 中的|bk〉代表|b〉的第k 个量子位。部分积|sum＞此时有n+k 位。虚框内的部分为1.2 节中的加法器电路，截取|sum〉 高位的n+1 位作为加法器的被加数，与|a〉做加法。得到的部分积存储在|sum〉的高n+1位中。引入一个量子位|0〉，将该量子位补位在|sum〉的最低位，做右移操作。完成后|sum〉增加至n+k+1 位，最高位实际为|0〉。特殊地，当k=n 时，此时为最后一块移位求和块，因此不进行右移操作。

图5 移位求和块电路

3 时间复杂度分析

根据量子计算复杂性理论[18]，一般使用量子算法中使用的通用量子门数量评价算法的时间复杂度。假设a为n 位的二进制数，b 为m 位的二进制数。QFT 加法器的时间复杂度为O(nm)。QFT 乘法电路如图4 所示，需要调用m 次加法器过程以及m 次右移电路。右移电路的复杂度为O(mn)，因此主要开销仍是循环调用加法器的过程，其时间复杂度为O(nm2)。如果两数都为n 位二进制数，其时间复杂度为O(n3)。

文献[19]中提出的乘法器需要n3的量子位，本文的算法实际使用了4n+1 量子位，相比下更加节省寄存器空间。文献[13]设计了一个基于二叉树的量子乘法器，其复杂度为O(n3)，但需要使用n2+2n 个量子比特。本文所设计的乘法器复杂度也为O(n3)，但是算法结构更加简单且使用了较少的量子比特数。

4 IBM Q 量子模拟器仿真实验

本实验以Python 语言为框架，利用IBM 提供的开源量子计算工具包Qiskit 完成量子电路的搭建。实验使用量子仿真模拟器进行模拟仿真实验。

在Qiskit 中构建如图4 所示的乘法器，量子电路如图6 所示，其中X、H、U1是Qiskit 生成的量子门，分别代表1.1 节和2.1 节中介绍的非门、Hadamard 量子门和量子相位门。输入的两个二进制数为11、10，理论输出值为0110，迭代次数设置为8 192。各量子态出现的概率如图7 所示。在模拟器环境下仅出现|0110〉态。实验结果与预期结果相符，因此可以证明该QFT 乘法器具有在该模拟量子系统下具有有效性。

图6 二进制数11 与10 相乘的量子电路图

图7 二进制数11 与10 相乘的仿真结果直方图

验证一个2 位二进制数和一个4 位二进制数相乘的乘法运算，输入的两个二进制数为11、1101，理论输出值为100111，迭代次数设置为8 192，各量子态出现的概率如图8 所示。仅出现|100111〉态这样一个量子态，与理论计算结果相符，说明乘法器有效。

图8 二进制数11 与1101 相乘的仿真结果直方图

5 结论

本文设计了一种基于QFT 的量子乘法器，它以QFT加法器为基础，并利用受控非门实现了移位电路，在节省量子寄存器资源的前提下实现了相对较低的计算复杂度。在IBM Q 量子计算平台上的仿真实验结果表明，该量子线路具有比较高的计算准确率。今后的研究方向是减少量子乘法器使用的寄存器数量以及进一步降低算法时间复杂度。