《電子技術(shù)應(yīng)用》
您所在的位置：首頁(yè) > 其他 > 設(shè)計(jì)應(yīng)用 > 基于量子傅里葉變換算法的量子乘法器
基于量子傅里葉變換算法的量子乘法器
2022年電子技術(shù)應(yīng)用第3期
錢俊愷1，朱家良2，葉 賓2
1.中國(guó)礦業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 徐州221116；2.中國(guó)礦業(yè)大學(xué) 信息與控制工程學(xué)院，江蘇 徐州221116
摘要： 乘法運(yùn)算是許多量子算法中的基本運(yùn)算之一。為了實(shí)現(xiàn)量子乘法運(yùn)算并且盡可能少地使用輔助量子比特，提出了一種基于量子傅里葉變換算法的量子乘法器。在量子傅里葉加法電路基礎(chǔ)上，設(shè)計(jì)了量子移位電路，并實(shí)現(xiàn)了兩個(gè)n位二進(jìn)制無(wú)符號(hào)數(shù)相乘的量子電路，其時(shí)間復(fù)雜度為O(n3)。使用IBM提供的開源量子計(jì)算工具包Qiskit分別驗(yàn)證了兩個(gè)2位二進(jìn)制數(shù)相乘，以及一個(gè)2位二進(jìn)制數(shù)與另一個(gè)4位二進(jìn)制數(shù)進(jìn)行量子乘法運(yùn)算的正確性。實(shí)驗(yàn)結(jié)果表明，所設(shè)計(jì)的量子乘法器使用較少的量子比特?cái)?shù)目實(shí)現(xiàn)了較高的準(zhǔn)確率和較低的計(jì)算復(fù)雜度。該量子乘法器代碼已開源。
中圖分類號(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ì)了一種基于二叉樹優(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://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)載。