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ǔ)。最初的量子加法器一般由量子門(mén)實(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://www.xxav2194.com/resource/share/2000004011。

作者信息：

錢(qián)俊愷1，朱家良2，葉  賓2

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