基于量子傅里葉變換算法的量子乘法器*

錢俊愷 ，朱家良 ，葉 賓

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

0 引言

基于量子邏輯的量子算法設(shè)計是目前量子計算和量子信息研究的熱點方向之一[1]。由于量子算法具有并行處理量子疊加態(tài)的能力，一些經(jīng)典算法在量子計算環(huán)境下能夠獲得指數(shù)級的加速。Grover 于1996 年提出的量子搜索算法[2]將搜索問題從經(jīng)典的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)典進(jìn)位思想引入量子算法的做法并未帶來運行效率的大幅提升，反而占用了大量輔助量子比特。文獻(xiàn)[9]中提出了一種基于carry-save 的量子加法器，在增加量子位的前提下提高了算法的運行效率，但仍未超越經(jīng)典數(shù)字邏輯的設(shè)計范疇。對于兩個n 位二進(jìn)制數(shù)字的加法運算，這些量子加法運算都至少需要3n 個量子比特。2014 年，Kotiyal 等設(shè)計了一種基于二叉樹優(yōu)化的量子乘法器[10]，實現(xiàn)了較高的運行效率，但仍未跳出經(jīng)典電路的設(shè)計范疇，因此未能很好地體現(xiàn)量子電路的優(yōu)勢。文獻(xiàn)[11]在carry-save 量子加法器的基礎(chǔ)上設(shè)計了量子移位電路實現(xiàn)了量子乘法器，雖然算法結(jié)構(gòu)較為簡單，但也繼承了carry-save 加法器的缺陷。這些基于經(jīng)典布爾邏輯的量子電路驗證了量子加法器和乘法器的理論可行性，但過高的空間復(fù)雜度使得這些算法無法在當(dāng)前小規(guī)模的量子計算硬件平臺上展現(xiàn)量子計算的優(yōu)勢。

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

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

1 量子加法器

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

1.1 量子傅里葉變換

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

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

圖1 量子傅里葉變換電路

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

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

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

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

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

因為a=an-12n-1+an-22n-2+…+a020，式(7)可化簡為：

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

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

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

1.2 QFT 加法器

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

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

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

圖2 QFT 加法電路

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

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

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

2 量子乘法器

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

2.1 量子右移

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

圖3 右移位運算量子電路

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

2.2 QFT 乘法

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

圖4 QFT 乘法電路

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

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

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

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

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

圖5 移位求和塊電路

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

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

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

4 IBM Q 量子模擬器仿真實驗

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

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

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

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

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

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

5 結(jié)論

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