周 林，郭 兵

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

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

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

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

1 相關(guān)工作

1.1 可逆門

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

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

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

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

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

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

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

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

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

2.1 基本思想

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

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

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

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

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

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

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

2.2 線路實現(xiàn)

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

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

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

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

2.3 代價分析

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

表1 2 bit比較器Table1 2 bit comparator

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

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

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

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

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

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

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

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

3 實驗仿真驗證

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

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

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

4 總結(jié)

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