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

Journal of Circuits Systems and Computers

REDUCING QUANTUM COST OF REVERSIBLE CIRCUITS FOR HOMOGENEOUS BOOLEAN FUNCTIONS

Ahmed Younes

Published Oct 26, 2010• 6 citations
Publisher

Abstract

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.

DOI
10.1142/s0218126610006736

Related papers

Synthesis and Optimization of Reversible Circuits for Homogeneous Boolean Functions

Ahmed Younes

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.

arXiv:0710.0664•Oct 2, 2007•6 citations

Optimized Boolean expression embedding in quantum and reversible logic circuits

Zaid Al-Wardi

The quantum and reversible circuits represent a promising replacement of conventional computers in many applications in the future. The transition between conventional computing and this alternative is indeed a huge paradigm shift. During the transition, embedding of conventional Boolean logic functions and expressions within quantum and reversible logic circuits has to be considered, because conventional computing is generally based on Boolean algebra. This embedding comes with a serious drawback of additional increase in the problem complexity represented by additional constant inputs, the so-called ancillary lines. An algorithmic optimization technique is suggested in this paper to reduce the number of these ancillary lines. With this algorithm embedding of Boolean expressions within reversible/quantum circuits comes out with minimal increase in circuit cost and gate count in the optimized circuits.

AIP conference proceedings•Jan 1, 2023•0 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, 2014•2 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•17 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, 2017•4 citations

Low-quantum cost circuit constructions for adder and symmetric Boolean functions

Anupam Chattopadhyay, Anubhab Baksi

Quantum computing necessitates the design of circuits via reversible logic gates. Efficient reversible circuit can be constructed by achieving low ancilla count, reducing logical depth and lowering Quantum costs. Generalized Peres gates have recently been realized with very low Quantum Cost (QC) by utilizing Quantum rotation gates. This is utilized in recent literature for efficient reversible circuit constructions for symmetric Boolean functions. In this paper, we extend this line of construction further by demonstrating efficient realization of adder circuits. In particular, we revisit the adder construction of Vedral, Barenco and Eckert to show that improvement of gate count and QC is achievable by exploiting a construction based only on Peres gates. We also report improved constructions of symmetric Boolean functions by following an approach recently proposed in the context of Boolean function complexity analysis.

IEEE International Symposium on Circuits and Systems proceedings•May 1, 2016•3 citations
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.
The quantum and reversible circuits represent a promising replacement of conventional computers in many applications in the future. The transition between conventional computing and this alternative is indeed a huge paradigm shift. During the transition, embedding of conventional Boolean logic functions and expressions within quantum and reversible logic circuits has to be considered, because conventional computing is generally based on Boolean algebra. This embedding comes with a serious drawback of additional increase in the problem complexity represented by additional constant inputs, the so-called ancillary lines. An algorithmic optimization technique is suggested in this paper to reduce the number of these ancillary lines. With this algorithm embedding of Boolean expressions within reversible/quantum circuits comes out with minimal increase in circuit cost and gate count in the optimized circuits.
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.
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.
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.
Quantum computing necessitates the design of circuits via reversible logic gates. Efficient reversible circuit can be constructed by achieving low ancilla count, reducing logical depth and lowering Quantum costs. Generalized Peres gates have recently been realized with very low Quantum Cost (QC) by utilizing Quantum rotation gates. This is utilized in recent literature for efficient reversible circuit constructions for symmetric Boolean functions. In this paper, we extend this line of construction further by demonstrating efficient realization of adder circuits. In particular, we revisit the adder construction of Vedral, Barenco and Eckert to show that improvement of gate count and QC is achievable by exploiting a construction based only on Peres gates. We also report improved constructions of symmetric Boolean functions by following an approach recently proposed in the context of Boolean function complexity analysis.