Design of Improved TR Gate Cascade Quantum Comparator

doi:10.3778/j.issn.1002-8331.2009-0193

Abstract

Abstract:

The quantum comparator is an important part in the design of quantum algorithms, and it is of great significance to the physical implementation of quantum algorithms. Aiming at the quantum cost and garbage output optimization problem of the comparator, a quantum comparator design scheme with improved TR gate cascade is proposed in three stages. The first stage uses Boolean logic to derive the realization of the scheme and simplify it, the second stage designs a 1?bit quantum comparator; the third stage cascades the comparators and realizes the generality of [n] bit comparators. Iterative derivation proves its correctness. Compared with other documents, this design reduces the quantum cost by nearly 12.6% and saves 47.6% of garbage output. Finally, experimental simulation proves that it can operate normally. Compared with other types of comparators, the quantum cost and garbage output required by the design are significantly reduced, and the structure is simple and easy to implement.

Key words: quantum computing, comparator, reversible logic, quantum cost, garbage output

摘要：

量子比较器是量子算法设计中的重要组成部分，其对于量子算法的物理实现具有重要意义。针对比较器的量子代价与垃圾输出优化问题，分成三个阶段提出了改进TR门级联的量子比较器设计方案：第一个阶段使用布尔逻辑推导了方案的实现，并对其进行简化；第二个阶段设计了1位的量子比较器；第三个阶段将比较器进行级联，并实现[n]位的一般性比较器。通过迭代式的推导证明了其正确性，对比其他文献，该设计减少了近12.6%的量子代价，同时节约了47.6%的垃圾输出。通过实验仿真，证明其可以正常运行。与其他类型比较器相比，该设计所需的量子代价与垃圾输出有明显的减少，且构造简单易于实现。

关键词: 量子计算, 比较器, 可逆逻辑, 量子代价, 垃圾输出

ZHOU Lin, GUO Bing. Design of Improved TR Gate Cascade Quantum Comparator[J]. Computer Engineering and Applications, 2021, 57(19): 112-115.

周林，郭兵. 改进TR门级联的量子比较器设计[J]. 计算机工程与应用, 2021, 57(19): 112-115.

References

[1] LANDAUER R.Irreversibility and heat generation in the computing process[J].IBM Journal of Research and Development，1961，5（3）：183-191.
[2] SHOR P W.Algorithms for quantum computation：Discrete logarithms and factoring[C]//Proceedings of the 35th Annual Symposium on Foundations of Computer Science，1994：124-134.
[3] GONG C，DU J，DONG Z，et al.Grover algorithm-based quantum homomorphic encryption ciphertext retrieval scheme in quantum cloud computing[J].Quantum Information Processing，2020，19（3）：105.
[4] CHEN Y，WEI S，GAO X，et al.An optimized quantum maximum or minimum searching algorithm and its circuits[J].arXiv：1908.07943，2019.
[5] ODEH A，ABDELFATTAH E.Quantum sort algorithm based on entanglement qubits{00，11}[C]//2016 IEEE Long Island Systems，Applications and Technology Conference（LISAT），2016：1-5.
[6] KHADIEV K，ILIKAEV A.Quantum algorithms for the most frequently string search，intersection of two string sequences and sorting of strings problems[C]//Proceedings of International Conference on Theory and Practice of Natural Computing，2019：234-245.
[7] MAMUN M，AL S，MENVILLE D.Quantum cost optimization for reversible sequential circuit[J].arXiv：1407.7098，2014.
[8] NIELSEN M A，CHUANG I L.Quantum computation and quantum information[M].[S.l.]：Cambridge University Press，2010.
[9] LI H S，FAN P，XIA H，et al.Efficient quantum arithmetic operation circuits for quantum image processing[J].Science China Physics，Mechanics & Astronomy，2020，63：1-13.
[10] MAITY H，BISWAS A，BHATTACHARJEE A K，et al.The quantum cost，garbage outputs and constant input optimized implementation of 2∶4 decoder using peres gate[C]//2019 Devices for Integrated Circuit（DevIC），2019：9-11.
[11] VUDADHA C，PHANEENDRA P S，SREEHARI V，et al.Design of prefix-based optimal reversible comparator[C]//2012 IEEE Computer Society Annual Symposium on VLSI，2012：201-206.
[12] WANG D，LIU Z H，ZHU W N，et al.Design of quantum comparator based on extended general Toffoli gates with multiple targets[J].Computer Science，2012，39（9）：302-306.
[13] MASLOV D，DUECK G W.Improved quantum cost for n-bit Toffoli gates[J].Electronics Letters，2003，39（25）：1790-1791.
[14] AL-RABADI A N.Closed-system quantum logic network implementation of the viterbi algorithm[J].Facta Universitatis-Series：Electronics and Energetics，2009，22（1）：1-33.
[15] THAPLIYAL H，RANGANATHAN N，FERREIRA R.Design of a comparator tree based on reversible logic[C]//Proceedings of the 10th IEEE International Conference on Nanotechnology，2010：1113-1116.
[16] 张小颖，王伶俐，吴文晋，等，扩展Toffoli门及其在多输出电路设计的应用[J]，计算机工程与应用，2009，45（2）：88-91.
ZHANG X Y，WANG L L，WU W J，et al.Extended Toffoli gates and its application in multi-output logic functions[J].Computer Engineering and Applications，2009，45（2）：88-91.