Function Design for Minimum Multiple-Control Toffoli Circuits of Reversible Adder/Subtractor Blocks and Arithmetic Logic Units

Md Belayet ALI  Takashi HIRAYAMA  Katsuhisa YAMANAKA  Yasuaki NISHITANI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E101-A   No.12   pp.2231-2243
Publication Date: 2018/12/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E101.A.2231
Type of Manuscript: Special Section PAPER (Special Section on VLSI Design and CAD Algorithms)
Category: 
Keyword: 
reversible function,  reversible adder/subtractor,  reversible arithmetic logic unit,  incompletely-specified function,  operation assignment,  quantum cost,  multiple-control Toffoli,  

Full Text: PDF(800.9KB)
>>Buy this Article


Summary: 
In this paper, we propose a design of reversible adder/subtractor blocks and arithmetic logic units (ALUs). The main concept of our approach is different from that of the existing related studies; we emphasize the function design. Our approach of investigating the reversible functions includes (a) the embedding of irreversible functions into incompletely-specified reversible functions, (b) the operation assignment, and (c) the permutation of function outputs. We give some extensions of these techniques for further improvements in the design of reversible functions. The resulting reversible circuits are smaller than that of the existing design in terms of the number of multiple-control Toffoli gates. To evaluate the quantum cost of the obtained circuits, we convert the circuits to reduced quantum circuits for experiments. The results also show the superiority of our realization of adder/subtractor blocks and ALUs in quantum cost.