首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到17条相似文献,搜索用时 86 毫秒
1.
基于Hash表的量子可逆逻辑电路综合的快速算法   总被引:4,自引:1,他引:3  
量子可逆逻辑电路是构建量子计算机的基本单元,通过量子门的级联与组合构成量子计算机,量子可逆逻辑电路的综合就是根据电路功能,以较小的量子代价自动构造量子可逆逻辑电路.结合可逆逻辑电路综合的多种算法,提出了一种新颖高效的量子电路综合算法,巧妙构造最小完备的Hash函数,可使用多种量子门,采用任意量子代价标准,以极高的效率生成最优的量子可逆逻辑电路.为实现量子电路综合的自动化,首次提出了利用量子线的置换自动构造各种量子门库的通用算法.采用国际同行认可的3变量可逆函数测试标准,该算法不仅能够生成全部最优电路.而且运行速度远远超过其他算法·实验结果表明,该算法按最小长度、最小代价标准综合电路的平均速度分别是目前最好结果的49.15倍、365.13倍.  相似文献   

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

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

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

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

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

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

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

9.
量子可逆逻辑综合的关键技术及其算法   总被引:1,自引:0,他引:1       下载免费PDF全文
李志强  李文骞  陈汉武 《软件学报》2009,20(9):2332-2343
最优化量子可逆逻辑的关键在于用最小的量子代价自动构造量子可逆逻辑.为了提高可逆逻辑自动生成与优化的效率,提出了类模板技术和一种快速算法.模板技术是一个有效的优化工具,类模板技术可以显著提高模板技术的匹配效率;R-M算法是可逆逻辑综合的一种较好的迭代方法,基于R-M算法的原始思想,构造了一个Hash函数,并在此基础上提出了一种可逆逻辑综合的快速算法.实验结果表明,在同等实验环境下使用类模板技术与快速算法,其优化的效果与效率远远优于已知的其他算法.  相似文献   

10.
改进的量子遗传算法及应用   总被引:5,自引:1,他引:4  
针对量子遗传算法在函数优化中迭代次数多,容易陷入局部最优解等缺点,提出新的量子遗传算法.该算法的核心是采用新的量子旋转门调整策略对种群进行更新操作,有效保证了种群的多样性,可以避免算法陷入局部最优解,提高了算法的全局寻优能力.同时能以更快的速度收敛于全局最优解.通过对典型复杂函数测试,计算结果表明,提出的算法优化质量和效率都要优于传统遗传算法和一般量子遗传算法.  相似文献   

11.
The reducing of the width of quantum reversible circuits makes multiple-valued reversible logic a very promising research area. Ternary logic is one of the most popular types of multiple-valued reversible logic, along with the Subtractor, which is among the major components of the ALU of a classical computer and complex hardware. In this paper the authors will be presenting an improved design of a ternary reversible half subtractor circuit. The authors shall compare the improved design with the existing designs and shall highlight the improvements made after which the authors will propose a new ternary reversible full subtractor circuit. Ternary Shift gates and ternary Muthukrishnan–Stroud gates were used to build such newly designed complex circuits and it is believed that the proposed designs can be used in ternary quantum computers. The minimization of the number of constant inputs and garbage outputs, hardware complexity, quantum cost and delay time is an important issue in reversible logic design. In this study a significant improvement as compared to the existing designs has been achieved in as such that with the reduction in the number of ternary shift and Muthukrishnan-Stroud gates used the authors have produced ternary subtractor circuits.  相似文献   

12.

Integrated circuits always face with two major challenges including heat caused by energy losses and the area occupied. In recent years, different strategies have been presented to reduce these two major challenges. The implementations of circuits in a reversible manner as well as the use of multiple-valued logic are among the most successful strategies. Reversible circuits reduce energy loss and ultimately eliminate the problem of overheating in circuits. Preferring multiple-valued logic over binary logic can also greatly reduce area occupied of circuits. When switching from binary logic to multiple-valued logic, the dominant thought in binary logic is the basis of designing computational circuits in multiple-valued logic, and disregards the capabilities of multiple-valued logic. This can cause a minimal use of multiple-valued logic capabilities, increase complexity and delay in the multiple-valued computational circuits. In this paper, we first introduce an efficient reversible ternary half-adder. Afterward, using the reversible ternary half-adder, we introduce two reversible versions of traditional and comprehensive reversible ternary full-adders. Finally, using the introduced reversible ternary full-adders, we propose two novel designs of reversible ternary 6:2 Compressor. The results of the comparisons show that although the proposed circuits are similar to or better than previous corresponding designs in terms of criteria number of constant input and number of garbage outputs, they are superior in criterion quantum cost.

  相似文献   

13.
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.  相似文献   

14.
Quantum ternary logic is a promising emerging technology for the future quantum computing. Ternary reversible logic circuit design has potential advantages over the binary ones like its logarithmic reduction in the number of qudits. In reversible logic all computations are done in an invertible fashion. In this paper, we propose a new quantum reversible ternary half adder with quantum cost of only 7 and a new quantum ternary full adder with a quantum cost of only 14. We termed it QTFA. Then we propose 3-qutrit parallel adders. Two different structures are suggested: with and without input carry. Next, we propose quantum ternary coded decimal (TCD) detector circuits. Two different approaches are investigated: based on invalid numbers and based on valid numbers. Finally, we propose the quantum realization of TCD adder circuits. Also here, two approaches are discussed. Overall, the proposed reversible ternary full adder is the best between its counterparts comparing the figures of merits. The proposed 3-qutrit parallel adders are compared with the existing designs and the improvements are reported. On the other hand, this paper suggested the quantum reversible TCD adder designs for the first time. All the proposed designs are realized using macro-level ternary Toffoli gates which are built on the top of the ion-trap realizable ternary 1-qutrit gates and 2-qutrit Muthukrishnan–Stroud gates.  相似文献   

15.
In the field of nanotechnology, quantum dot-cellular automata (QCA) is the promising archetype that can provide an alternative solution to conventional complementary metal oxide semiconductor (CMOS) circuit. QCA has high device density, high operating speed, and extremely low power consumption. Reversible logic has widespread applications in QCA. Researchers have explored several designs of QCA-based reversible logic circuits, but still not much work has been reported on QCA-based reversible binary subtractors. The low power dissipation and high circuit density of QCA pledge the energy-efficient design of logic circuit at a nano-scale level. However, the necessity of too many logic gates and detrimental garbage outputs may limit the functionality of a QCA-based logic circuit. In this paper we describe the design and implementation of a DG gate in QCA. The universal nature of the DG gate has been established. The QCA building block of the DG gate is used to achieve new reversible binary subtractors. The proposed reversible subtractors have low quantum cost and garbage outputs compared to the existing reversible subtractors. The proposed circuits are designed and simulated using QCA Designer-2.0.3.  相似文献   

16.
On figures of merit in reversible and quantum logic designs   总被引:1,自引:0,他引:1  
Five figures of merit including number of gates, quantum cost, number of constant inputs, number of garbage outputs, and delay are used casually in the literature to compare the performance of different reversible or quantum logic circuits. In this paper we propose new definitions and enhancements, and identify similarities between these figures of merit. We evaluate these measures to show their strength and weakness. Instead of the number of gates, we introduce the weighted number of gates, where a weighting factor is assigned to each quantum or reversible gate, based on its type, size and technology. We compare the quantum cost with weighted number of gates of a circuit and show three major differences between these measures. It is proved that it is not possible to define a universal reversible logic gate without adding constant inputs. We prove that there is an optimum value for number of constant inputs to obtain a circuit with minimum quantum cost. Some reversible logic benchmarks have been synthesized using Toffoli and Fredkin gates to obtain their optimum values of number of constant inputs. We show that the garbage outputs can also be used to decrease the quantum cost of the circuit. A new definition of delay in quantum and reversible logic circuits is proposed for music line style representation. We also propose a procedure to calculate the delay of a circuit, based on the quantum cost and the depth of the circuit. The results of this research show that to achieve a fair comparison among designs, figures of merit should be considered more thoroughly.   相似文献   

17.
Reversible logic is a new field of study that has applications in optical information processing, low power CMOS design, DNA computing, bioinformatics, and nanotechnology. Low power consumption is a basic issue in VLSI circuits today. To prevent the distribution of errors in the quantum circuit, the reversible logic gates must be converted into fault-tolerant quantum operations. Parity preserving is used to realize fault tolerant in this circuits. This paper proposes a new parity preserving reversible gate. We named it NPPG gate. The most significant aspect of the NPPG gate is that it can be used to produce parity preserving reversible full adder circuit. The proposed parity preserving reversible full adder using NPPG gate is more efficient than the existing designs in term of quantum cost and it is optimized in terms of number of constant inputs and garbage outputs. Compressors are of importance in VLSI and digital signal processing applications. Effective VLSI compressors reduce the impact of carry propagation of arithmetic operations. They are built from the full adder blocks. We also proposed three new approaches of parity preservation reversible 4:2 compressor circuits. The third design is better than the previous two in terms of evaluation parameters. The important contributions have been made in the literature toward the design of reversible 4:2 compressor circuits; however, there are not efforts toward the design of parity preservation reversible 4:2 compressor circuits. All the scales are in the nanometric criteria.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号