Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Constructive Reversible Logic Synthesis for Boolean Functions with Special Properties

Anupam Chattopadhyay, Soumajit Majumder, Chander Chandak, Nahian Chowdhury

Published Jan 1, 2014• 6 citations
Publisher
DOI
10.1007/978-3-319-08494-7_8

Related papers

Synthesis of Boolean Functions in Reversible Logic

Robert Wille, Rolf Drechsler

Synthesis lectures on digital circuits and systems•Jan 1, 2010•6 citations

Efficient reversible and quantum implementations of symmetric Boolean functions

D. Maslov

It is a well-known fact in logic design that synthesis of some special classes of Boolean functions is often easier than the synthesis of a general unrestricted specification. In reversible logic, well-scaled synthesis methods with a reasonably small cost of the associated implementation have been found for only a few classes of functions. This includes synthesis of multiple-output symmetric and reversible linear functions. The author presents an efficient reversible/quantum synthesis method for the class of multiple-output symmetric functions. The method is purely theoretical, therefore its scaling on functions with a large number of inputs/outputs requires minimal resources. The author calculates garbage, i.e. the number of outputs that are not required by the function specification, the number of reversible gates, and the quantum cost of the presented implementations. The proposed approach is then applied to the synthesis of benchmark functions. Comparison of the designs to the previously reported implementations is favourable.

IEE Proceedings - Circuits Devices and Systems•Jan 1, 2006•16 citations

Algorithm for constructing minimal representations of multiple-output Boolean functions in the reversible logic circuits

S. F. Vinokurov, L. V. Riabets, S. I. Todikov +1 more

In this paper, we study the problem Boolean function's representation in a class of reversible circuits. Each Boolean function is associated with reversible function, which is implemented by a reversible circuit. Reversible circuits are built from Toffoli elements. An operator approach is used for description of this representation. At building of reversible circuit the algorithm of finding of the minimum representation of Boolean function in a class of the extended polarized Zhegalkin polynomials is applied. The foundation of this algorithm is made by a embedding of a special operator form (SOF) of function in certain classes of operators. Previously generated library with the components corresponding to certain operators is used at construction of a Boolean function's SOF. Operators of a SOF, and the corresponding multiple-output reversible function, define the minimal reversible circuit for a given Boolean function.

IEEE International Conference on Soft Computing and Measurements (SCM)•May 1, 2017•1 citation

Exact Synthesis of Reversible Logic

Robert Wille, Rolf Drechsler

Springer eBooks•Jan 1, 2010•1 citation

Complexity Analysis of Reversible Logic Synthesis

Anupam Chattopadhyay, Chander Chandak, Kaushik Chakraborty

Reversible logic circuit is a necessary construction for achieving ultra low power dissipation as well as for prominent post-CMOS computing technologies such as Quantum computing. Consequently automatic synthesis of a Boolean function using elementary reversible logic gates has received significant research attention in recent times, creating the domain of reversible logic synthesis. In this paper, we study the complexity of reversible logic synthesis. The problem is separately studied for bounded-ancilla and ancilla-free optimal synthesis approaches. The computational complexity for both cases are linked to known/presumed hard problems. Finally, experiments are performed with a shortest-path based reversible logic synthesis approach and a (0-1) ILP-based formulation.

arXiv:1402.0491•Feb 3, 2014•12 citations

A new heuristic algorithm for reversible logic synthesis

Kerntopf

ACM/IEEE Design Automation Conference (DAC)•Jan 1, 2004•0 citations
It is a well-known fact in logic design that synthesis of some special classes of Boolean functions is often easier than the synthesis of a general unrestricted specification. In reversible logic, well-scaled synthesis methods with a reasonably small cost of the associated implementation have been found for only a few classes of functions. This includes synthesis of multiple-output symmetric and reversible linear functions. The author presents an efficient reversible/quantum synthesis method for the class of multiple-output symmetric functions. The method is purely theoretical, therefore its scaling on functions with a large number of inputs/outputs requires minimal resources. The author calculates garbage, i.e. the number of outputs that are not required by the function specification, the number of reversible gates, and the quantum cost of the presented implementations. The proposed approach is then applied to the synthesis of benchmark functions. Comparison of the designs to the previously reported implementations is favourable.
In this paper, we study the problem Boolean function's representation in a class of reversible circuits. Each Boolean function is associated with reversible function, which is implemented by a reversible circuit. Reversible circuits are built from Toffoli elements. An operator approach is used for description of this representation. At building of reversible circuit the algorithm of finding of the minimum representation of Boolean function in a class of the extended polarized Zhegalkin polynomials is applied. The foundation of this algorithm is made by a embedding of a special operator form (SOF) of function in certain classes of operators. Previously generated library with the components corresponding to certain operators is used at construction of a Boolean function's SOF. Operators of a SOF, and the corresponding multiple-output reversible function, define the minimal reversible circuit for a given Boolean function.
Reversible logic circuit is a necessary construction for achieving ultra low power dissipation as well as for prominent post-CMOS computing technologies such as Quantum computing. Consequently automatic synthesis of a Boolean function using elementary reversible logic gates has received significant research attention in recent times, creating the domain of reversible logic synthesis. In this paper, we study the complexity of reversible logic synthesis. The problem is separately studied for bounded-ancilla and ancilla-free optimal synthesis approaches. The computational complexity for both cases are linked to known/presumed hard problems. Finally, experiments are performed with a shortest-path based reversible logic synthesis approach and a (0-1) ILP-based formulation.