Transistor realization of reversible “ZS” series gates and reversible array multiplier

In order to reduce the redundant Toffoli gates and the line-crossings in the classical reversible full adder appearing in the present literatures, this paper gives a reconstructive structure of Fredkin gate, called RF gate, the corresponding quantum equivalent realization and electronic circuitry construction based on CMOS technology and pass-transistor of this gate are also designed in this paper. With the assistance of the RF gate and the basic reversible gates (including NOT gate, CNOT gate and Toffoli gate), we design new 4×4 reversible gates called “ZS” series gates and its corresponding electronic circuitry construction. The proposed “ZS” series gates have the ability to operate reversible add operation between two signed numbers by a single gate and at lower power consumption. At the same time, as an application of “ZS” series gates, this paper also designs reversible array multiplier in order to achieve the signed multiplication. It can be theoretically proved that the proposed reversible array multiplier can eliminate power loss associated with the irreversible operation of classical computer, and will be exponentially lower than reversible parallel multiplier with respect to time complexity.     

Efficient reversible NOR gates and their mapping in optical computing domain

Reversible logic is a computing paradigm in which there is a one to one mapping between the input and the output vectors. Reversible logic gates are implemented in an optical domain as it provides high speed and low energy computations. In the existing literature there are two types of optical mapping of reversible logic gates: (i) based on a semiconductor optical amplifier (SOA) using a Mach–Zehnder interferometer (MZI) switch; (ii) based on linear optical quantum computation (LOQC) using linear optical quantum logic gates. In reversible computing, the NAND logic based reversible gates and design methodologies based on them are widely popular. The NOR logic based reversible gates and design methodologies based on them are still unexplored. In this work, we propose two NOR logic based n-input and n-output reversible gates one of which can be efficiently mapped in optical computing using the Mach–Zehnder interferometer (MZI) while the other one can be mapped efficiently in optical computing using the linear optical quantum gates. The proposed reversible NOR gates work as a corresponding NOR counterpart of NAND logic based Toffoli gates. The proposed optical reversible NOR logic gates can implement the reversible boolean logic functions with a reduced number of linear optical quantum logic gates or reduced optical cost and propagation delay compared to their implementation using existing optical reversible NAND gates. It is illustrated that an optical reversible gate library having both optical Toffoli gate and the proposed optical reversible NOR gate is superior compared to the library containing only the optical Toffoli gate: (i) in terms of number of linear optical quantum gates when implemented using linear optical quantum computing (LOQC), (ii) in terms of optical cost and delay when implemented using the Mach–Zehnder interferometer.     

Reversible Gates and Testability of One Dimensional Arrays of Molecular QCA

An extensive literature exists on the mathematical characterization of reversible logic. However, the possible technological basis of this computing paradigm still remains unsolved. In this paper, quantum-dot cellular automata (QCA) is investigated for testable implementations of reversible logic. Two new reversible gates (referred to as QCA1 and QCA2) are proposed. These gates are compared (in terms of delay, area and logic synthesis) with other reversible gates (such as Toffoli and Fredkin) for QCA implementation. Due to the expected high error rates in nano-scale manufacturing, testing of nano devices, including QCA, has received considerable attention. The focus of this paper is on the testability of a one-dimensional array made of QCA reversible gates, because the bijective nature of reversible gates significantly facilitates testing of arrays. The investigation of testability relies on a fault model for molecular QCA that is based on a single missing/additional cell assumption. It is shown that C-testability of a 1D reversible QCA gate array can be guaranteed for single fault. Theory and circuit examples show that error masking can occur when multiple faults are considered.     

Computational analysis and comparison of reversible gates for design and test of logic circuits

Quantum computing is one of the most significant anticipation towards the accomplishment of interminable consumer demands of small, high speed, and low-power operable electronics devices. As reversible logic circuits have direct applicability to quantum circuits, design and synthesis of these circuits are finding grounds for emerging nano-technologies of quantum computing. Multiple Controlled Toffoli (MCT) and Multiple Controlled Fredkin (MCF) are the fundamental reversible gates that playing key role in this phase of development. A number of special reversible gates have also been presented so far, which were claimed superior for providing certain purposes like logic development and testing. This paper critically analyses a range of these gates to procure an optimal solution for design, synthesis and testing of reversible circuits. The experimentation is facilitated at three subsequent levels, i.e. gates properties, quantum cost and design & testability. MCT and MCF gates are found up to 50% more cost-effective than special gates at design level and 34.4% at testability level. Maximum reversibility depth (MRD) is included as a new measurement parameter for comparison. Special gates exhibit MRD up to 7 which ideally should be 1 for a system to be physically reversible as that of MCT and MCF gates.     

基于变换的可逆逻辑电路量子代价优化方法

电路优化是可逆逻辑综合的关键问题。为解决可逆逻辑电路优化算法的复杂度高和可伸缩性差的问题,文中针对常见的以Toffoli为构件的可逆逻辑电路,分析归纳了其中相邻逻辑门的关系,提出了该类电路中子序列的移动和化简规则,进而给出了基于这些规则的可逆逻辑电路优化算法。并在此基础上,提出了利用模板匹配法对已被规则优化的电路进行深度优化的有效方法。通过Benchmark的电路测试,结果表明,该方法能够部分减少可逆电路的门数和控制位数,降低了构建可逆电路的代价。     

An Exact approach for Complete Test Set Generation of Toffoli-Fredkin-Peres based Reversible Circuits

Reversible logic has gained interest of researchers worldwide for its ultra-low power and high speed computing abilities in the future quantum information processing. Testing of these circuits is important for ensuring high reliability of their operation. In this work, we propose an ATPG algorithm for reversible circuits using an exact approach to generate CTS (Complete Test Set) which can detect single stuck-at faults, multiple stuck-at faults, repeated gate fault, partial and complete missing gate faults which are very useful logical fault models for reversible logic to model any physical defect. Proposed algorithm can be used to test a reversible circuit designed with k-CNOT, Peres and Fredkin gates. Through extensive experiments, we have validated our proposed algorithm for several benchmark circuits and other circuits with family of reversible gates. This algorithm produces a minimal and complete test set while reducing test generation time as compared to existing state-of-the-art algorithms. A testing tool is developed satisfying the purpose of generating all possible CTS’s indicating the simulation time, number of levels and gates in the circuit. This paper also contributes to the detection and removal of redundant faults for optimal test set generation.     

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

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

基于矩阵初等变换的量子逻辑电路综合的新方法

量子逻辑电路是经典可逆计算和量子计算的交叉领域,对其综合方法的研究具有重要意义。提出了一个基于矩阵初等变换的全新的综合方法,Toffoli门集被选作基本门库,其中每个逻辑门的矩阵都可以分解为初等变换的乘积（称作一个初等变换路径）,结合一些启发式规则,将得到的初等变换路径变成Toffoli门序列的形式,也即逻辑电路形式。给出了一个三阶逻辑电路的例子,分析了该新方法的性能。     

光学偏振器的量子逻辑功能

光子的水平偏振态和竖直偏振态作为两种基本量子状态。利用光学偏振器实现量子操作、最子异或操作的逻辑功能,分析偏振器在构造量子Ｔｏｆｆｏｌｉ门和量子Ｆｒｅｄｋｉｎ门中的作用。     

Novel designs for fault tolerant reversible binary coded decimal adders

Reversible logic circuits have received emerging attentions in recent years. Reversible logic is widely applied in some new technical fields, such as quantum computing, nanocomputing and optical computing and so on. In this paper, three fault tolerant gates are proposed, ZPL gate, ZQC gate and ZC gate. By using the proposed gates, fault tolerant quantum and reversible BCD adder and skip carry BCD adder are designed, which overcome the limitations of the existing methods. The proposed reversible BCD adders have also parity-preserving property. They are better than the existing counterparts, especially in the quantum cost. Proposed designs have been compared with existing designs with respect to the number of gates, number of garbage outputs and quantum cost.     

Designing novel reversible BCD adder and parallel adder/subtraction using new reversible logic gates

Reversible logic has received much attention in recent years when calculation with minimum energy consumption is considered. Especially, interest is sparked in reversible logic by its applications in some technologies, such as quantum computing, low-power CMOS design, optical information processing and nanotechnology. This article proposes two new reversible logic gates, ZRQ and NC. The first gate ZRQ not only implements all Boolean functions but also can be used to design optimised adder/subtraction architectures. One of the prominent functionalities of the proposed ZRQ gate is that it can work by itself as a reversible full adder/subtraction unit. The second gate NC can complete overflow detection logic of Binary Coded Decimal (BCD) adder. This article proposes two approaches to design novel reversible BCD adder using new reversible gates. A comparative result which is presented shows that the proposed designs are more optimised in terms of number of gates, garbage outputs, quantum costs and unit delays than the existing designs.     

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

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

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

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

Debugging reversible circuits

A strong driving force for research of post-CMOS technologies is the fact that silicon-based transistors cannot be arbitrarily scaled down. Furthermore, power dissipation is a major barrier in the development of smaller and more efficient computer chips. In contrast, reversible logic with its applications e.g. in low-power design or quantum computation provides a promising alternative to traditional technologies. While there have been investigations in the domain of reversible logic synthesis, testing, and verification; debugging of reversible circuits has not yet been considered. The goal of debugging is to determine gates of an erroneous circuit that explain the observed incorrect behavior.In this paper, we propose the first approach for automatic debugging of reversible Toffoli circuits. Our method uses a formulation for the debugging problem based on Boolean satisfiability. We show the differences to traditional (irreversible) debugging. In addition, we introduce an improved approach that strengthens error candidate identification. This overcomes the limitations from traditional debugging, i.e. that error candidates are only an approximation of the real source of the error. Furthermore, observations are presented that can be applied to automatically fix an erroneous circuit just by replacing a single gate by a cascade. Due to reversibility this cascade can be efficiently computed. Experimental results show the quality and efficiency of our debugging approaches.     

腔QED中实现控制量子逻辑门的简易方案

受之前有关控制量子门工作的启发,提出了一个在腔QED中实现CNOT门,Toffoli门以及Fredkin门的简易方案。本方案只涉及到原子与腔场之间的大失谐相互作用,腔场处于虚激发,量子信息不会在原子和腔之间传递,因此对腔场的品质因子要求大大降低,在目前的实验技术条件下,该方案是是可行的。     

基于MCT可逆线路的量子线路近邻化排布

为了实现量子线路线性最近邻（LNN）排布,给出了可逆MCT门的最近邻Toffoli门级联方法.为了解决线路近邻化中额外插入的SWAP门增加量子代价的问题,引入NNTS门减少插入的SWAP门数,并给出了MCT门基于NNTS门的最近邻线路排布.提出了量子线路近邻化排布算法,将多控制MCT门通过交换线路的顺序得到其最近邻线路排布,然后将每个NNTS门替换为其最优的LNN量子线路实现,得到该MCT线路的LNN量子线路,该方法可以减少量子线路的长度和量子代价.通过Benchmark例题测试,并与现有的线路近邻化结果进行比较,所需插入的SWAP门数平均减少42.83%,量子代价平均改善率达14.80%.     

基于DNA链置换的三级联组合分子逻辑电路设计

DNA计算研究内容繁多复杂,DNA复杂逻辑电路的搭建属于DNA计算的一个重要研究分支,其中逻辑门的构建属于DNA复杂逻辑电路搭建的基础研究,设计出更为简单的逻辑门可以为研究者搭建复杂电路提供参考,节省基础研究的宝贵时间。针对上述问题,该文利用使能控制端思想,采用DNA链置换技术,设计了与或、与非或非和异或同或3种DNA组合逻辑门。结果显示,设计的3种组合逻辑门可实现6种逻辑运算功能,并利用所构建的组合逻辑门成功构造了多级联组合分子逻辑电路,为DNA计算提供了更多的解决方案,促进了DNA计算机的发展。     

通用Toffoli可逆门的固定故障测试

可逆电路技术在低功耗芯片和量子通信中广泛使用。目前,大部分学者着重研究可逆电路的合成,对电路的故障测试却很少问津,但是可逆电路的测试在应用中却十分重要。文中构造了一种四输入通用Toffoli门（universal toffoli gate,UTG）用来检测电路故障,这个门可以实现所有基本的布尔逻辑。UTG门可以检测到所...     

Exact synthesis of three-qubit quantum circuits from non-binary quantum gates

Because of recent nano-technological advances, nano-structured systems have become highly ordered, making it quantum computing schemas possible. We propose an approach to optimally synthesise quantum circuits from non-permutative quantum gates such as controlled-square-root-of-not (i.e., controlled-V). Our approach reduces the synthesis problem to multiple-valued optimisation and uses group theory. We devise a novel technique that transforms the quantum logic synthesis problem from a multi-valued constrained optimisation problem to a permutable representation. The transformation enables us to use group theory to exploit the symmetric properties of the synthesis problem. Assuming a cost of one for each two-qubit gate, we found all reversible circuits with quantum costs of 4, 5, 6, etc., and give another algorithm to realise these reversible circuits with quantum gates. The approach can be used for both binary permutative deterministic circuits and probabilistic circuits such as controlled random-number generators and hidden Markov models.     

基于Toffoli门族的可逆二进制加/减法器

以Toffoli 门族为基础,采用ESOP综合方法设计了一种4位可逆二进制加/减法器。引入了“共享控制位提取”的优化方法,并提出一种“传输线复用”的新思路,对可逆电路进行了优化。利用Quartus II软件进行了电路仿真,结果表明,该加/减法器的性能指标达到设计目标。该电路的量子代价、辅助输入、垃圾输出等性能指标均有较大程度的优化。