基于矩阵初等变换的量子可逆逻辑电路双向综合算法

基于矩阵初等变换,提出了量子可逆逻辑电路双向综合算法。该算法依据两数字间的汉明距离,通过交换矩阵行号或矩阵元素对量子可逆逻辑电路的矩阵进行初等行变换。在变换的过程中,利用邻接矩阵的电路转化规则,生成任意给定置换的量子可逆逻辑电路。与其它同类算法相比,由于不需要穷尽搜索,该算法的时空复杂度有大幅降低;又由于采用任意n量子扩展通用Toffoli门,该算法可综合任一置换(奇或偶置换)的量子可逆逻辑电路,并且电路中门的数量有所减少。     

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

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

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

量子可逆逻辑电路是构建量子计算机的基本单元.本文结合可逆逻辑电路综合的多种算法,根据可逆逻辑电路综合的本质是置换问题,巧妙应用位运算构造高效完备的Hash函数,提出了基于Hash表的新颖高效的量子可逆逻辑电路综合算法,可使用多种量子门,以极高的效率生成最优的量子可逆逻辑电路,从理论上实现制造量子电路的成本最低.按照国际同行认可的3变量可逆函数测试标准,该算法不仅能够生成全部最优电路,而且运行速度远远超过其它算法.实验结果表明,该算法按最小长度标准综合电路的平均速度是目前最好结果的69.8倍.     

类选择排序的可逆逻辑综合算法

可逆逻辑综合是指对给定的可逆函数自动构造对应的可逆逻辑电路.由于搜索空间随电路规模增长成指数增长,现有的可逆逻辑综合算法虽然能够得到近似最优的解,但是都存在计算时间过长的问题.文中提出了一种类似选择排序的可逆逻辑综合算法,其实质为基于变换规则的合成法.它采用一个无向无权图表示所有可以进行变换的路径,在综合的过程中,采用选择排序思想每次从小到大的选择需要交换的输出项,然后从路径选择图中找到最优的路径进行变换,最终使得函数的输出序列有序即完成综合.此外,文中还对得到的量子电路进行了优化.实验表明,相比其它综合算法,该算法不仅总能获得最优解或近似最优解,而且效率高、易于实现.     

基于规则的可逆Toffoli电路优化算法

可逆电路的优化是可逆逻辑综合的关键问题之一.为了解决可逆Toffoli电路优化问题中算法复杂度高和电路规模可扩充性差的问题,分析归纳了相邻Toffoli门的关系,提出并证明了可逆Toffoli电路中子序列的移动和化简规则,并基于这些规则给出了可逆Toffoli电路的优化算法.根据移动规则对可逆电路进行正向和反向扫描,寻找满足化简规则的子序列进行优化,直到可逆电路不发生变化为止.该优化算法与可逆电路的输入线数无关,无需存储额外信息,适用于各种不同类型的Toffoli电路合成方法,算法复杂度为O(s3),优于通常使用的模板优化的复杂度O(n!t2s3).在具体实例和国际认可的所有3变量可逆函数上的验证结果表明,该优化算法能有效地减少可逆电路的门数和控制位数,降低可逆电路的代价.     

量子可逆逻辑电路自动合成的方法研究

研究量子可逆逻辑电路优化设计问题,提出一种量子可逆逻辑电路自动合成的方法.可使用“图”的结构来对量子可逆逻辑电路进行编码,并且专门设计了几种变异操作算子来直接修改“图”的结构,并实现了利用“图”编码的克隆选择,最终完成了量子可逆逻辑电路的自动合成.实验结果表明所提出的量子可逆逻辑电路自动合成的方法是可行的,具有较高的合成效率,能够以较快的收敛速度获取所需合成的量子可逆逻辑电路的的最优解.     

混合多值可逆逻辑中广义Toffoli门仅用CNOT门的实现

混合多值量子可逆逻辑电路综合问题中,Toffoli门的合成是整个合成过程中最为关键的一步。针对混合多值5-qubits量子可逆逻辑电路综合问题,构造了PMX量子门,验证了CNOT门的合成能力,实现了对Toffoli门的合成,并设计了双向的BDS搜索算法,高效实现了量子电路的最优或者较优综合。     

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

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

一种量子可逆逻辑模板综合算法

模板技术是量子可逆逻辑优化的一个重要手段,其优化程度依赖于模板的完备性.采用遗传算法作为全局搜索工具,提出了一个基于遗传算法的量子可逆逻辑模板综合算法.实验表明,该算法能有效生成新的模板线路,扩充了现有的模板库,提高了优化效率.     

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

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

Evolutionary Approach to Quantum and Reversible Circuits Synthesis

The paper discusses theevolutionary computation approach to theproblem of optimal synthesis of Quantum andReversible Logic circuits. Our approach usesstandard Genetic Algorithm (GA) and itsrelative power as compared to previousapproaches comes from the encoding and theformulation of the cost and fitness functionsfor quantum circuits synthesis. We analyze newoperators and their role in synthesis andoptimization processes. Cost and fitnessfunctions for Reversible Circuit synthesis areintroduced as well as local optimizingtransformations. It is also shown that ourapproach can be used alternatively forsynthesis of either reversible or quantumcircuits without a major change in thealgorithm. Results are illustrated onsynthesized Margolus, Toffoli, Fredkin andother gates and Entanglement Circuits. This isfor the first time that several variants ofthese gates have been automatically synthesizedfrom quantum primitives.     

可逆电路的符号综合方法

描述一种基于矩阵模型和符号代数理论的可逆电路的综合方法,其中考虑到面积、时延、串扰等约束.实验结果已清楚地表明了利用这种启发式算法与现有的综合方法相比,在面积上所得结果近似,而总串扰得到了明显的改善.并且其路径时延要减少5%到20%之多.这种综合方法大大的改善了电路的性能,并且对输入输出较多的可逆电路的综合具有潜在的优势.     

Six Synthesis Methods for Reversible Logic

The (2 ^w )! reversible transformations on w wires, i.e. reversible logic circuits with w inputs and w outputs, together with the action of cascading, form a group, isomorphic to the symmetric group S ₂ ^w . Therefore, we investigate the group S _n as well as one of its subgroups isomorphic to S _n/2 × S _n/2. We then consider the left cosets, the right cosets, and the double cosets generated by the subgroup. Each element of a coset can function as the representative of the coset. The coset can then be considered as the set of all group elements that differ from the representative by merely multiplying (either to the left or to the right or to both sides) by an arbitrary element of the subgroup. Different choices of the coset space and different choices of the coset representatives lead to six different syntheses for implementing an arbitrary reversible logic operation into hardware. Evaluation of all six methods, by means of three different cost functions (gate cost, switch cost, and quantum cost), leads to a best choice.     

大电路固定极性Reed-Muller逻辑快速转换算法

针对已有的列表技术在极性转换中只能解决中小规模电路的问题,提出一种基于不相交乘积项列表技术的快速转换算法.首先将待处理的逻辑函数表示为不相交乘积项之和形式;然后通过对已有的基于最大项的列表技术进行分析和改进,使得改进后的列表技术可以实现将逻辑函数从不相交乘积项的AND?OR形式向固定极性XNOR?OR形式的Reed-Muller逻辑转化.文中算法用C编程实现,并用MCNC标准电路进行测试.实验结果表明,该算法可以快速实现大电路的极性转换,并且具有运算速度对电路的输入变量数不敏感的特点.     

基于免疫原理的逻辑电路设计算法

硬件进化是基于进化计算和可重构硬件的新兴研究领域。逻辑电路的进化设计是硬件进化的主要研究方向之一。文章将生物免疫系统的进化非选择机制引入到逻辑电路设计中,提出了相应的逻辑电路设计算法,并给出了该文算法和进化算法的对比实验结果,结果表明该文算法更加有效。     

快速启发式ESOP电路面积优化算法

针对积之异或和(ESOP)电路面积优化的时间效率问题,提出一种快速的启发式算法.该算法使用多输出立方体表示乘积项,首先由基于伪Kronecker判决图的方法得到初始ESOP覆盖,然后使用启发式局部极性转换与局部变换交替迭代的方式进行面积优化.为提高算法效率,启发式局部极性转换仅尝试改变立方体中单个变量的极性,并且仅接受对减少电路面积有帮助的极性转换,该转换有助于使优化过程跳出局部极小;局部变换则通过对ESOP覆盖中距离为1或2的立方体进行变形来减少电路面积,该变换有助于算法的收敛.实验结果表明,文中算法能够适用于具有较多输入变量的多输出电路;与MPRM电路相比,ESOP电路能够降低电路面积开销;与其他ESOP电路优化算法相比,该算法能够显著改善面积优化的时间效率.