量子可逆逻辑综合的关键技术及其算法

最优化量子可逆逻辑的关键在于用最小的量子代价自动构造量子可逆逻辑.为了提高可逆逻辑自动生成与优化的效率,提出了类模板技术和一种快速算法.模板技术是一个有效的优化工具,类模板技术可以显著提高模板技术的匹配效率;R-M算法是可逆逻辑综合的一种较好的迭代方法,基于R-M算法的原始思想,构造了一个Hash函数,并在此基础上提出了一种可逆逻辑综合的快速算法.实验结果表明,在同等实验环境下使用类模板技术与快速算法,其优化的效果与效率远远优于已知的其他算法.

基于协同多目标差分进化的可逆逻辑综合方法

可逆逻辑电路可避免因信息丢失而产生的热耗散,从而有望解决集成电路热耗问题.将可逆逻辑电路设计问题抽象为带有强约束的多目标优化问题,提出以协同多目标差分进化算法为核心的可逆逻辑综合方法.该方法基于种群自适应调节的差分进化算法,结合协同进化的多种群策略优化多目标,经种群选择及自适应调节策略和Paroto最优评估评价更新候选个体.通过求解经典电路测试集,验证了所提方法的可行性及有效性.与经典及基于启发式算法的可逆逻辑综合方法相比,该方法生成的电路性能更优.

紧凑型纳米薄膜铌酸锂复合波导光电子可逆逻辑门

基于纳米薄膜铌酸锂与氮化硅复合波导结构,构建了光电子可逆逻辑门,应用于神经形态光子学和量子计算。该光电子可逆逻辑门的主体由两个马赫-曾德尔调制器级联而成,结构紧凑,全长仅为4.4 mm,是普通质子交换铌酸锂调制器长度的百分之一。工作在1.55μm波长时,该马赫-曾德尔调制器仅需4.9 V电压就可以实现一次完整的功率交换,很好地与CMOS工艺相兼容。器件特性研究表明,该光电子可逆逻辑门能够实现可逆逻辑运算功能。此外,该器件在1.4~1.6μm波长范围内,插入损耗均值为0.6 dB,输出端口的最小串扰为-47 dB,消光比的最大值为41 dB;在4~6 V电压范围内,插入损耗均值为0.63 dB,输出端口的最小串扰为-26 dB,消光比的最大值为22 dB,显示出了良好的响应特性。

可逆逻辑门网络的表示与级联

可逆计算是一个新兴的研究领域,可逆逻辑门网络的级联是可逆计算的重要内容.本文提出了一种可逆逻辑网络表示方法,给出了相应的可逆网络模型.为了构造可逆逻辑网络,给出了一种可逆逻辑门单元库的构造方法.证明了同一垂直线上两个不相交可逆逻辑门单元的输出值与此二逻辑门单元分布到相同平行线的两条相邻垂直线上的输出值之间的关系;给出了分布在相同平行线上奇数和偶数个相邻的相同可逆逻辑门单元输出结果的性质.提出了一种可逆网络输出向量的表示方法和基于可逆门编码的可逆网络级联方法,以此生成给定范围内的可逆网络.通过变进制数的方法快速找到可逆网络输出向量所对应的序号,降低了搜索次数,减小了搜索空间,为进一步综合大规模可逆网络,提高可逆网络级联效率提供了支持.Benchmark例题验证表明,该方法构造的可逆网络控制门数更少,代价更小.

基于遗传算法的可逆逻辑综合方法及其CUDA并行化实现

提出和实现了一种基于遗传算法和CUDA(Compute Unified Device Architecture)技术的可逆逻辑并行综合方法.其特点是预先求出并存储可逆逻辑门的组态编码和真值表,通过可逆逻辑门的"定轨级联"构成染色体暨可逆逻辑电路,在迭代中按照预期的逻辑功能和优化目标等部分并行地评估适应度,再利用选择、交叉、变异等部分并行化遗传操作,逐步找到功能正确、性能优化的可逆逻辑电路.实验结果证明了该方法的可行性、有效性,及其与同类传统方法相比在运算速度、求解能力等方面的显著改进.

基于NCV门库的可逆逻辑门进化设计与优化

提出和实现了一种基于遗传算法的可逆逻辑门的设计方法。其特点是预先求出并存储所需功能的可逆逻辑门的真值表,并对NCV基本门库中的控制V门,控制V+门,控制非门,非门进行编码,通过这些基本门的级联,构成染色体暨可逆逻辑门,在逐代进化中按照既定逻辑功能和优化目标进行适应度评估,再利用遗传换代中的选择,交叉,变异等功能进行遗传操作,进而找到功能和性能均符合预定目标的可逆逻辑门。实验结果证明,此方法的可行性、有效性,与传统手工设计可逆逻辑门相比,其在求解速度和能力方面有显著提高。

基于最小混乱度的三值可逆逻辑综合算法

三值可逆逻辑综合是可逆逻辑综合的延伸和扩展.为了简化可逆网络,提高三值可逆逻辑门的通用性,对现有三值可逆控制门控制位的生效值扩展为0、1和2.在此基础上提出了基于最小混乱度原则的三值可逆逻辑综合算法.该算法根据三值可逆函数计算其对应真值表中每个变量的相对混乱度和绝对混乱度,以最小混乱度原则选取三值可逆逻辑门,直至真值表中的每个变量的混乱度为零,得到三值可逆网络.该算法的时间复杂度为O(n2×3n),空间复杂度为O(n×3n).实验结果表明,与现有已知算法对比,平均门数更少.

可逆逻辑表达式的识别和图示方法

可逆逻辑电路是仅包含可逆运算的新型电路,还可根除源于信息损失的能耗和发热,是研究与实现超低功耗集成电路、量子计算机及信息安全等的关键基础。文中针对可逆逻辑电路研究的需要,研究了通过识别可逆逻辑表达式提取可逆逻辑电路结构信息,并加以图形化显示的有效方法和可行算法,以便更形象、直观地表达可逆逻辑电路综合、优化的结果,进而为分析、理解和优化可逆逻辑电路提供方便。

四量子可逆逻辑电路快速综合算法

量子可逆逻辑电路综合是以较小量子代价自动构造所求量子可逆逻辑电路.本文提出了一种新颖高效的4量子电路综合算法,巧妙构造置换的最短编码,通过对量子电路进行特定拓扑变换,无损压缩n量子最优电路占用内存空间近2×n!倍,通过对已生成最优电路的双向级联,可使用多种量子门,采用最小长度标准,以极高效率生成较长的4量子电路,如率先生成基于控制非门、非门、Toffoli门库的全部前8层共3120218828个电路,还可快速综合任意长度不超过16的最优电路,并对4量子标准测试电路进行快速且全面的优化.

基于正反控制模型的可逆逻辑综合

对一般Toffoli门进行了衍变和推广,给出了一个正反控制可逆级联模型(PNCRC),该模型拥有五种基本线型,并能正反控制目标位的输出.基于该模型给出了相应的可逆综合算法.对输入数不大于16的NCMCBench-mark函数进行测试并与已有的可逆综合方法比较,结果表明,利用该模型进行的可逆综合,垃圾信息数和可逆门数的优化效果都具有一定程度的改善.

基于矩阵编码的量子可逆逻辑电路进化设计方法

本文研究基于遗传算法的量子可逆逻辑电路综合技术,能实现可逆逻辑电路功能、量子门数、垃圾位数和量子代价的多目标优化设计.建立了量子可逆逻辑电路综合数学模型,采用了量子可逆逻辑电路矩阵编码方案,设计了量子可逆逻辑电路进化操作算子,给出了量子可逆逻辑电路多目标进化设计算法.以8位量子可逆乘法器为设计实例,实验结果证明了所提出的量子可逆逻辑电路多目标进化设计方法是正确有效的.

基于汉明距离递减变换的可逆逻辑综合算法

可逆逻辑综合是指对给定的可逆函数自动构造对应的可逆逻辑电路.现有的可逆逻辑综合算法虽然通过后期优化能够得到近似最优解,但是都存在生成的原始电路门数较多的问题,增加了后期优化工作的难度.文中提出一种基于真值表异位数计算的综合方法,根据异位数判定是否需增加逻辑非门达到减少输入和输出向量的汉明距离,从而实现边计算边简化函数,最后采用汉明距离递减变换的方法生成最终的电路.通过实验表明,相比于其他的综合算法,该算法得到的原始电路更接近于最优解或近似最优解,很大程度上减少了算法后续的优化工作量.

量子可逆逻辑电路综合的快速算法研究

可逆逻辑有许多应用,尤其在量子计算领域,量子可逆逻辑电路是构建量子计算机的基本单元,量子可逆逻辑电路综合就是根据电路功能,以较小的量子代价自动构造量子可逆逻辑电路.文中结合可逆逻辑电路综合的多种算法,提出了一种新颖高效的算法,自动构造正极性Reed-Muller展开式(RM),在生成量子可逆逻辑电路的解空间树上,采用总体层次遍历,局部深度搜索,借鉴模板优化技术,构造限界函数快速剪去无解或非最优解的分枝,优先探测RM中的因子,以极高的效率生成最优电路.以国际公认的3变量可逆函数测试标准,该算法不仅能够生成全部最优电路,而且运行速度远远超过同类算法.

非可逆逻辑门的量子可逆实现研究

经典的逻辑关系可以使用逻辑函数加以表示,通过类比可以定义量子逻辑函数。然而量子逻辑门实现的都是幺正变换,从而是可逆变换,非可逆变换不能直接实现。通过添加辅助量子位可以增添量子输出信号的区分位,完成对非可逆逻辑门的改造,使得非可逆逻辑门在量子逻辑电路中得到可逆实现。具体研究了或门、与非门以及或非门等常见的逻辑门的改造方法。以丢失部分量子信息为代价来改造量子逻辑电路,并给出了可以实现的优化后的量子逻辑电路。

综合法研究量子可逆逻辑电路

量子可逆逻辑电路优化与综合主要研究在给定的量子门和量子电路的约束条件下,找到最小或较小的量子代价电路以实现所需电路逻辑功能。量子逻辑真值表综合法是量子电路可逆逻辑综合中最有效的方法之一,包括正向综合、逆向综合和双向综合。推广和定义了横向汉明距离、纵向汉明距离和交叉汉明距离,使用广义汉明距离提出了一种量子电路优化与综合的新方法。研究表明,此方法使量子逻辑电路得到了更好的优化。

基于二分法量子可逆逻辑电路综合

为了能以较小的代价自动高效地构造量子可逆逻辑电路,提出了一种新颖的量子可逆逻辑电路综合方法.该方法通过线拓扑变换和对换演算,利用递归思想,将n量子电路综合问题转换成单量子电路综合问题,从而完成电路综合,经过局部优化生成最终电路.该算法综合出全部的3变量可逆函数,未优化时平均需6.41个EGT门,优化后平均只需5.22个EGT门;理论分析表明,综合n量子电路最多只需要n2n-1个EGT门.与同类算法相比,综合电路所用可逆门的数量大幅减少.同时该算法还避免了时空复杂度太大的问题,便于经典计算机实现.

基于真值表变换的可逆逻辑综合算法

为实现将给定的二元可逆函数快速综合为相应电路,并保持其结果的最优或较优,提出一种基于真值表变换的快速综合算法.可逆函数与置换同构,任意置换均可表示为若干对换的乘积,通过将可逆函数转化为一系列对换的乘积,从对换的乘积中综合电路.对于3bit逻辑电路只有28种对换,事先将28种对换的最优电路存入库中生成3bit电路综合基,通过在库中查找快速生成可逆电路.根据逻辑门可交换规则引入优化方法,完成快速综合算法.结果表明,该方法不但可以提高可逆逻辑综合的效率,而且结构简单,易于实现,可以O(4n)的时间效率快速综合任意3bit可逆逻辑电路,实现综合结果达到或接近最优.

基于Hash表的量子可逆逻辑电路综合的快速算法

量子可逆逻辑电路是构建量子计算机的基本单元,通过量子门的级联与组合构成量子计算机,量子可逆逻辑电路的综合就是根据电路功能,以较小的量子代价自动构造量子可逆逻辑电路.结合可逆逻辑电路综合的多种算法,提出了一种新颖高效的量子电路综合算法,巧妙构造最小完备的Hash函数,可使用多种量子门,采用任意量子代价标准,以极高的效率生成最优的量子可逆逻辑电路.为实现量子电路综合的自动化,首次提出了利用量子线的置换自动构造各种量子门库的通用算法.采用国际同行认可的3变量可逆函数测试标准,该算法不仅能够生成全部最优电路,而且运行速度远远超过其他算法.实验结果表明,该算法按最小长度、最小代价标准综合电路的平均速度分别是目前最好结果的491.5倍、365.13倍.

量子电路可逆逻辑综合的研究及进展

分析了量子电路可逆逻辑综合的意义、研究现状和研究进展,给出了相关的研究方法和目前量子可逆逻辑综合研究中存在的主要问题,提出了量子可逆逻辑综合中的最小量子代价、最小化垃圾信息位、最小化门的数量和可逆逻辑综合的规模等关键技术问题的解决思路。

量子可逆逻辑电路在线错误检测方法

针对现有的量子可逆逻辑电路在线错误检测方法均存在个别输出位错误无法检测的问题,提出了一种基于容错门的量子可逆逻辑电路在线错误检测方法,该方法对电路输入进行复制,将待测电路分层并将所有非容错门封装成对应的容错门,利用构建电路的奇偶保持特性在线检测电路输出错误。并基于汉明码技术,设计量子可逆逻辑电路实现数据传输错误的检测与自动纠正。选取多种典型量子可逆逻辑电路进行分析验证,结果表明,本方法能够在线检测电路所有单个位输出错误,并且随着电路规模增加,可逆逻辑门、垃圾位和电路中错误点的数量明显减少。