《電子技術(shù)應(yīng)用》
您所在的位置：首頁(yè) > 其他 > 设计应用 > 基于量子傅里叶变换算法的量子乘法器
基于量子傅里叶变换算法的量子乘法器
2022年电子技术应用第3期
钱俊恺1，朱家良2，叶 宾2
1.中国矿业大学 计算机科学与技术学院，江苏 徐州221116；2.中国矿业大学 信息与控制工程学院，江苏 徐州221116
摘要： 乘法运算是许多量子算法中的基本运算之一。为了实现量子乘法运算并且尽可能少地使用辅助量子比特，提出了一种基于量子傅里叶变换算法的量子乘法器。在量子傅里叶加法电路基础上，设计了量子移位电路，并实现了两个n位二进制无符号数相乘的量子电路，其时间复杂度为O(n3)。使用IBM提供的开源量子计算工具包Qiskit分别验证了两个2位二进制数相乘，以及一个2位二进制数与另一个4位二进制数进行量子乘法运算的正确性。实验结果表明，所设计的量子乘法器使用较少的量子比特数目实现了较高的准确率和较低的计算复杂度。该量子乘法器代码已开源。
中圖分類號(hào)： Q413
文獻(xiàn)標(biāo)識(shí)碼： A
DOI：10.16157/j.issn.0258-7998.211576
中文引用格式： 錢俊愷，朱家良，葉賓. 基于量子傅里葉變換算法的量子乘法器[J].電子技術(shù)應(yīng)用，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 引言

基于量子邏輯的量子算法設(shè)計(jì)是目前量子計(jì)算和量子信息研究的熱點(diǎn)方向之一[1]。由于量子算法具有并行處理量子疊加態(tài)的能力，一些經(jīng)典算法在量子計(jì)算環(huán)境下能夠獲得指數(shù)級(jí)的加速。Grover于1996年提出的量子搜索算法[2]將搜索問(wèn)題從經(jīng)典的N步縮小到√N(yùn)步，體現(xiàn)了量子算法的強(qiáng)大加速能力。1997年，Shor因子分解算法[3]使用量子傅里葉變換在多項(xiàng)式時(shí)間內(nèi)實(shí)現(xiàn)對(duì)整數(shù)的因子分解，其采用模塊化的算數(shù)運(yùn)算更是奠定了量子計(jì)算領(lǐng)域模塊化的算法設(shè)計(jì)基礎(chǔ)。近年來(lái)，隨著量子調(diào)控技術(shù)的發(fā)展以及眾多量子仿真平臺(tái)的推出，量子算法的研究得到快速的發(fā)展[4-5]。

    乘法運(yùn)算是許多量子算法中的基本運(yùn)算之一，它在量子人工智能算法、量子信號(hào)處理等領(lǐng)域有著廣泛的應(yīng)用[6-7]。量子乘法器通常以量子加法器為基礎(chǔ)。最初的量子加法器一般由量子門實(shí)現(xiàn)經(jīng)典布爾邏輯運(yùn)算規(guī)則[8]，但是將經(jīng)典進(jìn)位思想引入量子算法的做法并未帶來(lái)運(yùn)行效率的大幅提升，反而占用了大量輔助量子比特。文獻(xiàn)[9]中提出了一種基于carry-save的量子加法器，在增加量子位的前提下提高了算法的運(yùn)行效率，但仍未超越經(jīng)典數(shù)字邏輯的設(shè)計(jì)范疇。對(duì)于兩個(gè)n位二進(jìn)制數(shù)字的加法運(yùn)算，這些量子加法運(yùn)算都至少需要3n個(gè)量子比特。2014年，Kotiyal等設(shè)計(jì)了一種基于二叉樹(shù)優(yōu)化的量子乘法器[10]，實(shí)現(xiàn)了較高的運(yùn)行效率，但仍未跳出經(jīng)典電路的設(shè)計(jì)范疇，因此未能很好地體現(xiàn)量子電路的優(yōu)勢(shì)。文獻(xiàn)[11]在carry-save量子加法器的基礎(chǔ)上設(shè)計(jì)了量子移位電路實(shí)現(xiàn)了量子乘法器，雖然算法結(jié)構(gòu)較為簡(jiǎn)單，但也繼承了carry-save加法器的缺陷。這些基于經(jīng)典布爾邏輯的量子電路驗(yàn)證了量子加法器和乘法器的理論可行性，但過(guò)高的空間復(fù)雜度使得這些算法無(wú)法在當(dāng)前小規(guī)模的量子計(jì)算硬件平臺(tái)上展現(xiàn)量子計(jì)算的優(yōu)勢(shì)。




本文詳細(xì)內(nèi)容請(qǐng)下載：http://m.ihrv.cn/resource/share/2000004011。




作者信息：

錢俊愷1，朱家良2，葉  賓2

(1.中國(guó)礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州221116；2.中國(guó)礦業(yè)大學(xué) 信息與控制工程學(xué)院，江蘇 徐州221116)




wd.jpg

此內(nèi)容為AET網(wǎng)站原創(chuàng)，未經(jīng)授權(quán)禁止轉(zhuǎn)載。

相關(guān)內(nèi)容