CN101776934A - 进位产生和传递函数发生器及可逆最优加法线路设计方法 - Google Patents

Abstract

本发明“进位产生和传递函数发生器及可逆最优加法线路设计方法”公开了一种新型的可逆逻辑门——“ZS”门，以及它的量子线路设计图。该设计图只含有双量子比特受控门和单量子比特门。同时利用该门设计了“进位产生函数和传递函数发生器”(ZSGPD)，实现了单个门以零无用输出产生多个进位传递函数。并以该门为基础，设计了“可逆最优化”的两种加法线路结构——量子全加法器(ZSQFA)和量子无等待进位加法器(ZSNWCA)。这两种线路结构实现了可逆门的种类和数量以及无用输出的最小化，最优化。大大降低了运算部件的运行功耗和设计成本。本发明适用于量子系统线路设计和应用。

Description

进位产生和传递函数发生器及可逆最优加法线路设计方法

技术领域

本发明涉及一种新型可逆“ZS”门的设计方法及应用，属于量子线路设计和优化技术领域。

背景技术

量子计算机是由包含连线和基本量子门排列起来、形成的处理量子信息的量子线路建造的。相对于经典电子计算机，量子计算机有许多诱人的优点：储存能力提高；计算过程可逆减少能耗；尤其在一些问题如大数的质因子分解和无序数据库搜索中，量子计算机可使所用时间大大缩短，有着经典电子计算机无法比拟的优越性。

在量子信息理论中，一个量子比特就是一个二维希尔伯特空间(Hilbert)，它的状态可以落在|0＞和|1＞之外，可表示为：|Ψ＞＝α|0＞+β|1＞，且|α|²+|β|²＝1。得到0的概率为|α|²，得到1的概率为|β|²，其中α、β为复数，代表可连续取值几率幅。α、β不同，则量子位储存的信息不同，所以一个量子比特位所能表示的信息量远多于一个经典比特位。n个经典比特位只能储存n个一位二进制数或者一个n位二进制数，而n个量子位却可以同时储存2ⁿ个n量子比特二进制数，储存能力提高了2ⁿ倍。

在量子信息理论中，对任意一个新的量子态的制备和操作都是通过对量子比特门的操纵来完成的。n量子比特门可以用相应的2ⁿ×2ⁿ的矩阵来表示，量子比特门的相应矩阵必须满足酉性，即U⁺U＝I，其中U⁺是U的共轭转置矩阵，I是2ⁿ×2ⁿ的单位阵。单量子比特门表示如附图1，其中U是一个2×2的酉矩阵，而相应的I应该是一个2×2得单位矩阵。例如量子非门和Hadamard门就分别对应着如下的两个2×2酉矩阵：

$\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$

$\frac{1}{\sqrt{2}}\left(\begin{array}{cc}1& 1\\ 1& -1\end{array}\right)$

若把单量子比特推广到多量子比特，则可以得到多量子比特量子逻辑门。多量子比特量子逻辑门的原型是受控非门(Controlled-NOT)这个门的线路图和对应的酉矩阵如图2所示。对于CNOT门，有两个输入量子比特，即|A＞和|B＞，分别称之为控制比特和目标比特。该门的作用可表述如下：当控制量子比特置1时，目标量子比特将反转它的状态；否则，目标量子比特保持状态不变。从而可总结该门的作用为：

其中

是模2加法，这也正是经典异或运算所做的，即CNOT门完成控制量子比特和目标量子比特的异或运算，并将计算结果存在目标量子比特当中。因此理论上，类似于经典计算机理论，任意多量子比特门都可以由CNOT门和单量子比特门复合而成。所以，从某种意义上说，CNOT门和单量子比特门是所有其他门的原型。

经典计算机当中，为了完成两个比特数的交换必须借助于第三方的操作才能够实现。而利用CNOT门则可以很简便地一次完成两个量子比特状态的兑换，这种交换门也是本发明的线路设计不可或缺的部件之一，其线路图如图3所示。在本发明中对于线路的设计都采用表示图和线路设计图两种形式，其中表示图只是简单的表达了该门所能完成的功能，而线路设计图则详细的说明了该门利用二量子比特和单量子比特门设计的过程。并且约定所有线路的读法是从左到右，每条线都表示量子线路的连线，并不一定对应物理上的连接线。该门是通过对控制量子比特和目标量子比特的一系列异或操作实现两个量子比特状态交换的，即：

$|A,B>\→|A,A\⊕B>\→|A\⊕(A\⊕B),A\⊕B>$

$\→|B,A\⊕B>\→|B,(A\⊕B)\⊕B>\→|B,A>$

同时，对于CNOT门若设置目标比特为0，则目标比特的输出与控制比特输入是一致的。即CNOT门还可以完成量子线路中扇出的功能。

比CNOT门具有更广泛意义的二量子比特门是受控-U门，记为CON-U门。量子线路图如图4所示。CON-U门实现的功能是：当控制比特A为0态时，目标量子位B将保持状态不变；当控制比特A为1态时，将对相应的目标量子位B实施幺正操作U。例如，当用非门X代替U门时，该CON-U即为前述的CNOT门。同样，当用V门(V是一个称为“Square-Root-of-Not”的幺正矩阵，即有V*V⁺＝I。对V的组合可以完成一个非门的作用，即V*V＝NOT)代替U门时，该CON-U即为另外一种比较常用的二量子比特受控门，简记为CV门。利用受控门和单量子比特门可以更加简单地完成任意比特的量子门操作。图5即为利用CV门和CNOT门完成三量子比特中应用广泛的Toffoli门的线路设计图。该门有三个输入比特和三个输出比特，其中两个控制比特不受Toffoli门作用的影响，第三个比特是目标比特，在控制比特都置1的情况下，目标比特才翻转。否则，目标比特保持不变。在图5中，对于右边线路当控制比特A＝1，B＝0时，V*V⁺＝I操作将作用到目标比特C上，使得目标比特保持原来状态不变。这与左边Toffoli线路的功能是相符的；当A＝1，B＝1时，V*V＝NOT操作将作用到目标比特C上，使得目标比特翻转原来状态。这也与左边Toffoli线路的功能是一样的。对于其余的情况可以类似验证。从而可以知道，利用CV门和CNOT门合成的线路与Toffoli门是等价的。

为了下文线路设计的需要，这里还将给出利用CV门和CNOT门合成另外一种重要的三量子比特门——Fredkin门的的线路设计图，如图6所示。类似于Toffoli门的验证方法，可以验证左边的Fredkin门线路和右边的利用CV门和CNOT门合成的线路是等价的。

发明内容

本发明的目的是，设计一种新的可逆逻辑门——“ZS”门，实现利用该门设计的量子全加法器和串行进位并行输出量子加法器的“代价”最小(“代价”指为完成一个量子操作而设计的线路的无用输出数量和种类，可逆逻辑门数量等)。同时，利用该门设计出一种“进位产生函数和传递函数发生器”(ZSGPD)，通过该装置的应用，大大减少了进位产生函数和进位传递函数生成的“代价”，而且利用该装置设计的“可逆最优化”(本发明定义使用可逆逻辑门数量和种类以及无用输出数量最少的线路为“可逆最优化”线路)无等待进位加法器克服了串行进位并行输出量子加法器的必须等待进位的缺点，大大降低了运算部件的运行功耗和设计成本。

实现本发明目的的指导思想是，本发明充分借鉴了经典电子线路设计中真值表的思想，将可逆逻辑中的幺正性与真值表联系起来，从而简便地设计出一种真值表输入输出一一对应的可逆逻辑门——“ZS”门。并且在设计中，充分应用级联的思想，将两个或两个以上的逻辑门级联在一起。这种级联的思想有着两个突出的优点：①级联的两个或多个门之间通过某个门的无用输出作为其他门的输入可以消除一些无用输出，降低线路的“代价”。②两个或多个门级联可以得到一些单个门无法实现的新的功能。

本发明的技术方案是，

本发明将量子计算机中可逆的含义与真值表输入输出一一对应联系在一起，设计一种真值表输入输出一一对应的可逆逻辑门-ZS门以及只含有双量子比特受控门和单量子比特门的量子线路图；

本发明根据ZS门的应用，设计一种“进位产生函数和传递函数产生装置”(ZSGPD)，实现了单个门以零无用输出产生多个进位传递函数；

本发明以“ZS”门为基础，设计了可逆最优化的两种加法线路结构，即量子全加法器(ZSQFA)和量子无等待进位加法器(ZSNWCA)。

本发明的具体设计方案和步骤为：

1、可逆“ZS”门的线路设计方案以及量子全加法器的实现

本发明将经典计算机的加法器设计思路应用到量子计算机中，将经典计算机中加法器的进位函数公式和和函数公式：

$C_{i+1}=a_i{b}_i+(a_i\⊕b_i)c_i$

$S_{i+1}=a_i\⊕b_i\⊕c_i---\left(1\right)$

变形为：

$C_{i+1}=a_i{b}_i+(a_i\⊕b_i)c_i$

$=a_i{b}_i+(a_i\stackrel{\‾}{b_i}+\stackrel{\‾}{a_i}{b}_i)c_i$

$=a_i{b}_i+a_i\stackrel{\‾}{b_i}{c}_i+\stackrel{\‾}{a_i}{b}_i{c}_i$

$=a_i{b}_i+a_i{c}_i+b_i{c}_i$

或可将C_i+1记为：

$C_{i+1}=a_i{b}_i\⊕a_i{c}_i\⊕b_i{c}_i$ (

表示异或操作)    (2)

利用以上和函数和进位函数公式(1)和(2)并充分考虑真值表的一一对应关系，本发明设计了新型可逆“ZS”门表示图如图7，并同时给出其相应的真值表。真值表中输入与输出的是一一对应的关系，给定输入可以确定其输出，同时给定输出可以得到其唯一的输入，从而可以验证该“ZS”门满足可逆的要求。

图8为本发明根据“ZS”门设计的含有双量子比特受控门和单量子比特门的该可逆门的量子线路图。

下面对该设计结构图各个模块进行说明：

(1)模块

模块

在线路1上得到输出

，此即为“ZS”门的1号线输出。

(2)模块

对于“ZS”门的4号线，做如下变形：

$d\⊕\mathrm{ab}\⊕\mathrm{ac}\⊕\mathrm{bc}=d\⊕\mathrm{ab}\⊕(a\⊕b)c$

模块

中运用了两个Toffoli门，其中第一个Toffoli门将a、b作为控制比特，将d作为目标比特，得到

的输出。而第二个Toffoli门则将和c作为控制比特，而将第一个Toffoli门输出

作为目标比特，得到最终“ZS”门的4号线输出

(2)模块

对于“ZS”门的3号线的输出|r＞＝|bcd+ad+ac＞，做简单的变形如下：

$b\stackrel{\‾}{\mathrm{cd}}+\mathrm{ad}+\mathrm{ac}=\stackrel{\‾}{\stackrel{\‾}{b\stackrel{\‾}{\mathrm{cd}}}}+a(c+d)=\stackrel{\‾}{\stackrel{\‾}{b}+c+d}+a(c+d)$

$=\stackrel{\‾}{\stackrel{\‾}{b}\⊕c\⊕d}\⊕a(c\⊕d)$

从而利用前面背景知识中受控非门设计的交换线路和单量子比特门中的非门可以设计出该部分，如图中模块

模块

通过两个受控非门的作用将

交换至2线，同时在3线得到输出从而结合Toffoli门的输入输出性质，将作为控制比特可以方便的得到线路3的输出。如图中模块

(3)模块

结合数字逻辑相关知识，对于模块

其前一个个受控非门的作用是将1号线，2号线的当前输出进行异或操作，得到输出结果为

将此输出结果与4号线输出进行受控非操作，如模块

的第二个受控非门，对此时的结果变形如下：

$d\⊕\mathrm{ab}\⊕(a\⊕b)c\⊕a\⊕b\⊕c\⊕d=\mathrm{ab}\⊕(a\⊕b)c\⊕a\⊕b\⊕c$

$=a\stackrel{\‾}{b}\⊕b\⊕c\⊕(a\⊕b)c=a\⊕b\⊕\left(\stackrel{\‾}{a\⊕b}\right)c$

$=a\⊕b\⊕c$

从以上分析可以看出，模块

得到的输出即为“ZS”门的2号线将所设计的zs门的第四输入置0，便可以得到量子全加法器。量子全加法器的表示图见图10，线路设计图只需将前设计的ZS门的4线路输入置为0即可。由此可见，给所述ZS门设置相应的输入，就可以以一个门完成量子全加法器的加法操作，降低了设计可逆线路的代价和运算的功耗。

利用所设计的一位量子全加法器串接，就可以实现位数大于1位的两个量子比特数相加的逻辑功能电路。如图11所示是4位串行进位并行输出加法器。这种连接方法，高一位相加的结果必须要等待低一位的相加结果是否产生进位才能确定。如果每个一位加法器延迟时间t，那么最高一位必须等待4t时间才能完成运算。这将直接影响运算速度。为了解决这一问题，本发明设计了一种“进位产生函数和传递函数发生器”(ZSGPD)，利用该装置成功实现“可逆最优化”，无需等待进位加法器从而克服了串行进位并行输出量子加法器的等待进位的缺点。ZSGPD的设置一次性完成了三个进位产生函数和进位传递函数，这种装置可以跳过进位使得多位加法的操作更加方便、快速，而且无需付出任何量子代价。

2、ZSGPD的线路设计方案以及量子无等待进位加法器的实现

对于表达式(1)和(2)，做如下变化，设置进位传递函数P_i和进位产生函数G_i，则：

$S_{i+1}=a_i\⊕b_i\⊕c_i$

$=P_i\⊕c_i---\left(3\right)$

$C_{i+1}=a_i{b}_i+(a_i\⊕b_i)c_i$

$=G_i\⊕P_i{c}_i---\left(4\right)$

其中 $P_i=a_i\⊕b_i$

G_i＝a_ib_i

从而通过(3)和(4)式的变换，可以得到：

$c_1=G_0\⊕P_0{c}_0$

$c_2=G_1\⊕P_1{c}_1=G_1\⊕P_1(G_0\⊕P_0{c}_0)$

$=G_1\⊕P_1{G}_0\⊕P_1{P}_0{c}_0$

$c_3=G_2\⊕P_2{c}_2=G_2\⊕P_2(G_1\⊕P_1{G}_0\⊕P_1{P}_0{c}_0)$

$=G_2\⊕P_2{G}_1\⊕P_2{P}_1{G}_0\⊕P_2{P}_1{P}_0{c}_0$

$c_4=G_3\⊕P_3{c}_3=G_3\⊕P_3(G_2\⊕P_2{G}_1\⊕P_2{P}_1{G}_0\⊕P_2{P}_1{P}_0{c}_0)$

$=G_3\⊕P_3{G}_2\⊕P_3{P}_2{G}_1\⊕P_3{P}_2{P}_1{G}_0\⊕P_3{P}_2{P}_1{P}_0{c}_0)$

.....

.....

$S_0=P_0\⊕c_0$

$S_1=P_1\⊕c_1=P_1\⊕G_0\⊕P_0{c}_0$

$S_2=P_2\⊕c_2=P_2\⊕G_1\⊕P_1{G}_0\⊕P_1{P}_0{c}_0$

$S_3=P_3\⊕c_3=P_3\⊕G_2\⊕P_2{G}_1\⊕P_2{P}_1{G}_0\⊕P_2{P}_1{P}_0{c}_0$

通过以上的变换，可以发现通过进位传递和进位产生函数的设置，高一位相加的结果不再需要要等待低一位的相加是否产生进位，而是直接由最低位的进位输入来确定，同时从和函数的迭代中可以发现：和函数的输出只与进位产生函数和进位传递函数和最低位进位有关即只与P_i，G_i，c₀。这样，无需等待高位进位就可以实现量子比特的加法，大大减少了门的数量和门与门之间延迟。基于以上原因，对“ZS”门做如图12的变换，构造“进位产生函数和传递函数发生器”(ZSGPD)。相应的图13为线路设计图。该装置充分考虑“可逆最优化”的标准实现了单个门以零无用输出生产出多个超前进位传递函数，而无需借助其他可逆门。

所述量子无等待进位加法器(ZSNWCA)中为了完成和函数，引入了完成线路复制功能的FG门和产生和函数表达式中“与”操作的F门。

利用ZSGPD，构造量子无等待进位加法器表示图如图14，其中F门即为背景知识中所述的Fredkin门，而FG门所完成的功能与CNOT门实质上是一样的。

本发明与现有技术比较的有益效果是，量子线路的可逆限制必然会导致无用输出的产生，本发明与现有的关于可逆加法器设计的结构相比，将量子代价降到最低，是现有的可逆加法器设计中较优的一种。可逆计算在量子计算、光学计算、纳米技术等多个领域都有着广泛的应用。而本发明所设计的“ZS”门以及由此生成的相关电路正是在可逆计算领域的一些尝试，这些尝试对于设计更加复杂而优化的量子系统，如量子CPU的运算部件和逻辑部件来说，将会是一个促进作用。

本发明所设计的“ZS”门以及由此生成“进位产生函数和传递函数发生器”(ZSGPD)，实现了单个门以零无用输出产生多个进位传递函数。并以该门为基础，设计了可逆最优化的两种加法线路结构——量子全加法器(ZSQFA)和量子无等待进位加法器(ZSNWCA)。这两种线路结构使得实现加法操作所需的可逆门的种类和数量以及无用输出都达到最优。大大降低了运算部件的运行功耗和设计成本。

本发明适用于量子系统线路设计和应用。

附图说明

图1单量子比特门表示图

图2受控非门表示图及其相应的幺正矩阵

图3交换门线路设计图

图4受控-U门表示图

图5Toffoli门线路设计图

图6Fredkin门线路设计图

图7ZS门表示图及其相应的真值表

图8含有双量子比特受控门和单量子比特门的可逆门量子线路

图9变形Toffoli门线路设计图

图10由“ZS”门设计的量子全加法器

图114位串行进位并行输出的量子加法器

图12ZSGPD表示图

图13ZSGPD线路设计图

图14ZSNWCA表示图

具体实施方式

本发明具体实施方式如下：

本发明设计的新型可逆“ZS”门表示图如图7所示，并同时给出其相应的真值表。真值表中输入与输出的是一一对应的关系，给定输入可以确定其输出，同时给定输出可以得到其唯一的输入，可以验证该“ZS”门满足可逆的要求。

本发明根据“ZS”门设计的含有双量子比特受控门和单量子比特门的该可逆门的量子线路图如图8所示，图中均为构成“ZS”门所需要的模块，1、2、3、4分别表示“ZS”门的1号、2号、3号和4号线路输出。

模块

主要完成1号线路的输出，即 $|p>=|a\⊕b>;$

模块

主要完成4号线路输出，即 $|s>=|d\⊕\mathrm{ab}\⊕\mathrm{ac}\⊕\mathrm{bc}>;$

模块

为完成2号和3号线输出，充分结合数字逻辑知识，将“ZS”门的2号和3号线输出变形为可以用单量子比特逻辑门和双量子比特受控门设计实现的表达式，从而方便的设计出“ZS”门的2号和3号线输出

将所设计的“ZS”门的第四输入置0，便可以得到量子全加法器。量子全加法器的表示图见图10，线路设计图只需将前设计的“ZS”门的4号线路输入置为0即可。由此可见，给所述“ZS”门设置相应的输入，就可以以一个门完成量子全加法器的加法操作，降低了设计可逆线路的代价和运算的功耗。

本发明设计的“进位产生函数和传递函数发生器”(ZSGPD)如图12所示，利用该装置成功实现“可逆最优化”，无需等待进位加法器从而克服了串行进位并行输出量子加法器的等待进位的缺点。ZSGPD的设置一次性完成了三个进位产生函数和进位传递函数，这种装置可以跳过进位使得多位加法的操作更加方便、快速，而且无需付出任何“代价”。

图13为进位产生函数和传递函数发生器线路设计图，它是从“ZS”门经过变换，构造成“进位产生函数和传递函数发生器”(ZSGPD)。该装置充分考虑“可逆最优化”的标准，实现了单个门以零无用输出生产出多个超前进位传递函数，而无需借助其他可逆门。

所述量子无等待进位加法器(ZSNWCA)中为了完成和函数，引入了完成线路复制功能的FG门和产生和函数表达式中“与”操作的F门。

利用ZSGPD，构造量子无等待进位加法器表示图如图14所示，其中F门即为背景知识中所述的Fredkin门，而FG门所完成的功能与CNOT门实质上是一样的。

Claims (4)

1.一种进位产生和传递函数发生器及可逆最优加法线路设计方法，其特征在于，

所述方法将量子计算机中可逆的含义与真值表输入输出一一对应联系在一起，设计一种真值表输入输出一一对应的可逆逻辑门一“ZS”门以及只含有双量子比特受控门和单量子比特门的量子线路图；

所述方法根据“ZS”门，设计一种进位产生函数和传递函数产生装置(ZSGPD)，实现了单个可逆门以零无用输出产生多个进位传递函数；

所述方法以“ZS”门为基础，设计可逆最优化的两种加法线路结构，即量子全加法器(ZSQFA)和量子无等待进位加法器(ZSNWCA)。

2.根据权利要求1所述的进位产生和传递函数发生器及可逆最优加法线路设计方法，其特征在于，给所述ZS门设置相应的输入，就可以以一个可逆门完成量子全加法器的加法操作。

3.根据权利要求1所述的进位产生和传递函数发生器及可逆最优加法线路设计方法，其特征在于，所述ZSGPD的设置一次性完成了三个进位产生函数和进位传递函数。

4.根据权利要求1所述的进位产生和传递函数发生器及可逆最优加法线路设计方法，其特征在于，所述量子无等待进位加法器(ZSNWCA)中为了完成和函数，引入了完成线路复制功能的FG门和产生和函数表达式中“与”操作的F门。

Images