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:2609.05327

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

Youngho Sim, Federico Berto, Chuanbo Hua, Jinkyoo Park, Changhyun Kwon

Published Sep 4, 2026• 1 citation
arXivHTMLPDF

Abstract

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.

DOI
10.48550/arxiv.2609.05327

Related papers

BDD2Seq: Enabling Scalable Reversible-Circuit Synthesis via Graph-to-Sequence Learning

Mingkai Miao, Jianheng Tang, Guangyu Hu +1 more

Binary Decision Diagrams (BDDs) are instrumental in many electronic design automation (EDA) tasks thanks to their compact representation of Boolean functions. In BDD‑based reversible‑circuit synthesis, which is critical for quantum computing, the chosen variable ordering governs the number of BDD nodes and thus the key metrics of resource consumption, such as Quantum Cost. Because finding an optimal variable ordering for BDDs is an NP‑complete problem, existing heuristics often degrade as circuit complexity grows. We introduce BDD2Seq, a graph‑to‑sequence framework that couples a Graph Neural Network encoder with a Pointer‑Network decoder and Diverse Beam Search to predict high‑quality orderings. By treating the circuit netlist as a graph, BDD2Seq learns structural dependencies that conventional heuristics overlooked, yielding smaller BDDs and faster synthesis. Extensive experiments on three public benchmarks show that BDD2Seq achieves around 1.4 times lower Quantum Cost and 3.7 times faster synthesis than modern heuristic algorithms. To the best of our knowledge, this is the first work to tackle the variable‑ordering problem in BDD‑based reversible‑circuit synthesis with a graph‑based generative model and diversity‑promoting decoding.

Proceedings of the AAAI Conference on Artificial Intelligence•Mar 14, 2026•1 citation

BDD2Seq: Enabling Scalable Reversible-Circuit Synthesis via Graph-to-Sequence Learning

Mingkai Miao, Jianheng Tang, Guangyu Hu +1 more

Binary Decision Diagrams (BDDs) are instrumental in many electronic design automation (EDA) tasks thanks to their compact representation of Boolean functions. In BDD-based reversible-circuit synthesis, which is critical for quantum computing, the chosen variable ordering governs the number of BDD nodes and thus the key metrics of resource consumption, such as Quantum Cost. Because finding an optimal variable ordering for BDDs is an NP-complete problem, existing heuristics often degrade as circuit complexity grows. We introduce BDD2Seq, a graph-to-sequence framework that couples a Graph Neural Network encoder with a Pointer-Network decoder and Diverse Beam Search to predict high-quality orderings. By treating the circuit netlist as a graph, BDD2Seq learns structural dependencies that conventional heuristics overlooked, yielding smaller BDDs and faster synthesis. Extensive experiments on three public benchmarks show that BDD2Seq achieves around 1.4 times lower Quantum Cost and 3.7 times faster synthesis than modern heuristic algorithms. To the best of our knowledge, this is the first work to tackle the variable-ordering problem in BDD-based reversible-circuit synthesis with a graph-based generative model and diversity-promoting decoding.

arXiv:2511.08315•Nov 11, 2025•0 citations

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

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

Baker K. Abdalhaq, Ahmed Awad, Amjad Hawash

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.

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

Evolutionary Quantum Logic Synthesis of Boolean Reversible Logic Circuits Embedded in Ternary Quantum Space using Heuristics

Maartin Lukac, Marek A. Perkowski, Michitaka Kameyama

It has been experimentally proven that realizing universal quantum gates using higher-radices logic is practically and technologically possible. We developed a Parallel Genetic Algorithm that synthesizes Boolean reversible circuits realized with a variety of quantum gates on qudits with various radices. In order to allow synthesizing circuits of medium sizes in the higher radix quantum space we performed the experiments using a GPU accelerated Genetic Algorithm. Using the accelerated GA we compare heuristic improvements to the mutation process based on cost minimization, on the adaptive cost of the primitives and improvements due to Baldwinian vs. Lamarckian GA. We also describe various fitness function formulations that allowed for various realizations of well known universal Boolean reversible or quantum-probabilistic circuits.

arXiv:1107.3383•Jul 18, 2011•7 citations
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.
Binary Decision Diagrams (BDDs) are instrumental in many electronic design automation (EDA) tasks thanks to their compact representation of Boolean functions. In BDD‑based reversible‑circuit synthesis, which is critical for quantum computing, the chosen variable ordering governs the number of BDD nodes and thus the key metrics of resource consumption, such as Quantum Cost. Because finding an optimal variable ordering for BDDs is an NP‑complete problem, existing heuristics often degrade as circuit complexity grows. We introduce BDD2Seq, a graph‑to‑sequence framework that couples a Graph Neural Network encoder with a Pointer‑Network decoder and Diverse Beam Search to predict high‑quality orderings. By treating the circuit netlist as a graph, BDD2Seq learns structural dependencies that conventional heuristics overlooked, yielding smaller BDDs and faster synthesis. Extensive experiments on three public benchmarks show that BDD2Seq achieves around 1.4 times lower Quantum Cost and 3.7 times faster synthesis than modern heuristic algorithms. To the best of our knowledge, this is the first work to tackle the variable‑ordering problem in BDD‑based reversible‑circuit synthesis with a graph‑based generative model and diversity‑promoting decoding.
Binary Decision Diagrams (BDDs) are instrumental in many electronic design automation (EDA) tasks thanks to their compact representation of Boolean functions. In BDD-based reversible-circuit synthesis, which is critical for quantum computing, the chosen variable ordering governs the number of BDD nodes and thus the key metrics of resource consumption, such as Quantum Cost. Because finding an optimal variable ordering for BDDs is an NP-complete problem, existing heuristics often degrade as circuit complexity grows. We introduce BDD2Seq, a graph-to-sequence framework that couples a Graph Neural Network encoder with a Pointer-Network decoder and Diverse Beam Search to predict high-quality orderings. By treating the circuit netlist as a graph, BDD2Seq learns structural dependencies that conventional heuristics overlooked, yielding smaller BDDs and faster synthesis. Extensive experiments on three public benchmarks show that BDD2Seq achieves around 1.4 times lower Quantum Cost and 3.7 times faster synthesis than modern heuristic algorithms. To the best of our knowledge, this is the first work to tackle the variable-ordering problem in BDD-based reversible-circuit synthesis with a graph-based generative model and diversity-promoting decoding.
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.
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.
It has been experimentally proven that realizing universal quantum gates using higher-radices logic is practically and technologically possible. We developed a Parallel Genetic Algorithm that synthesizes Boolean reversible circuits realized with a variety of quantum gates on qudits with various radices. In order to allow synthesizing circuits of medium sizes in the higher radix quantum space we performed the experiments using a GPU accelerated Genetic Algorithm. Using the accelerated GA we compare heuristic improvements to the mutation process based on cost minimization, on the adaptive cost of the primitives and improvements due to Baldwinian vs. Lamarckian GA. We also describe various fitness function formulations that allowed for various realizations of well known universal Boolean reversible or quantum-probabilistic circuits.