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

International Conference on Design & Technology of Integrated Systems in Nanoscale Era (DTIS)

A Swarm based Binary Decision Diagram (BDD) Reordering Optimizer for Reversible Circuit Synthesis

Baker K. Abdalhaq, Ahmed Awad, Amjad Hawash

Published Apr 1, 2020• 4 citations
Publisher

Abstract

Reversible logic has been considered as a promising direction in the field of low power design and quantum computing. However, synthesizing reversible circuits is totally different from that of irreversible circuits. Therefore, several algorithms have been devoted to optimize the synthesis process of reversible circuits in terms of the Quantum Cost (QC). Binary Decision Diagram (BDD) based synthesis has been found as one of the dominant algorithms in reversible logic synthesis, due to its scalability in synthesizing large-scale circuits within a reasonable synthesis time that is bounded by the BDD size. However, the QC of the synthesized circuit is strongly correlated with the used BDD size in the synthesis process, wherein, each BDD node is substituted by a cascade or reversible gates. As a result, exploiting effective BDD reordering algorithms combined with BDD reduction rules turns out into less QC. In this paper, we propose a BDD reordering methodology wherein recently published swarm based optimization algorithms are integrated and compared in terms of the resultant BDD size. Experimental results show that Moth-Flame optimization (MFO) algorithm outperforms other algorithms on the public benchmarks.

DOI
10.1109/dtis48698.2020.9081221

Related papers

Reversible Logic Synthesis Using Binary Decision Diagrams With Exploiting Efficient Reordering Operators

Baker K. Abdalhaq, Ahmed Awad, Amjad Hawash

With the continuous shrinkage of transistor sizes in very large scale integrated circuits, power consumption forms a serious concern to be tackled. With their ability to allow for zero energy dissipation, reversible circuits have been considered as promising solution to meetup with low power design requirements. Moreover, advances in their synthesis methodologies can be easily applied to quantum circuits due to the inherited reversibility of the latter. Although numerous algorithms have been proposed in the literature to synthesize reversible circuits and map them into their corresponding quantum circuits, the scalability and computational effort of such algorithms form a serious concern when synthesizing large size input functions. Binary Decision Diagram-based synthesis for reversible circuits has shown great evidence in realizing reversible circuits with low quantum cost through exploiting proper reduction rules for smaller graph size. However, the order of the variables in the decision diagram impacts its overall size, and thus, the cost of its corresponding reversible circuit. While several reordering algorithms have been proposed in this manner, their direct impact on the quantum cost has not been considered. In this article, a Binary Decision Diagram-based algorithm for reversible circuit synthesis is proposed to synthesize reversible circuits for a given Boolean function with low quantum cost through exploiting a linearized relationship between the decision diagram size and the corresponding quantum cost. Thereafter, different decision diagram reordering algorithms have been integrated with the proposed algorithm and compared in terms of their impact on the quantum cost. Experimental results show that Genetic Algorithm-based reordering for decision diagram, supported with, cycle crossover, inverse mutation, and tournament selection, results in the least quantum cost of the output circuit if compared with other algorithms due to its property in preserving the nodes of the decision diagram in their near-optimal locations during the optimiation recipe.

IEEE Access•Jan 1, 2020•7 citations

BDD-Based Synthesis of Reversible Logic

Robert Wille, Rolf Drechsler

Reversible logic became a promising alternative to traditional circuits because of its applications in emerging technologies such as quantum computing, low-power design, DNA computing, or nanotechnologies. As a result, synthesis of the respective circuits is an intensely studied topic. However, most synthesis methods are limited, because they rely on a truth table representation of the function to be synthesized. In this paper, the authors present a synthesis approach that is based on Binary Decision Diagrams (BDDs). The authors propose a technique to derive reversible or quantum circuits from BDDs by substituting all nodes of the BDD with a cascade of Toffoli or quantum gates, respectively. Boolean functions containing more than a hundred of variables can efficiently be synthesized. More precisely, a circuit can be obtained from a given BDD using an algorithm with linear worst case behavior regarding run-time and space requirements. Furthermore, using the proposed approach, theoretical results known from BDDs can be transferred to reversible circuits. Experiments show better results (with respect to the circuit cost) and a significantly better scalability in comparison to previous synthesis approaches.

International Journal of Applied Metaheuristic Computing•Oct 1, 2010•8 citations

Effect of BDD Optimization on Synthesis of Reversible and Quantum Logic

Robert Wille, Rolf Drechsler

Synthesis of reversible and quantum logic has become an intensely studied topic in the last years. However, most synthesis methods are limited, since they rely on a truth table representation of the function to be synthesized. BDD-based synthesis offers an alternative. Here, reversible or quantum circuits are derived from a function given as Binary Decision Diagram (BDD) by substituting all nodes of the BDD with a cascade of Toffoli or elementary quantum gates, respectively. As a result, the application of the approach is not limited by the truth table of the function but by the (quite more efficient) BDD representation. Furthermore, many optimization techniques for BDDs exist which can be exploited. In this work, we evaluate the effect of three optimization methods for BDDs (namely shared nodes, complement edges, and advanced orderings) on the resulting reversible and quantum circuits. We describe in detail the adjustments, which have to be done to support these optimizations for synthesis, and discuss possible improvements and drawbacks. In a case study, the effects are experimentally evaluated. The results showed, that applying these optimization techniques leads to significant smaller circuits (with respect to number of gates and lines) in most of the cases.

Electronic Notes in Theoretical Computer Science•Mar 1, 2010•55 citations

Positive Davio-based synthesis algorithm for reversible logic

Yu Pang, Shaoquan Wang, Zhilong He +3 more

Reversible logic is a key technique for quantum computing so leading to low-power designs. However, current synthesis algorithms for reversible circuits are low efficiency and do not obtain optimized reversible circuits, so they are only applied to small logic functions. In this paper, we propose a new method based on positive Davio expansion to synthesize reversible circuits, which generates a positive Davio decision diagram for a logic function and transfers diagram nodes to reversible circuits. The algorithm has advantages of optimizing area and fast synthesis speed compared to BDD (Binary decision diagram) based and RM (Reed-Muller) based synthesis method, so it can be adapted for large functions.

IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD)•Oct 1, 2011•17 citations

Synthesis of Reversible and Quantum Circuit Using ROCBDD and Mixed-Polarity Toffoli Gate

Hieu Nguyen, Linh Hoang Tran

In the last decade, the synthesis of reversible logic circuits has become a trending topic because of its future necessity and importance. Many methods have been studied and proposed, for instance, transformation-based, search-based, cycle-based, ESOP-based and BDD-based methods. Each of them has its limitation related to time processing, ancilla and garbage line, quantum cost. This study develops an algorithm that could synthesize quantum circuits based on mixed-polarity Toffoli gate and a variant of binary decision diagram (BDD) called reduced-ordered-complemented edge-bdd (ROCBDD). It is an optimized method of BDD to reduce nodes in the representation of Boolean functions, which leads to adding more lines and quantum gates in the reversible circuit. First, the differences between synthesis using ROCBDD, the traditional BDD and others methods are introduced. Then, we define a new structure consisting of mixed-polarity Toffoli gates relied on nodes of ROCBDD. An efficient algorithm to match BDD representation to the reversible logic circuit is also mentioned. Finally, the experimental results show that our algorithm has better synthesizing costs than previous BDD-based methods.

IEEE Access•Jan 1, 2021•5 citations

LLM-Driven Algorithm Design for Quantum Circuit Synthesis based on Binary Decision Diagrams

Youngho Sim, Federico Berto, Chuanbo Hua +2 more

Quantum circuits are central to implementing quantum algorithms on quantum devices, where quantum gates must be reversible. Many quantum algorithms rely on Boolean functions, which must therefore be implemented reversibly within quantum circuits. Reversible circuit synthesis provides a way to translate such Boolean functions into reversible circuits. Binary decision diagrams (BDDs) offer a scalable approach to this task, but the resulting BDDs and circuits depend heavily on variable ordering. Existing ordering heuristics commonly minimize BDD size because it is closely tied to the circuit size. However, BDD size is an imperfect proxy for the quantum cost of the synthesized circuit (QCC). We propose \texttt{QuantumEvo}, an evolutionary framework that uses an LLM as a heuristic generator for QCC-aware BDD variable ordering. Instead of predicting orderings directly, \texttt{QuantumEvo} searches over ordering heuristics initialized from multiple heuristic families. Candidate heuristics directly manipulate variable orderings using standard BDD operations and are selected by downstream QCC. The discovered heuristic, HGA-QE, modifies the sifting step inside a genetic algorithm so that the procedure is better aligned with QCC. Across the benchmark set, HGA-QE achieves a 70.9\% tie-or-win rate against the per-function best baseline and is strictly best on 13.5\% of the functions. The results demonstrate broadly competitive QCC performance, with HGA-QE showing a clearer relative advantage in strict wins on the two benchmark suites drawn from sources different from the data used for heuristic discovery.

arXiv:2609.05327•Sep 4, 2026•1 citation
Reversible logic has been considered as a promising direction in the field of low power design and quantum computing. However, synthesizing reversible circuits is totally different from that of irreversible circuits. Therefore, several algorithms have been devoted to optimize the synthesis process of reversible circuits in terms of the Quantum Cost (QC). Binary Decision Diagram (BDD) based synthesis has been found as one of the dominant algorithms in reversible logic synthesis, due to its scalability in synthesizing large-scale circuits within a reasonable synthesis time that is bounded by the BDD size. However, the QC of the synthesized circuit is strongly correlated with the used BDD size in the synthesis process, wherein, each BDD node is substituted by a cascade or reversible gates. As a result, exploiting effective BDD reordering algorithms combined with BDD reduction rules turns out into less QC. In this paper, we propose a BDD reordering methodology wherein recently published swarm based optimization algorithms are integrated and compared in terms of the resultant BDD size. Experimental results show that Moth-Flame optimization (MFO) algorithm outperforms other algorithms on the public benchmarks.
With the continuous shrinkage of transistor sizes in very large scale integrated circuits, power consumption forms a serious concern to be tackled. With their ability to allow for zero energy dissipation, reversible circuits have been considered as promising solution to meetup with low power design requirements. Moreover, advances in their synthesis methodologies can be easily applied to quantum circuits due to the inherited reversibility of the latter. Although numerous algorithms have been proposed in the literature to synthesize reversible circuits and map them into their corresponding quantum circuits, the scalability and computational effort of such algorithms form a serious concern when synthesizing large size input functions. Binary Decision Diagram-based synthesis for reversible circuits has shown great evidence in realizing reversible circuits with low quantum cost through exploiting proper reduction rules for smaller graph size. However, the order of the variables in the decision diagram impacts its overall size, and thus, the cost of its corresponding reversible circuit. While several reordering algorithms have been proposed in this manner, their direct impact on the quantum cost has not been considered. In this article, a Binary Decision Diagram-based algorithm for reversible circuit synthesis is proposed to synthesize reversible circuits for a given Boolean function with low quantum cost through exploiting a linearized relationship between the decision diagram size and the corresponding quantum cost. Thereafter, different decision diagram reordering algorithms have been integrated with the proposed algorithm and compared in terms of their impact on the quantum cost. Experimental results show that Genetic Algorithm-based reordering for decision diagram, supported with, cycle crossover, inverse mutation, and tournament selection, results in the least quantum cost of the output circuit if compared with other algorithms due to its property in preserving the nodes of the decision diagram in their near-optimal locations during the optimiation recipe.
Reversible logic became a promising alternative to traditional circuits because of its applications in emerging technologies such as quantum computing, low-power design, DNA computing, or nanotechnologies. As a result, synthesis of the respective circuits is an intensely studied topic. However, most synthesis methods are limited, because they rely on a truth table representation of the function to be synthesized. In this paper, the authors present a synthesis approach that is based on Binary Decision Diagrams (BDDs). The authors propose a technique to derive reversible or quantum circuits from BDDs by substituting all nodes of the BDD with a cascade of Toffoli or quantum gates, respectively. Boolean functions containing more than a hundred of variables can efficiently be synthesized. More precisely, a circuit can be obtained from a given BDD using an algorithm with linear worst case behavior regarding run-time and space requirements. Furthermore, using the proposed approach, theoretical results known from BDDs can be transferred to reversible circuits. Experiments show better results (with respect to the circuit cost) and a significantly better scalability in comparison to previous synthesis approaches.
Synthesis of reversible and quantum logic has become an intensely studied topic in the last years. However, most synthesis methods are limited, since they rely on a truth table representation of the function to be synthesized. BDD-based synthesis offers an alternative. Here, reversible or quantum circuits are derived from a function given as Binary Decision Diagram (BDD) by substituting all nodes of the BDD with a cascade of Toffoli or elementary quantum gates, respectively. As a result, the application of the approach is not limited by the truth table of the function but by the (quite more efficient) BDD representation. Furthermore, many optimization techniques for BDDs exist which can be exploited. In this work, we evaluate the effect of three optimization methods for BDDs (namely shared nodes, complement edges, and advanced orderings) on the resulting reversible and quantum circuits. We describe in detail the adjustments, which have to be done to support these optimizations for synthesis, and discuss possible improvements and drawbacks. In a case study, the effects are experimentally evaluated. The results showed, that applying these optimization techniques leads to significant smaller circuits (with respect to number of gates and lines) in most of the cases.
Reversible logic is a key technique for quantum computing so leading to low-power designs. However, current synthesis algorithms for reversible circuits are low efficiency and do not obtain optimized reversible circuits, so they are only applied to small logic functions. In this paper, we propose a new method based on positive Davio expansion to synthesize reversible circuits, which generates a positive Davio decision diagram for a logic function and transfers diagram nodes to reversible circuits. The algorithm has advantages of optimizing area and fast synthesis speed compared to BDD (Binary decision diagram) based and RM (Reed-Muller) based synthesis method, so it can be adapted for large functions.
In the last decade, the synthesis of reversible logic circuits has become a trending topic because of its future necessity and importance. Many methods have been studied and proposed, for instance, transformation-based, search-based, cycle-based, ESOP-based and BDD-based methods. Each of them has its limitation related to time processing, ancilla and garbage line, quantum cost. This study develops an algorithm that could synthesize quantum circuits based on mixed-polarity Toffoli gate and a variant of binary decision diagram (BDD) called reduced-ordered-complemented edge-bdd (ROCBDD). It is an optimized method of BDD to reduce nodes in the representation of Boolean functions, which leads to adding more lines and quantum gates in the reversible circuit. First, the differences between synthesis using ROCBDD, the traditional BDD and others methods are introduced. Then, we define a new structure consisting of mixed-polarity Toffoli gates relied on nodes of ROCBDD. An efficient algorithm to match BDD representation to the reversible logic circuit is also mentioned. Finally, the experimental results show that our algorithm has better synthesizing costs than previous BDD-based methods.
Quantum circuits are central to implementing quantum algorithms on quantum devices, where quantum gates must be reversible. Many quantum algorithms rely on Boolean functions, which must therefore be implemented reversibly within quantum circuits. Reversible circuit synthesis provides a way to translate such Boolean functions into reversible circuits. Binary decision diagrams (BDDs) offer a scalable approach to this task, but the resulting BDDs and circuits depend heavily on variable ordering. Existing ordering heuristics commonly minimize BDD size because it is closely tied to the circuit size. However, BDD size is an imperfect proxy for the quantum cost of the synthesized circuit (QCC). We propose \texttt{QuantumEvo}, an evolutionary framework that uses an LLM as a heuristic generator for QCC-aware BDD variable ordering. Instead of predicting orderings directly, \texttt{QuantumEvo} searches over ordering heuristics initialized from multiple heuristic families. Candidate heuristics directly manipulate variable orderings using standard BDD operations and are selected by downstream QCC. The discovered heuristic, HGA-QE, modifies the sifting step inside a genetic algorithm so that the procedure is better aligned with QCC. Across the benchmark set, HGA-QE achieves a 70.9\% tie-or-win rate against the per-function best baseline and is strictly best on 13.5\% of the functions. The results demonstrate broadly competitive QCC performance, with HGA-QE showing a clearer relative advantage in strict wins on the two benchmark suites drawn from sources different from the data used for heuristic discovery.