skip to main content
10.1145/1228784.1228812acmconferencesArticle/Chapter ViewAbstractPublication PagesglsvlsiConference Proceedingsconference-collections
Article

Exact sat-based toffoli network synthesis

Published: 11 March 2007 Publication History

Abstract

Compact realizations of reversible logic functions are of interest in the design of quantum computers. Such reversible functions are realized as a cascade of Toffoli gates. In this paper, we present the first exact synthesis algorithm for reversible functions using generalized Toffoligates. Our iterative algorithm formulates the synthesis problem with d Toffoli gates as a sequence of Boolean Satisfiability (SAT) instances. Such an instance is satisfiable if there exists a network representation with d gates. Thus, we can guarantee minimality. In addition to fully specified reversible functions, the algorithm can be applied to incompletely specified functions. For a set of benchmarks experimental results are given.

References

[1]
S. Cook. The complexity of theorem proving procedures. In 3. ACM Symposium on Theory of Computing, pages 151--158, 1971.
[2]
NEén and NSörensson. An extensible SAT solver. In SAT 2003, volume 2919 of LNCS, pages 502--518, 2004.
[3]
D. Große, X. Chen, and R. Drechsler. Exact toffoli network synthesis of reversible logic using boolean satisfiability. In IEEE Dallas/CAS Workshop, pages 51--54, 2006.
[4]
P. Gupta, A. Agrawal, and N. Jha. An algorithm for synthesis of reversible logic circuits. IEEE Trans. on CAD of Integrated Circuits and Systems, 25(11):2317--2330, 2006.
[5]
W. Hung, X. Song, G. Yang, J. Yang, and M. Perkowski. Optimal synthesis of multiple output Boolean functions using a set of quantum gates by symbolic reachability analysis. IEEE Trans. on CAD of Integrated Circuits and Systems, 25(9):1652--1663, 2006.
[6]
T. Larrabee. Test pattern generation using Boolean satisfiability. IEEE Trans. on CAD, 11:4--15, 1992.
[7]
D. Maslov. Reversible Logic Synthesis Benchmarks Page. http://www.cs.uvic.ca/dmaslov/.
[8]
D. Maslov and G.W. Dueck. Reversible cascades with minimal garbage. IEEE Trans. on CAD of Integrated Circuits and Systems, 23(11):1497--1509, 2003.
[9]
D. Maslov, G.W. Dueck, and D.M. Miller. Toffoli network synthesis with templates. IEEE Trans. on CAD of Integrated Circuits and Systems, 24(6):807--817, 2005.
[10]
D.M. Miller and G.W. Dueck. Spectral techniques for reversible logic synthesis. In 6th International Symposium on Representations and Methodology of Future Computing Technology, pages 56--62, 2003.
[11]
D.M. Miller, D. Maslov, and G.W. Dueck. A transformation based algorithm for reversible logic synthesis. In Design Automation Conf., pages 318--323, 2003.
[12]
M.A. Nielsen and I. Chuang. Quantum computation and quantum information. Cambridge University Press, 2000.
[13]
V. Shende, A. Prasad, I. Markov, and J. Hayes. Reversible logic circuit synthesis. In Int'l Conf. on CAD, pages pp. 353--360, 2002.
[14]
T. Toffoli. Reversible computing. In Wde Bakker and Jvan Leeuwen, editors, Automata, Languages and Programming, page 632. Springer, 1980. Technical Memo MIT/LCS/TM-151, MIT Lab. for Comput. Sci.

Cited By

View all
  • (2022)SAT-based Exact Synthesis of Ternary Reversible Circuits using a Functionally Complete Gate Library2022 25th Euromicro Conference on Digital System Design (DSD)10.1109/DSD57027.2022.00108(769-776)Online publication date: Aug-2022
  • (2020)A Swarm based Binary Decision Diagram (BDD) Reordering Optimizer for Reversible Circuit Synthesis2020 15th Design & Technology of Integrated Systems in Nanoscale Era (DTIS)10.1109/DTIS48698.2020.9081221(1-6)Online publication date: Apr-2020
  • (2020)Reversible Logic Synthesis Using Binary Decision Diagrams With Exploiting Efficient Reordering OperatorsIEEE Access10.1109/ACCESS.2020.30193568(156001-156016)Online publication date: 2020
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
GLSVLSI '07: Proceedings of the 17th ACM Great Lakes symposium on VLSI
March 2007
626 pages
ISBN:9781595936059
DOI:10.1145/1228784
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 March 2007

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. boolean satisfiability
  2. minimization
  3. quantum circuits
  4. reversible logic
  5. synthesis

Qualifiers

  • Article

Conference

GLSVLSI07
Sponsor:
GLSVLSI07: Great Lakes Symposium on VLSI 2007
March 11 - 13, 2007
Stresa-Lago Maggiore, Italy

Acceptance Rates

Overall Acceptance Rate 312 of 1,156 submissions, 27%

Upcoming Conference

GLSVLSI '25
Great Lakes Symposium on VLSI 2025
June 30 - July 2, 2025
New Orleans , LA , USA

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)10
  • Downloads (Last 6 weeks)0
Reflects downloads up to 27 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2022)SAT-based Exact Synthesis of Ternary Reversible Circuits using a Functionally Complete Gate Library2022 25th Euromicro Conference on Digital System Design (DSD)10.1109/DSD57027.2022.00108(769-776)Online publication date: Aug-2022
  • (2020)A Swarm based Binary Decision Diagram (BDD) Reordering Optimizer for Reversible Circuit Synthesis2020 15th Design & Technology of Integrated Systems in Nanoscale Era (DTIS)10.1109/DTIS48698.2020.9081221(1-6)Online publication date: Apr-2020
  • (2020)Reversible Logic Synthesis Using Binary Decision Diagrams With Exploiting Efficient Reordering OperatorsIEEE Access10.1109/ACCESS.2020.30193568(156001-156016)Online publication date: 2020
  • (2018)Function Design for Minimum Multiple-Control Toffoli Circuits of Reversible Adder/Subtractor Blocks and Arithmetic Logic UnitsIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.E101.A.2231E101.A:12(2231-2243)Online publication date: 1-Dec-2018
  • (2017)Exact Synthesis of Ternary Reversible Functions Using Ternary Toffoli Gates2017 IEEE 47th International Symposium on Multiple-Valued Logic (ISMVL)10.1109/ISMVL.2017.51(179-184)Online publication date: May-2017
  • (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
  • (2014)Synthesizing Optimal Switching LatticesACM Transactions on Design Automation of Electronic Systems10.1145/266163220:1(1-14)Online publication date: 18-Nov-2014
  • (2014)Challenges and advances in Toffoli network optimisationIET Computers & Digital Techniques10.1049/iet-cdt.2013.00558:4(172-177)Online publication date: Jul-2014
  • (2012)Synthesis of Reversible Circuits Using Heuristic Search MethodProceedings of the 2012 25th International Conference on VLSI Design10.1109/VLSID.2012.92(328-333)Online publication date: 7-Jan-2012
  • (2011)A novel method of synthesizing reversible logic2011 IEEE International Symposium of Circuits and Systems (ISCAS)10.1109/ISCAS.2011.5938201(2857-2860)Online publication date: May-2011
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media