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.cowatch.cn/resource/share/2000004011。

作者信息：

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

(1.中國礦業大學 計算機科學與技術學院，江蘇 徐州221116；2.中國礦業大學 信息與控制工程學院，江蘇 徐州221116)