research-article

Synthesis of fredkin-toffoli reversible networks

Authors:

Gerhard W. Dueck,

D. Michael MillerAuthors Info & Claims

IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Volume 13, Issue 6

Pages 765 - 769

https://doi.org/10.1109/TVLSI.2005.844284

Published: 01 June 2005 Publication History

Abstract

Reversible logic has applications in quantum computing, low power CMOS, nanotechnology, optical computing, and DNA computing. The most common reversible gates are the Toffoli gate and the Fredkin gate. We present a method that synthesizes a network with these gates in two steps. First, our synthesis algorithm finds a cascade of Toffoli and Fredkin gates with no backtracking and minimal look-ahead. Next we apply transformations that reduce the number of gates in the network. Transformations are accomplished via template matching. The basis for a template is a network with gates that realizes the identity function. If a sequence of gates in the network to be reduced matches a sequence of gates comprising more than half of a template, then a transformation that reduces the gate count can be applied. We have synthesized all three input, three output reversible functions and here compare our results to the optimal results. We also present the results of applying our synthesis tool to obtain networks for a number of benchmark functions.

References

[1]

A. Agrawal and N. K. Jha, "Synthesis of reversible logic," Proc. DATE, pp. 21 384-21 385, Feb. 2004.

[2]

A. Barenco, C. H. Bennett, R. Cleve, D. P. DiVinchenzo, N. Margolus, P. Shor, T. Sleator, J. A. Smolin, and H. Weinfurter, "Elementary gates for quantum computation," Phys. Rev. A, vol. 52, pp. 3457-3467, 1995.

[3]

C. H. Bennett, "Logical reversibility of computation," IBM J. Res. Development, vol. 17, pp. 525-532, Nov. 1973.

Digital Library

[4]

G. W. Dueck and D. Maslov, "Reversible function synthesis with minimum garbage outputs," in Proc. 6th Int. Symp. Representations and Methodology of Future Computing Technologies, Mar. 2003, pp. 154-161.

[5]

G.W. Dueck, D. Maslov, and D. M. Miller, "Transformation-based synthesis of networks of Toffoli/Fredkin gates," in Proc. IEEE Canadian Conf. Electrical and Computer Engineering, May 2003, pp. 211-214.

[6]

X. Fei, D. Jiang-Feng, S. Ming-Jun, Z. Xian-Yi, H. Rong-Dian, and W. Ji-Hui, "Realization of the Fredkin gate by three transition pulses in a nuclear magnetic resonance quantum information processor," Chinese Phys. Lett., vol. 19, no. 8, pp. 1048-1050, 2002.

[7]

R. Feynman, "Quantum mechanical computers," Opt. News, vol. 11, pp. 11-20, 1985.

[8]

E. Fredkin and T. Toffoli, "Conservative logic," Int. J. Theoretical Phys., vol. 21, pp. 219-253, 1982.

[9]

K. Iwama, Y. Kambayashi, and S. Yamashita, "Transformation rules for designing CNOT-based quantum circuits," Proc. DAC, pp. 419-424, Jun. 2002.

[10]

R. Landauer, "Irreversibility and heat generation in the computing process," IBM J. Res. Develop., vol. 5, pp. 183-191, 1961.

Digital Library

[11]

D. Maslov and G. Dueck, "Improved quantum cost for -bit Toffoli gates," IEE Electron. Lett., vol. 39, no. 25, pp. 1790-1791, Dec. 2003.

[12]

D. Maslov and G. W. Dueck, "Garbage in reversible design of multiple output functions," in Proc. 6th Int. Symp. Representations and Methodology of Future Computing Technologies, Mar. 2003, pp. 162-170.

[13]

D. Maslov, N. Scott, and G. W. Dueck. (2004, Aug.) Reversible logic synthesis benchmarks page. {Online}. Available: http://www.cs.uvic.ca/ ~dmaslov/

[14]

D. M. Miller and G.W. Dueck, "Spectral techniques for reversible logic synthesis," in Proc. 6th Int. Symp. Representations and Methodology of Future Computing Technologies, Mar. 2003, pp. 56-62.

[15]

D. M. Miller, D. Maslov, and G. W. Dueck, "A transformation based algorithm for reversible logic synthesis," Proc. DAC, pp. 318-323, Jun. 2003.

[16]

A. Mishchenko and M. Perkowski, "Logic synthesis of reversible wave cascades," Proc. IWLS, pp. 197-202, Jun. 2002.

[17]

M. Nielsen and I. Chuang, Quantum Computation and Quantum Information. Cambridge, U.K.: Cambridge Univ. Press, 2000.

Digital Library

[18]

V. V. Shende, A. K. Prasad, I. L. Markov, and J. P. Hayes, "Synthesis of reversible logic circuits," IEEE Trans. Computer-Aided Design Integr. Syst., vol. 22, no. 6, pp. 723-729, Jun. 2003.

Digital Library

[19]

T. Toffoli, "Reversible computing,"MIT Lab., Comp. Sci., Tech. Memo MIT/LCS/TM-151, 1980.

[20]

V. V. Zhirnov, R. K. Cavin, J. A. Hutchby, and G. I. Bourianoff, "Limits to binary logic switch scaling--A gedanken model," Proc. IEEE, vol. 91, no. 11, pp. 1934-1939, Nov. 2003.

Cited By

Bernasconi ABerti ACiriani VDel Corso GFulginiti I(2023)XOR-AND-XOR Logic Forms for Autosymmetric Functions and Applications to Quantum ComputingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.321321442:6(1861-1872)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1109/TCAD.2022.3213214
He JXu HFeng SDu M(2022)Heuristic Reordering Strategy for Quantum Circuit Mapping on LNN ArchitecturesComputational Intelligence and Neuroscience10.1155/2022/17659552022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/1765955
Iten RMoyard RMetger TSutter DWoerner S(2022)Exact and Practical Pattern Matching for Quantum Circuit OptimizationACM Transactions on Quantum Computing10.1145/34983253:1(1-41)Online publication date: 22-Jan-2022
https://dl.acm.org/doi/10.1145/3498325
Show More Cited By

Recommendations

Fredkin/Toffoli Templates for Reversible Logic Synthesis
ICCAD '03: Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design

Reversible logic has applications in quantum computing, lowpower CMOS, nanotechnology, optical computing, and DNAcomputing. The most common reversible gates are the Toffoli gate and the Fredkin gate. Our synthesis algorithm first finds a cascade of ...
Reversible logic synthesis with Fredkin and Peres gates

Reversible logic has applications in low-power computing and quantum computing. Most reversible logic synthesis methods are tied to particular gate types, and cannot synthesize large functions. This article extends RMRLS, a reversible logic synthesis ...
Toffoli network synthesis with templates

Reversible logic functions can be realized as networks of Toffoli gates. The synthesis of Toffoli networks can be divided into two steps. First, find a network that realizes the desired function. Second, transform the network such that it uses fewer ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Very Large Scale Integration (VLSI) Systems

IEEE Transactions on Very Large Scale Integration (VLSI) Systems Volume 13, Issue 6

June 2005

135 pages

ISSN:1063-8210

Issue’s Table of Contents

Copyright © 2005.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 June 2005

Revised: 08 September 2004

Received: 18 March 2004

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bernasconi ABerti ACiriani VDel Corso GFulginiti I(2023)XOR-AND-XOR Logic Forms for Autosymmetric Functions and Applications to Quantum ComputingIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2022.321321442:6(1861-1872)Online publication date: 1-Jun-2023
https://dl.acm.org/doi/10.1109/TCAD.2022.3213214
He JXu HFeng SDu M(2022)Heuristic Reordering Strategy for Quantum Circuit Mapping on LNN ArchitecturesComputational Intelligence and Neuroscience10.1155/2022/17659552022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/1765955
Iten RMoyard RMetger TSutter DWoerner S(2022)Exact and Practical Pattern Matching for Quantum Circuit OptimizationACM Transactions on Quantum Computing10.1145/34983253:1(1-41)Online publication date: 22-Jan-2022
https://dl.acm.org/doi/10.1145/3498325
Shahidi SEtemadi Borujeni S(2021)A new method for reversible circuit synthesis using a Simulated Annealing algorithm and don’t-caresJournal of Computational Electronics10.1007/s10825-020-01620-420:1(718-734)Online publication date: 1-Feb-2021
https://dl.acm.org/doi/10.1007/s10825-020-01620-4
Sultana MChaudhuri ASengupta DChaudhuri A(2019)Toffoli Netlist and QCA implementations for existing four variable reversible gatesMicrosystem Technologies10.1007/s00542-018-4065-125:5(1987-2009)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1007/s00542-018-4065-1
Chaudhuri ASultana MSengupta DChaudhuri CChaudhuri A(2019)A reversible approach to two's complement addition using a novel reversible TCG gate and its 4 dot 2 electron QCA architectureMicrosystem Technologies10.1007/s00542-018-4042-825:5(1965-1975)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1007/s00542-018-4042-8
Abubakar MJung LZakaria NYounes AAbdel-Aty A(2017)Reversible circuit synthesis by genetic programming using dynamic gate librariesQuantum Information Processing10.1007/s11128-017-1609-816:6(1-24)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1007/s11128-017-1609-8
Kianpour MSabbaghi-Nadooshan R(2017)Novel 8-bit reversible full adder/subtractor using a QCA reversible gateJournal of Computational Electronics10.1007/s10825-017-0963-116:2(459-472)Online publication date: 1-Jun-2017
https://dl.acm.org/doi/10.1007/s10825-017-0963-1
Mirkhani ZMohammadzadeh N(2016)Physical synthesis of quantum circuits using templatesQuantum Information Processing10.1007/s11128-016-1377-x15:10(4117-4135)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1007/s11128-016-1377-x
Nagamani AAshwin SAbhishek BAgrawal V(2016)An Exact approach for Complete Test Set Generation of Toffoli-Fredkin-Peres based Reversible CircuitsJournal of Electronic Testing: Theory and Applications10.1007/s10836-016-5574-432:2(175-196)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1007/s10836-016-5574-4
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents