2011

Synthesis and Optimization of Reversible Circuits - A Survey

Saeedi, Mehdi, Markov, Igor L.

Understand

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, post-synthesis 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.

Built on

Irreversibility and heat generation in the computing process
Landauer, R · 1961
Earlier work this paper cites.
Theory of Self-Reproducing Automata
Von Neumann, J · 1966
Earlier work this paper cites.
Logical reversibility of computation
Bennett, C. H · 1973
Earlier work this paper cites.
Reversible computing
Toffoli, T · 1980
Earlier work this paper cites.
Conservative logic
Fredkin, E. F · 1982
Earlier work this paper cites.
Reversible logic and quantum computers
Peres, A · 1985
Earlier work this paper cites.
Graph-based algorithms for boolean function manipulation
Bryant, R · 1986
Earlier work this paper cites.
Quantum mechanical computers
Feynman, R · 1986
Earlier work this paper cites.
Computing [pi](x): An analytic method
Lagarias, J. C · 1987
Earlier work this paper cites.
Elementary gates for quantum computation
Barenco, A · 1995
Earlier work this paper cites.
Efficient networks for quantum factoring
Beckman, D · 1996
Earlier work this paper cites.
Decomposing a permutation into a conjugated tensor product
Egner, S · 1997
Earlier work this paper cites.
A silicon-based nuclear spin quantum computer
Kane, B · 1998
Earlier work this paper cites.
On The Complexity of the Hidden Weighted Bit Function for Various BDD Models
Bollig, B · 1999
Earlier work this paper cites.
Artificial intelligence search algorithms
Korf, R · 1999
Earlier work this paper cites.
Group theoretical aspects of reversible logic gates
Storme, L · 1999
Earlier work this paper cites.
Essentials of Electronic Testing for Digital, Memory and Mixed-Signal VLSI Circuits
Bushnell, M · 2000
Earlier work this paper cites.
Logic Synthesis and Verification Algorithms
Hachtel, G. D · 2000
Earlier work this paper cites.
Quantum automata and quantum grammars
Moore, C · 2000
Earlier work this paper cites.
Quantum Computation and Quantum Information
Nielsen, M · 2000
Earlier work this paper cites.
Bit permutation instructions for accelerating software cryptography
Shi, Z · 2000
Earlier work this paper cites.
Generating the group of reversible logic gates
De Vos, A · 2002
Earlier work this paper cites.
A reversible carry-look-ahead adder using control gates
Desoete, B · 2002
Earlier work this paper cites.
Realization of the Fredkin gate by three transition pulses in a nuclear magnetic resonance quantum information processor
Fei, X · 2002
Earlier work this paper cites.
Transformation rules for designing CNOT-based quantum circuits
Iwama, K · 2002
Earlier work this paper cites.
Logic synthesis of reversible wave cascades
Mishchenko, A · 2002
Earlier work this paper cites.
Principles and Practices of Interconnection Networks
Dally, W · 2003
Earlier work this paper cites.
Circuits for quantum error-correcting codes
Grassl, M · 2003
Earlier work this paper cites.
On sub-optimality and scalability of logic synthesis tools
Markov, I. L · 2003
Earlier work this paper cites.
Improved quantum cost for n n -bit Toffoli gates
Maslov, D · 2003
Earlier work this paper cites.
Architectural techniques for accelerating subword permutations with repetitions
McGregor, J. P · 2003
Earlier work this paper cites.
A transformation based algorithm for reversible logic synthesis
Miller, D. M · 2003
Earlier work this paper cites.
Synthesis of reversible logic circuits
Shende, V. V · 2003
Earlier work this paper cites.
Hydrogenic spin quantum computing in silicon: A digital approach
Skinner, A. J · 2003
Earlier work this paper cites.
Geometric theory of nonlocal two-qubit operations
Original
Zhang, J · 2003
Earlier work this paper cites.
Improved simulation of stabilizer circuits
Aaronson, S · 2004
Earlier work this paper cites.

Similar

Improved bounds for the approximate QFT
Cheung, D · 2004
Cited alongside, same era.
Discrete non-Abelian gauge theories in Josephson-junction arrays and quantum computation
Douçot, B · 2004
Cited alongside, same era.
A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
Jerrum, M · 2004
Cited alongside, same era.
A new heuristic algorithm for reversible logic synthesis
Kerntopf, P · 2004
Cited alongside, same era.
Reversible cascades with minimal garbage
Maslov, D · 2004
Cited alongside, same era.
Minimal universal two-qubit quantum circuits
Shende, V. V · 2004
Cited alongside, same era.
Photonic state tomography
Altepeter, J · 2005
Cited alongside, same era.
New structural quantum circuit simulating a Toffoli gate
Asano, M · 2005
Cited alongside, same era.
Quantum circuits with uniformly controlled one-qubit gates
Bergholm, V · 2005
Cited alongside, same era.
A new quantum ripple-carry addition circuit
Cuccaro, S. A · 2005
Cited alongside, same era.
A method for automatic program inversion based on lr(0) parsing
Glück, R · 2005
Cited alongside, same era.
Scalable multiparticle entanglement of trapped ions
Häffner, H · 2005
Cited alongside, same era.

Then

Checking equivalence of quantum circuits and states
Viamontes, G. F · 2007
Later among the works it cites.
Effects of interaction distance on quantum addition circuits
Choi, B · 2008
Later among the works it cites.
Reversible logic synthesis with Fredkin and Peres gates
Donald, J · 2008
Later among the works it cites.
Fast bit gather, bit scatter and bit permutation instructions for commodity microprocessors
Hilewitz, Y · 2008
Later among the works it cites.
Reversible computing and cellular automata - a survey
Morita, K · 2008
Later among the works it cites.
Optimal synthesis of linear reversible circuits
Patel, K. N · 2008
Later among the works it cites.
Reversible fourier transform chip
Skoneczny, M · 2008
Later among the works it cites.
A fast quantum circuit for addition with few qubits
Takahashi, Y · 2008
Later among the works it cites.
Bi-directional synthesis of 4-bit reversible circuits
Yang, G · 2008
Later among the works it cites.
Principles of a reversible programming language
Yokoyama, T · 2008
Later among the works it cites.
On the design and optimization of a quantum polynomial-time attack on elliptic curve cryptography
Cheung, D · 2009
Later among the works it cites.
Exact multiple-control Toffoli network synthesis with SAT techniques
Grosse, D · 2009
Later among the works it cites.
Shor’s quantum factoring algorithm on a photonic chip
Politi, A · 2009
Later among the works it cites.
On the CNOT-cost of TOFFOLI gates
Shende, V. V · 2009
Later among the works it cites.
Quantum Circuit Simulation
Viamontes, G · 2009
Later among the works it cites.
Temporal debugging using URDB
Original
Visan, A. M · 2009
Later among the works it cites.
BDD-based synthesis of reversible logic for large functions
Wille, R · 2009
Later among the works it cites.
Equivalence checking of reversible circuits
Wille, R · 2009
Later among the works it cites.
Rule-based optimization of reversible circuits
Arabzadeh, M · 2010
Later among the works it cites.
Recent progress in quantum algorithms
Bacon, D · 2010
Later among the works it cites.
Quantum algorithms for algebraic problems
Childs, A. M · 2010
Later among the works it cites.
Experimental realization of a controlled-NOT gate with four-photon six-qubit cluster states
Gao, W.-B · 2010
Later among the works it cites.
Synthesis of the optimal 4-bit reversible circuits
Golubitsky, O · 2010
Later among the works it cites.
Improving the NCV realization of multiple-control Toffoli gates
Miller, D · 2010
Later among the works it cites.
Reducing reversible circuit cost by adding lines
Miller, D. M · 2010
Later among the works it cites.
Quantum addition circuits and unbounded fan-out
Takahashi, Y · 2010
Later among the works it cites.
Towards a Design Flow for Reversible Logic
Wille, R · 2010
Later among the works it cites.
Fast equivalence-checking for quantum circuits
Yamashita, S · 2010
Later among the works it cites.
RCviewer+, A viewer/analyzer for reversible and quantum circuits, version 1.88
Arabzadeh, M · 2011
Closest in time.
Area-efficient multipliers based on multiple-radix representations
Dimitrov, V. S · 2011
Closest in time.
A study of optimal 4-bit reversible toffoli circuits and their synthesis
Original
Golubitsky, O · 2011
Closest in time.
An efficient conversion of quantum circuits to a linear nearest neighbor architecture
Hirata, Y · 2011
Closest in time.
Reversible logic synthesis benchmarks page
Maslov, D · 2011
Closest in time.
Reversible circuit optimization via leaving the Boolean domain
Maslov, D · 2011
Closest in time.
Constant-optimized quantum circuits for modular multiplication and exponentiation
Markov, I. L · 2012
Closest in time.
Faster quantum number factoring via circuit synthesis
Markov, I. L · 2013
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…