基于量子傅里叶变换算法的量子乘法器-AET-电子技术应用

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

2022年电子技术应用第3期

钱俊恺1，朱家良2，叶宾2

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

摘要：乘法运算是许多量子算法中的基本运算之一。为了实现量子乘法运算并且尽可能少地使用辅助量子比特，提出了一种基于量子傅里叶变换算法的量子乘法器。在量子傅里叶加法电路基础上，设计了量子移位电路，并实现了两个n位二进制无符号数相乘的量子电路，其时间复杂度为O(n3)。使用IBM提供的开源量子计算工具包Qiskit分别验证了两个2位二进制数相乘，以及一个2位二进制数与另一个4位二进制数进行量子乘法运算的正确性。实验结果表明，所设计的量子乘法器使用较少的量子比特数目实现了较高的准确率和较低的计算复杂度。该量子乘法器代码已开源。

关键词： 量子乘法器量子加法器量子傅里叶变换 IBMQiskit平台量子电路

中图分类号：Q413
文献标识码：A
DOI：10.16157/j.issn.0258-7998.211576
中文引用格式：钱俊恺，朱家良，叶宾. 基于量子傅里叶变换算法的量子乘法器[J].电子技术应用，2022，48(3)：94-98.
英文引用格式：Qian Junkai，Zhu Jialiang，Ye Bin. A quantum multiplier based on the quantum Fourier transform algorithm[J]. Application of Electronic Technique，2022，48(3)：94-98.

A quantum multiplier based on the quantum Fourier transform algorithm

Qian Junkai1，Zhu Jialiang2，Ye Bin2

1.School of Computer Science & Technology，China University of Mining and Technology，Xuzhou 221116，China； 2.School of Information and Control Engineering，China University of Mining and Technology，Xuzhou 221116，China

Abstract：Multiplier is one of the basic units in many quantum algorithms. In order to implement the multiplying operations and use as few auxiliary qubits in the quantum circuit as possible, a quantum multiplier based on the quantum Fourier transform is proposed. By utilizing the quantum Fourier adder, a quantum shift circuit is designed. A quantum circuit for the multiplication of two n bit binary unsigned numbers is realized and its time complexity is O(n3). The validity of multiplying a 2 bit binary number by another 2 bit or 4 bit binary number is tested through Qiskit-an open source quantum computing toolkit provided by IBM. The experimental results show that the quantum multiplier achieves higher accuracy and lower computational complexity with less qubits. The open source code of the quantum multiplier is publicly available.

Key words :quantum multiplier；quantum adder；QFT；IBM Qiskit platform；quantum circuit

0 引言

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

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

本文详细内容请下载：http://www.chinaaet.com/resource/share/2000004011。

作者信息：

钱俊恺1，朱家良2，叶宾2

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

原创声明：此内容为AET网站原创，未经授权禁止转载。

相关内容