迈向量子加速的大规模拓扑优化

《Computer Methods in Applied Mechanics and Engineering》：Towards quantum accelerated large-scale topology optimization

提出一种结合改进Dantzig-Wolfe分解与量子计算的拓扑优化方法，适用于大规模三维多材料结构设计，显著提升计算效率，尤其在量子硬件上实现数量级加速。

　　

叶志生|潘文晓

威斯康星大学麦迪逊分校机械工程系，美国威斯康星州麦迪逊市，53706

摘要

我们提出了一种高效的拓扑优化（TO）方法，该方法不仅提高了传统计算上的效率，还为利用量子计算进一步加速提供了实用途径。该方法针对大规模、多材料的三维（3D）连续结构进行优化，超越了以往仅限于小规模和单材料问题的量子TO研究。在基于离散变量TO框架（DVTO-MT）的基础上，该方法采用多割优化和信赖区域来减少迭代次数，从而降低偏微分方程（PDE）求解器的调用次数；同时引入改进的Dantzig-Wolfe（MDW）分解方法以进一步缩短每次迭代的优化时间。MDW方法利用问题的块角结构将混合整数线性规划（MILP）分解为规模较小的全局和局部子问题。在大型3D桥梁设计问题上的评估显示，计算时间大幅减少，即使对于具有超过5000万个变量的复杂设计，该方法也能保持稳健的性能，而传统MILP求解器在这种情况下往往无法收敛。此外，计算密集型的局部子问题被转化为等效的二次无约束二进制优化（QUBO）形式，以利用量子计算加速。所生成的QUBO仅需稀疏的量子比特连接性，这对于近期的量子硬件来说是一个关键考虑因素，并且构建成本较低，从而具有额外的加速潜力。随着问题规模的增加以及从单材料设计扩展到多材料设计，观察到的和估计到的加速效果更加显著，这突显了所提出方法结合量子计算在解决实际TO挑战时的潜力。

引言

从结构力学[1]、流体动力学[2][3][4]、电磁学[5]和光子学[6]到多物理场应用[7][8][9]，以及从汽车[10]到航空航天[11]等行业，对于设计高性能、节能和轻量化的组件、设备和结构的需求日益增长。拓扑优化（TO）作为一种强大的计算工具应运而生，它可以在满足物理和设计约束的同时，确定给定设计域内材料的最佳分布，以最大化结构或功能性能。TO可以处理离散桁架结构（设计具有有限维度并由有限参数集定义），也可以处理连续结构（设计表示为分布函数）。本研究重点关注后者，因为它在计算和理论上面临更大的挑战。在连续结构TO中，无论是结构力学、流体动力学还是多物理场，通常通过偏微分方程（PDE）的形式来表达控制物理规律。当受到设计约束（例如限制总体积或材料使用量）时，问题就变成了一个受PDE约束的优化问题。TO应用的扩展带来了巨大的计算挑战，这些挑战源于高维和复杂的设计空间、求解PDE的高成本，以及在优化过程中需要反复求解PDE。决定总计算时间的两个关键因素是：达到收敛所需的迭代次数（这决定了PDE求解器的调用次数）；以及每次迭代解决优化子问题所需的时间。因此，改进计算方法和框架以提高TO解决方案效率应侧重于减少迭代次数和加速每次迭代的解决时间。

作为受PDE约束的优化问题，TO需要通过有限元方法（FEM）对设计域进行离散化，每个元素代表一个潜在的材料位置。这导致了一个具有大量二进制（0/1）设计变量的优化问题，其中1表示材料的存在，0表示材料的缺失。连续状态变量对这些二进制变量的非线性依赖性使得TO问题成为大规模的混合整数非线性规划（MINLP）问题，受到等式和不等式约束。这类问题通常被认为是NP难问题[12]，使用传统方法[13][14][15][16][17][18][19]进行计算非常耗时。我们之前的工作引入了一个TO框架[20]，通过减少优化迭代次数，从而显著提高了计算效率，进而减少了PDE求解的频率。该框架称为DVTO-MT，它结合了广义Benders分解[21]和自适应信赖区域，将主子问题（从MINLP问题派生而来）表述为多割混合整数线性规划（MILP）问题。这种方法能够估计原始目标函数的上界和下界，加速了凸和非凸问题的求解收敛速度，无论是单材料还是多材料设计。与广泛使用的传统方法（如Solid Isotropic Material with Penalty (SIMP)[13]、Floating Projection (FP)[17]和Sequential Approximate Integer Programming (SAIP)[18]相比，该框架显著减少了优化迭代次数和FEM分析次数，同时实现了类似的目标函数值和优化的拓扑结构。为了将该框架扩展到更大的TO问题，需要改进MILP求解器。量子计算作为一种新兴范式，在组合优化任务[22][23][24][25][26][27]方面可能优于传统计算。例如，量子退火可以通过更快地逃离局部最优解来加速二次无约束二进制优化（QUBO）问题中的全局最小值搜索[28][29]。然而，直接将MILP问题转换为等效的QUBO问题引入了新的挑战。在TO中，一些设计约束通常转化为MILP中的全局约束，这些约束涉及所有设计变量。当映射到QUBO公式中时，这些全局约束会产生一个密集的哈密顿矩阵，即系数矩阵密集的QUBO。这不仅要求全连接量子比特，超出了大多数近期量子硬件的能力[30][31][32]，还会导致高昂的预处理成本。具体来说，构建QUBO的密集系数矩阵的计算成本随设计变量数量的增加而呈二次方增长，从而降低了整体效率，抵消了任何潜在的量子加速效果。

因此，本文提出了一种新方法，显著提高了解决大规模TO产生的MILP问题的效率和可扩展性。该方法还提供了一种实用的方法来利用量子计算的优势，仅需要稀疏的量子比特连接性，并确保构建QUBO的成本随问题规模线性增长。该方法基于改进的Dantzig-Wolfe（MDW）分解。利用其块角结构，MILP问题被分解为一系列规模较小的子问题，这些子问题被分类为全局或局部子问题，分别对应于全局和局部约束。与标准的Dantzig-Wolfe分解[33]不同，MDW公式旨在有效控制全局子问题的规模。结合MDW的DVTO-MT框架可以将计算时间减少几个数量级，并且在传统MILP求解器无法收敛的极端情况下（例如具有超过5000万个变量的设计）也能保持较低的运行时间。此外，占计算成本大部分的局部子问题本质上是二进制整数规划（BIP）问题，可以通过将其转换为等效的QUBO问题来利用量子计算进行加速。重要的是，每个局部子问题仅涉及局部约束，从而产生具有稀疏哈密顿矩阵的QUBO公式。这种稀疏性消除了全连接量子比特的需求，使该方法非常适合近期的量子硬件。由于每个局部子问题是独立的，所有QUBO都可以在每次MDW迭代中并行求解，从而实现显著的计算速度提升。

这项工作代表了之前将量子计算应用于TO以提高计算效率的努力的重大进步。与早期仅限于离散桁架结构[34][35]的研究不同（这些结构仅占TO应用的一小部分），本研究解决了更具挑战性的连续结构问题。它还超越了包括我们自己[21]和其他[36]在内的先前工作，这些工作专注于小规模、单材料设计，并且构建的QUBO具有密集的哈密顿矩阵，需要全连接量子比特，并且随着设计变量的增加导致QUBO构建成本呈二次方增长。

本文的其余部分组织如下：第2节介绍了用于3D连续结构多材料TO的DVTO-MT框架的构建方法。第3节介绍了所提出的MDW方法及其在传统和量子计算范式下的实现。第4节通过大规模3D桥梁设计案例，包括单材料和多材料情况以及不同的离散化分辨率，评估并比较了所提出方法与现有方法的解决方案质量和计算效率。最后，第5节总结了研究并强调了其关键贡献。

DVTO-MT的构建方法

考虑在连续域（Ω）内设计结构，其中材料分布的设计由指示函数ρ(x)表示，x ∈ Ω [37]。结构的物理平衡状态由受适当边界条件（BCs）约束的偏微分方程（PDE）控制。在设计由线性弹性控制的结构的背景下，控制PDE表示为：