改進(jìn)TR門級(jí)聯(lián)的量子比較器設(shè)計(jì)

周 林，郭 兵

四川大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)，成都 610065

在20 世紀(jì)60 年代，學(xué)者們發(fā)現(xiàn)在邏輯電路中丟失的信息是導(dǎo)致計(jì)算機(jī)發(fā)熱的原因之一[1]。為了解決計(jì)算復(fù)雜度與能量消耗的問(wèn)題，自費(fèi)曼提出量子計(jì)算的概念以來(lái)，其發(fā)展得到了國(guó)內(nèi)外學(xué)者的重視。量子計(jì)算提供了解決NP 問(wèn)題的思路，比如實(shí)現(xiàn)質(zhì)因數(shù)分解的shor 算法[2]，對(duì)現(xiàn)代密碼學(xué)體系造成了沖擊。

量子比較器是量子算法實(shí)現(xiàn)的重要組成部分。在量子同態(tài)加密算法[3]、量子最大值算法[4]、量子排序算法[5]，量子字符串搜索算法[6]等常用算法中，都使用了量子比較器進(jìn)行比較操作。量子比較器使用廣泛，一個(gè)性質(zhì)良好的比較器會(huì)為量子算法的物理實(shí)現(xiàn)提供基礎(chǔ)性的幫助。

量子代價(jià)（quantum cost）是一個(gè)量子電路需要的單比特門與雙比特門的數(shù)量，通常用來(lái)度量構(gòu)造一個(gè)量子電路的代價(jià)[7]；垃圾輸出（garbage output）是量子計(jì)算機(jī)輸出的無(wú)用的比特。由于目前量子電路的物理實(shí)現(xiàn)困難，退相干時(shí)間短，因此量子代價(jià)與垃圾輸出是衡量一個(gè)量子電路好壞的重要指標(biāo)。本文通過(guò)對(duì)量子可逆門和基礎(chǔ)布爾代數(shù)的研究，提出一種基于改進(jìn)TR 門級(jí)聯(lián)的量子比較器構(gòu)造方法，該方法對(duì)量子代價(jià)與垃圾輸出都有明顯的優(yōu)化。

1 相關(guān)工作

1.1 可逆門

量子計(jì)算機(jī)是由包含導(dǎo)線和基本量子門構(gòu)成的，可以攜帶和操縱量子信息的電路[8]。量子門是可逆的，滿足酉性變換性質(zhì)。常用的可逆門有V 門、NOT 門、CNOT門、TR門[9]、Peres門[10]、Toffoli門等。

V門、V?門和NOT門都是單量子比特門，量子代價(jià)（quantum cost）為1，其中V?指V門的共軛轉(zhuǎn)置。它們的酉矩陣可以表示為：

CNOT門是兩量子比特門，由一個(gè)控制比特和一個(gè)目標(biāo)比特組成，作用是根據(jù)控制比特的值選擇翻轉(zhuǎn)目標(biāo)比特。當(dāng)控制比特為|1>時(shí)，CNOT門將會(huì)對(duì)目標(biāo)比特施行NOT變換，對(duì)于輸入A、B實(shí)現(xiàn)A、A⊕B輸出，量子代價(jià)為1。由單比特門和雙比特門可以構(gòu)造N比特門。TR門和Peres門都是三量子比特門，它們都可由兩個(gè)V門、一個(gè)V?門和一個(gè)CNOT 門構(gòu)造，量子代價(jià)均為4。TR門對(duì)于輸入A、B、C分別實(shí)現(xiàn)A、A⊕B、ABˉ⊕C的輸出。Peres 門對(duì)于輸入A、B、C分別實(shí)現(xiàn)A、A⊕B、AB⊕C的輸出。Toffoli 門也是一個(gè)三輸出可逆門，量子代價(jià)為5。不同的可逆門有不同的代價(jià)，圖1 展示了常用可逆門的構(gòu)造方法及其量子代價(jià)[11]。

圖1 可逆門及其代價(jià)Fig.1 Reversible gate and quantum cost

1.2 其他比較器設(shè)計(jì)

文獻(xiàn)[12]提出了基于多目標(biāo)擴(kuò)展通用Toffoli門的設(shè)計(jì)，該方法從最高位向最低位進(jìn)行比較，直接得到比較結(jié)果。其只需要2n-2 個(gè)輔助比特，優(yōu)點(diǎn)在于簡(jiǎn)單直觀，同時(shí)節(jié)約了量子比特。其中n位通用Toffoli門的構(gòu)造量子代價(jià)比較高昂，學(xué)者M(jìn)aslov[13]指出n+1 比特通用Toffoli門需要32n-120的量子代價(jià)以及一個(gè)垃圾比特。

文獻(xiàn)[14]提出了基于流水線的設(shè)計(jì)，其包含了一系列的比較單元（cell），每個(gè)cell 比較兩個(gè)比特之間的大小。單位cell 使用了Toffoli 門、CNOT 門和NOT 門生成，cell的量子代價(jià)為39且輸出了8個(gè)垃圾比特。

文獻(xiàn)[15]提出了基于樹(shù)結(jié)構(gòu)的設(shè)計(jì)，將需要比較的比特分別置于葉節(jié)點(diǎn)，比較結(jié)果從葉節(jié)點(diǎn)傳遞向根節(jié)點(diǎn)，最終由根節(jié)點(diǎn)匯總結(jié)果。該方案葉節(jié)點(diǎn)使用TR 門設(shè)計(jì)，對(duì)于n位通用比較器，該設(shè)計(jì)需要18n-9 的量子代價(jià)，同時(shí)生成6n-6 垃圾比特。

2 量子比較器設(shè)計(jì)

2.1 基本思想

假設(shè)需要比較的兩個(gè)數(shù)為A與B，都由n+1 個(gè)比特表示。Ai表示A的從低位到高位的第i個(gè)比特，Bi同理，則使用gi表示Ai>Bi的真值，同理li表示Ai

其中，·表示交運(yùn)算，⊕表示異或運(yùn)算，利用真值表很容易驗(yàn)證上式的正確性，接下來(lái)考慮組合多個(gè)比特的情況。使用Gi表示從低位到高位截取第0 到第i個(gè)比特的A與B的大小比較，即當(dāng)Gi=1 時(shí)，A0～i>B0～i，故若Gn=1 意味著A>B。同理定義Li與Ei，便將比較大小的問(wèn)題轉(zhuǎn)化為了求解Gn、Ln與En的問(wèn)題。寫出迭代式：

其中，+表示或運(yùn)算。分析上式（4），當(dāng)gi為1 時(shí)，意味著Ai>Bi，按照高位比較原則，Gi為1；當(dāng)gi的值為0，說(shuō)明Ai≤Bi，若關(guān)系為小于，則Gi為0，若關(guān)系為等于，則需要比較Gi-1的值，若Gi-1為1，則Gi為1。式（5）分析同理，對(duì)于式（6）則顯然當(dāng)A與B的所有位都相等時(shí)，兩個(gè)數(shù)相等。

根據(jù)式（1）～（6），便得到了整個(gè)迭代關(guān)系。由于量子電路中實(shí)現(xiàn)或運(yùn)算代價(jià)較高，因此可以考慮將或運(yùn)算化簡(jiǎn)為異或運(yùn)算。有結(jié)論[16]：

這很容易證明。由于gi·ei=0，因此式（4）、（5）在i>0時(shí)可寫作：

一般的不需要將三個(gè)值全部求出來(lái)，根據(jù)式（10）可以很容易從任意兩個(gè)值得到第三個(gè)值。

根據(jù)式（7），由于L·G=0，因此上式可以很容易推導(dǎo)出來(lái)。

2.2 線路實(shí)現(xiàn)

利用TR 門構(gòu)造單比特比較器，根據(jù)式（1）和（2）將TR門的輸出后面添加一個(gè)CNOT門進(jìn)行組合，便可得到單比特比較器，將其封裝，記為TR1門如圖2所示。TR1門同時(shí)實(shí)現(xiàn)了li、gi，且構(gòu)造該門使用了5個(gè)量子比特。

圖2 TR1門實(shí)現(xiàn)Fig.2 TR1 gate implementation

同理利用三個(gè)CNOT 門與TR 門可以構(gòu)造需要的門，記為TR2 門，得到一個(gè)三輸出電路。每個(gè)輸出分別代表著ei、li與gi如圖3所示。這樣使用7個(gè)量子比特構(gòu)造了一個(gè)完整的單比特比較三輸出電路。

圖3 TR2門實(shí)現(xiàn)Fig.3 TR2 gate implementation

2.3 代價(jià)分析

首先考慮2 bit 的情況。文獻(xiàn)[12]基于多目標(biāo)的擴(kuò)展通用Toffoli 門的設(shè)計(jì)，2 bit 比較器使用了4 個(gè)擴(kuò)展Toffoli門，量子代價(jià)為70，垃圾輸出為4；對(duì)于文獻(xiàn)[14]流水線設(shè)計(jì)，2 bit比較器量子代價(jià)為39，垃圾輸出為8；對(duì)于文獻(xiàn)[15]基于樹(shù)的設(shè)計(jì)，量子代價(jià)為27，垃圾輸出為6；對(duì)比本文使用的方法如圖2 所示，量子代價(jià)為20，垃圾輸出為1。2 bit比較如表1所示。

表1 2 bit比較器Table1 2 bit comparator

關(guān)系式（8）（9）可以使用Toffoli 門實(shí)現(xiàn)，然而由于Toffoli 門需要5 量子代價(jià)，故選擇Peres 門實(shí)現(xiàn)，量子代價(jià)只需要4。根據(jù)式（8）（9），如此便可以構(gòu)造迭代關(guān)系如圖4所示。

圖4 迭代式實(shí)現(xiàn)Fig.4 Iterative implementation

對(duì)于任意比特比較器來(lái)說(shuō)，整個(gè)電路可以通過(guò)迭代式構(gòu)造。由于當(dāng)i=0 時(shí)G0=g0,L0=l0，為了節(jié)約量子代價(jià)，因此，在比較第一個(gè)量子比特時(shí)使用TR1 代替TR2，此后根據(jù)式（8）（9）迭代式構(gòu)造電路，最終通過(guò)式

（10）得到所有比較關(guān)系。完整電路實(shí)現(xiàn)如圖5所示。

圖5 比較器電路圖Fig.5 Circuit diagram of comparator

考慮nbit的情況。對(duì)于文獻(xiàn)[12]，量子代價(jià)主要來(lái)自于擴(kuò)展多目標(biāo)Toffoli 門的設(shè)計(jì)。由于原文沒(méi)有給出該門的電路圖，無(wú)法準(zhǔn)確計(jì)算量子代價(jià)。因此，本文根據(jù)文獻(xiàn)[13]的對(duì)于擴(kuò)展多目標(biāo)Toffoli門的實(shí)現(xiàn)，估計(jì)該方法所需的量子代價(jià)。可知沒(méi)有垃圾比特的擴(kuò)展多目標(biāo)Toffoli 需要的量子代價(jià)是指數(shù)級(jí)別的。根據(jù)圖5 可得，本文方法總量子代價(jià)=(TR1+(n-1)×TR2+2n×4)=15n-2，總垃圾輸出=3n-2。因此得到如表2 所示結(jié)果。

表2 n bit比較器Table 2 n bit comparator

由表2 可知，對(duì)于nbit 比較器，對(duì)比文獻(xiàn)[15]當(dāng)n=8 時(shí)，量子代價(jià)有近12.6%減少，垃圾輸出有近47.6%的優(yōu)化。

3 實(shí)驗(yàn)仿真驗(yàn)證

為了驗(yàn)證本文設(shè)計(jì)的正確性，使用IBM Q 團(tuán)隊(duì)開(kāi)發(fā)的Qiskit 量子開(kāi)發(fā)工具包進(jìn)行模擬仿真實(shí)現(xiàn)。模擬程序運(yùn)行于Windows 10 系統(tǒng)，硬件配置為Intel Core i7-4720HQ，RAM大小4 GB。

分別構(gòu)造1、2、8個(gè)bit的比較器作為實(shí)驗(yàn)對(duì)象，由于Qiskit 中每一位量子線路的默認(rèn)輸入為0，因此通過(guò)在線路最前添加NOT門達(dá)到調(diào)整輸入數(shù)字的目的。通過(guò)多次隨機(jī)抽樣測(cè)試，最終每個(gè)例子都符合測(cè)試結(jié)果，表3是部分測(cè)試結(jié)果的實(shí)例。

表3 部分測(cè)試結(jié)果Table 3 Some testing results

4 總結(jié)

本文實(shí)現(xiàn)了一種新的量子比較器方案，對(duì)其進(jìn)行了邏輯推導(dǎo)與證明，給出了完整的電路實(shí)現(xiàn)，對(duì)比前人的設(shè)計(jì)，本文方案更加細(xì)化且易于實(shí)現(xiàn)，利用改進(jìn)TR門級(jí)聯(lián)設(shè)計(jì)，構(gòu)造簡(jiǎn)單可擴(kuò)展性強(qiáng)。實(shí)驗(yàn)結(jié)果表明，該方案在量子代價(jià)與垃圾輸出上有明顯的優(yōu)化。