改進TR門級聯的量子比較器設計

周 林，郭 兵

四川大學 計算機科學與技術，成都 610065

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

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

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

1 相關工作

1.1 可逆門

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

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

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

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

1.2 其他比較器設計

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

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

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

2 量子比較器設計

2.1 基本思想

假設需要比較的兩個數為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，便將比較大小的問題轉化為了求解Gn、Ln與En的問題。寫出迭代式：

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

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

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

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

根據式（7），由于L·G=0，因此上式可以很容易推導出來。

2.2 線路實現

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

圖2 TR1門實現Fig.2 TR1 gate implementation

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

圖3 TR2門實現Fig.3 TR2 gate implementation

2.3 代價分析

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

表1 2 bit比較器Table1 2 bit comparator

關系式（8）（9）可以使用Toffoli 門實現，然而由于Toffoli 門需要5 量子代價，故選擇Peres 門實現，量子代價只需要4。根據式（8）（9），如此便可以構造迭代關系如圖4所示。

圖4 迭代式實現Fig.4 Iterative implementation

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

（10）得到所有比較關系。完整電路實現如圖5所示。

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

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

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

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

3 實驗仿真驗證

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

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

表3 部分測試結果Table 3 Some testing results

4 總結

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