Data structures and algorithms for simplifying reversible circuits
Aditya K. Prasad, Vivek Shende, Igor L. Markov, John P. Hayes, Ketan N. Patel · ACM Journal on Emerging Technologies in Computing Systems · 2006
Reversible logic is motivated by low-power design, quantum circuits, and nanotechnology. We develop a compact representation of small reversible circuits to generate and store optimal circuits for all 40,320 three-input reversible functions, and millions of four-input circuits. This allows implementing a function optimally in constant time for use in the peephole optimization of larger circuits produced by existing techniques, and guarantees that every three-bit subcircuit is optimal. To generate subcircuits, we use a graph-based data structure and algorithms for circuit restructuring. Finally, we demonstrate a suboptimal circuit for which peephole optimization fails.