A Study of Optimal 4-bit Reversible Toffoli Circuits and Their Synthesis
arXiv:1103.2686 · doi:10.1109/TC.2011.144
Abstract
Optimal synthesis of reversible functions is a non-trivial problem. One of the major limiting factors in computing such circuits is the sheer number of reversible functions. Even restricting synthesis to 4-bit reversible functions results in a huge search space (16! {\approx} 2^{44} functions). The output of such a search alone, counting only the space required to list Toffoli gates for every function, would require over 100 terabytes of storage. In this paper, we present two algorithms: one, that synthesizes an optimal circuit for any 4-bit reversible specification, and another that synthesizes all optimal implementations. We employ several techniques to make the problem tractable. We report results from several experiments, including synthesis of all optimal 4-bit permutations, synthesis of random 4-bit permutations, optimal synthesis of all 4-bit linear reversible circuits, synthesis of existing benchmark functions; we compose a list of the hardest permutations to synthesize, and show distribution of optimal circuits. We further illustrate that our proposed approach may be extended to accommodate physical constraints via reporting LNN-optimal reversible circuits. Our results have important implications in the design and optimization of reversible and quantum circuits, testing circuit synthesis heuristics, and performing experiments in the area of quantum information processing.
arXiv commentarXiv admin note: substantial text overlap with arXiv:1003.1914
References in corpus (6)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Improved Simulation of Stabilizer Circuits
- Scalable multi-particle entanglement of trapped ions
- Benchmarking quantum control methods on a 12-qubit system
- Techniques for the Synthesis of Reversible Toffoli Networks
- Comparison of the Cost Metrics for Reversible and Quantum Logic Synthesis
Cited by in corpus (11)
- A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits
- Synthesis and Optimization of Reversible Circuits - A Survey
- Fault-Tolerant High Level Quantum Circuits: Form, Compilation and Description
- Optimization of Clifford Circuits
- Reducing Quantum Cost in Reversible Toffoli Circuits
- Reversible circuit compilation with space constraints
- 6-qubit Optimal Clifford Circuits
- An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition
- On the Complexity of the Cycles based Synthesis of Ternary Reversible Circuits
- Ancilla-Input and Garbage-Output Optimized Design of a Reversible Quantum Integer Multiplier
- Hybrid Reward-Driven Reinforcement Learning for Efficient Quantum Circuit Synthesis