Optimal 4-bit Reversible Mixed-Polarity Toffoli Circuits
Marek Szyprowski , Paweł Kerntopf
AbstractOptimal 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.
|Publication size in sheets||0.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|
|Project||Synthesis 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
|Publication indicators||= 2.0|
|Citation count*||2 (2015-12-05)|
* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.