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

arXiv:1405.6073

Ancilla-Quantum Cost Trade-off during Reversible Logic Synthesis using Exclusive Sum-of-Products

Anupam Chattopadhyay, Pal, Nilanjan, Soumajit Majumder

Published May 23, 2014• 5 citations
arXivHTMLPDF

Abstract

Emerging technologies with asymptotic zero power dissipation, such as quantum computing, require the logical operations to be done in a reversible manner. In recent years, the problem of synthesizing Boolean functions in the reversible logic domain has gained significant research attention. The efficiency of the synthesis methods is measured in terms of quantum cost, gate cost, garbage lines, logic depth and speed of synthesis. In this paper, we present an approach based on Exclusive sum-of-Products (ESOP), which allows the user to explore the trade-off between quantum cost and garbage lines. The proposed technique adds a new dimension to the reversible logic synthesis solutions. We demonstrate by detailed experiments that controlled improvement in quantum cost and gate count by increasing garbage count can be achieved. In some cases, improved quantum cost and gate count compared to state-of-the-art synthesis methods are reported. Furthermore, we propose a novel rule-based approach to achieve ancilla-free reversible logic synthesis starting from an ESOP formulation.

DOI
10.48550/arxiv.1405.6073

Related papers

Reversible Logic Circuit Complexity Analysis via Functional Decomposition

Anupam Chattopadhyay, Anubhab Baksi

Reversible computation is gaining increasing relevance in the context of several post-CMOS technologies, the most prominent of those being Quantum computing. One of the key theoretical problem pertaining to reversible logic synthesis is the upper bound of the gate count. Compared to the known bounds, the results obtained by optimal synthesis methods are significantly less. In this paper, we connect this problem with the multiplicative complexity analysis of classical Boolean functions. We explore the possibility of relaxing the ancilla and if that approach makes the upper bound tighter. Our results are negative. The ancilla-free synthesis methods by using transformations and by starting from an Exclusive Sum-of-Product (ESOP) formulation remain, theoretically, the synthesis methods for achieving least gate count for the cases where the number of variables $n$ is $< 8$ and otherwise, respectively.

arXiv:1602.00101•Jan 30, 2016•3 citations

A shared-cube approach to ESOP-based synthesis of reversible logic

Noor Muhammed Nayeem, Jacqueline Rice

Reversible logic is being suggested as a possibility for overcoming potential power loss and heat dissipation problems that the computing industry may soon be at a loss to overcome. However, for reversible logic to be a solution we must have techniques for synthesizing function descriptions to reversible circuits. This paper presents an improved ESOP-based reversible logic synthesis approach which leverages situations where cubes are shared by multiple outputs and ensures that the implementation of each cube requires just one Toffoli gate. It has the potential to minimize both gate count and quantum cost, and in fact our experimental results show that this technique can reduce the quantum cost up to 75% compared to results from the existing work.

Facta universitatis - series Electronics and Energetics•Jan 1, 2011•41 citations

A Novel Perspective in Designing a Low Quantum Cost Synchronous Reversible Counters

Shivangi Gupta, Somesh Kumar

Reversible circuits are one of the most promising technologies that allow the reproduction of the inputs from the observed outputs and thus reducing the power dissipation in the form of heat. Many basic and universal logic gates i.e. nand, nor, or, and etc. are irreversible and result in energy consumption during calculations. In the reversible technology, like quantum circuits energy is not consumed during the entire calculation process and these circuits can be used for low-power and quantum communication applications circuits. Counters are considered as one of the most important sequential circuits used in many real-time applications. This paper presents a new approach to design a quantum cost-effective reversible up/down counter circuit using exclusive-or sum of product (ESOP) expressions and TR gates. The proposed counter circuits are simulated in the Xilinx Vivado simulator to verify the functionality of the proposed designs. The comparative study indicates that the proposed counters are superior to the best previous designs in terms of quantum cost (QC) and gate count (GC). Moreover, they are very close to or better than the previously available designs in terms of garbage outputs (GO) and Ancilla inputs (AI).

International Conference on Design & Technology of Integrated Systems in Nanoscale Era (DTIS)•Apr 1, 2020•4 citations

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

Optimization of Reversible Logic Networks with Gate Sharing

Yung‐Chih Chen, Feng-Jie Chao

Logic synthesis for quantum computing aims to transform a Boolean logic network into a quantum circuit. A conventional two-stage flow first synthesizes the given Boolean logic network into a reversible logic network composed of reversible logic gates. Then, it maps each reversible logic gate into quantum gates to generate a quantum circuit. The state-of-the-art method for the first stage takes advantage of the lookup-table (LUT) mapping technology for FPGAs to decompose the given Boolean logic network into sub-networks, and then maps the sub-networks into reversible logic networks. Although every sub-network is well synthesized, we observe that the reversible logic networks could be further optimized by sharing the reversible logic gates belonging to different sub-networks. Thus, in this paper, we propose a new optimization method for the reversible logic networks by sharing gates. We translate the problem of extracting shareable gates to the exclusive-sums-of-product term optimization problem. The experimental results show that the proposed method successfully optimizes the reversible logic networks generated by the LUT-based method. It is able to reduce an average of approximately 4% of quantum gate cost without increasing the number of ancilla lines for a set of IWLS 2005 benchmarks.

Asia and South Pacific Design Automation Conference (ASP-DAC)•Jan 16, 2023•2 citations

Scaling-up ESOP Synthesis for Quantum Compilation

Bruno de O. Schmitt, Mathias Soeken, Giovanni De Micheli +1 more

Today's rapid advances in quantum computing hardware call for scalable synthesis methods to map combinational logic represented as multi-level Boolean networks (e.g., an and-inverter graph, AIG) to quantum circuits. Such synthesis process must yield reversible logic function since quantum circuits are reversible. Thus, logic representations using exclusive sum-of-products (ESOP) are advantageous because of their natural relation to Toffoli gates, one of the primitives in reversible logic. This motivates developing effective methods to collapse AIG logic networks into ESOPs. In this work, we present two state-of-the-art methods to collapse an AIG into an ESOP expression, describe their shortcomings and introduce a new approach based on the divide-and-conquer paradigm. We demonstrate the effectiveness of our method in collapsing IEEE-compliant half precision floating point networks. Results show that our method can collapse designs-which were previously not solvable within a week-in less than 5 minutes. We also describe a technique capable of taking advantage of this new method to generate quantum circuits with up to 50% fewer T gates compared to state-of-the-art methods.

IEEE International Symposium on Multiple-Valued Logic (ISMVL)•May 1, 2019•8 citations
Emerging technologies with asymptotic zero power dissipation, such as quantum computing, require the logical operations to be done in a reversible manner. In recent years, the problem of synthesizing Boolean functions in the reversible logic domain has gained significant research attention. The efficiency of the synthesis methods is measured in terms of quantum cost, gate cost, garbage lines, logic depth and speed of synthesis. In this paper, we present an approach based on Exclusive sum-of-Products (ESOP), which allows the user to explore the trade-off between quantum cost and garbage lines. The proposed technique adds a new dimension to the reversible logic synthesis solutions. We demonstrate by detailed experiments that controlled improvement in quantum cost and gate count by increasing garbage count can be achieved. In some cases, improved quantum cost and gate count compared to state-of-the-art synthesis methods are reported. Furthermore, we propose a novel rule-based approach to achieve ancilla-free reversible logic synthesis starting from an ESOP formulation.
Reversible computation is gaining increasing relevance in the context of several post-CMOS technologies, the most prominent of those being Quantum computing. One of the key theoretical problem pertaining to reversible logic synthesis is the upper bound of the gate count. Compared to the known bounds, the results obtained by optimal synthesis methods are significantly less. In this paper, we connect this problem with the multiplicative complexity analysis of classical Boolean functions. We explore the possibility of relaxing the ancilla and if that approach makes the upper bound tighter. Our results are negative. The ancilla-free synthesis methods by using transformations and by starting from an Exclusive Sum-of-Product (ESOP) formulation remain, theoretically, the synthesis methods for achieving least gate count for the cases where the number of variables nnn is <8< 8<8 and otherwise, respectively.
Reversible logic is being suggested as a possibility for overcoming potential power loss and heat dissipation problems that the computing industry may soon be at a loss to overcome. However, for reversible logic to be a solution we must have techniques for synthesizing function descriptions to reversible circuits. This paper presents an improved ESOP-based reversible logic synthesis approach which leverages situations where cubes are shared by multiple outputs and ensures that the implementation of each cube requires just one Toffoli gate. It has the potential to minimize both gate count and quantum cost, and in fact our experimental results show that this technique can reduce the quantum cost up to 75% compared to results from the existing work.
Reversible circuits are one of the most promising technologies that allow the reproduction of the inputs from the observed outputs and thus reducing the power dissipation in the form of heat. Many basic and universal logic gates i.e. nand, nor, or, and etc. are irreversible and result in energy consumption during calculations. In the reversible technology, like quantum circuits energy is not consumed during the entire calculation process and these circuits can be used for low-power and quantum communication applications circuits. Counters are considered as one of the most important sequential circuits used in many real-time applications. This paper presents a new approach to design a quantum cost-effective reversible up/down counter circuit using exclusive-or sum of product (ESOP) expressions and TR gates. The proposed counter circuits are simulated in the Xilinx Vivado simulator to verify the functionality of the proposed designs. The comparative study indicates that the proposed counters are superior to the best previous designs in terms of quantum cost (QC) and gate count (GC). Moreover, they are very close to or better than the previously available designs in terms of garbage outputs (GO) and Ancilla inputs (AI).
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.
Logic synthesis for quantum computing aims to transform a Boolean logic network into a quantum circuit. A conventional two-stage flow first synthesizes the given Boolean logic network into a reversible logic network composed of reversible logic gates. Then, it maps each reversible logic gate into quantum gates to generate a quantum circuit. The state-of-the-art method for the first stage takes advantage of the lookup-table (LUT) mapping technology for FPGAs to decompose the given Boolean logic network into sub-networks, and then maps the sub-networks into reversible logic networks. Although every sub-network is well synthesized, we observe that the reversible logic networks could be further optimized by sharing the reversible logic gates belonging to different sub-networks. Thus, in this paper, we propose a new optimization method for the reversible logic networks by sharing gates. We translate the problem of extracting shareable gates to the exclusive-sums-of-product term optimization problem. The experimental results show that the proposed method successfully optimizes the reversible logic networks generated by the LUT-based method. It is able to reduce an average of approximately 4% of quantum gate cost without increasing the number of ancilla lines for a set of IWLS 2005 benchmarks.
Today's rapid advances in quantum computing hardware call for scalable synthesis methods to map combinational logic represented as multi-level Boolean networks (e.g., an and-inverter graph, AIG) to quantum circuits. Such synthesis process must yield reversible logic function since quantum circuits are reversible. Thus, logic representations using exclusive sum-of-products (ESOP) are advantageous because of their natural relation to Toffoli gates, one of the primitives in reversible logic. This motivates developing effective methods to collapse AIG logic networks into ESOPs. In this work, we present two state-of-the-art methods to collapse an AIG into an ESOP expression, describe their shortcomings and introduce a new approach based on the divide-and-conquer paradigm. We demonstrate the effectiveness of our method in collapsing IEEE-compliant half precision floating point networks. Results show that our method can collapse designs-which were previously not solvable within a week-in less than 5 minutes. We also describe a technique capable of taking advantage of this new method to generate quantum circuits with up to 50% fewer T gates compared to state-of-the-art methods.