BDD2Seq: Enabling Scalable Reversible-Circuit Synthesis via Graph-to-Sequence Learning
Mingkai Miao, Jianheng Tang, Guangyu Hu, Hongce Zhang
二进制决策图(BDD)在许多电子设计自动化(EDA)任务中发挥了重要作用,因为它们对布尔函数的紧凑表示。 在基于BDD的可逆电路合成中,对于量子计算至关重要,所选的变量排序管理BDD节点的数量,从而管理资源消耗的关键指标,如Quantum Cost。 由于为BDD找到最佳变量排序是一个NP完全的问题,因此现有的后周系统通常会随着电路复杂性的增长而降解。 我们引入了BDD2Seq,一个图形到序列框架,将图形神经网络编码器与指针网络解码器和Diverse Beam Search相结合,以预测高质量的排序。 通过将电路网表视为图形,BDD2Seq学习传统方法所忽略的结构依赖性,产生较小的BDD和更快的合成。 对三个公共基准的广泛实验表明,BDD2Seq比现代方法的量子成本低约1.4倍,合成速度是现代方法的3.7倍。 据我们所知,这是第一个通过基于图形的生成模型和多样性促进解码来解决基于BDD的可逆电路合成中的变量排序问题的工作。
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 circui...
