量子乘法器的設(shè)計(jì)及其實(shí)現(xiàn)方法

袁素真，王 艷，王玉嬋，黃 斐

(重慶郵電大學(xué) 光電工程學(xué)院，重慶 400065)

0 前 言

20世紀(jì)80年代初， P. Benioff[1]首先提出了量子計(jì)算的思想；1982年，費(fèi)曼[2]提出用量子計(jì)算機(jī)來模擬量子系統(tǒng)，其計(jì)算速度遠(yuǎn)超過經(jīng)典計(jì)算機(jī)?，F(xiàn)有的研究表明，量子計(jì)算以其并行計(jì)算的特性在一些領(lǐng)域里比經(jīng)典計(jì)算有著很大的優(yōu)勢，例如信息論，密碼學(xué)和圖像處理等[3-7]。因?yàn)樵诹孔佑?jì)算機(jī)中，數(shù)據(jù)以量子疊加態(tài)的形式存儲，而對量子疊加態(tài)的處理將同時(shí)對疊加態(tài)的每個(gè)分量進(jìn)行，根據(jù)這個(gè)特性，可以將信息存儲到疊加態(tài)的分量重，便于進(jìn)行并行處理。也就是說，僅需要通過一次計(jì)算就可以得到函數(shù)f(x)在x處于不同值時(shí)的相應(yīng)函數(shù)值。由于量子算法具有指數(shù)級加速部分經(jīng)典算法的能力，被認(rèn)為是解決當(dāng)前物理系統(tǒng)計(jì)算能力瓶頸的有效手段之一。

量子乘法器是以更基本的量子加法器為基礎(chǔ)，它可應(yīng)用于量子圖像處理中的濾波、邊緣檢測和頻率控制等領(lǐng)域，設(shè)計(jì)快速高效的量子乘法器具有重要的意義。2014年，Kotiyal[8]設(shè)計(jì)了基于二叉樹的量子乘法器，但其時(shí)間復(fù)雜度較高(即硬件復(fù)雜度)，為O(n3)。2017年，Hafiz Md[9]提出了一種高效的量子乘法器設(shè)計(jì)方案，利用乘數(shù)累加單元、量子全加器和量子“與”操作，實(shí)現(xiàn)了時(shí)間復(fù)雜度為O(n2)的量子乘法器。雖然文獻(xiàn)[9]比前人所提出的量子乘法器在時(shí)間復(fù)雜度上有所提升，但其實(shí)現(xiàn)方法復(fù)雜。本文將提出一種結(jié)構(gòu)簡單的量子乘法器的設(shè)計(jì)方法，僅需要量子全加器和量子右移算子，其時(shí)間復(fù)雜度為O(n2)。

1 量子計(jì)算基礎(chǔ)

1.1 通用量子門

對應(yīng)于經(jīng)典計(jì)算機(jī)中比特的概念，量子比特是量子計(jì)算機(jī)中存儲信息的最小單元。一個(gè)量子比特，其一般形式為[10]

|ψ〉=α|0〉+β|1〉

(1)

(1)式中：α和β是復(fù)數(shù)，滿足|α|2+|β|2=1；|0〉和|1〉狀態(tài)稱為計(jì)算基態(tài)。由此可見，n位經(jīng)典比特只能表示2n個(gè)數(shù)中的一個(gè)，而n位量子比特可以表示為2n個(gè)數(shù)線性疊加的形式，也即對n位量子比特進(jìn)行一次處理，等價(jià)于對2n個(gè)疊加項(xiàng)都同時(shí)進(jìn)行了處理，這為設(shè)計(jì)高并行量子算法提供了理論基礎(chǔ)。

經(jīng)典電路是由包含連線和邏輯門的線路組成的，類似地，量子線路是由連線和基本量子門組成的。任意的多量子比特門都可以由受控非門和單量子比特門復(fù)合而成，某種意義上，受控非門和單量子比特門是所有其他門的原型。所以在這里僅介紹4個(gè)通用量子門：非(NOT)門、受控非(CNOT)門、哈德(Hadamard)門以及Toffoli門。圖1為4個(gè)通用量子門的示意圖。圖1a的非門，實(shí)現(xiàn)基本狀態(tài)|0〉和|1〉的翻轉(zhuǎn);圖1b的Hadamard門則把狀態(tài)|0〉和|1〉分別轉(zhuǎn)換為中間狀態(tài);圖1c為作用在2個(gè)量子比特上的受控非門，它實(shí)現(xiàn)的是異或關(guān)系，當(dāng)a=1時(shí)，b實(shí)現(xiàn)0，1的翻轉(zhuǎn)， |a〉稱為控制量子比特，|b〉稱為目標(biāo)量子比特;圖1d為Toffoli門，此門有2個(gè)控制位，當(dāng)|a〉和|b〉同時(shí)為|1〉時(shí)，|c〉實(shí)現(xiàn)0，1翻轉(zhuǎn)。因此,可以讓|c〉處于不同的狀態(tài)，則可以發(fā)揮不同的作用。

圖1 通用量子門Fig.1 Universal quantum gate

1.2 計(jì)算復(fù)雜性理論

計(jì)算復(fù)雜性理論為計(jì)算機(jī)科學(xué)的一個(gè)分支[11]，與問題所需的計(jì)算資源相關(guān)。算法的復(fù)雜性是由算法解決問題時(shí)所需的時(shí)間來衡量的，算法所需的時(shí)間又由算法的執(zhí)行細(xì)節(jié)以及所使用的計(jì)算機(jī)決定。對于算法的復(fù)雜性，一般指的是算法的時(shí)間復(fù)雜度。

一般地，算法的時(shí)間復(fù)雜度與輸入信號的尺寸有關(guān)，即與實(shí)例有關(guān)，例如，對100個(gè)數(shù)排序比對10個(gè)數(shù)排序需要的時(shí)間更長。為了最小化時(shí)間復(fù)雜度對具體實(shí)例的依賴，一般考慮最壞情況下的時(shí)間復(fù)雜度T(n)為

(2)

(2)式中，t(x)為輸入是x時(shí)算法的運(yùn)行時(shí)間。

計(jì)算算法的時(shí)間復(fù)雜度應(yīng)基于一個(gè)與CPU鐘頻率無關(guān)的時(shí)間單元。此時(shí)間單元可為運(yùn)行一個(gè)基本運(yùn)算所需的時(shí)間，例如2個(gè)整數(shù)的加法運(yùn)算。測量任意算法所需的時(shí)間等價(jià)于計(jì)算此算法中包含的基本運(yùn)算數(shù)目。本文中以通用量子門(或叫簡單量子門)為時(shí)間單元，計(jì)算所設(shè)計(jì)的量子算法時(shí)，僅需要計(jì)算實(shí)現(xiàn)算法的量子線路中包含的通用量子門數(shù)量。

2 量子乘法器

2.1 量子加法器

圖2a展示了一位量子全加器的具體構(gòu)造線路圖；圖2b為其簡化圖。用n個(gè)一位的量子全加器疊加在一起就是一個(gè)n位的量子全加器，如圖2c所示，可以實(shí)現(xiàn)2個(gè)n位數(shù)的加和。

圖2 量子全加器示意圖Fig.2 Schematic diagram of quantum-integrator

2.2 二進(jìn)制乘法的實(shí)現(xiàn)步驟

為了實(shí)現(xiàn)量子乘法運(yùn)算，首先對傳統(tǒng)乘法運(yùn)算的步驟進(jìn)行改進(jìn)。例如，計(jì)算2個(gè)二進(jìn)制數(shù)1011和1101的乘積，圖3a為乘法的實(shí)現(xiàn)步驟?？偨Y(jié)其規(guī)律可知，每次部分積要加的數(shù)是被乘數(shù)乘于1，或者被乘數(shù)乘于0，即每一步中，根據(jù)乘數(shù)中每一位的值，部分積加上被乘數(shù)，或者不加。根據(jù)此特點(diǎn)，可以設(shè)計(jì)由加法操作和右移操作協(xié)同工作的乘法步驟；圖3b展示了改進(jìn)后的算法步驟，首先把部分積置零，然后乘數(shù)的低位是1，所以要加上被乘數(shù)1011，然后把和右移一位；乘數(shù)高一位的數(shù)是0，就加上0000，再把和右移一位，如此循環(huán)，直到得出結(jié)果。雖然是一個(gè)簡單的轉(zhuǎn)換，卻節(jié)省了很多計(jì)算步驟。例如，對于一個(gè)n位二進(jìn)制數(shù)乘于一個(gè)m位二進(jìn)制數(shù)，本來需要計(jì)算2m次的加法，改進(jìn)后只需要m次加法和m-1次的右移操作。關(guān)于加法的計(jì)算可以量子加法器。接下來需要設(shè)計(jì)一個(gè)量子右移線路以解決乘法的運(yùn)算。

2.3 量子右移算子

在經(jīng)典的數(shù)字電路中，需要沿著每條線從頭到尾來分析整個(gè)電路實(shí)現(xiàn)的功能，對于每條線，可以簡單地對其實(shí)現(xiàn)扇出以及扇入操作。因?yàn)殡娐分械拿織l線代表著實(shí)際物品中的電線，和實(shí)際電線一樣起著傳遞信息的作用，一條導(dǎo)線就可以把一個(gè)位置上的電位傳遞到任何地方，而比特的概念在電路圖里沒有體現(xiàn)得那么清楚。而在量子計(jì)算的過程中，也是按照每條線來分析其功能，不同的是，每一條線都代表一個(gè)或幾個(gè)量子比特的狀態(tài)轉(zhuǎn)化過程，而且沒有扇出和扇入操作。這是因?yàn)榱孔颖忍赜酶⑿〉奈锢憩F(xiàn)象表示，每條線代表的是一個(gè)相應(yīng)的微觀狀態(tài)，例如電子的自旋方向，原子核的自旋方向等。這些狀態(tài)不能簡單地通過介質(zhì)傳遞。因?yàn)榱孔硬豢煽寺≡?，不可能完全地對任意量子態(tài)進(jìn)行復(fù)制，也就無法對任意量子態(tài)實(shí)現(xiàn)完全的扇出，而扇入在這里是荒謬的，因?yàn)?個(gè)量子態(tài)并不能合并。例如圖4a，2個(gè)輸入量子比特為|a〉和|0〉，其中，|a〉為任意的單量子比特態(tài)?？梢园演斎霠顟B(tài)寫作|a,0〉，表示2個(gè)量子比特耦合在一起的系統(tǒng)，圖4a中利用了受控非門實(shí)現(xiàn)異或操作，經(jīng)過第1個(gè)受控非門輸入狀態(tài)轉(zhuǎn)換為|a,a⊕0〉=|a,a〉，經(jīng)過第2個(gè)不同的受控非門后的輸出狀態(tài)為|a⊕a,a〉=|0,a〉。可以看出，這個(gè)簡單的電路實(shí)現(xiàn)了量子比特|a〉和|0〉的交換，可以把它叫做置零線路。或者說實(shí)現(xiàn)了把|a〉復(fù)制到量子比特|0〉上，若把此操作應(yīng)用到多位的二進(jìn)制數(shù)，即可實(shí)現(xiàn)多位二進(jìn)制數(shù)的復(fù)制操作，只不過需要n位的輔助量子比特。假設(shè)需要右移操作的二進(jìn)制數(shù)是Cn-1Cn-2…C1C0，一個(gè)量子右移操作線路需要n位的量子比特來表示這個(gè)數(shù)，需要一個(gè)輔助的量子比特，輔助量子比特的初始狀態(tài)一般都為|0〉，如4b所示。首先交換|C0〉和輔助量子比特|0〉，然后依次交換相鄰的2個(gè)量子比特，從最終輸出可以看到實(shí)現(xiàn)了右移操作。每次右移一共需要n次交換，共需2n個(gè)受控非門。為了使用方便，圖4c為簡化后的右移算符。

圖3 乘法步驟Fig.3 Multiplication steps

圖4 量子右移操作Fig.4 Quantum right shift operation

如果需要實(shí)現(xiàn)很多位的右移，那么可以把整個(gè)右移算法重復(fù)使用多次，或者可以設(shè)計(jì)更簡單的右移線路，圖5為右移三位時(shí)的線路圖。其他情況可以以此類推，同理可以設(shè)計(jì)左移操作算符。

圖5 右移三位算符的具體線路圖Fig.5 Detailed circuit diagram of the three-right shift operator

2.4 量子乘法器設(shè)計(jì)

按照圖3中的乘法步驟，使用量子加法器和量子移位算子可以設(shè)計(jì)量子乘法器。

假設(shè)要計(jì)算一個(gè)m位和一個(gè)n位的二進(jìn)制數(shù)的乘積。用量子態(tài)|a〉代表n位的被乘數(shù)；|b〉代表m位的乘數(shù)。n位的部分積初始狀態(tài)為零，即處于基態(tài)|0〉|0〉…|0〉，然后依次用乘數(shù)的從低位到高位的每一位來控制部分積是加上被乘數(shù)還是加零，并在每次加和之后讓部分積右移一位。這樣就得到了2個(gè)數(shù)的乘積。結(jié)果存儲在m+n位的量子比特中。圖6為量子乘法器的線路圖，圖6中&為量子加法器的縮寫，未標(biāo)注的初始為零的量子比特均為輔助量子比特。該線路圖中主要有2種類型的量子門，受控加法器和右移一位操作算符，其中，受控加法器的控制量子位分別是乘數(shù)|b〉的每一位，目標(biāo)位實(shí)現(xiàn)部分積和被乘數(shù)的加和，結(jié)果仍存儲在n位部分積和一位進(jìn)位量子比特|En〉中。右移操作算符作用在m+n位的量子比特上。

圖6 量子乘法器Fig.6 Quantum multiplier

圖6展示的量子乘法器原理上只能夠計(jì)算2個(gè)正整數(shù)的積。然而，計(jì)算2個(gè)小數(shù)的乘積更具有普適性。只需要在圖6的基礎(chǔ)上稍作改進(jìn)即可實(shí)現(xiàn)。對于小數(shù)，它和整數(shù)的差別是小數(shù)點(diǎn)位置不同，因此，可以首先忽略小數(shù)點(diǎn)而作為整數(shù)進(jìn)行相乘，計(jì)算出乘積之后再利用圖5中的量子右移算子進(jìn)行移位操作即可得到正確結(jié)果。二進(jìn)制數(shù)的正負(fù)使用一個(gè)比特來表示，如用0表示正數(shù)，1表示負(fù)數(shù)，而在進(jìn)行數(shù)的乘法計(jì)算時(shí)，數(shù)值部分和符號部分是分開進(jìn)行處理的。在乘法運(yùn)算中，2個(gè)數(shù)的符號位運(yùn)算規(guī)則遵循的是異或關(guān)系，圖1中的受控非門即可實(shí)現(xiàn)這一運(yùn)算。這樣，經(jīng)過改進(jìn)后的量子乘法器便可計(jì)算任意2個(gè)有限位小數(shù)的乘積。

同樣，二進(jìn)制除法可以轉(zhuǎn)換為減法和向左移位，和量子乘法器的過程類似，可以設(shè)計(jì)出量子除法器，這樣，二進(jìn)制的四則運(yùn)算都可以使用量子計(jì)算的方法實(shí)現(xiàn)。

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

根據(jù)算法復(fù)雜性理論，本文以通用量子門為時(shí)間單元，計(jì)算量子乘法器線路中包含的通用量子門數(shù)量，即為其時(shí)間復(fù)雜度。

對于n位二進(jìn)制數(shù)乘以m位二進(jìn)制數(shù)，本文所設(shè)計(jì)的量子乘法器的線路如圖6所示，需要m次加法操作和m-1次右移操作。由圖6可知，單比特量子全加器需要5個(gè)CNOT門和2個(gè)Toffoli門，2個(gè)n位數(shù)相加時(shí)需要n比特量子全加器，由n個(gè)單比特量子全加器組成。所以，一次加法操作需要7n個(gè)通用量子門。這樣m次加法操作的時(shí)間復(fù)雜度為O(7nm)。對于一個(gè)n位二進(jìn)制數(shù)，一個(gè)右移算符其時(shí)間復(fù)雜度為2n，m-1次右移操作的時(shí)間復(fù)雜度為O(2nm)。所以，整個(gè)乘法運(yùn)算的時(shí)間復(fù)雜度為O(nm)。如果計(jì)算的二進(jìn)制數(shù)都是n位，則其時(shí)間復(fù)雜度為O(n2)。

文獻(xiàn)[8]設(shè)計(jì)了基于二叉樹的量子乘法器，其時(shí)間復(fù)雜度為O(n3)。文獻(xiàn)[9]利用乘數(shù)累加單元、量子全加器和量子“與”操作設(shè)計(jì)了目前最高效的量子乘法器，其時(shí)間復(fù)雜度為O(n2)。本文所設(shè)計(jì)的量子乘法器時(shí)間復(fù)雜度也為O(n2)，并且本文算法的結(jié)構(gòu)更簡單，僅需要加法操作和右移操作?？梢?，本文的量子乘法器設(shè)計(jì)是三者中最優(yōu)的方案。

4 結(jié)束語

本文設(shè)計(jì)了一種量子乘法器，通過量子全加器實(shí)現(xiàn)了n位二進(jìn)制數(shù)的加和，并且利用2個(gè)控制非門設(shè)計(jì)了置零電路，并使用置零電路設(shè)計(jì)量子右移算子。改進(jìn)了二進(jìn)制乘法，按照改進(jìn)后的步驟設(shè)計(jì)了量子乘法器。此設(shè)計(jì)充分考慮了每個(gè)二進(jìn)制數(shù)存儲在一個(gè)量子態(tài)中，對每個(gè)二進(jìn)制數(shù)進(jìn)行整體操作時(shí)更節(jié)省資源的特點(diǎn)，提供了一個(gè)合理的二進(jìn)制數(shù)乘法步驟。時(shí)間復(fù)雜度分析表明，本文所設(shè)計(jì)的量子乘法器，與文獻(xiàn)[8]中設(shè)計(jì)的量子乘法器具有相同的時(shí)間復(fù)雜度，但具有更簡單的實(shí)現(xiàn)方法。