可逆邏輯電路

可逆邏輯有許多套用,尤其在量子計算領域,量子可逆邏輯電路是構建量子計算機的基本單元,量子可逆邏輯電路綜合就是根據電路功能,以較小的量子代價自動構造量子可逆邏輯電路.

基本介紹

• 中文名：可逆邏輯電路
• 外文名：Reversible logic circuits

背景

量子計算機可等效一個量子圖靈機.理論上已證明,量子圖靈機可等價一個量子邏輯電路.量子邏輯門的組合與級聯是組成量子計算機的基本元素.所有量子邏輯門均可表示成復變空間酋矩陣,其輸入與輸出的比特數相等,也稱可逆運算元.量子邏輯門對輸入比特進行確定的酋變換,得到輸出比特.Deutsch最早考慮用量子邏輯門構造量子計算機的問題,他發現幾乎所有的三比特量子邏輯門都是通用邏輯門.通用邏輯門的含義是指,通過該邏輯門的級聯,能夠以任意精度逼近任意一個么正操作,么正操作對應操作的數理解析,邏輯門的級聯將生成物理上的量子邏輯電路.
Deutsch的結果隨後得到發展,最後Deutsch等和Lloyd各自獨立證明了幾乎所有的二比特量子邏輯門都是通用的,這裡“幾乎”是指,二比特通用量子邏輯門的集合是所有二比特邏輯門的集合的一個稠密子集.實驗上通常用一些具體的量子邏輯門構造量子計算機.Barenco[2]等人證明,一個二比特的異或門與對一比特進行任意操作的門可構成一個通用量子門集.

相對而言,單比特邏輯門在實驗上比較容易實現,現在多數實驗方案都集中於製造量子異或門.量子異或門和經典異或門非常相似,它有兩個輸入比待:控制比特和受控比特.當控制比特處於微粒子上能級(激活態)時,受控比特狀態發生反轉.用記號C12代表量子異或操作,其中1,2分別代表控制和受控比特,則有n1〉1n2〉2C12n1〉1n1n2〉2,其中n1,n2取值0或1,表示模2加(異或)運算.

迄今為止,雖然世界上還沒有真正意義的量子計算機.但是,世界主要經濟已開發國家都在制定戰略性規劃,各國有代表性的實驗室正以巨大的熱情投入人財物,期望在新一代計算機的科學與技術上占據領導地位.正因為實現量子計算機的技術困難重重,而量子計算機的實現必將為信息科學與通信技術帶來革命性的突破,所以量子可逆邏輯電路的設計、最佳化與測試等方法的研究作為量子信息與量子計算理論的基礎研究越來越受到理論研究者與套用研究者的關注,也將筆者所在研究小組的研究重點從經典信息領域逐漸轉向量子信息與計算領域.量子可逆邏輯綜合源於可逆計算機的研究.

20世紀中葉,人們發現計算機晶片的能耗導致晶片發熱,限制晶片集成度,影響計算機的運行速度.Landauer發現,晶片能耗主要源於計算中的不可逆操作.因此降低能耗的關鍵是將不可逆操作變為可逆操作.Bennett對此有嚴格證明.經典計算機本質上是一個通用圖靈機,是不可逆的,但所有不可逆通用圖靈機,都對應一個可逆圖靈機,且兩者的計算能力和計算效率完全相同.由於量子邏輯門都是可逆的,因此可以用可逆的設計方法綜合量子邏輯電路.量子電路理論上不丟失輸入信息,因此也不存在熱耗散,從而從理論上有效地解決了晶片的熱耗問題.Bennett證明只要是可逆門構造的網路,能量零損耗是可能的.可逆邏輯已廣泛套用在量子計算、低功耗CMOS電路、納米技術、光計算、加密技術等許多領域,因此可逆邏輯的研究將變得越來越重要.最近30年,人們提出了多種可逆量子門.如Feynman提出的控制非門(CNOT)、Toffoli門、Fredkin門等.如何使用規定的量子門自動生成量子代價較小的量子電路,即製造量子電路的成本較低,通常認為量子代價是指使用量子門的數量,最優的量子電路是指使用量子門的數量最少.Shende、Song等人提出了一些可逆邏輯綜合的算法,Shende[等人提出了一種3個輸入變數的綜合方法.Iwama等人給出了CNOT電路的綜合規則,提出CNOT門序列順序變化的規則,通過將實現麼變換的相鄰且相同的門消除,最終實現可逆電路的化簡.Miller套用譜函式實現近似最優的可逆電路化簡.然而目前人們還沒有找到通用高效的算法,特別對多個輸入變數的量子電路,這是量子電路中急需解決的重要問題之一.Shende等人提出的窮舉算法較慢,Miller、Iwama、Maslov給出了幾個啟發式算法,有些還需要模板最佳化技術.Mishchenko等人提出使用RM綜合可逆邏輯電路,Gupta給出了基於RM的啟發式規則,但這些算法缺乏普遍適用性,且通常生成的電路不能達到最優.

量子計算機可等效為量子圖靈機,量子圖靈機可等價為量子邏輯電路,因此可通過量子邏輯門的級聯構建量子計算機.目前常用的量子邏輯門有NOT門、CNOT門、Toffoli門、通用Toffoli門等.如何使用指定量子門自動生成量子代價較小的量子電路,其本質就是量子可逆邏輯綜合問題,為此諸多學者提出了各種綜合算法,如Song等研究了可逆邏輯門的代數特徵,提出用群論方法綜合量子可逆邏輯電路;Iwama等針對特定CNOT,給出了電路的綜合規則;Miller等套用譜函式實現近似最優的可逆電路化簡;Maslov等率先在量子可逆電路綜合中提出真值表構造法以及使用模板技術最佳化電路的思想;Li等給出了通用的模板構造與最佳化算法;Shende等將可逆邏輯電路綜合簡化為置換問題,並提出了性能較好的遞歸算法;Yang等提出了以3-循環作為電路綜合的基本塊,使之在僅使用NT量子門庫情況下,實現了可逆邏輯電路的自動構造.上述算法雖可以較高效率綜合出電路,但並非最優電路.Shende等利用窮盡搜尋法,綜合出所有三量子最優電路,但其所需的時空複雜度太大,隨著綜合量子比特數的增加,綜合可逆邏輯電路所需的時間和空間都遠遠超過經典計算機所能承受的範圍.

定義

定義1(可逆邏輯)設f(x1,x2,…,xk)=(y1,y2,…,yk)為一個k元的布爾函式,即f:Bk※Bk,其中B={0,1},則f是可逆的若且唯若f是雙射函式.邏輯門是可逆的若且唯若它實現的是一個可逆函式,若干可逆邏輯門的級聯構成的電路稱為可逆電路.

定義2(量子門)Toffoli量子門,記為TOF(C,T),簡稱TOF門。

定義3擴展通用Toffoli(ExtendedGeneralToffoli)門記為EGT(C,T),是由下面4種線型組成(1)肯定控制線:如果在這條線上輸入的是0,則受控線的值將不改變.如果輸入的是1,則其它的肯定/否定控制線確定受控線上的值是否被反轉.通過肯定控制線的值不變.(2)否定控制線:如果在這條線上輸入的是1,則受控線的值將不改變.如果輸入的是0,則其它的肯定/否定控制線確定受控線上的值是否被反轉.通過否定控制線的值不變.(3)受控線每個門只有一條受控線,通過受控線的值,受肯定/否定控制線的控制.(4)無關線:通過無關線的值不變,也不對其它線產生影響.由這四種線型組成的可逆邏輯門,稱之為擴展通用Toffoli門,簡稱EGT.EGT門可轉化成TOF門。

定義4(鄰接矩陣)設有兩個不同的二進制數s和t.連線s和t的一個鄰接矩陣定義為:以s開頭以t結束的一組二進制數組成的矩陣，使得相鄰的兩個二進制數恰好僅有一位不同.

量子可逆邏輯電路的基本概念

利用微觀粒子狀態表示的信息稱為量子信息,量子信息的基本單位是量子比特(qubit),與經典信息不同,量子比特能夠以疊加態的形式存在,任何量子比特均可由一個二元向量形式表示,形式如φ〉=α0〉+β1〉,其中α和β為複數,滿足歸一化條件α2+β2=1.

量子邏輯門是處理量子信息的基本單元,量子邏輯門的級聯構成量子電路,量子電路必須是可逆的,即量子信息的動態過程在復向量空間上必須保持正交變換.在量子計算中,一個量子邏輯門對應一個么正變換,根據輸入輸出的對數,邏輯門可分為單量子比特門與多量子比特門.

定義1.通用Toffoli量子門記為TOF(C;t),其中輸入變數集合In=x1,x2,…,xn,控制端集合C=xi1,xi2,…,xik,k∈{1,2,…,n-1},受控端集合為t=xj,且滿足C∩t=,C∪tIn.TOF(C;t)將輸出變數集合映射成:{x1,x2,…,xj-1,xjxi1xi2…xik,xj+1,…,xn}.若m∈{1,2,…,k},xim=0※xi1xi2…xik=0,受控端xj輸出為xjxi1xi2…xik=xj0=xj;若m∈{1,2,…,k},
xim=1※xi1xi2…xik=1,受控端xj的輸出為xjxi1xi2…xik=xj1=xj.該Toffoli量子門通常表示為TOF(xi1,xi2,…,xik;xj)。

當k=0時,C=,TOF(xj)為非門(NOT);

當k=1時,C={xi1},TOF(xi1;xj)為控制非門(CNOT);

當k=2時,C={xi1,xi2},TOF(xi1,xi2;xj)為標準Toffoli門.

這裡只有非門為單量子比特門,其它均為多量子比特門. 定義2.n個輸入與n個輸出變數的布爾函式f(x1,x2,…,xn)={y1,y2,…,yn},是可逆函式,若且唯若它是雙射,即任意一個輸入都對應著唯一的輸出,如任意輸入值(xn…x2x1)2對應唯一的輸出值(yn…y2y1)2,反之亦然.其中,xi,yi,1≤i≤n分別表示第i個輸入與輸出變數,(X)2表示將二進制數X轉換為十進制的值,如(101)2=5.

定義3.能用可逆函式描述的電路稱為可逆邏輯電路.可逆邏輯電路的特點是:(1)輸入線數與輸出線數相等;(2)沒有扇出與扇入;(3)沒有反饋;(4)電路分層級聯,有時為保證電路可逆,需添加一些輔助位,即垃圾位.

定義4.n個輸入與n個輸出變數的布爾函式f(x1,x2,…,xn)={y1,y2,…,yn}的展開式:f(xn,xn-1…,x1)=2n-1i=0(diPi)(2)稱為正極性ReedMuller展開式(RM),即任意一個布爾函式均可用若干個輸入變數的乘積的異或和的形式表示.

量子可逆邏輯電路綜合方法及其比較

量子可逆邏輯綜合是以較小的量子代價自動構造所求的量子可逆邏輯電路,具有很強的實際套用價值.

(1)真值表法.根據真值表自動構造可逆邏輯電路.f為如式(1)的可逆函式.有3種方法:①前向合成.先按照i的升序,對於每一個i尋找j,使得f(j)=i,再通過選取Toffoli門,將j轉換為i,不斷重複此過程,直至滿足i,f(i)=i.將選擇的門順序排列;②後向合成.先按照i的升序,對於每個i,通過選取Toffoli門,將f(i)轉換為i,不斷重複此過程,直至滿足i,f(i)=i.將選擇的門逆序排列;③雙向合成.

(2)專用構造方法.本方法根據一些特定功能的可逆邏輯電路的特點,用專用構造算法,快速生成電路.如用Bitonic方法可快速構造大規模的量子排序電路,然而這些算法不具有通用性,但性能很好.例如構造可逆排序電路,如果用其它方法,則算法複雜性較高,且構造的電路沒有規律,很難由此直接構造更大的排序電路.

(3)RM法。執行下列步驟:①根據可逆邏輯電路的功能構造可逆函式;②通過可逆函式構造RM展開式;③通過對RM展開式逐步化簡,生成可逆邏輯電路.這是本文使用的方法.

基於 RM 的量子可逆邏輯電路綜合的快速算法

基於 RM 的量子可逆邏輯電路綜合的本質是對 RM 展開式進行化簡, 可以將 RM 展開式的化簡過程表示為一棵解空間樹 . 綜合可逆邏輯電路的方法主要有 3 種 ,分別為: ( 1)啟發式規則; ( 2)回溯法 ; ( 3)分枝定界法,在這些方法的基礎上研製而成. 其中“解” 是指滿足要求的量子可逆邏輯電路。

設最優電路的長度為 N ,可選用的量子門數為M ,生成的量子電路解空間樹是高度為 N +1 的滿M 叉樹, 最壞情況下訪問節點總數為 M0 +M1 +M 2 +…+M N =( M N +1 -1) /( M -1),若排除相鄰且相同的量子門 ,解空間樹變為準滿 M -1 叉樹, 例外的是根節點有 M 個子節點 , 則訪問節點數為1 +( M -1) 0 +( M -1) 1 +…+( M -1) N =( ( M -1) N +1 +M -3) /( M -2). 根據引理 3 可得 , 當電路有 n 條線 ,全部通用 Toffo li 門有 M =n2n -1種 . 因此當 n 增大時,最壞情況下訪問節點總數成指數量級增加 ,算法若不最佳化 ,當 n 較大時 ,如 n ≥3 , 量子電路就很難綜合.用自動構造 RM 展開式 ,在生成量子可逆邏輯電路的解空間樹上, 採用總體層次遍歷 ,局部深度搜尋 , 借鑑模板最佳化技術, 構造限界函式快速刪除無解與非最優解的分枝, 優先探測 RM 中的因子,以極高的效率生成最優量子可逆邏輯電路 . 其中 ,總體層次遍歷的思想來自分枝定界法,局部深度搜尋的思想來自回溯法, 優先探測 RM中的因子的思想來自啟發式規則。