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 af dette arbejde

Datalogisk Institut

10 Citationer (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%.

Originalsprog	Engelsk
Tidsskrift	Information Processing Letters
Vol/bind	114
Udgave nummer	6
Sider (fra-til)	282-286
Antal sider	5
ISSN	0020-0190
DOI	https://doi.org/10.1016/j.ipl.2014.01.003
Status	Udgivet - 2014

Emneord

Combinatorial problems
Reversible functions
Synthesis
Upper bounds

Adgang til dokumentet

10.1016/j.ipl.2014.01.003

Citationsformater

@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

Emneord

Adgang til dokumentet

Fingeraftryk

Citationsformater