2011/10/31 by Mehdi Saeedi, Igor L. Markov · 2 citations
Computer Science · Physics and Astronomy · #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum-Dot Cellular Automata #cs.ET #quant-ph
paper · pdf · doi:10.1145/2431211.2431220
published as M. Saeedi and I. L. Markov, "Synthesis and Optimization of Reversible Circuits - A Survey", ACM Computing Surveys, 45, 2, Article 21 (34 pages), 2013 · 34 pages, 15 figures, 2 tables
openalex publication_date 2013/02/01 · arxiv created 2013/03/20 · arxiv updated 2013/03/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Reversible logic circuits have been historically motivated by theoretical research in low-power electronics as well as practical improvement of bit manipulation transforms in cryptography and computer graphics. Recently, reversible circuits have attracted interest as components of quantum algorithms, as well as in photonic and nano-computing technologies where some switching devices offer no signal gain. Research in generating reversible logic distinguishes between circuit synthesis, postsynthesis optimization, and technology mapping. In this survey, we review algorithmic paradigms—search based, cycle based, transformation based, and BDD based—as well as specific algorithms for reversible synthesis, both exact and heuristic. We conclude the survey by outlining key open challenges in synthesis of reversible and quantum logic, as well as most common misconceptions.