Synthesis and optimization of reversible circuits—a survey
Top Cited Papers
- 1 February 2013
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Computing Surveys
- Vol. 45 (2), 1-34
- https://doi.org/10.1145/2431211.2431220
Abstract
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.Keywords
Other Versions
Funding Information
- University of Southern California
This publication has 85 references indexed in Scilit:
- Reversible logic synthesis with Fredkin and Peres gatesACM Journal on Emerging Technologies in Computing Systems, 2008
- Benchmarking Quantum Control Methods on a 12-Qubit SystemPhysical Review Letters, 2006
- A layered software architecture for quantum computing design toolsComputer, 2006
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entriesJournal of the ACM, 2004
- Hydrogenic Spin Quantum Computing in Silicon: A Digital ApproachPhysical Review Letters, 2003
- Realization of the Fredkin Gate by Three Transition Pulses in a Nuclear Magnetic Resonance Quantum Information ProcessorChinese Physics Letters, 2002
- Quantum automata and quantum grammarsTheoretical Computer Science, 2000
- Computing π(x): An analytic methodJournal of Algorithms, 1987
- Quantum mechanical computersFoundations of Physics, 1986
- Conservative logicInternational Journal of Theoretical Physics, 1982