量子计算 [ζ(1)] -- 可逆逻辑计算

在 量子计算 [2].ext 里说过:  在电子计算机里,  X门为NOT门,  CNOT门为可逆XOR门,  CCNOT门为可逆AND门,  并且通过这3个门组合可以还原任意逻辑电路.

不过yysy,  对于不熟悉可逆计算的人[比如说我]来说,  可逆计算是挺难上手的一个东西,  下面用过一个小例子来展示如何用可逆计算实现基本逻辑.

加法器

加法器是一个不算难并且有一定复杂程度的电路,  所以加法器是一个绝妙的例子.

基本介绍

普通的波纹进位加法器由一大堆全加器构成.  全加器输入3bits:  A, B 和 Cin,  Cin表示从上一个全加器获得的进位,  而输出2bits: S 和 Cout,  S为加法的结果,  Cout为进位输出.  则一个n-bits加法器可以表示为:

不难推断在一个全加器里:   和 ,  其中是XOR,   是AND.  稍微化简一下Cout得:  

可逆逻辑门

可逆逻辑电路由可逆逻辑门构成,  并且可逆逻辑门输入比特数与输出比特数保持一致 [准确来说, 是输入即输出].  所以不像传统电子电路,  可逆逻辑电路没有明显的输出.  为了做到像传统电路具有明显的输出,  可逆电路必须有一个额外的比特用于储存结果,  以XOR做例子:

可以看到可逆XOR门[即CNOT门]把输入的一个比特用作储存结果,  而可逆AND门[即CCNOT门]则是把结果作用在第3个比特上:

这就是说可逆逻辑门"没有明显输出"的原因,  为了做到"明显的输出"需要额外一个比特输入为输出为,  比如传统XOR可以表示为:

对于AND就更好办了,  在CCNOT里,  如果C=0, 那么第3比特就为 A·B

逻辑分解

不做任何优化把全加器分解为单个逻辑的形式:

写为电路形式为:

来测试一下:  (使用自制的库 nyasQuantumCalculate [老推销员了])

Can we do betttttter?

Sure.  如果没要求在运算过程里保持输入比特不变的话,  则把临时结果与输入合拼到一起得到:

最后找到数据位[也就是输入比特]被修改的位门,  并反向作用这些位门[],  得到最后的全加器:

修改FullAdder函数,  再试着自己测试:

组合全加器

以3-bits加法器为例,  通过组合全加器,  则加法器电路为:

可以注意到,  在单个全加器里,  进位输入是第一个比特,  进位输出是最后一个比特,  所以可以排列成这么规则的形状,  不然需要插入大量的SWAP [虽然排得这么整齐对写代码没有明显的好处],  并且对于n-bits加法器,  一共需要 4*n + 1 bits

把FullAdder函数包装成黑箱,  再测试一下

运行结果就不展示了,  可以自己尝试运行一下

需要留意的是,  运算过程里只用到了可逆逻辑门,  也就是说整个过程也是可逆的,  把加法电路反着运行就可以从输出得到输入,  这是传统电子电路无法做到的.

Can we do the best?

确实,  就算是这个5bits的全加器也不是最好的方案.  以下来不严格讨论最好可以做成什么样子.

可逆逻辑过程的重点是可逆,  即从输出推导输入.  在全加器里,  必定输入3个bits: A, B, Cin 和必定输出2个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},  仅依靠一个额外的比特X不足以覆盖所有情况.  所以不难知道,  最好的全加器由4bits构成 [也就是输入A,B,Cin和0,  输出S,Cout,X,Y,  其中XY逻辑未定]

结语

最后,  可以自己试着设计这个4bits全加器的电路.  也欢迎大家进瑟图群讨论啦:  [274767696]

nyasQuantumCalculate仓库 (已更新单独的可逆电子电路的包: RevCal):  [github.com/nyasyamorina/nyasQuantumCalculate]

也许以后会出一篇这节的附章,  把4bits全加器的可逆电路介绍一下,  然后再介绍一下量子版的全加器.  不过说不定也不会做  (咕咕咕