用图神经网络预测最优变量顺序，显著降低量子电路资源消耗
BDD2Seq: Enabling Scalable Reversible-Circuit Synthesis via Graph-to-Sequence Learning
- 将电路网表建模为图，用GNN+指针网络生成变量顺序
- 相比现有算法，量子代价降低约1.4倍，合成速度提升3.7倍
- 首次用生成式模型解决BDD变量排序问题，适合量子电路设计者
二元决策图（BDD）在电子设计自动化中因能紧凑表示布尔函数而广泛应用。在基于BDD的可逆电路综合中，变量顺序直接影响BDD节点数量，进而决定量子代价等关键资源指标。由于最优变量顺序求解是NP难问题，现有启发式方法随电路复杂度增加性能下降。本文提出BDD2Seq，一种图到序列框架，结合图神经网络编码器、指针网络解码器与多样化的束搜索，预测高质量变量顺序。通过将电路网表视为图，该方法学习了传统启发式忽略的结构依赖关系，实现了更小的BDD和更快的综合速度。在三个公开基准上的实验表明，BDD2Seq相比现代启发式算法实现约1.4倍的量子代价降低和3.7倍的合成速度提升。据我们所知，这是首个采用基于图的生成模型与多样性解码策略解决BDD基可逆电路综合中变量排序问题的工作。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。