PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2609.05327v1cs.AIcs.AR

TL;DR

BDD variable ordering affects reversible-circuit synthesis, yet BDD size is only an imperfect proxy for the resulting quantum cost. QuantumEvo uses an LLM-driven evolutionary search to discover QCC-aware ordering heuristics, and HGA-QE achieves competitive performance across benchmark circuits while improving over baselines on a substantial subset of functions.

  • Problem

    BDD size does not necessarily minimize the quantum cost of synthesized reversible circuits, motivating QCC-aware variable ordering.

  • Method

    QuantumEvo evolves executable BDD ordering heuristics from multiple seeded heuristic families and selects them using downstream QCC.

  • Results

    HGA-QE achieves competitive QCC across diverse benchmark circuits and improves over classical CUDD and learning-based baselines on a substantial subset of functions.

  • Takeaways & Limitations

    The framework demonstrates that LLM-driven evolutionary search can discover interpretable, reusable BDD ordering heuristics for reversible circuit synthesis.

  • Takeaways & Limitations

    The discovered heuristic remains influenced by the heuristic families used to seed the search, limiting evidence that it represents an entirely new ordering strategy.

Abstract

from arXiv · show

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.

1 Introduction

Reversible circuit synthesis translates Boolean functions into quantum circuits, but BDD-based synthesis depends strongly on variable ordering. Because BDD size does not reliably predict QCC, the paper proposes QuantumEvo to discover QCC-aware ordering heuristics and reports competitive results for HGA-QE.

  • Motivation: Reversible circuit synthesis translates Boolean functions into reversible circuits that can be mapped to quantum gate libraries.Quantum circuits are reversible because quantum operations are unitary.
  • Motivation: BDD-based synthesis improves scalability by representing Boolean functions as binary decision diagrams and translating their structure into reversible circuits.The resulting circuit is constructed from the BDD representation.
  • Research gap: BDD size is an imperfect proxy for QCC: a smaller BDD does not necessarily produce a lower quantum cost.This motivates optimizing variable ordering directly for downstream QCC.
  • Approach: QuantumEvo uses an LLM as a heuristic generator and searches executable ordering heuristics initialized from multiple heuristic families.Candidate heuristics manipulate variable orderings using standard BDD operations.
  • Approach: HGA-QE modifies genetic-algorithm sifting to align variable ordering more closely with downstream QCC.The framework evaluates ordering heuristics using QCC rather than only BDD size.
  • Results: HGA-QE shows broadly competitive QCC performance, with clearer strict-win advantages on benchmark suites from sources distinct from the discovery data.The reported comparison covers classical and learning-based baselines.

2 Background and Related Work

The background introduces reversible logic, BDD-based synthesis, and variable ordering, then positions QuantumEvo among classical, learning-based, and LLM-driven heuristic methods. The central distinction is optimizing downstream QCC rather than relying on BDD size alone.

  • Reversible Logic and Circuit Synthesis: Reversible functions are bijections with equal numbers of input and output bits, while general Boolean functions can be embedded using ancilla inputs and garbage outputs.Reversible logic preserves information and is relevant to quantum computing.
  • Reversible Logic and Circuit Synthesis: The paper focuses on the NCT library, whose NOT, CNOT, and Toffoli gates receive costs based on decomposition into elementary quantum gates.Total QCC is derived from the costs of the circuit gates.
  • Binary Decision Diagrams: Truth tables scale exponentially, whereas BDDs provide compact intermediate representations for scalable reversible circuit synthesis.The synthesis procedure replaces each non-terminal BDD node with a cascade of reversible gates.
  • Binary Decision Diagrams: A BDD is a directed acyclic graph whose labeled non-terminal nodes have two branches and can share repeated subgraphs.Variable ordering strongly affects the resulting graph size.
  • Variable Ordering: BDD size is an indirect QCC proxy: two orderings can produce equal-sized BDDs but different synthesized-circuit costs.Finding an ordering that minimizes BDD size is NP-complete.
  • Related Work: Prior ordering methods include exact algorithms, sifting, genetic algorithms, simulated annealing, swarm-based search, and the learning-based BDD2Seq approach.These methods primarily select orderings using BDD size, while QCC is observed after synthesis.
  • LLM-Based Approaches: QuantumEvo extends LLM-driven heuristic design to BDD variable ordering for reversible synthesis, targeting large Boolean functions with downstream QCC as the objective.This differs from quantum-LLM work focused mainly on code generation, parameterized circuits, or textbook-level oracles.

3 Methodology

QuantumEvo formulates QCC-aware BDD variable ordering as an evolutionary heuristic-design problem, using LLM-generated executable heuristics and downstream circuit evaluation. Its best discovered heuristic, HGA-QE, replaces standard sifting with targeted local procedures while retaining BDD-size fitness, improving QCC and reducing runtime.

  • 3 Methodology: QuantumEvo searches for reusable BDD variable-ordering heuristics rather than directly predicting orderings.The framework is presented as an LLM-driven evolutionary search over executable heuristic programs.
  • 3 Methodology: Each candidate heuristic reorders a BDD, synthesizes the reordered structure into a reversible circuit, and evaluates the result using downstream QCC.The synthesis uses a fixed BDD-based procedure implemented in RevKit.
  • 3 Methodology: QuantumEvo initializes its population from sifting, genetic-algorithm, and simulated-annealing heuristic families.These seed families provide distinct search strategies for the evolutionary process.
  • 3 Methodology: Candidate fitness is the average relative QCC gap to the instance-wise best classical baseline, where lower values are better and negative values indicate improvement.Stochastic heuristics are evaluated multiple times per instance.
  • 3 Methodology: HGA-QE replaces standard sifting with PartialSift and MiniSift, which locally reorder affected levels while preserving the inverse-BDD-size fitness function.PartialSift identifies affected levels and invokes MiniSift for local refinement.
  • 3 Methodology: Replacing standard sifting improves QCC while reducing runtime, with MiniSift providing the main gain and additional local refinement yielding only marginal improvement.The analysis links the improvement to more diverse orderings and synthesis-relevant BDD structures, including fewer Toffoli gates and total controls.

4 Experiment

The experiments test whether BDD size reliably predicts QCC, evaluate HGA-QE against classical and learning-based baselines, and analyze QuantumEvo’s design choices. HGA-QE is competitive overall, with stronger strict-win performance on benchmark suites from sources distinct from search and validation data.

  • Experimental setup: The evaluation uses 148 held-out reversible functions from RevLib, LGSynth91, and ISCAS85/89, compared against five CUDD ordering methods and BDD2Seq.Search and validation functions are separated from the final benchmark set, which contains 96 RevLib, 48 LGSynth91, and 4 ISCAS85/89 circuits.
  • Finding 1: BDD size correlates strongly with QCC, but substantial residual deviations and reversals make it an unreliable optimization proxy.Spearman ρ = 0.989, mean absolute deviation is 79.3, deviations reach 980, and 35% of functions contain an ordering pair where a smaller BDD has higher QCC.
  • Finding 2: HGA-QE matches or improves the best baseline on 105 of 148 functions and is uniquely best on 20.Its gains are clearer on LGSynth91 and ISCAS85/89, suggesting transfer beyond the augmented RevLib functions used for search and validation.
  • Finding 2: After two runs, HGA-QE has a quality–runtime trade-off comparable to BDD2Seq, while additional runs improve QCC at increased cumulative runtime.The Pareto analysis summarizes geometric-mean runtime and relative QCC gaps across all 148 circuits.
  • Trade-offs: The method prioritizes circuit quality when synthesis runtime remains practically manageable, but reducing runtime on expensive instances remains an optimization direction.The synthesis pipeline includes BDD construction, variable ordering, and reversible circuit synthesis, while selected heuristics are evaluated using downstream QCC.
  • Ablation study: The ablations show that LLM guidance, multi-family initialization, and QCC-based fitness affect validation and benchmark performance differently.Non-LLM search can achieve stronger validation fitness, multi-family initialization attains a higher validation win-or-tie rate, and BDD-size fitness underperforms QCC-based fitness on the benchmark.

5 Discussion

The discussion identifies seed dependence, synthesis-procedure dependence, and discovery cost as important boundaries for QuantumEvo. It also motivates hybrid strategies that selectively use LLM guidance.

  • Limitations: The discovered heuristic remains influenced by the initial heuristic families and combines ideas from sifting, simulated annealing, and genetic algorithms.Whether alternative framework designs can discover substantially different and more effective strategies remains open.
  • Limitations: QuantumEvo optimizes variable ordering, but ancilla count and other resource measures also depend on the synthesis procedure itself.The authors suggest combining QuantumEvo with post-synthesis ancilla reduction or alternative synthesis methods.
  • Discovery cost: The non-LLM search remains competitive while avoiding the token and inference costs of LLM guidance.This supports hybrid strategies that rely mainly on predefined evolutionary operators and invoke the LLM selectively.

6 Conclusion

The conclusion presents QuantumEvo as a reusable framework for discovering QCC-oriented BDD ordering heuristics. HGA-QE is competitive across diverse benchmarks, while the approach illustrates a broader pattern for domain-specific heuristic design.

  • Contribution: QuantumEvo discovers interpretable and reusable BDD variable ordering heuristics for reversible circuit synthesis.Its best discovered heuristic is HGA-QE.
  • Results: HGA-QE achieves competitive QCC across diverse benchmark circuits and improves over classical CUDD and learning-based baselines on a substantial subset of functions.Its implementation as a general CUDD variable-ordering heuristic enables reuse in other BDD-based workflows.
  • Broader implication: QuantumEvo illustrates how LLM-based heuristic design can be adapted to domain-specific settings by evaluating candidates directly on the relevant downstream objective.The authors suggest that this approach may extend to other optimization decisions within specialized computational workflows.
  • Implementation: The implementation uses CUDD-linked individuals and initializes searches from sifting, genetic-algorithm, and simulated-annealing heuristics.The compared classical methods include sifting, symmetric sifting, group sifting, genetic algorithm, and simulated annealing.

B.3 Analysis of Dataset and Benchmarks

The experiments use a 100-function augmented RevLib search set and a broader 148-function benchmark set with no shared Boolean functions. The non-LLM control uses the same evolutionary pipeline but restricts heuristic generation to predefined components.

  • Datasets: The search set contains 100 augmented RevLib functions, while the benchmark set contains 148 functions from RevLib, LGSynth91, and ISCAS85/89.The benchmark set has broader structural variety in input count, output count, and gate count.
  • Datasets: The search and benchmark sets share no Boolean functions, although some RevLib instances overlap at the metadata level.Non-RevLib suites add configurations not observed in the RevLib-based search set.
  • Control: The non-LLM control uses the same evolutionary procedure, fitness function, initialization scheme, and search and validation sets as QuantumEvo.It differs only by constructing candidates from predefined algorithmic components rather than generating and revising them with an LLM.
  • Control: The non-LLM search spans sifting, genetic-algorithm, and simulated-annealing families, with ten individuals from each family in the initial population.Its predefined search space includes the sifting procedure embedded within the genetic algorithm but cannot introduce ideas outside that space.
  • Heuristic design: MiniSift refines only the levels affected by the preceding variation operator.

C.2 Study on the Choice of LLM

The LLM-choice study compares two models under the same search pipeline across ten independent runs each. The larger model produces stronger validation results and different heuristic-family trajectories, while pooled candidate results do not establish a clear overall advantage for either setting.

  • Experimental setup: The study runs ten independent searches for each LLM, selects the best validation individual, and evaluates it on 148 benchmark functions.The compared models are gpt-oss-120b and gpt-5.4-mini.
  • Validation comparison: The gpt-5.4-mini runs show wider validation variance and a lower median validation score, and their best run does not match the best gpt-oss-120b result.
  • Validation comparison: gpt-oss-120b produces stronger validation results than gpt-5.4-mini, with a higher win-or-tie rate and lower mean QCC.The two settings also tend to converge to different heuristic families.
  • Family composition: gpt-oss-120b selects simulated-annealing-family individuals in 9 of 10 runs, whereas gpt-5.4-mini more often converges to sifting-family individuals.
  • Pooled candidates: The full QuantumEvo setting achieves the best median validation fitness for both top-5 and top-10 pooled candidate populations.For the top-10 pool, its distribution widens substantially, while the non-LLM control remains tightly concentrated; the overlap prevents a clear overall advantage.

C.4 Sensitivity Analysis

The sensitivity analysis examines how search-set choice, validation-set choice, and evaluation timeouts affect QuantumEvo outcomes. The full setting is comparatively robust to validation variation, while HGA-QE ranks first in half of the tested search sets.

  • Analysis design: The analysis reuses recorded candidate evaluations and runtime logs to characterize sensitivity within the observed search outcomes.It considers both alternate validation and search sets and hypothetical shorter timeout limits.
  • Search set: HGA-QE ranks first in 5 of 10 original or alternate search sets, although the top-ranked candidate varies across sets.The analysis reevaluates 30 leading candidates across the original and nine alternate 100-function search sets.
  • Validation set: The full QuantumEvo setting is more robust to validation-set variation than the alternative settings.The full setting and GA-only initialization are comparatively stable, whereas other settings are more sensitive to validation-set choice.
  • Timeout: Shorter timeout limits are evaluated by replaying production wall-clock times, with evaluations exceeding the limit counted as failures.Evaluations that already timed out at 40 seconds remain failures under shorter hypothetical limits.
  • Implementation: The section documents the BDD-reordering subroutines and their correspondence to CUDD functions.PartialSift imposes an individual ordering and applies MiniSift to changed levels, while MiniSift performs targeted upward and downward local sifting.

D.2 Diagnostic Analysis of MINISIFT Algorithm

MiniSift improves downstream reversible-circuit quality by exploring more diverse orderings that can preserve BDD size while reducing synthesis-specific costs. Across same-size cases, these reductions include fewer preservation cases, Toffoli gates, controls, and QCC.

  • Diversity: MiniSift produces more diverse candidate orderings than standard sifting.The diversity statistics use all search-set functions and three independent seeds.
  • Diagnostic comparison: On same-BDD-size cases where MiniSift lowers QCC, it also reduces child-node line preservation cases, Toffoli gates, and total controls.These metrics are computed on the 31 circuits where both methods produce the same BDD size but MiniSift achieves lower QCC.
  • Mechanism: MiniSift can expose orderings with comparable BDD size that are more favorable for reversible-circuit synthesis.Fewer preservation cases indicate fewer restrictions on circuit-line use and are associated with fewer Toffoli gates and total controls.
  • Example: In the representative four-input example, swapping the top two variables preserves BDD size while reducing QCC from 40 to 30.MiniSift changes the order from (x0, x3, x1, x2) to (x3, x0, x1, x2).
  • Mechanism: The example’s altered sharing eliminates one child-node line preservation case, along with two Toffoli gates and five controls.Across all 31 same-BDD-size functions, the analysis reports consistent reductions and statistically significant decreases in Toffoli gates, total controls, and QCC.
  • Baseline comparison: Across all 148 functions, HGA-QE has significantly lower QCC than every baseline after Holm correction, but significance varies by benchmark suite.No comparison is significant on ISCAS85/89, which contains only four circuits and tied results; the tests therefore have insufficient power there.
  • Loss cases: HGA-QE has the lowest loss rate overall and on every benchmark suite, while BDD2Seq and SA account for 21 and 11 of its 43 losses.These results identify BDD2Seq and SA as its strongest competitors under the reported loss analysis.
  • FPGA mapping: HGA-QE does not outperform SA and GA under the FPGA-mapping objective.Aggregate FPGA statistics exclude incomplete benchmark-stage runs, and HGA-QE completed only partially on c432 and c880 and not on rot_orig.

E Offline and Online Cost

QuantumEvo separates an expensive offline discovery phase from a fixed, LLM-free online heuristic. Offline search includes substantial LLM and synthesis evaluation cost, whereas deployment requires only the compiled heuristic, synthesis, and QCC evaluation.

  • Offline search: One QuantumEvo production run used an average of 291.6 LLM calls, 3.11M input tokens, 1.04M output tokens, and 108.5 minutes of wall-clock time.The searches used gpt-oss-120b self-hosted on a single NVIDIA RTX PRO 6000 GPU.
  • Cost comparison: QuantumEvo’s offline cost cannot be directly compared with BDD2Seq’s original training cost because BDD2Seq does not report training wall-clock time or GPU-hours.Classical CUDD heuristics require no analogous discovery phase.
  • Offline evaluation: Each candidate reaching evaluation is tested on 100 search-set functions, with up to approximately 40,000 synthesis calls per production run.Each function invokes the reversible-synthesis pipeline twice before QCC computation, with a maximum of 200 candidate evaluations per run.
  • Evaluation cost: 8.3% of candidate evaluations reached the 40 s timeout; completed evaluations had mean time 9.3 s, median 7.0 s, and 95th percentile 26.0 s.The timeout distribution is reported for the QuantumEvo production setting.
  • Online cost: After discovery, HGA-QE requires no LLM calls and runs as a fixed compiled heuristic.Its online phase consists of BDD reordering, reversible synthesis, and QCC evaluation.

G Full Per-Instance Results

The full per-instance results report QCC and runtime across 148 benchmark functions and multiple method classes. Comparisons account for stochastic variation, deterministic methods, and hardware-adjusted BDD2Seq(B*) timing.

  • Benchmark coverage: The per-instance results cover all 148 benchmark functions, grouped by benchmark suite.RevLib instances occupy Tables 16–20, while ISCAS85/89 and LGSynth91 instances appear in Tables 18 and 21.
  • Metrics: Stochastic methods report best QCC, average QCC with standard deviation, and average runtime, while deterministic methods report best QCC and runtime.The reporting convention distinguishes stochastic ordering methods from BDD2Seq and deterministic methods.
  • Runtime accounting: BDD2Seq runtimes include variable ordering and reversible synthesis, with BDD2Seq(E*) synthesizing one final ordering and BDD2Seq(B*) synthesizing 20 beam-search candidates.BDD2Seq(B*) uses beam width 20, while its additional CPU-based synthesis calls are hardware-normalized.
  • Runtime normalization: BDD2Seq(B*) timing is adjusted under the assumption that TB*−TE* represents 19 additional CPU-based synthesis calls.That component is rescaled from the original dual Xeon 8375C platform to a single-thread Ryzen 9 5900X platform using PassMark single-thread performance.
Loading 2609.05327v1…