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 (17)

• Scalable multi-particle entanglement of trapped ions
• Synthesis of Quantum Logic Circuits
• Shor's quantum factoring algorithm on a photonic chip
• A new quantum ripple-carry addition circuit
• Quantum Circuit Simplification and Level Compaction
• Synthesis of Quantum Circuits for Linear Nearest Neighbor Architectures
• Benchmarking quantum control methods on a 12-qubit system
• Fast Quantum Modular Exponentiation
• Quantum Circuit Placement
• Linear Depth Stabilizer and Quantum Fourier Transformation Circuits with no Auxiliary Qubits in Finite Neighbor Quantum Architectures
• 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
• Using error correction to determine the noise model
• Faster Quantum Number Factoring via Circuit Synthesis
• Computation at a distance
• Temporal Debugging using URDB

Cited by in corpus (49)

• 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
• 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
• Gaussian Elimination versus Greedy Methods for the Synthesis of Linear Reversible Circuits
• Application of Permutation Group Theory in Reversible Logic Synthesis
• A Regular Representation of Quantum Circuits
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems
• Reversible Logic Synthesis with Minimal Usage of Ancilla Bits
• Finding solutions to the integer case constraint satisfiability problem using Grover's algorithm
• Complexity Analysis of Reversible Logic Synthesis
• Automatic Depth-Optimized Quantum Circuit Synthesis for Diagonal Unitary Matrices with Asymptotically Optimal Gate Count
• 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
• Software Pauli Tracking for Quantum Computation
• An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition
• A finite alternation result for reversible boolean circuits
• Ancilla-free synthesis of large reversible functions using binary decision diagrams
• Ancilla-free Reversible Logic Synthesis via Sorting
• Tight Bounds on the Spooky Pebble Game: Recycling Qubits with Measurements
• Reversible Logic Circuit Complexity Analysis via Functional Decomposition
• Categorical Semantics of Reversible Pattern-Matching
• Statistical distribution of the reversible gates: what percentage of them are self-inverse?
• Asymptotically optimal synthesis of reversible circuits
• Cayley graphs and analysis of quantum cost for reversible circuit synthesis
• Structured decomposition for reversible Boolean functions
• Faster manipulation of large quantum circuits using wire label reference diagrams
• MIO: Multiverse Debugging in the Face of Input/Output -- Extended Version with Additional Appendices
• Digital Circuits Implementation On Rpga Simulator
• Quantum Circuit Optimization by Graph Coloring
• Generalised Precoded Spatial Modulation for Integrated Wireless Information and Power Transfer
• Fault Tolerant Synthesis of Reversible Circuits