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

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

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

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

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

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

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

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

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

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

基于关联选择的可逆逻辑综合算法

可逆逻辑综合是可逆计算的重要内容,为了解决可逆逻辑综合中可逆电路构造和优化问题,提出一种基于关联选择的可逆逻辑综合算法及相应的优化算法.将可逆函数用真值表表示,按真值表从上往下的顺序综合,并若干相关联变量作为综合的目标位,分别计算相对混乱度和绝对混乱度,以最小混乱度原则选取可逆逻辑门.该算法及其优化算法的时间复杂度为O(n2×2n),空间复杂度为O(n×2n),优于最佳算法的空间复杂度O(2n!).通过C++语言实现对3变量全部函数及部分4变量函数的综合,并与其他可逆逻辑综合算法的结果及benchmark范例比较,结果表明平均门数均具有一定优势.     

基于控制K次平方根非门的类Toffoli门构造方法

在量子电路综合算法中,由于非置换量子门比置换量子门具有更复杂的规则,直接使用非置换量子门会大幅度提高综合算法的复杂性,因此可先使用非置换量子门生成相应的置换量子门,然后再用这些置换量子门综合所求量子可逆逻辑电路,从而提高算法性能。本文重点研究如何用非置换量子门构造新的置换量子门,为此吸收了格雷码的思想,提出了一种高效的递归构造方法,实现使用控制非门和控制K次平方根非门(非置换量子门),快速生成最优的类Toffoli门(置换量子门)。     

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

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

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

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

基于卡诺图的三变量可逆逻辑综合算法

提出了一种基于卡诺图的可逆逻辑综合算法,该算法可以快速地求解带垃圾位的可逆逻辑综合问题。大量特定的可逆逻辑门都不可避免地带有一定的垃圾位, 如果使用真值表、置换群等经典可逆逻辑综合算法求解这些带垃圾位的可逆逻辑门,则因无法获得全局状态而很难得到结果。根据卡诺图的特点,将可逆逻辑问题分解为多个变量分别求解,无需关心全局状态。提出的卡诺图可逆逻辑综合算法 根据在卡诺图上的邻接性将3变量可逆逻辑问题划分为5个等价类;对每个等价类分别进行计算,在常数时间内解决了带垃圾位的可逆逻辑综合问题。     

Optimization of Quantum Cost for Low Energy Reversible Signed/Unsigned Multiplier Using Urdhva-Tiryakbhyam Sutra

One of the elementary operations in computing systems is multiplication. Therefore, high-speed and low-power multipliers design is mandatory for efficient computing systems. In designing low-energy dissipation circuits, reversible logic is more efficient than irreversible logic circuits but at the cost of higher complexity. This paper introduces an efficient signed/unsigned 4 × 4 reversible Vedic multiplier with minimum quantum cost. The Vedic multiplier is considered fast as it generates all partial product and their sum in one step. This paper proposes two reversible Vedic multipliers with optimized quantum cost and garbage output. First, the unsigned Vedic multiplier is designed based on the Urdhava Tiryakbhyam (UT) Sutra. This multiplier consists of bitwise multiplication and adder compressors. Compared with Vedic multipliers in the literature, the proposed design has a quantum cost of 111 with a reduction of 94% compared to the previous design. It has a garbage output of 30 with optimization of the best-compared design. Second, the proposed unsigned multiplier is expanded to allow the multiplication of signed numbers as well as unsigned numbers. Two signed Vedic multipliers are presented with the aim of obtaining more optimization in performance parameters. DesignI has separate binary two’s complement (B2C) and MUX circuits, while DesignII combines binary two’s complement and MUX circuits in one circuit. DesignI shows the lowest quantum cost, 231, regarding state-of-the-art. DesignII has a quantum cost of 199, reducing to 86.14% of DesignI. The functionality of the proposed multiplier is simulated and verified using XILINX ISE 14.2.     

Heuristic methods to use <Emphasis Type="Italic">don’t cares</Emphasis> in automated design of reversible and quantum logic circuits

This paper introduces a broad concept of don’t cares in reversible and quantum logic circuits. Don’t cares are classified into three categories: inputs, outputs, and conditions. Some heuristic methods to use these don’t cares, when an optimization algorithm such as genetic algorithm is used, are also presented. We show that, these methods decrease the quantum cost of the reversible or quantum logic circuit, as well as the design time of the resulting circuit. Some examples are also synthesized and optimized using the don’t care concept and genetic algorithms.      

基于扫描D触发器的可逆电路测试综合方法

为了实现可逆逻辑电路的可测性设计,充分利用可逆逻辑电路中存在的输出引脚,提出一种可逆逻辑电路测试综合方法.通过定义可逆逻辑门的可观性值和可控性值的计算方法,对可逆逻辑电路的可测性进行建模;通过插入观察点,制定了可逆组合逻辑电路可测性实现方案;通过对现有的D触发器进行改造并构建全新的扫描D触发器,制定了可逆时序电路的可测性逻辑实现方案;最后分析了扫描D触发器的工作特点,规范了测试步骤,建立一种可逆逻辑电路的测试综合方法.实验结果表明,与现有方法相比,文中方法插入观察点代价平均增加不到1%,但电路的可观性平均能得到24%的改善.     

An efficient and fast polarity optimization approach for mixed polarity Reed-Muller logic circuits

Although the genetic algorithm has been widely used in the polarity optimization of mixed polarity Reed-Muller (MPRM) logic circuits, few studies have taken into account the polarity conversion sequence. In order to improve the efficiency of polarity optimization of MPRM logic circuits, we propose an efficient and fast polarity optimization approach (FPOA) considering the polarity conversion sequence. The main idea behind the FPOA is that, firstly, the best polarity conversion sequence of the polarity set waiting for evaluation is obtained by using the proposed hybrid genetic algorithm (HGA); secondly, each of polarity in the polarity set is converted according to the best polarity conversion sequence obtained by HGA. Our proposed FPOA is implemented in C and a comparative analysis has been presented for MCNC benchmark circuits. The experimental results show that for the circuits with more variables, the FPOA is highly effective in improving the efficiency of polarity optimization of MPRM logic circuits compared with the traditional polarity optimization approach which neglects the polarity conversion sequence and the improved polarity optimization approach with heuristic technique.     

基于结构的多级逻辑优化

本文提出一个基于结构的多级逻辑优化算法ＭＬＯＢＬＳ，多级组合逻辑网络的优化通过分析名逻辑门的可替代函数，并用简单的替代函数作替代变换完成。算法ＭＬＯＢＬＳ具有良好的逻辑结构重构能力，能得到近似最优的多级逻辑结构。整个优化过程在多级逻辑结构上直接进行，其时／空复杂性较少依赖于多级逻辑结构的基本输入／输出数目。／     

A recursive method for synthesizing quantum/reversible quaternary parallel adder/subtractor with look-ahead carry

Multiple-valued quantum logic circuits are a promising choice for future quantum computing technology since they have several advantages over binary quantum logic circuits. Adder/subtractor is the major component of the ALU of a computer and is also used in quantum oracles. In this paper, we propose a recursive method of hand synthesis of reversible quaternary full-adder circuit using macro-level quaternary controlled gates built on the top of ion-trap realizable 1-qudit quantum gates and 2-qudit Muthukrishnan–Stroud quantum gates. Based on this quaternary full-adder circuit we propose a reversible circuit realizing quaternary parallel adder/subtractor with look-ahead carry. We also show the way of adapting the quaternary parallel adder/subtractor circuit to an encoded binary parallel adder/subtractor circuit by grouping two qubits together into quaternary qudit values.