在?量子計(jì)算 [2].ext?里說過:? 在電子計(jì)算機(jī)里,? X門為NOT門,? CNOT門為可逆XOR門,? CCNOT門為可逆AND門,? 并且通過這3個(gè)門組合可以還原任意邏輯電路.

不過yysy,? 對(duì)于不熟悉可逆計(jì)算的人[比如說我]來說,? 可逆計(jì)算是挺難上手的一個(gè)東西,? 下面用過一個(gè)小例子來展示如何用可逆計(jì)算實(shí)現(xiàn)基本邏輯.

加法器

加法器是一個(gè)不算難并且有一定復(fù)雜程度的電路,? 所以加法器是一個(gè)絕妙的例子.

基本介紹

普通的波紋進(jìn)位加法器由一大堆全加器構(gòu)成.? 全加器輸入3bits:? A, B 和 Cin,? Cin表示從上一個(gè)全加器獲得的進(jìn)位,? 而輸出2bits: S 和 Cout,? S為加法的結(jié)果,? Cout為進(jìn)位輸出.? 則一個(gè)n-bits加法器可以表示為:

不難推斷在一個(gè)全加器里:???和 ,? 其中是XOR,?? 是AND.? 稍微化簡(jiǎn)一下Cout得:??

可逆邏輯門

可逆邏輯電路由可逆邏輯門構(gòu)成,? 并且可逆邏輯門輸入比特?cái)?shù)與輸出比特?cái)?shù)保持一致 [準(zhǔn)確來說, 是輸入即輸出].? 所以不像傳統(tǒng)電子電路,? 可逆邏輯電路沒有明顯的輸出.? 為了做到像傳統(tǒng)電路具有明顯的輸出,? 可逆電路必須有一個(gè)額外的比特用于儲(chǔ)存結(jié)果,? 以XOR做例子:

可以看到可逆XOR門[即CNOT門]把輸入的一個(gè)比特用作儲(chǔ)存結(jié)果,? 而可逆AND門[即CCNOT門]則是把結(jié)果作用在第3個(gè)比特上:

這就是說可逆邏輯門"沒有明顯輸出"的原因,? 為了做到"明顯的輸出"需要額外一個(gè)比特輸入為輸出為,? 比如傳統(tǒng)XOR可以表示為:

對(duì)于AND就更好辦了,? 在CCNOT里,? 如果C=0, 那么第3比特就為 A·B

邏輯分解

不做任何優(yōu)化把全加器分解為單個(gè)邏輯的形式:

寫為電路形式為:

來測(cè)試一下:? (使用自制的庫 nyasQuantumCalculate [老推銷員了])

Can we do betttttter?

Sure.? 如果沒要求在運(yùn)算過程里保持輸入比特不變的話,? 則把臨時(shí)結(jié)果與輸入合拼到一起得到:

最后找到數(shù)據(jù)位[也就是輸入比特]被修改的位門,? 并反向作用這些位門[],? 得到最后的全加器:

修改FullAdder函數(shù),? 再試著自己測(cè)試:

組合全加器

以3-bits加法器為例,? 通過組合全加器,? 則加法器電路為:

可以注意到,? 在單個(gè)全加器里,? 進(jìn)位輸入是第一個(gè)比特,? 進(jìn)位輸出是最后一個(gè)比特,? 所以可以排列成這么規(guī)則的形狀,? 不然需要插入大量的SWAP [雖然排得這么整齊對(duì)寫代碼沒有明顯的好處],? 并且對(duì)于n-bits加法器,? 一共需要 4*n + 1 bits

把FullAdder函數(shù)包裝成黑箱,? 再測(cè)試一下

運(yùn)行結(jié)果就不展示了,? 可以自己嘗試運(yùn)行一下

需要留意的是,? 運(yùn)算過程里只用到了可逆邏輯門,? 也就是說整個(gè)過程也是可逆的,? 把加法電路反著運(yùn)行就可以從輸出得到輸入,? 這是傳統(tǒng)電子電路無法做到的.

Can we do the best?

確實(shí),? 就算是這個(gè)5bits的全加器也不是最好的方案.? 以下來不嚴(yán)格討論最好可以做成什么樣子.

可逆邏輯過程的重點(diǎn)是可逆,? 即從輸出推導(dǎo)輸入.? 在全加器里,? 必定輸入3個(gè)bits: A, B, Cin 和必定輸出2個(gè)bits: S, Cout.? 輸出少于輸入,? 這明顯不可逆.? 那么把輸出增加到3bits: S, Cout, X,? 其中X的邏輯未定,? 這樣子存在可逆電路嗎.? 答案也是否,? 如果給出 S=1,? Cout=0,? 則存在3種可能的輸入:? {A=1, B=0, Cin=0},?{A=0, B=1, Cin=0},?{A=0, B=0, Cin=1},? 僅依靠一個(gè)額外的比特X不足以覆蓋所有情況.? 所以不難知道,? 最好的全加器由4bits構(gòu)成 [也就是輸入A,B,Cin和0,? 輸出S,Cout,X,Y,? 其中XY邏輯未定]

結(jié)語

最后,? 可以自己試著設(shè)計(jì)這個(gè)4bits全加器的電路.? 也歡迎大家進(jìn)瑟圖群討論啦:? [274767696]

nyasQuantumCalculate倉(cāng)庫 (已更新單獨(dú)的可逆電子電路的包: RevCal):? [github.com/nyasyamorina/nyasQuantumCalculate]

也許以后會(huì)出一篇這節(jié)的附章,? 把4bits全加器的可逆電路介紹一下,? 然后再介紹一下量子版的全加器.? 不過說不定也不會(huì)做? (咕咕咕