錢俊愷 ，朱家良 ，葉 賓

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

0 引言

基于量子邏輯的量子算法設(shè)計(jì)是目前量子計(jì)算和量子信息研究的熱點(diǎn)方向之一[1]。由于量子算法具有并行處理量子疊加態(tài)的能力，一些經(jīng)典算法在量子計(jì)算環(huán)境下能夠獲得指數(shù)級(jí)的加速。Grover 于1996 年提出的量子搜索算法[2]將搜索問題從經(jīng)典的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ǔ)。近年來，隨著量子調(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)位思想引入量子算法的做法并未帶來運(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)證了量子加法器和乘法器的理論可行性，但過高的空間復(fù)雜度使得這些算法無法在當(dāng)前小規(guī)模的量子計(jì)算硬件平臺(tái)上展現(xiàn)量子計(jì)算的優(yōu)勢(shì)。

與基于經(jīng)典布爾邏輯的設(shè)計(jì)思路不同，Draper 提出了一種基于量子傅里葉變換的加法器[12]，它使用量子傅里葉變換從而更好地利用了量子態(tài)的疊加和糾纏特性，在量子計(jì)算機(jī)上可以獲得更高的性能提升。Lidia 等在Draper 所提出加法器的基礎(chǔ)上設(shè)計(jì)了量子乘法器[13]，在保證運(yùn)行效率的前提下使用了較少的輔助量子位。然而，其算法過程中實(shí)際存在著兩個(gè)問題：(1)在對(duì)部分積做相位加法的過程中并未考慮到量子相位變換的周期性，而是沿用加法電路中的相位，因此最終得到的結(jié)果與實(shí)際會(huì)存在較大的誤差；(2)提出了通過移位循環(huán)相加的方法，卻并未給出其量子移位電路的實(shí)現(xiàn)。以上所提出的所有方法受限于其提出時(shí)間的量子計(jì)算發(fā)展水平的限制，都缺乏相應(yīng)的實(shí)驗(yàn)支撐。

本文在量子傅里葉加法器以及量子移位電路的基礎(chǔ)上，設(shè)計(jì)并實(shí)現(xiàn)了基于量子傅里葉變換算法的乘法器電路，并使用IBM Q 量子計(jì)算平臺(tái)[14]進(jìn)行了實(shí)驗(yàn)驗(yàn)證。與基于經(jīng)典布爾邏輯以及基于二叉樹的量子乘法器相比，該量子乘法器結(jié)構(gòu)簡(jiǎn)單，且使用了更少的量子比特資源。與Draper 提出的量子傅里葉變換的乘法器相比，該乘法器通過循環(huán)調(diào)用加法器避免了其在加法過程中的錯(cuò)誤，且給出了包括移位電路在內(nèi)的完整的量子電路。

1 量子加法器

早期的量子加法器基于經(jīng)典布爾邏輯進(jìn)行量子電路設(shè)計(jì)，效率較為低下。Draper 提出的基于量子傅里葉變換的加法器消除了對(duì)臨時(shí)進(jìn)位的需要，從而減少了加法所需的量子比特的數(shù)目。盡管這種量子加法器在計(jì)算復(fù)雜度上并未體現(xiàn)出很大的優(yōu)勢(shì)，但是卻利用量子態(tài)的疊加性，將所需的量子比特?cái)?shù)目縮減到2n。以下簡(jiǎn)要介紹量子傅里葉變換以及基于該變換的量子加法器。

1.1 量子傅里葉變換

量子傅里葉變換(QFT)是在波函數(shù)振幅上實(shí)現(xiàn)的離散傅里葉變換。一個(gè)由n 個(gè)量子比特構(gòu)成的量子寄存器A，狀態(tài)|a〉可表示為由基態(tài){|0〉，|1〉，…，|2n-1〉}構(gòu)成的一個(gè)疊加態(tài)，即，其中N=2n，復(fù)數(shù)ax滿足歸一化條件。QFT 將量子態(tài)通過式(1)映射為

QFT 量子電路如圖1 所示，圖中H 和Rn分別表示Hadamard 量子門和量子相位門：

圖1 量子傅里葉變換電路

對(duì)于一般形式的量子態(tài)|a〉=|an-1an-2…a1a0〉，QFT 電路實(shí)現(xiàn)可分解為以下步驟：

(1)對(duì)于量子寄存器最高位A[n-1]施加H 門：

其中，?為張量積運(yùn)算[15]，其運(yùn)算規(guī)則為：

(2)對(duì)量子比特A[n-1]施加受控相位門R2，控制位為A[n-2]：

(3)類似地，依次對(duì)量子比特A[n-1]施加受控相位門Rn，控制位分別為A[n-3]至A[0]，可得量子態(tài)：

因?yàn)閍=an-12n-1+an-22n-2+…+a020，式(7)可化簡(jiǎn)為：

(4)依次對(duì)A[n-2]至A[0]施加類似的變換，其最終結(jié)果為：

(5)QFT 逆變換可定義為：

其中，k 為十進(jìn)制累加變量，當(dāng)以向量形式|k〉出現(xiàn)時(shí)實(shí)際需要變換為二進(jìn)制形式，a 亦是如此。向量|k〉代表了0 到N-1 的各量子態(tài)。此時(shí)，式(10)的結(jié)果相當(dāng)于各量子態(tài)的疊加。這種形式的相位編碼是所有使用QFT 算法的基本共同要素[16-17]。

1.2 QFT 加法器

QFT 提供了在量子計(jì)算機(jī)上進(jìn)行算數(shù)運(yùn)算的另一種方式，其核心是通過酉變換將任意單量子態(tài)制備成疊加量子態(tài)以達(dá)到指數(shù)加速的目的。

假設(shè)兩個(gè)數(shù)a 和b 分別用n 位量子比特表示：

考慮到加法運(yùn)算時(shí)進(jìn)位問題，需要對(duì)a 增加1 位量子比特表示，如圖2 所示，且a 的這個(gè)最高位初始化為0。首先對(duì)|a〉施加QFT 得：

圖2 QFT 加法電路

然后使用受控量子相位門Rn對(duì)|a〉和|b〉進(jìn)行加法：

該受控旋轉(zhuǎn)門由|b〉的第j 個(gè)量子位控制，僅在bj為1時(shí)作用于結(jié)果寄存器的第s 個(gè)量子位。當(dāng)j+s-n＞0 時(shí)，受控量子相位門為Rj+s-n，當(dāng)j+s-n≤0 時(shí)，其相位為1，此時(shí)ai狀態(tài)保持不變。

隨后對(duì)|a〉施加量子傅里葉逆變換得到|a+b〉。整個(gè)電路需要使用到2n+1 個(gè)量子位。

2 量子乘法器

量子乘法器以量子加法器為基礎(chǔ)。假設(shè)a 為被乘數(shù)，且用n 個(gè)量子位表示；b 為乘數(shù)，也用n 個(gè)量子位表示。通過調(diào)用n 個(gè)連續(xù)的受控加法門來實(shí)現(xiàn)被乘數(shù)的逐步相加，最后使用一個(gè)2n 位的量子位寄存器存儲(chǔ)ab 相乘的結(jié)果。

2.1 量子右移

在量子乘法器中需要使用到右移操作，其量子電路圖如圖3 所示，電路中的X 為非門：

圖3 右移位運(yùn)算量子電路

該量子電路通過兩個(gè)受控非門交換相鄰兩個(gè)量子位，這樣的組合在圖3 中有n+1 組。電路將引入一個(gè)輔助量子位|0〉作為右移后的最低位，受控非門在相鄰兩個(gè)量子位間將|0〉由低位逐步向高位置換，最終實(shí)現(xiàn)整體右移的操作。不同于尋常右移操作過程中舍棄最低位的性質(zhì)，該右移操作將保留最低位的|x0〉，因此每進(jìn)行一次右移操作實(shí)際效果等同于在高位添加一個(gè)|0〉。左移算法只需參考右移算法，將輔助量子位添加在高位即可。

2.2 QFT 乘法

QFT 乘法器由n 次連續(xù)可控的加法運(yùn)算構(gòu)成，電路如圖4 所示。圖中有n 個(gè)相似的受控算數(shù)塊，依次由|b〉的低位至高位控制。將這樣的受控算數(shù)塊命名為移位求和塊。|sum〉負(fù)責(zé)記錄部分積結(jié)果，共有2n 個(gè)量子位，被初始化為|0〉，經(jīng)過n 個(gè)移位求和塊后存儲(chǔ)ab 信息。理論上整個(gè)乘法電路需要使用4n 量子位，在實(shí)際編碼中使用了4n+1 量子位。

圖4 QFT 乘法電路

對(duì)于第一個(gè)移位求和塊，由|b1〉控制。其進(jìn)行的運(yùn)算為20a+sum，由于此時(shí)sum 為0，因此實(shí)際相當(dāng)于將被乘數(shù)a 增加到部分積，此時(shí)|sum〉的結(jié)果為：

隨后第二個(gè)移位求和塊由|b2〉控制，進(jìn)行的運(yùn)算為21a+sum，則運(yùn)算后的|sum〉結(jié)果為：

以相同步驟處理直至b 的最高位，其結(jié)果為：

下面考慮更一般的情況，對(duì)于第k 個(gè)移位求和塊(圖4 中虛線框的部分)，其進(jìn)行的運(yùn)算為2ka+sum。

圖4 中受控的移位求和塊可進(jìn)一步分解為圖5 所示電路。圖5 中的|bk〉代表|b〉的第k 個(gè)量子位。部分積|sum＞此時(shí)有n+k 位。虛框內(nèi)的部分為1.2 節(jié)中的加法器電路，截取|sum〉 高位的n+1 位作為加法器的被加數(shù)，與|a〉做加法。得到的部分積存儲(chǔ)在|sum〉的高n+1位中。引入一個(gè)量子位|0〉，將該量子位補(bǔ)位在|sum〉的最低位，做右移操作。完成后|sum〉增加至n+k+1 位，最高位實(shí)際為|0〉。特殊地，當(dāng)k=n 時(shí)，此時(shí)為最后一塊移位求和塊，因此不進(jìn)行右移操作。

圖5 移位求和塊電路

3 時(shí)間復(fù)雜度分析

根據(jù)量子計(jì)算復(fù)雜性理論[18]，一般使用量子算法中使用的通用量子門數(shù)量評(píng)價(jià)算法的時(shí)間復(fù)雜度。假設(shè)a為n 位的二進(jìn)制數(shù)，b 為m 位的二進(jìn)制數(shù)。QFT 加法器的時(shí)間復(fù)雜度為O(nm)。QFT 乘法電路如圖4 所示，需要調(diào)用m 次加法器過程以及m 次右移電路。右移電路的復(fù)雜度為O(mn)，因此主要開銷仍是循環(huán)調(diào)用加法器的過程，其時(shí)間復(fù)雜度為O(nm2)。如果兩數(shù)都為n 位二進(jìn)制數(shù)，其時(shí)間復(fù)雜度為O(n3)。

文獻(xiàn)[19]中提出的乘法器需要n3的量子位，本文的算法實(shí)際使用了4n+1 量子位，相比下更加節(jié)省寄存器空間。文獻(xiàn)[13]設(shè)計(jì)了一個(gè)基于二叉樹的量子乘法器，其復(fù)雜度為O(n3)，但需要使用n2+2n 個(gè)量子比特。本文所設(shè)計(jì)的乘法器復(fù)雜度也為O(n3)，但是算法結(jié)構(gòu)更加簡(jiǎn)單且使用了較少的量子比特?cái)?shù)。

4 IBM Q 量子模擬器仿真實(shí)驗(yàn)

本實(shí)驗(yàn)以Python 語言為框架，利用IBM 提供的開源量子計(jì)算工具包Qiskit 完成量子電路的搭建。實(shí)驗(yàn)使用量子仿真模擬器進(jìn)行模擬仿真實(shí)驗(yàn)。

在Qiskit 中構(gòu)建如圖4 所示的乘法器，量子電路如圖6 所示，其中X、H、U1是Qiskit 生成的量子門，分別代表1.1 節(jié)和2.1 節(jié)中介紹的非門、Hadamard 量子門和量子相位門。輸入的兩個(gè)二進(jìn)制數(shù)為11、10，理論輸出值為0110，迭代次數(shù)設(shè)置為8 192。各量子態(tài)出現(xiàn)的概率如圖7 所示。在模擬器環(huán)境下僅出現(xiàn)|0110〉態(tài)。實(shí)驗(yàn)結(jié)果與預(yù)期結(jié)果相符，因此可以證明該QFT 乘法器具有在該模擬量子系統(tǒng)下具有有效性。

圖6 二進(jìn)制數(shù)11 與10 相乘的量子電路圖

圖7 二進(jìn)制數(shù)11 與10 相乘的仿真結(jié)果直方圖

驗(yàn)證一個(gè)2 位二進(jìn)制數(shù)和一個(gè)4 位二進(jìn)制數(shù)相乘的乘法運(yùn)算，輸入的兩個(gè)二進(jìn)制數(shù)為11、1101，理論輸出值為100111，迭代次數(shù)設(shè)置為8 192，各量子態(tài)出現(xiàn)的概率如圖8 所示。僅出現(xiàn)|100111〉態(tài)這樣一個(gè)量子態(tài)，與理論計(jì)算結(jié)果相符，說明乘法器有效。

圖8 二進(jìn)制數(shù)11 與1101 相乘的仿真結(jié)果直方圖

5 結(jié)論

本文設(shè)計(jì)了一種基于QFT 的量子乘法器，它以QFT加法器為基礎(chǔ)，并利用受控非門實(shí)現(xiàn)了移位電路，在節(jié)省量子寄存器資源的前提下實(shí)現(xiàn)了相對(duì)較低的計(jì)算復(fù)雜度。在IBM Q 量子計(jì)算平臺(tái)上的仿真實(shí)驗(yàn)結(jié)果表明，該量子線路具有比較高的計(jì)算準(zhǔn)確率。今后的研究方向是減少量子乘法器使用的寄存器數(shù)量以及進(jìn)一步降低算法時(shí)間復(fù)雜度。