Please wait a minute...
Shopping Cart Email List Chinese
Advanced Search Fig/Tab
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Featured Articles  |  Most Downloaded  |  Most Reading
Online Submission Subscribe to Our RSS Content Feed
Front. Comput. Sci.    2024, Vol. 18 Issue (6) : 186908    https://doi.org/10.1007/s11704-023-2492-3
RESEARCH ARTICLE
A new design of parity-preserving reversible multipliers based on multiple-control toffoli synthesis targeting emerging quantum circuits
Mojtaba NOORALLAHZADEH1(), Mohammad MOSLEH1(), Kamalika DATTA2,3
1. Department of Computer Engineering, Dezful Branch, Islamic Azad University, Dezful, Iran
2. German Research Centre for Artificial Intelligence (DFKI), Bremen 28359, Germany
3. Institute of Computer Science, University of Bremen, Bremen 28359, Germany
 Download: PDF(9583 KB)   HTML
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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.
Keywords reversible circuits      parity-preserving      NCV library      multiple-control Toffoli gates      quantum circuits      quantum cost     
Corresponding Author(s): Mojtaba NOORALLAHZADEH,Mohammad MOSLEH   
Just Accepted Date: 14 June 2023   Issue Date: 26 September 2023
 Cite this article:   
Mojtaba NOORALLAHZADEH,Mohammad MOSLEH,Kamalika DATTA. A new design of parity-preserving reversible multipliers based on multiple-control toffoli synthesis targeting emerging quantum circuits[J]. Front. Comput. Sci., 2024, 18(6): 186908.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-023-2492-3
https://academic.hep.com.cn/fcs/EN/Y2024/V18/I6/186908
Fig.1  Toffoli blocks: (a) TF1(A), (b) TF2(A,B), (c) TF3(A,B,C), (d) TF3(A,C,B), (e) quantum gate realization of TF3(A,B,C), and (f) another quantum gate realization of TF3(A,C,B)
Fig.2  Primitive gates: (a) NOT, (b) CNOT, (c) C-V, (d) C-V+, (e) integrated qubits, and (f) rules
Fig.3  Templates with 3 and 4 inputs
Fig.4  Parity-preserving reversible gates: (a) DFG gate, (b) FRG gate, and(c) LMH gate
Fig.5  Proposed Z-block: (a) Toffoli-based circuit, (b) NCV-based circuit, and (c) the optimized NCV of the Z block
Fig.6  Proposed F-block: (a) Toffoli-based circuit, (b) NCV-based circuit, and (c) the optimized NCV of the F block
Fig.7  Proposed A-block: (a) Toffoli-based circuit, (b) NCV-based circuit, and (c) the optimized NCV of the A block
Fig.8  Proposed T-block: (a) Toffoli-based circuit, (b) NCV-based circuit, and (c) the optimized NCV of the T block
Fig.9  Proposed S-block: (a) Toffoli-based circuit, (b) NCV-based circuit, and (c) the optimized NCV of the S block
Fig.10  Proposed L-block: (a) Toffoli-based circuit, (b) NCV-based circuit, and (c) the optimized NCV of the L-block
Fig.11  Proposed parity-preserving reversible full adder: (a) block diagram, (b) NCV realization
Fig.12  Unsigned multiplication of two 4-bit numbers
Fig.13  Proposed PPG module for 4×4 multiplier
Fig.14  Proposed MOA module for 4×4 multiplier
Size of multiplier Performance metrics
QC GO CI GC
4×4 151 39 39 19
8×8 679 171 171 109
12×12 1591 399 399 263
16×16 2887 723 723 481
32×32 11911 2979 2979 1993
Tab.1  Performance metrics for the unsigned multiplier for various data sizes
Fig.15  signed multiplication of two 5-bit numbers
Fig.16  Proposed PPG module for 5×5 multiplier
Fig.17  Proposed MOA module for 5×5 multiplier
Size of multiplier Performance metrics
QC GO CI GC
5×5 262 74 74 35
8×8 706 191 191 92
12×12 1634 431 431 210
16×16 2946 767 767 376
32×32 12034 3071 3071 3040
Tab.2  Performance metrics for the signed multiplier for various data sizes
Designs QC GO CI GC Improv. (in QC)/%
[10] 20 3 2 4 65.00
[11] 18 6 5 6 61.11
[12] 14 3 2 2 50.00
[13] 14 3 2 1 50.00
[14] 14 3 2 2 50.00
[15] 14 3 2 2 50.00
[16] 11 3 2 4 36.36
[17] 11 3 2 1 36.36
[18] 10 3 2 3 30.00
[19] 10 3 2 1 30.00
[20] 10 3 2 3 30.00
[21] 8 3 2 1 12.50
[22] 8 3 2 1 12.50
[23] 8 3 2 1 12.50
Proposed 7 3 2 1 –
Average (in QC) 37.59
Tab.3  Comparison of parity-preserving reversible full-adder designs
Module Design QC GO CI GC
PPG [25] 104 32 40 28
[24] 89 17 25 16
[26] 96 24 32 24
[23] 89 17 23 16
Proposed 83 13 19 9
% improv. [25] 20.19 59.37 52.50 67.85
% improv.[24] 6.74 23.52 24.00 43.75
% improv.[26] 13.54 45.83 40.62 62.50
% improv.[23] 6.74 23.52 17.39 43.75
Average 11.80 38.06 33.62 54.46
MOA [25] 140 32 24 20
[24] 116 32 24 36
[26] 88 32 24 12
[23] 80 28 22 10
Proposed 68 26 20 10
% improv. [25] 51.42 18.75 16.66 50.00
% improv.[24] 41.37 18.75 16.66 72.22
% improv.[26] 22.72 18.75 16.66 16.66
% improv.[23] 15.00 7.14 9.09 0.00
Average 32.62 15.84 14.76 34.72
Tab.4  Comparison of parity-preserving reversible ppg and moa unsigned multiplier designs
Designs QC GO GI GC
[25] 244 64 64 48
[24] 205 49 49 52
[26] #1 184 56 56 36
[26] #2 177 49 49 28
[27] 184 44 44 33
[23] 169 45 45 26
[28] 300 44 45 124
Proposed 151 39 39 19
% improv. [25] 38.11 39.06 39.06 60.41
% improv. [24] 26.34 20.40 20.40 63.46
% improv. [26] #1 17.93 30.35 30.35 47.22
% improv. [26] #2 14.68 20.40 20.40 32.14
% improv. [27] 17.93 11.36 11.36 42.42
% improv. [23] 10.65 13.33 13.33 26.92
% improv. [28] 49.66 11.36 13.33 84.67
Average 25.04 20.89 21.17 51.03
Tab.5  Comparison of parity-preserving reversible unsigned multiplier designs
Module Design QC GO CI GC
PPG [12] 149 34 49 37
[26] 143 28 43 25
[23] 143 28 41 25
Proposed 136 22 35 16
% improve.[12] 8.72 35.29 28.57 56.75
% improve.[26] 4.89 21.42 18.60 36.00
% improve.[23] 4.89 21.42 14.63 36.00
Average 6.16 26.04 20.6 42.91
MOA [12] 252 55 41 20
[26] 154 58 43 21
[23] 146 54 41 19
Proposed 126 52 39 19
% improve.[12] 50.00 5.45 4.87 5.00
% improve.[26] 18.18 10.34 9.30 9.52
% improve.[23] 13.69 3.70 4.87 0.00
Average 27.29 6.49 6.34 4.84
Tab.6  Comparison of parity-preserving reversible ppg and moa signed multiplier designs
Designs QC GO GI GC
[12] 401 90 90 57
[26] 297 86 86 46
[23] 289 82 82 44
Proposed 262 74 74 35
% improv. [12] 34.66 17.77 17.77 38.59
% improv. [26] 11.78 13.95 13.95 23.91
% improv. [23] 9.34 9.75 9.75 20.45
Average 18.59 13.82 13.82 27.65
Tab.7  Comparison of parity-preserving reversible signed multiplier designs
Fig.18  (a) Full adder realization using NCV gates, (b) swap gate realization, (c) 3×2 2D array, (d) nearest-neighbor realization using swap gates
  
  
  
1 R Landauer . Irreversibility and heat generation in the computing process. IBM Journal of Research and Development, 1961, 5( 3): 183–191
2 C H Bennett . Logical reversibility of computation. IBM Journal of Research and Development, 1973, 17( 6): 525–532
3 D, Maslov G W Dueck . Reversible cascades with minimal garbage. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2004, 23( 11): 1497–1509
4 A, Barenco C H, Bennett R, Cleve D P, DiVincenzo N, Margolus P, Shor T, Sleator J A, Smolin H Weinfurter . Elementary gates for quantum computation. Physical Review A, 1995, 52( 5): 3457–3467
5 A, Zulehner A, Paler R Wille . 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 P, Niemann C, Bandyopadhyay R Drechsler . 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 B Parhami . Fault-tolerant reversible circuits. In: Proceedings of the 40th Asilomar Conference on Signals, Systems and Computers. 2006, 1726−1729
8 E, Muñoz-Coreas H Thapliyal . Quantum circuit design of a t-count optimized integer multiplier. IEEE Transactions on Computers, 2018, 68( 5): 729–739
9 A, Bose A Sarker . 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 J W, Bruce M A, Thornton L, Shivakumaraiah P S, Kokate X Li . 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 M, Haghparast K Navi . Design of a novel fault tolerant reversible full adder for nanotechnology based systems. World Applied Sciences Journal, 2008, 3( 1): 114–118
12 X, Qi F, Chen K, Zuo L, Guo Y, Luo M Hu . Design of fast fault tolerant reversible signed multiplier. International Journal of the Physical Sciences, 2012, 7( 17): 2506–2514
13 S, Islam Z Begum . Reversible logic synthesis of fault tolerant carry skip BCD adder. 2010, arXiv preprint arXiv: 1008.3288
14 X, Qi F, Chen L, Guo Y, Luo M Hu . Efficient approaches for designing fault tolerant reversible BCD adders. Journal of Computational Information Systems, 2013, 9( 14): 5869–5877
15 S K, Mitra A R Chowdhury . 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 S, Shoaei M Haghparast . Novel designs of nanometric parity preserving reversible compressor. Quantum Information Processing, 2014, 13( 8): 1701–1714
18 M, Valinataj M, Mirshekar H Jazayeri . Novel low-cost and fault-tolerant reversible logic adders. Computers & Electrical Engineering, 2016, 53: 56–72
19 N K, Misra B, Sen S Wairya . 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 B, Sen M, Dutta D, Banik D K, Singh B K Sikdar . 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 B, Sen S, Ganeriwal B K Sikdar . Reversible logic-based fault-tolerant nanocircuits in QCA. International Scholarly Research Notices, 2013, 2013: 850267
22 R G, Zhou Y C, Li M Q Zhang . Novel designs for fault tolerant reversible binary coded decimal adders. International Journal of Electronics, 2014, 101( 10): 1336–1356
23 E, PourAliAkbar K, Navi M, Haghparast M Reshadi . Novel optimum parity-preserving reversible multiplier circuits. Circuits, Systems, and Signal Processing, 2020, 39( 10): 5148–5168
24 L, Jamal M, Rahman H M H Babu . An optimal design of a fault tolerant reversible multiplier. In: Proceedings of 2013 IEEE International SOC Conference. 2013, 37−42
25 S, Babazadeh M Haghparast . Design of a nanometric fault tolerant reversible multiplier circuit. Journal of Basic and Applied Scientific Research, 2012, 2( 2): 1355–1361
26 M Valinataj . 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 H M, Gaur A K, Singh U Ghanekar . An efficient design of scalable reversible multiplier with testability. Journal of Circuits, Systems and Computers, 2022, 31( 10): 2250179
29 E, PourAliAkbar K, Navi M, Haghparast M Reshadi . Novel designs of fast parity-preserving reversible vedic multiplier. The CSI Journal on Computer Science and Engineering, 2019, 17( 1): 9–20
30 H M, Gaur A K, Singh U Ghanekar . Testable design of reversible circuits using parity preserving gates. IEEE Design & Test, 2018, 35( 4): 56–64
31 H M, Gaur A K, Singh U Ghanekar . Design of reversible arithmetic logic unit with built-in testability. IEEE Design & Test, 2019, 36( 5): 54–61
32 H M, Gaur A K, Singh A, Mohan M, Fujita D K Pradhan . Design of single-bit fault-tolerant reversible circuits. IEEE Design & Test, 2021, 38( 2): 89–96
33 H M, Gaur A K, Singh U Ghanekar . Simplification and modification of multiple controlled Toffoli circuits for testability. Journal of Computational Electronics, 2019, 18( 1): 356–363
34 H M, Gaur A K Singh . Design of reversible circuits with high testability. Electronics Letters, 2016, 52( 13): 1102–1104
35 M, Noorallahzadeh M, Mosleh S S, Ahmadpour J, Pal B Sen . 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 M, Noorallahzadeh M, Mosleh N K, Misra A Mehranzadeh . A novel design of reversible quantum multiplier based on multiple-control toffoli synthesis. Quantum Information Processing, 2023, 22( 4): 167
37 H M, Gaur A K, Singh U Ghanekar . Design for stuck-at fault testability in toffoli–fredkin reversible circuits. National Academy Science Letters, 2021, 44( 3): 215–220
38 A K, Singh H M, Gaur U Ghanekar . Fault detection in multiple controlled Fredkin circuits. IET Circuits, Devices & Systems, 2019, 13( 5): 723–729
39 H M, Gaur A K, Singh U Ghanekar . Offline testing of reversible logic circuits: an analysis. Integration, 2018, 62: 50–67
40 H M, Gaur A K, Singh U Ghanekar . Reversible circuits with testability using quantum controlled-not and swap gates. Indian Journal of Pure & Applied Physics, 2018, 56: 529–532
41 H M, Gaur A K, Singh U Ghanekar . A new DFT methodology for k-CNOT reversible circuits and its implementation using quantum-dot cellular automata. Optik, 2016, 127( 22): 10593–10601
42 H M, Gaur A K, Singh U Ghanekar . A comprehensive and comparative study on online testability for reversible logic. Pertanika Journal of Science & Technology, 2016, 24( 2): 245–271
43 H, Thapliyal N Ranganathan . A new reversible design of BCD adder. In: Proceedings of 2011 Design, Automation & Test in Europe. 2011, 1−4
44 R P Feynman . Quantum mechanical computers. Optics News, 1985, 11( 2): 11–20
45 T Toffoli . Reversible computing. In: Proceedings of the 7th International Colloquium on Automata, Languages, and Programming. 1980, 632−644
46 D M, Miller D, Maslov G W Dueck . A transformation based algorithm for reversible logic synthesis. In: Proceedings of 2003 Design Automation Conference. 2003, 318−323
47 A, Kole S, Hillmich K, Datta R, Wille I Sengupta . 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 M, Lewandowski N, Ranganathan M Morrison . 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 W N N, Hung X Y, Song G W, Yang J, Yang M Perkowski . 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 M, Rahman G W Dueck . Properties of quantum templates. In: Proceedings of the 4th International Workshop on Reversible Computation. 2012, 125−137
52 D, Maslov G W, Dueck D M Miller . 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 V V, Shende A K, Prasad I L, Markov J P Hayes . Synthesis of reversible logic circuits. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2003, 22( 6): 710–722
55 D M, Miller M, Soeken R Drechsler . Mapping NCV circuits to optimized Clifford+T circuits. In: Proceedings of the 6th International Conference on Reversible Computation. 2014, 163−175
56 M, Soeken M K Thomsen . White dots do matter: rewriting reversible logic circuits. In: Proceedings of the 5th International Conference on Reversible Computation. 2013, 196−208
57 E, Fredkin T Toffoli . Conservative logic. International Journal of Theoretical Physics, 1982, 21(3−4): 219−253
58 B Parhami . Computer Arithmetic: Algorithms and Hardware Designs. 2nd ed. New York: Oxford University Press, 2010
59 C R, Baugh B A Wooley . A two’s complement parallel array multiplication algorithm. IEEE Transactions on Computers, 1973, C-22( 12): 1045–1047
60 T R, Tan J P, Gaebler Y, Lin Y, Wan R, Bowler D, Leibfried D J Wineland . Multi-element logic gates for trapped-ion qubits. Nature, 2015, 528( 7582): 380–383
61 A, Kole K, Datta I Sengupta . 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
[1] FCS-22492-OF-MN_suppl_1 Download
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed