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

• URL: http://arxiv.org/abs/2511.08315v1
• Date: Wed, 12 Nov 2025 01:52:28 GMT
• Title: BDD2Seq: Enabling Scalable Reversible-Circuit Synthesis via Graph-to-Sequence Learning
• Abstract summary: 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.<n>We show that BDD2Seq achieves around 1.4 times lower Quantum Cost and 3.7 times faster synthesis than modern algorithms.<n>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.
• Score: 9.434983938743349
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• LLM-Driven Algorithm Design for Quantum Circuit Synthesis based on Binary Decision Diagrams [24.594574306757043]
  Reversible circuit synthesis provides a way to translate reversible Boolean functions into quantum circuits.<n>We propose textQuantumEvo, an evolutionary framework that uses an LLM as a generator for QCC-aware BDD variable ordering.<n>H-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.
  arXiv  Detail & Related papers  (2026-09-04T16:25:01Z)
• Nonvariational quantum optimisation approaches to pangenome-guided sequence assembly [0.42970700836450487]
  We develop near-term quantum optimisation approaches for genome assembly problems.<n>We use the Iterative-QAOA framework, which combines a fixed linear-ramp QAOA schedule with iterative warm-start bias updates.<n>A custom circuit compilation strategy reduces hardware gate overhead by up to 67% compared with standard tools.
  arXiv  Detail & Related papers  (2026-04-07T17:17:34Z)
• An Efficient Quantum Classifier Based on Hamiltonian Representations [50.467930253994155]
  Quantum machine learning (QML) is a discipline that seeks to transfer the advantages of quantum computing to data-driven tasks.<n>We propose an efficient approach that circumvents the costs associated with data encoding by mapping inputs to a finite set of Pauli strings.<n>We evaluate our approach on text and image classification tasks, against well-established classical and quantum models.
  arXiv  Detail & Related papers  (2025-04-13T11:49:53Z)
• KodCode: A Diverse, Challenging, and Verifiable Synthetic Dataset for Coding [49.56049319037421]
  KodCode is a synthetic dataset that addresses the persistent challenge of acquiring high-quality, verifiable training data.<n>It comprises question-solution-test triplets that are systematically validated via a self-verification procedure.<n>This pipeline yields a large-scale, robust and diverse coding dataset.
  arXiv  Detail & Related papers  (2025-03-04T19:17:36Z)
• Resource-efficient context-aware dynamical decoupling embedding for arbitrary large-scale quantum algorithms [0.0]
  GraphDD is an efficient method for circuit-specific, optimal embedding of dynamical decoupling (DD) into executable quantum algorithms. We demonstrate that GraphDD refocuses both quasi-static single-qubit dephasing and crosstalk idling errors over the entire circuit. We verify the ability of GraphDD to deliver enhanced circuit-level error suppression on 127-qubit IBM devices.
  arXiv  Detail & Related papers  (2024-09-09T18:01:33Z)
• Compacting Binary Neural Networks by Sparse Kernel Selection [58.84313343190488]
  This paper is motivated by a previously revealed phenomenon that the binary kernels in successful BNNs are nearly power-law distributed. We develop the Permutation Straight-Through Estimator (PSTE) that is able to not only optimize the selection process end-to-end but also maintain the non-repetitive occupancy of selected codewords. Experiments verify that our method reduces both the model size and bit-wise computational costs, and achieves accuracy improvements compared with state-of-the-art BNNs under comparable budgets.
  arXiv  Detail & Related papers  (2023-03-25T13:53:02Z)
• DeepSeq: Deep Sequential Circuit Learning [10.402436619244911]
  Circuit representation learning is a promising research direction in the electronic design automation (EDA) field. Existing solutions only target combinational circuits, significantly limiting their applications. We propose DeepSeq, a novel representation learning framework for sequential netlists.
  arXiv  Detail & Related papers  (2023-02-27T09:17:35Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  We study the OOD generalization of neural algorithmic reasoning tasks. The goal is to learn an algorithm from input-output pairs using deep neural networks.
  arXiv  Detail & Related papers  (2022-11-01T18:33:20Z)
• Encoding trade-offs and design toolkits in quantum algorithms for discrete optimization: coloring, routing, scheduling, and other problems [0.0]
  We present an intuitive method for synthesizing and analyzing discrete (i.e., integer-based) optimization problems. This method is expressed using a discrete quantum intermediate representation (DQIR) that is encoding-independent. Second, we perform numerical studies comparing several runtime encodings. Third, we design low-depth graph-derived partial mixers (GDPMs) up to 16-level quantum variables.
  arXiv  Detail & Related papers  (2022-03-28T01:01:12Z)
• Towards Bi-directional Skip Connections in Encoder-Decoder Architectures and Beyond [95.46272735589648]
  We propose backward skip connections that bring decoded features back to the encoder. Our design can be jointly adopted with forward skip connections in any encoder-decoder architecture. We propose a novel two-phase Neural Architecture Search (NAS) algorithm, namely BiX-NAS, to search for the best multi-scale skip connections.
  arXiv  Detail & Related papers  (2022-03-11T01:38:52Z)
• QGo: Scalable Quantum Circuit Optimization Using Automated Synthesis [3.284627771501259]
  On NISQ devices, two-qubit gates such as CNOTs are much noisier than single-qubit gates. Quantum circuit synthesis is a process of decomposing an arbitrary unitary into a sequence of quantum gates. We propose a hierarchical, block-by-block optimization framework, QGo, for quantum circuit optimization.
  arXiv  Detail & Related papers  (2020-12-17T18:54:38Z)
• Auto-Encoding Twin-Bottleneck Hashing [141.5378966676885]
  This paper proposes an efficient and adaptive code-driven graph. It is updated by decoding in the context of an auto-encoder. Experiments on benchmarked datasets clearly show the superiority of our framework over the state-of-the-art hashing methods.
  arXiv  Detail & Related papers  (2020-02-27T05:58:12Z)
• Quantum Algorithm for Finding the Optimal Variable Ordering for Binary Decision Diagrams [0.0]
  An ordered binary decision diagram (OBDD) is a directed acyclic graph that represents a Boolean function.<n>This paper shows that a further speedup is possible with quantum computers by demonstrating the existence of a quantum algorithm that produces a minimum OBDD.
  arXiv  Detail & Related papers  (2019-09-27T12:52:07Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.