Synthesis and Optimization of Reversible Circuits - A Survey

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, 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. We conclude the survey by outlining key open challenges in synthesis of reversible and quantum logic, as well as most common misconceptions.

34 pages, 15 figures, 2 tables

References in corpus (39)

• Elementary gates for quantum computation
• Improved Simulation of Stabilizer Circuits
• Scalable multi-particle entanglement of trapped ions
• Synthesis of Quantum Logic Circuits
• Classical simulation of quantum many-body systems with a tree tensor network
• Shor's quantum factoring algorithm on a photonic chip
• A geometric theory of non-local two-qubit operations
• Quantum algorithms for algebraic problems
• A new quantum ripple-carry addition circuit
• Minimal Universal Two-qubit Quantum Circuits
• Efficient Networks for Quantum Factoring
• Quantum Circuit Simplification and Level Compaction
• Synthesis of Quantum Circuits for Linear Nearest Neighbor Architectures
• Benchmarking quantum control methods on a 12-qubit system
• Techniques for the Synthesis of Reversible Toffoli Networks
• Hydrogenic Spin Quantum Computing in Silicon: A Digital Approach
• Fast Quantum Modular Exponentiation
• Quantum circuits with uniformly controlled one-qubit gates
• Improved Quantum Cost for n-bit Toffoli Gates
• Reversible Circuit Synthesis Using a Cycle-Based Approach
• Quantum Circuit Placement
• A Study of Optimal 4-bit Reversible Toffoli Circuits and Their Synthesis
• Discrete non-Abelian gauge theories in two-dimensional lattices and their realizations in Josephson-junction arrays
• Experimental Realization of a Controlled-NOT Gate with Four-Photon Six-Qubit Cluster States
• Decompositions of general quantum gates
• Linear Depth Stabilizer and Quantum Fourier Transformation Circuits with no Auxiliary Qubits in Finite Neighbor Quantum Architectures
• A Library-Based Synthesis Methodology for Reversible Logic
• Quantum Error Correction on Linear Nearest Neighbor Qubit Arrays
• Shor's algorithm on a nearest-neighbor machine
• Reversible Circuit Optimization via Leaving the Boolean Domain
• A Novel Synthesis Algorithm for Reversible Circuits
• Using error correction to determine the noise model
• Single spin measurement using cellular automata techniques
• Faster Quantum Number Factoring via Circuit Synthesis
• On the Effect of Quantum Interaction Distance on Quantum Addition Circuits
• Computation at a distance
• Temporal Debugging using URDB
• Fast Equivalence-checking for Quantum Circuits
• New Structural Quantum Circuit Simulating a Toffoli Gate

Cited by in corpus (50)

• Limits on Fundamental Limits to Computation
• Automated Search for new Quantum Experiments
• Automated optimization of large quantum circuits with continuous parameters
• Valleytronics in merging Dirac cones: All-electric-controlled valley filter, valve and universal reversible logic gate
• Quantum Algorithm Implementations for Beginners
• Basic circuit compilation techniques for an ion-trap quantum machine
• Computer-inspired Quantum Experiments
• Efficient CMOS Invertible Logic Using Stochastic Computing
• Linear-Depth Quantum Circuits for n-qubit Toffoli gates with no Ancilla
• Verified compilation of space-efficient reversible circuits
• Logic circuits from zero forcing
• Reversible circuit compilation with space constraints
• Wire Recycling for Quantum Circuit Optimization
• Decomposition of bipartite and multipartite unitary gates into the product of controlled unitary gates
• Solving search problems by strongly simulating quantum circuits
• Depth-Optimized Reversible Circuit Synthesis
• Topological-Graph Dependencies and Scaling Properties of a Heuristic Qubit-Assignment Algorithm
• Application of Permutation Group Theory in Reversible Logic Synthesis
• Gaussian Elimination versus Greedy Methods for the Synthesis of Linear Reversible Circuits
• A Regular Representation of Quantum Circuits
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Complexity Analysis of Reversible Logic Synthesis
• Finding solutions to the integer case constraint satisfiability problem using Grover's algorithm
• Automatic Depth-Optimized Quantum Circuit Synthesis for Diagonal Unitary Matrices with Asymptotically Optimal Gate Count
• Reversible Logic Synthesis with Minimal Usage of Ancilla Bits
• Signal processing techniques for efficient compilation of controlled rotations in trapped ions
• Synthesis of Topological Quantum Circuits
• Efficient ancilla-free reversible and quantum circuits for the Hidden Weighted Bit function
• Reinforcement Learning Generation of 4-Qubits Entangled States
• Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs
• High Convergence Rates of CMOS Invertible Logic Circuits Based on Many-Body Hamiltonians
• That is not dead which can eternal lie: the aestivation hypothesis for resolving Fermi's paradox
• An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition
• Software Pauli Tracking for Quantum Computation
• A finite alternation result for reversible boolean circuits
• Ancilla-free synthesis of large reversible functions using binary decision diagrams
• Tight Bounds on the Spooky Pebble Game: Recycling Qubits with Measurements
• Ancilla-free Reversible Logic Synthesis via Sorting
• Reversible Logic Circuit Complexity Analysis via Functional Decomposition
• Categorical Semantics of Reversible Pattern-Matching
• Cayley graphs and analysis of quantum cost for reversible circuit synthesis
• Asymptotically optimal synthesis of reversible circuits
• Statistical distribution of the reversible gates: what percentage of them are self-inverse?
• Faster manipulation of large quantum circuits using wire label reference diagrams
• Structured decomposition for reversible Boolean functions
• MIO: Multiverse Debugging in the Face of Input/Output -- Extended Version with Additional Appendices
• Generalised Precoded Spatial Modulation for Integrated Wireless Information and Power Transfer
• Quantum Circuit Optimization by Graph Coloring
• Digital Circuits Implementation On Rpga Simulator
• Fault Tolerant Synthesis of Reversible Circuits