基于机器学习的量子电路布局优化研究

作者与机构：
本文由来自英国伦敦帝国理工学院（Imperial College London）计算机系的Hongxiang Fan、Ce Guo和Wayne Luk共同完成，发表于2022年7月的DAC ‘22会议（Proceedings of the 59th ACM/IEEE Design Automation Conference）。

学术背景

量子计算（Quantum Computing）因在数据安全、量子化学等领域的潜力而备受关注。随着IBM、英特尔和谷歌相继发布49至72量子比特的处理器，硬件快速发展对软件工具链提出了更高要求。量子程序在实际设备上运行需经过逻辑合成（logic synthesis）和量子电路布局（Quantum Circuit Placement, QCP）两个关键步骤，其中QCP需将逻辑量子门映射到物理量子位，常因硬件连接限制需插入交换门（swap gates），不仅增加电路深度，还会降低计算保真度。然而，最小化交换门数量已被证明是NP完全问题。

传统启发式方法（如IBM的Qiskit和Cambridge Quantum的t|ket〉）存在最优性差距；精确方法（如OLSQ-swap）虽能提高最优性，但其计算复杂度随量子比特数指数增长。为突破这一瓶颈，本研究提出首个基于机器学习（ML）的端到端QCP框架，通过双层优化模型同时优化初始映射和交换策略。

研究方法

1. 问题建模与框架设计

将QCP构建为双层优化问题：
- 上层问题：优化初始量子位映射，最小化交换代价（swap cost），采用进化算法（Evolutionary Algorithm, EA）实现大规模离散空间搜索。
- 下层问题：给定初始映射，通过策略梯度强化学习（Deep Reinforcement Learning, DRL）优化交换策略，解决组合优化问题。

2. 核心技术实现

（1）DRL代理设计

• 状态空间：突破传统分层处理的局限性，构建包含全电路信息的矩阵：
  
  • 每行代表一个物理量子位及其关联的逻辑量子位；
    
  • 每列为时间步（level），元素值表示当前时间步的连接关系（-2表示无关联门）。
    
• 动作空间：定义为硬件允许的所有交换门操作，编码为整数对应边的索引。
  
• 奖励函数：包含四项——
  
  • 执行门奖励（+1/门）、完成奖励（+10）；
    
  • 交换惩罚（-3）、不可执行惩罚（+1）。
    
• 策略网络：采用三层MLP（64-64-96隐藏层），结合近端策略优化（PPO）算法训练。
  

（2）进化算法优化

• 种群初始化：生成合法初始映射（如IBM QX2的种群规模N_pop=40，Melbourne/Aspen-4为800）。
  
• 评估与选择：使用训练好的DRL代理生成交换策略，QCP模拟器计算累积奖励，优选前25%个体。
  
• 变异与交叉：变异概率P_mutate=0.5（通过合法交换实现），交叉概率P_cross=0.5。
  

（3）自主开发的QCP模拟器

基于OpenAI Gym实现，核心功能包括：
- 状态更新：根据DRL动作交换量子位矩阵的行；
- 门级执行：循环检测当前层可执行门，完成则左移矩阵并填充-2；
- 奖励反馈：动态计算门执行、交换插入等即时奖励。

关键结果

1. 知识迁移能力验证

以IBM QX2为例，训练电路mod5mils_65的DRL代理仅需21.2秒（GPU），在未参与训练的5个测试电路上，平均交换门数从22.8降至2.2（降幅90.4%），验证了框架的泛化能力（表1）。

2. 与启发式方法的对比

在18个基准电路（3-16量子比特）上的实验显示：
- IBM QX2：对4mod5-v0_18电路，比Qiskit减少20个交换门（25→5）；
- Rigetti Aspen-4：queko_15_1电路的交换门从38降至0，最优性提升100%（表2）。

3. 与精确方法的对比

与当前最优精确方法OLSQ-swap相比：
- 最优性：在17/18测试案例中匹配OLSQ的交换门数量；
- 效率：在IBM Melbourne上，vbe_adder_3案例的运行时从2183.6秒降至65.7秒（加速33倍）（表3）。

4. 最优性-运行时权衡

通过调整EA种群规模（400-1200），用户可灵活控制优化深度。例如mod_mult_55电路在N_pop=800时取得最佳平衡（交换门9个，耗时62.8秒）（图5）。

结论与价值

1. 科学价值：

   • 首次将DRL与EA结合解决QCP的NP难问题，为量子编译优化提供新范式；
     
   • 提出的全电路状态编码方法克服了分层处理的次优性局限。
     

2. 应用价值：

   • 在IBM、Rigetti等主流量子硬件上实现交换门数量100%的优化；
     
   • 相比精确方法实现40倍加速，为大规模量子电路布局提供可行方案。
     

创新亮点

1. 方法创新：

   • 双层优化框架同时解决初始映射（EA）和动态路由（DRL）问题；
     
   • 知识迁移机制使DRL代理可泛化至未见过的量子电路。
     

2. 工程贡献：

   • 开源QCP模拟器支持量子硬件的快速验证；
     
   • 模块化设计支持保真度约束等未来扩展。
     

未来方向

作者计划在三个方向延伸本工作：
1. 支持超大规模（>50量子比特）电路的映射优化；
2. 整合量子门保真度作为优化目标；
3. 开发噪声自适应的QCP算法。

本研究获英国EPSRC多项基金支持（EP/L016796/1、EP/N031768/1等），相关代码已整合至工业级量子编译工具链。