用大模型设计量子电路,让可逆逻辑更省资源。
LLM-Driven Algorithm Design for Quantum Circuit Synthesis based on Binary Decision Diagrams

- 用大模型生成变量排序启发式,优化量子电路成本
- 新方法在13.5%的函数上严格优于最佳基准,70.9%持平或胜出
- 特别适合来自不同数据源的复杂电路合成任务
量子电路是实现量子算法的核心,其中量子门必须为可逆。许多量子算法依赖布尔函数,因此需在量子电路中可逆实现。可逆电路综合提供将布尔函数转化为可逆电路的方法。二叉决策图(BDD)为此提供可扩展方案,但其结果严重依赖变量排序。现有排序启发式通常最小化BDD大小,因其与电路规模密切相关。然而,BDD大小并非量子电路成本(QCC)的精确代理。本文提出 exttt{QuantumEvo},一种基于大模型的进化框架,将大模型作为QCC感知的变量排序启发式生成器。不直接预测排序,而是从多个启发式家族初始化,通过标准BDD操作操纵变量排序,并由下游QCC选择候选启发式。发现的启发式HGA-QE修改遗传算法中的筛选步骤,使其更契合QCC。在基准测试集上,HGA-QE对每函数最优基线达到70.9%的平局或胜率,在13.5%的函数上严格最优。结果表明其具备广泛竞争力,尤其在源自不同数据源的两个基准套件中表现出更明显的相对优势。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。