Upper bounds for reversible circuits based on Young subgroups

Nabila Abdessaied; Mathias Soeken; Michael Kirkedal Thomsen; Rolf Drechsler

doi:10.1016/j.ipl.2014.01.003

Upper bounds for reversible circuits based on Young subgroups

Nabila Abdessaied^*, Mathias Soeken, Michael Kirkedal Thomsen, Rolf Drechsler

^*Corresponding author for this work

Department of Computer Science

10 Citations (Scopus)

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%.

Original language	English
Journal	Information Processing Letters
Volume	114
Issue number	6
Pages (from-to)	282-286
Number of pages	5
ISSN	0020-0190
DOIs	https://doi.org/10.1016/j.ipl.2014.01.003
Publication status	Published - 2014

Access to Document

10.1016/j.ipl.2014.01.003

Cite this

@article{e2805606b7b84878bcf9cfdc96e7ef40,

title = "Upper bounds for reversible circuits based on Young subgroups",

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%.",

keywords = "Combinatorial problems, Reversible functions, Synthesis, Upper bounds",

author = "Nabila Abdessaied and Mathias Soeken and Thomsen, {Michael Kirkedal} and Rolf Drechsler",

year = "2014",

doi = "10.1016/j.ipl.2014.01.003",

language = "English",

volume = "114",

pages = "282--286",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "6",

}

TY - JOUR

T1 - Upper bounds for reversible circuits based on Young subgroups

AU - Abdessaied, Nabila

AU - Soeken, Mathias

AU - Thomsen, Michael Kirkedal

AU - Drechsler, Rolf

PY - 2014

Y1 - 2014

N2 - 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%.

AB - 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%.

KW - Combinatorial problems

KW - Reversible functions

KW - Synthesis

KW - Upper bounds

U2 - 10.1016/j.ipl.2014.01.003

DO - 10.1016/j.ipl.2014.01.003

M3 - Journal article

AN - SCOPUS:84893303513

SN - 0020-0190

VL - 114

SP - 282

EP - 286

JO - Information Processing Letters

JF - Information Processing Letters

IS - 6

ER -

Upper bounds for reversible circuits based on Young subgroups

Abstract

Access to Document

Fingerprint

Cite this