Optimal 4-bit Reversible Mixed-Polarity Toffoli Circuits

Marek Szyprowski , Paweł Kerntopf


Optimal synthesis of reversible circuits is a very hard task. For example, up to year 2009 this problem had not been solved even for 4-bit reversible functions, in spite of intensive research during previous decade. In 2010, a method and a tool of practical usage for finding optimal circuits for any 4-bit reversible specification were finally developed. Namely, with sophisticated optimizations it was possible to find gate count optimal circuits for any 4-bit reversible function built from multi-control Toffoli gates. Last year, we published an extension to the algorithm, which allows to reduce the quantum cost of the resulting circuits. In this paper we present another extension to this approach. Namely, we have extended the reversible gate library to mixed-polarity multi-control Toffoli gates (i.e. with both positive and negative controls). Our experimental results for the known reversible benchmarks show that using mixed-polarity Toffoli gates gives significant savings in gate count. The paper presents results of different computational experiments including optimal 4-bit circuits for the known reversible benchmarks with respect to both gate count and quantum cost criteria.
Author Marek Szyprowski (FEIT / IN)
Marek Szyprowski,,
- The Institute of Computer Science
, Paweł Kerntopf (FEIT / IN) - [Wydział Fizyki i Informatyki Stosowanej [Uniwersytet Łódzki (UŁ)]]
Paweł Kerntopf,,
- The Institute of Computer Science
- Wydział Fizyki i Informatyki Stosowanej
Publication size in sheets0.65
Book Glück Robert, Yokoyama Tetsuo (eds.): Reversible Computation, Lecture Notes In Computer Science, vol. 7581, 2013, Heidelberg New York Dordrecht London, Springer, ISBN 978-3-642-36314-6, 241 p., DOI:10.1007/978-3-642-36315-3
ProjectSynthesis of reversible logic circuits – new approaches and algorithms. Project leader: Kerntopf Paweł, , Phone: +48 22 234 7711, start date 17-05-2010, end date 16-11-2012, II/2010/M/2, Completed
WEiTI Projekty finansowane przez MNiSW
Languageen angielski
Score (nominal)0
Publication indicators GS Citations = 2.0
Citation count*2 (2015-12-05)
Share Share

Get link to the record

* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Are you sure?