《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 其他 > 設(shè)計應(yīng)用 > 基于量子傅里葉變換算法的量子乘法器
基于量子傅里葉變換算法的量子乘法器
2022年電子技術(shù)應(yīng)用第3期
錢俊愷1,朱家良2,葉 賓2
1.中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,江蘇 徐州221116;2.中國礦業(yè)大學(xué) 信息與控制工程學(xué)院,江蘇 徐州221116
摘要: 乘法運算是許多量子算法中的基本運算之一。為了實現(xiàn)量子乘法運算并且盡可能少地使用輔助量子比特,提出了一種基于量子傅里葉變換算法的量子乘法器。在量子傅里葉加法電路基礎(chǔ)上,設(shè)計了量子移位電路,并實現(xiàn)了兩個n位二進制無符號數(shù)相乘的量子電路,其時間復(fù)雜度為O(n3)。使用IBM提供的開源量子計算工具包Qiskit分別驗證了兩個2位二進制數(shù)相乘,以及一個2位二進制數(shù)與另一個4位二進制數(shù)進行量子乘法運算的正確性。實驗結(jié)果表明,所設(shè)計的量子乘法器使用較少的量子比特數(shù)目實現(xiàn)了較高的準確率和較低的計算復(fù)雜度。該量子乘法器代碼已開源。
中圖分類號: Q413
文獻標識碼: 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è)計是目前量子計算和量子信息研究的熱點方向之一[1]。由于量子算法具有并行處理量子疊加態(tài)的能力,一些經(jīng)典算法在量子計算環(huán)境下能夠獲得指數(shù)級的加速。Grover于1996年提出的量子搜索算法[2]將搜索問題從經(jīng)典的N步縮小到√N步,體現(xiàn)了量子算法的強大加速能力。1997年,Shor因子分解算法[3]使用量子傅里葉變換在多項式時間內(nèi)實現(xiàn)對整數(shù)的因子分解,其采用模塊化的算數(shù)運算更是奠定了量子計算領(lǐng)域模塊化的算法設(shè)計基礎(chǔ)。近年來,隨著量子調(diào)控技術(shù)的發(fā)展以及眾多量子仿真平臺的推出,量子算法的研究得到快速的發(fā)展[4-5]。

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




本文詳細內(nèi)容請下載:http://ihrv.cn/resource/share/2000004011。




作者信息:

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

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




wd.jpg

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