arXiv:0710.0664

Synthesis and Optimization of Reversible Circuits for Homogeneous Boolean Functions

Ahmed Younes

Published Oct 2, 2007• 6 citations

Abstract

Homogenous Boolean function is an essential part of any cryptographic system. The ability to construct an optimized reversible circuits for homogeneous Boolean functions might arise the possibility of building cryptographic system on novel computing paradigms such as quantum computers. This paper shows a factorization algorithm to synthesize such circuits.

DOI: 10.48550/arxiv.0710.0664

Related papers

REDUCING QUANTUM COST OF REVERSIBLE CIRCUITS FOR HOMOGENEOUS BOOLEAN FUNCTIONS

Ahmed Younes

Homogeneous Boolean functions have many applications in computing systems, e.g., cryptography. This paper presents a factorization algorithm for reducing the quantum cost of the reversible circuits for that class of Boolean functions. The algorithm reduces the multi-calculation of any common parts of the circuit. This allows Homogeneous Boolean related applications to be implemented efficiently on novel computing paradigms such as quantum computers and low power devices.

Journal of Circuits Systems and ComputersOct 26, 20106 citations

An efficient algorithm to synthesize quantum circuits and optimization

Ömercan Susam, Mustafa Altun

Quantum computers, more specifically quantum circuits, take on the eyes with their computational promises such as reversibility. In this paper, we perform synthesis and optimization of quantum circuits. In the first part, we propose a fast synthesis algorithm that implements any given reversible Boolean function with quantum gates. Instead of an exhaustive search on every given function, our algorithm creates a library of essential functions and performs sorting. As an example, to implement 4 bit circuits we only use 120 essential functions out of all 20922789888000 functions. In the second part, we optimize our circuits by using new templates. The proposed templates mainly consist of Toffoli gates with negative and positive controlling lines. These templates also show us that optimum area solutions proposed in the literature are not actually optimum; they can be improved.

IEEE International Conference on Electronics, Circuits and Systems (ICECS)Dec 1, 20142 citations

An Algorithm for Synthesis of Reversible Logic Circuits

P. Gupta, Abhinav Agrawal, Niraj Kumar Jha

Reversible logic finds many applications, especially in the area of quantum computing. A completely specified n-input, n-output Boolean function is called reversible if it maps each input assignment to a unique output assignment and vice versa. Logic synthesis for reversible functions differs substantially from traditional logic synthesis and is currently an active area of research. The authors present an algorithm and tool for the synthesis of reversible functions. The algorithm uses the positive-polarity Reed-Muller expansion of a reversible function to synthesize the function as a network of Toffoli gates. At each stage, candidate factors, which represent subexpressions common between the Reed-Muller expansions of multiple outputs, are explored in the order of their attractiveness. The algorithm utilizes a priority-based search tree, and heuristics are used to rapidly prune the search space. The synthesis algorithm currently targets the generalized n-bit Toffoli gate library. However, other algorithms exist that can convert an n-bit Toffoli gate into a cascade of smaller Toffoli gates. Experimental results indicate that the authors' algorithm quickly synthesizes circuits when tested on the set of all reversible functions of three variables. Furthermore, it is able to quickly synthesize all four-variable and most five-variable reversible functions that were in the test suite. The authors also present results for some benchmark functions widely discussed in literature and some new benchmarks that the authors have developed. The algorithm is shown to synthesize many, but not all, randomly generated reversible functions of as many as 16 variables with a maximum gate count of 25

IEEE Transactions on Computer-Aided Design of Integrated Circuits and SystemsOct 30, 2006379 citations

Fast Synthesis of Reversible Circuits Using a Sorting Algorithm and Optimization.

Ömercan Susam, Mustafa Altun

This paper studies synthesis and optimization of reversible circuits composed of Toffoli gates with negative and positive control lines. The proposed synthesis algorithm performs sorting among optimal implementations of certain functions - called as essential functions - to implement any reversible Boolean function. Essential functions comprise very small amount of all functions. For example, to implement 3 bit circuits, 28 essential functions out of all 40320 functions are needed. The proposed optimization algorithm considers both reversible and quantum circuit costs. First, reversible cost is reduced by considering adjacent gate pairs. Then, inner quantum structures of the gates are investigated and quantum optimization is performed. The proposed algorithms are evaluated on benchmark circuits in comparison with the results in the literature.

J. Multiple Valued Log. Soft Comput.Jan 1, 20174 citations

Reversible Circuit Realizations of Boolean Functions

Alex Brodsky

Reversible circuits are a concrete model of reversible computation with applications in areas such as quantum computing and analysis of cryptographic block cyphers. In 1980, Toffoli showed how to realize a Boolean function by a reversible circuit, however the resulting complexity of such circuits has remained an open problem. We investigate the reversible circuit complexity of families of Boolean functions and derive conditions that characterize whether a polynomial realization is possible. First, we derive sufficient conditions on families of Boolean functions that guarantee a polynomial-size reversible circuit realization. Namely, we show that if a Boolean function can be embedded into an even parity permutation that has a polynomial-size cycle representation, then the Boolean function can be realized by a polynomial-size reversible circuit. Furthermore, we provide a construction for the realization. Second, we provide concrete realizations for several families of Boolean functions, such as the adder, incrementor, and threshold functions, which do not necessarily satisfy the preceding condition, but still have polynomial-size realizations; this is important because such realizations will necessarily form the building blocks of quantum computers.

Kluwer Academic Publishers eBooksFeb 21, 20065 citations

Synthesis of the Optimal 4-bit Reversible Circuits

Oleg Golubitsky, Sean M. Falconer, Maslov, Dmitri

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!~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 an algorithm that synthesizes an optimal circuit for any 4-bit reversible specification. We employ several techniques to make the problem tractable. We report results from several experiments, including synthesis of random 4-bit permutations, optimal synthesis of all 4-bit linear reversible circuits, synthesis of existing benchmark functions, and distribution of optimal circuits. Our results have important implications for the design and optimization of quantum circuits, testing circuit synthesis heuristics, and performing experiments in the area of quantum information processing.

arXiv:1003.1914Mar 9, 20100 citations