Skip to main content
Article
An Improved Factorization Approach to Reversible Circuit Synthesis Based on EXORs of Products of EXORs
Multiple-Valued Logic (ISMVL), 2016 IEEE 46th International Symposium on
  • Linh Tran, Portland State University
  • Addison Gronquist, Portland State University
  • Marek Perkowski, Portland State University
  • John S. Caughman, IV, Portland State University
Document Type
Citation
Publication Date
7-21-2016
Abstract
This paper introduces new algorithms to synthesize reversible functions using EXOR-sum of Products-of-EXOR-sums (EPOE) structures. The motivation for using these structures is to reduce the number of as well as the sizes of multiple controlled Toffoli gates, and thus the quantum cost. To achieve these reductions the paper generalizes from existing 2-level AND-EXOR structures (ESOP) commonly used in reversible logic to a mixture of 3-level EXOR-AND-EXOR structures and ESOPs. Our approach can be applied to reversible and permutative quantum circuits to synthesize single output functions on to an output line, with no additional ancilla bits. A comparison of the ESOP minimizer EXORCISM-4 and two variants of the EPOE minimizer, called EPOEM-1s and EPOEM-2, is presented. The results show that EPOE circuits do in fact achieve the above-stated cost reductions, in particular when expressed in terms of Maslov's quantum cost, the metric commonly used in quantum circuit synthesis.
DOI
10.1109/ISMVL.2016.56
Persistent Identifier
http://archives.pdx.edu/ds/psu/20211
Citation Information
L. Tran, A. Gronquist, M. Perkowski and J. Caughman, "An Improved Factorization Approach to Reversible Circuit Synthesis Based on EXORs of Products of EXORs," 2016 IEEE 46th International Symposium on Multiple-Valued Logic (ISMVL), Sapporo, 2016, pp. 37-43.