research-article

Upper bounds for reversible circuits based on Young subgroups

Authors:

Nabila Abdessaied,

Mathias Soeken,

Michael Kirkedal Thomsen,

Rolf DrechslerAuthors Info & Claims

Information Processing Letters, Volume 114, Issue 6

Pages 282 - 286

https://doi.org/10.1016/j.ipl.2014.01.003

Published: 01 June 2014 Publication History

Abstract

We present tighter upper bounds on the number of Toffoli gates needed in reversible circuits. Both multiple controlled Toffoli gates and mixed polarity Toffoli gates have been considered for this purpose. The calculation of the bounds is based on a synthesis approach based on Young subgroups that results in circuits using a more generalized gate library. Starting from an upper bound for this library we derive new bounds which improve the existing bound by around 77%. We present new upper bounds on the number of Toffoli gates in reversible circuits.The idea is to use a synthesis method based on Young subgroups as starting point.One technique derives the bounds based on function decomposition.Another technique is based on existing ESOP upper bounds.The best new upper bound improves the existing one by around 77%.

References

[1]

De Vos, A., Reversible Computing: Fundamentals, Quantum Computing and Applications. 2010. Wiley.

Digital Library

[2]

Knill, E., Laflamme, R. and Milburn, G.J., A scheme for efficient quantum computation with linear optics. Nature. v409 i1. 46-52.

[3]

Ren, J., Semenov, V.K., Polyakov, Y.A., Averin, D.V. and Tsai, J.S., Progress towards reversible computing with nSQUID arrays. IEEE Trans. Appl. Supercond. v19 i3. 961-967.

[4]

Houri, S., Valentian, A. and Fanet, H., Comparing CMOS-based and NEMS-based adiabatic logic circuits. In: Lect. Notes Comput. Sci., vol. 7948. pp. 36-45.

Digital Library

[5]

Athas, W.C. and Svensson, L.J., Reversible logic issues in adiabatic CMOS. In: Workshop on Physics and Computation, pp. 111-118.

[6]

Gupta, P., Agrawal, A. and Jha, N.K., An algorithm for synthesis of reversible logic circuits. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. v25 i11. 2317-2330.

Digital Library

[7]

De Vos, A. and Van Rentergem, Y., Young subgroups for reversible computers. Adv. Math. Commun. v2 i2. 183-200.

[8]

Soeken, M., Wille, R., Hilken, C., Przigoda, N. and Drechsler, R., Synthesis of reversible circuits with minimal lines for large functions. In: Asian South-Pacific Design Automation Conference, pp. 59-70.

[9]

Mohammadi, M. and Eshghi, M., On figures of merit in reversible and quantum logic designs. Quantum Inf. Process. v8 i4. 297-318.

Digital Library

[10]

Maslov, D. and Dueck, G.W., Reversible cascades with minimal garbage. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. v23 i11. 1497-1509.

Digital Library

[11]

Saeedi, M., Zamani, M.S., Sedighi, M. and Sasanian, Z., Reversible circuit synthesis using a cycle-based approach. ACM J. Emerg. Technol. Comput. Syst. v6 i4. 13

Digital Library

[12]

Groíe, D., Wille, R., Dueck, G.W. and Drechsler, R., Exact multiple control Toffoli network synthesis with SAT techniques. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. v28 i5. 703-715.

Digital Library

[13]

Wille, R., Soeken, M., Przigoda, N. and Drechsler, R., Exact synthesis of Toffoli gate circuits with negative control lines. In: International Symposium on Multiple-Valued Logic, pp. 69-74.

Digital Library

[14]

Sasao, T., AND-EXOR expressions and their optimization. In: Sasao, T. (Ed.), Logic Synthesis and Optimization, Kluwer Academic Publisher. pp. 287-312.

[15]

Sasao, T., EXMIN2: A simplification algorithm for exclusive-OR-sum-of-products expressions for multiple-valued-input two-valued-output functions. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. v12 i5. 621-632.

Digital Library

[16]

Mishchenko, A. and Perkowski, M., Fast heuristic minimization of exclusive-sums-of-products. In: International Workshop on Applications of the Reed-Muller Expansion in Circuit Design, pp. 242-250.

[17]

Hirayama, T. and Nishitani, Y., Exact minimization of AND-EXOR expressions of practical benchmark functions. J. Circuits Syst. Comput. v18 i3. 465-486.

[18]

Shende, V.V., Prasad, A.K., Markov, I.L. and Hayes, J.P., Synthesis of reversible logic circuits. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. v22 i6. 710-722.

Digital Library

[19]

Miller, D.M., Maslov, D. and Dueck, G.W., A transformation based algorithm for reversible logic synthesis. In: Design Automation Conference, pp. 318-323.

Digital Library

[20]

Soeken, M. and Thomsen, M.K., White dots do matter: Rewriting reversible logic circuits. In: Lect. Notes Comput. Sci., vol. 7948. pp. 196-208.

Digital Library

[21]

Gaidukov, A., Algorithm to derive minimum ESOP for 6-variable function. In: International Workshop on Boolean Problems, pp. 141-148.

Cited By

Biswal LBhattacharjee DChakrabarti AChattopadhyay A(2024)Synthesis Techniques for Fault-tolerant Quantum Circuit Implementation using Clifford+Z-groupACM Transactions on Quantum Computing10.1145/36732405:3(1-14)Online publication date: 14-Jun-2024
https://dl.acm.org/doi/10.1145/3673240
Abdessaied NAmy MDrechsler RSoeken M(2016)Complexity of reversible circuits and their quantum implementationsTheoretical Computer Science10.1016/j.tcs.2016.01.011618:C(85-106)Online publication date: 7-Mar-2016
https://dl.acm.org/doi/10.1016/j.tcs.2016.01.011
Soeken MTague LDueck GDrechsler R(2016)Ancilla-free synthesis of large reversible functions using binary decision diagramsJournal of Symbolic Computation10.1016/j.jsc.2015.03.00273:C(1-26)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1016/j.jsc.2015.03.002

Recommendations

Complexity of reversible circuits and their quantum implementations

We provide an extensive overview of upper bounds on the number of gates needed in reversible and quantum circuits. As reversible gate libraries we consider single-target gates, mixed-polarity multiple-controlled Toffoli gates, and the set consisting of ...
Synthesis and optimization of multiple-valued combinational and sequential reversible circuits with don't cares

In this paper, a synthesis method for combinational multiple-valued reversible logic (MVRL) circuits is proposed. This algorithm can use the don't care values in the synthesis process to obtain the optimal circuit with respect to quantum cost. The ...
Fredkin-Enabled Transformation-Based Reversible Logic Synthesis
ISMVL '15: Proceedings of the 2015 IEEE 45th International Symposium on Multiple-Valued Logic

Reversible computation is gaining increasing relevance in the context of several post-CMOS technologies, the most prominent of those being quantum computing. The problem of implementing a given Boolean function using a set of elementary reversible logic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Copyright © Elsevier B.V.

Publisher

Elsevier North-Holland, Inc.

United States

Publication History

Published: 01 June 2014

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 03 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Biswal LBhattacharjee DChakrabarti AChattopadhyay A(2024)Synthesis Techniques for Fault-tolerant Quantum Circuit Implementation using Clifford+Z-groupACM Transactions on Quantum Computing10.1145/36732405:3(1-14)Online publication date: 14-Jun-2024
https://dl.acm.org/doi/10.1145/3673240
Abdessaied NAmy MDrechsler RSoeken M(2016)Complexity of reversible circuits and their quantum implementationsTheoretical Computer Science10.1016/j.tcs.2016.01.011618:C(85-106)Online publication date: 7-Mar-2016
https://dl.acm.org/doi/10.1016/j.tcs.2016.01.011
Soeken MTague LDueck GDrechsler R(2016)Ancilla-free synthesis of large reversible functions using binary decision diagramsJournal of Symbolic Computation10.1016/j.jsc.2015.03.00273:C(1-26)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1016/j.jsc.2015.03.002

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents