A new design of parity-preserving reversible multipliers based on multiple-control toffoli synthesis targeting emerging quantum circuits

Abstract

With the recent demonstration of quantum computers, interests in the field of reversible logic synthesis and optimization have taken a different turn. As every quantum operation is inherently reversible, there is an immense motivation for exploring reversible circuit design and optimization. When it comes to faults in circuits, the parity-preserving feature donates to the detection of permanent and temporary faults. In the context of reversible circuits, the parity-preserving property ensures that the input and output parities are equal. In this paper we suggest six parity-preserving reversible blocks (Z, F, A, T, S, and L) with improved quantum cost. The reversible blocks are synthesized using an existing synthesis method that generates a netlist of multiple-control Toffoli (MCT) gates. Various optimization rules are applied at the reversible circuit level, followed by transformation into a netlist of elementary quantum gates from the NCV library. The designs of full-adder and unsigned and signed multipliers are proposed using the functional blocks that possess parity-preserving properties. The proposed designs are compared with state-of-the-art methods and found to be better in terms of cost of realization. Average savings of 25.04%, 20.89%, 21.17%, and 51.03%, and 18.59%, 13.82%, 13.82%, and 27.65% respectively, are observed for 4-bit unsigned and 5-bit signed multipliers in terms of quantum cost, garbage output, constant input, and gate count as compared to recent works.

Graphical abstract

Keywords

reversible circuits / parity-preserving / NCV library / multiple-control Toffoli gates / quantum circuits / quantum cost

References

[1] Landauer R . Irreversibility and heat generation in the computing process. IBM Journal of Research and Development, 1961, 5( 3): 183–191

[2] Bennett C H . Logical reversibility of computation. IBM Journal of Research and Development, 1973, 17( 6): 525–532

[3] Maslov D, Dueck G W . Reversible cascades with minimal garbage. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2004, 23( 11): 1497–1509

[4] Barenco A, Bennett C H, Cleve R, DiVincenzo D P, Margolus N, Shor P, Sleator T, Smolin J A, Weinfurter H . Elementary gates for quantum computation. Physical Review A, 1995, 52( 5): 3457–3467

[5] Zulehner A, Paler A, Wille R . An efficient methodology for mapping quantum circuits to the IBM QX architectures. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 38( 7): 1226–1236

[6] Niemann P, Bandyopadhyay C, Drechsler R. Combining SWAPs and remote toffoli gates in the mapping to IBM QX architectures. In: Proceedings of 2021 Design, Automation & Test in Europe Conference & Exhibition (DATE). 2021, 200−205

[7] Parhami B. Fault-tolerant reversible circuits. In: Proceedings of the 40th Asilomar Conference on Signals, Systems and Computers. 2006, 1726−1729

[8] Muñoz-Coreas E, Thapliyal H . Quantum circuit design of a t-count optimized integer multiplier. IEEE Transactions on Computers, 2018, 68( 5): 729–739

[9] Bose A, Sarker A. A novel approach for constructing reversible fault tolerant n-bit binary comparator. In: Proceedings of 2014 International Conference on Informatics, Electronics & Vision (ICIEV). 2014, 1−6

[10] Bruce J W, Thornton M A, Shivakumaraiah L, Kokate P S, Li X. Efficient adder circuits based on a conservative reversible logic gate. In: Proceedings of IEEE Computer Society Annual Symposium on VLSI. New Paradigms for VLSI Systems Design. ISVLSI 2002. 2002, 83−88

[11] Haghparast M, Navi K . Design of a novel fault tolerant reversible full adder for nanotechnology based systems. World Applied Sciences Journal, 2008, 3( 1): 114–118

[12] Qi X, Chen F, Zuo K, Guo L, Luo Y, Hu M . Design of fast fault tolerant reversible signed multiplier. International Journal of the Physical Sciences, 2012, 7( 17): 2506–2514

[13] Islam S, Begum Z. Reversible logic synthesis of fault tolerant carry skip BCD adder. 2010, arXiv preprint arXiv: 1008.3288

[14] Qi X, Chen F, Guo L, Luo Y, Hu M . Efficient approaches for designing fault tolerant reversible BCD adders. Journal of Computational Information Systems, 2013, 9( 14): 5869–5877

[15] Mitra S K, Chowdhury A R. Minimum cost fault tolerant adder circuits in reversible logic synthesis. In: Proceedings of the 25th International Conference on VLSI Design. 2012, 334−339

[16] Shoaei S, Haghparast M. Novel designs of nanometric parity preserving reversible circuits. In: Proceedings of 8th Symposium on Advances in Science and Technology. 2013

[17] Shoaei S, Haghparast M . Novel designs of nanometric parity preserving reversible compressor. Quantum Information Processing, 2014, 13( 8): 1701–1714

[18] Valinataj M, Mirshekar M, Jazayeri H . Novel low-cost and fault-tolerant reversible logic adders. Computers & Electrical Engineering, 2016, 53: 56–72

[19] Misra N K, Sen B, Wairya S . Novel tree structure based conservative reversible binary coded decimal adder and sequential circuit with added high testability. Journal of Computational and Theoretical Nanoscience, 2017, 14( 5): 2515–2527

[20] Sen B, Dutta M, Banik D, Singh D K, Sikdar B K. Design of fault tolerant reversible arithmetic logic unit in QCA. In: Proceedings of 2012 International Symposium on Electronic System Design (ISED). 2012, 241−245

[21] Sen B, Ganeriwal S, Sikdar B K . Reversible logic-based fault-tolerant nanocircuits in QCA. International Scholarly Research Notices, 2013, 2013: 850267

[22] Zhou R G, Li Y C, Zhang M Q . Novel designs for fault tolerant reversible binary coded decimal adders. International Journal of Electronics, 2014, 101( 10): 1336–1356

[23] PourAliAkbar E, Navi K, Haghparast M, Reshadi M . Novel optimum parity-preserving reversible multiplier circuits. Circuits, Systems, and Signal Processing, 2020, 39( 10): 5148–5168

[24] Jamal L, Rahman M, Babu H M H. An optimal design of a fault tolerant reversible multiplier. In: Proceedings of 2013 IEEE International SOC Conference. 2013, 37−42

[25] Babazadeh S, Haghparast M . Design of a nanometric fault tolerant reversible multiplier circuit. Journal of Basic and Applied Scientific Research, 2012, 2( 2): 1355–1361

[26] Valinataj M . Novel parity-preserving reversible logic array multipliers. The Journal of Supercomputing, 2017, 73( 11): 4843–4867

[27] Chowdhury E S, Ahmed N, Jamal L. A new perspective in designing an optimized fault tolerant reversible multiplier. In: Proceedings of Joint the 8th International Conference on Informatics, Electronics & Vision (ICIEV) and the 3rd International Conference on Imaging, Vision & Pattern Recognition (icIVPR). 2019, 274−279

[28] Gaur H M, Singh A K, Ghanekar U . An efficient design of scalable reversible multiplier with testability. Journal of Circuits, Systems and Computers, 2022, 31( 10): 2250179

[29] PourAliAkbar E, Navi K, Haghparast M, Reshadi M . Novel designs of fast parity-preserving reversible vedic multiplier. The CSI Journal on Computer Science and Engineering, 2019, 17( 1): 9–20

[30] Gaur H M, Singh A K, Ghanekar U . Testable design of reversible circuits using parity preserving gates. IEEE Design & Test, 2018, 35( 4): 56–64

[31] Gaur H M, Singh A K, Ghanekar U . Design of reversible arithmetic logic unit with built-in testability. IEEE Design & Test, 2019, 36( 5): 54–61

[32] Gaur H M, Singh A K, Mohan A, Fujita M, Pradhan D K . Design of single-bit fault-tolerant reversible circuits. IEEE Design & Test, 2021, 38( 2): 89–96

[33] Gaur H M, Singh A K, Ghanekar U . Simplification and modification of multiple controlled Toffoli circuits for testability. Journal of Computational Electronics, 2019, 18( 1): 356–363

[34] Gaur H M, Singh A K . Design of reversible circuits with high testability. Electronics Letters, 2016, 52( 13): 1102–1104

[35] Noorallahzadeh M, Mosleh M, Ahmadpour S S, Pal J, Sen B. A new design of parity preserving reversible Vedic multiplier targeting emerging quantum circuits. International Journal of Numerical Modelling: Electronic Networks, Devices and Fields, 2023, e3089

[36] Noorallahzadeh M, Mosleh M, Misra N K, Mehranzadeh A . A novel design of reversible quantum multiplier based on multiple-control toffoli synthesis. Quantum Information Processing, 2023, 22( 4): 167

[37] Gaur H M, Singh A K, Ghanekar U . Design for stuck-at fault testability in toffoli–fredkin reversible circuits. National Academy Science Letters, 2021, 44( 3): 215–220

[38] Singh A K, Gaur H M, Ghanekar U . Fault detection in multiple controlled Fredkin circuits. IET Circuits, Devices & Systems, 2019, 13( 5): 723–729

[39] Gaur H M, Singh A K, Ghanekar U . Offline testing of reversible logic circuits: an analysis. Integration, 2018, 62: 50–67

[40] Gaur H M, Singh A K, Ghanekar U . Reversible circuits with testability using quantum controlled-not and swap gates. Indian Journal of Pure & Applied Physics, 2018, 56: 529–532

[41] Gaur H M, Singh A K, Ghanekar U . A new DFT methodology for k-CNOT reversible circuits and its implementation using quantum-dot cellular automata. Optik, 2016, 127( 22): 10593–10601

[42] Gaur H M, Singh A K, Ghanekar U . A comprehensive and comparative study on online testability for reversible logic. Pertanika Journal of Science & Technology, 2016, 24( 2): 245–271

[43] Thapliyal H, Ranganathan N. A new reversible design of BCD adder. In: Proceedings of 2011 Design, Automation & Test in Europe. 2011, 1−4

[44] Feynman R P . Quantum mechanical computers. Optics News, 1985, 11( 2): 11–20

[45] Toffoli T. Reversible computing. In: Proceedings of the 7th International Colloquium on Automata, Languages, and Programming. 1980, 632−644

[46] Miller D M, Maslov D, Dueck G W. A transformation based algorithm for reversible logic synthesis. In: Proceedings of 2003 Design Automation Conference. 2003, 318−323

[47] Kole A, Hillmich S, Datta K, Wille R, Sengupta I . Improved mapping of quantum circuits to IBM QX architectures. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2020, 39( 10): 2375–2383

[48] Rahman M, Banerjee A, Dueck G W, Pathak A. Two-qubit quantum gates to reduce the quantum cost of reversible circuit. In: Proceedings of the 41st IEEE International Symposium on Multiple-Valued Logic. 2011, 86−92

[49] Lewandowski M, Ranganathan N, Morrison M. Behavioral model of integrated qubit gates for quantum reversible logic design. In: Proceedings of 2013 IEEE Computer Society Annual Symposium on VLSI (ISVLSI). 2013, 194−199

[50] Hung W N N, Song X Y, Yang G W, Yang J, Perkowski M . Optimal synthesis of multiple output Boolean functions using a set of quantum gates by symbolic reachability analysis. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006, 25( 9): 1652–1663

[51] Rahman M, Dueck G W. Properties of quantum templates. In: Proceedings of the 4th International Workshop on Reversible Computation. 2012, 125−137

[52] Maslov D, Dueck G W, Miller D M . Toffoli network synthesis with templates. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2005, 24( 6): 807–817

[53] Soeken M, Sasanian Z, Wille R, Miller D M, Drechsler R. Optimizing the mapping of reversible circuits to four-valued quantum gate circuits. In: Proceedings of the 42nd IEEE International Symposium on Multiple-Valued Logic. 2012, 173−178

[54] Shende V V, Prasad A K, Markov I L, Hayes J P . Synthesis of reversible logic circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2003, 22( 6): 710–722

[55] Miller D M, Soeken M, Drechsler R. Mapping NCV circuits to optimized Clifford+T circuits. In: Proceedings of the 6th International Conference on Reversible Computation. 2014, 163−175

[56] Soeken M, Thomsen M K. White dots do matter: rewriting reversible logic circuits. In: Proceedings of the 5th International Conference on Reversible Computation. 2013, 196−208

[57] Fredkin E, Toffoli T. Conservative logic. International Journal of Theoretical Physics, 1982, 21(3−4): 219−253

[58] Parhami B. Computer Arithmetic: Algorithms and Hardware Designs. 2nd ed. New York: Oxford University Press, 2010

[59] Baugh C R, Wooley B A . A two’s complement parallel array multiplication algorithm. IEEE Transactions on Computers, 1973, C-22( 12): 1045–1047

[60] Tan T R, Gaebler J P, Lin Y, Wan Y, Bowler R, Leibfried D, Wineland D J . Multi-element logic gates for trapped-ion qubits. Nature, 2015, 528( 7582): 380–383

[61] Kole A, Datta K, Sengupta I . A new heuristic for N-dimensional nearest neighbor realization of a quantum circuit. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2018, 37( 1): 182–192

RIGHTS & PERMISSIONS

Higher Education Press