Reversible Algorithms

Wen-Hsin Wang, Chia-Hui Chiu, Shu–Yu Kuo +2 more

Reversible logic plays an important role in quantum computation, which is a promising research field. The reversible logic synthesis problem focuses on generating a reversible circuit automatically and finding the lowest cost when an output function is given. The synthesis of reversible logic circuits can be formulated as a combinatorial optimization problem. This paper proposes a new evolutionary algorithm for synthesizing reversible circuits based on Quantum-Inspired Tabu Search Algorithm (QTS). The proposed algorithm uses the QTS-based approach to find fewer gates and reduce the cost of reversible circuits. This method is simpler, has better performance in computational cost, and reduce the gate counts of reversible circuits. This paper also compares experimental results with other heuristic and evolutionary algorithms. The final outcome shows that the QTS-based approach performs much better than other algorithms.

Erik D. Demaine, Jayson Lynch, Jiaying Sun

This paper presents an efficient reversible algorithm for linear regression, both with and without ridge regression. Our reversible algorithm matches the asymptotic time and space complexity of standard irreversible algorithms for this problem. Needed for this result is the expansion of the analysis of efficient reversible matrix multiplication to rectangular matrices and matrix inversion.

Osama M. Raisuddin, Suvranu De

Yi-Tzu Lo, Shu–Yu Kuo, Guo-Jyun Zeng +2 more

Reversible circuit synthesis is an important field in quantum computing, low-power design, and reversible circuit. The problem of reversible circuit synthesis is complicated and hard to solve because the input of the reversible circuit will experience a huge increase when extended to multi-bit. In this paper, a novel algorithm of reversible circuit synthesis is proposed. With the satisfied priority of positions, we can efficiently select the position which should be satisfied, and each selected gate is generated to benefit the overall situation. Therefore, the proposed algorithm is able to optimize the reversible circuit with fewer gates and can be implemented in regard to multibit reversible circuit synthesis. In addition, the gate set we used contains only Toffoli, spanning all wires. This Toffoli gate is liable to be transformed into another gate set and is helpful for algorithm design. The experiment shows that the proposed algorithm, with efficient and optimal results, is superior to others.