作者: Xin Wei Lee, Hoong Chuin Lau

1. 核心物理图象

这篇论文的核心思想是：为量子计算机解决带约束的优化问题设计一个更“聪明”的罚函数。

传统方法在处理“不能超过某个上限”这类不等式约束时，会引入额外的“虚拟变量”（slack variables）来将不等式转化为等式，但这会像给问题“注水”一样，增加问题的复杂度，在量子计算机上需要更多量子比特，也让优化问题变得更难解。

本文的贡献是提出了一种无需引入虚拟变量的新罚函数。它巧妙地利用一个“阶跃函数”作为惩罚：一旦违反约束就施加一个大的惩罚，否则惩罚为零。为了在量子计算机上高效计算这个非线性函数，作者采用了有限采样和条件风险价值等采样技术，最终在更少量子比特的情况下，找到了比传统方法更好的解决方案，并且在实际的离子阱量子计算机上验证了其可行性。

2. 关键术语解释

• 条件风险价值：一种用于评估风险的金融概念。在这篇论文中，它被用来筛选量子计算机采样得到的众多解。它不是计算所有采样的平均质量，而是只关注最好的那一小部分（比如前10%）解的平均质量。这样做的好处是，算法能更专注于找到高质量的解，而不会被大量平庸的解“带偏”。
• 有限采样：一种通过有限次数的测量来估计某个物理量平均值的方法。由于量子计算是概率性的，一次测量只能得到一个结果。多次测量后，这些结果的平均值就近似于理论上的真实平均值。本文用它来高效估计包含非线性罚函数的总能量的期望值，避免了计算量随问题规模指数增长的难题。
• 自定义惩罚函数：本文的核心创新。它不是使用传统的二次型惩罚，而是用一个非线性的阶跃函数来惩罚违反约束的解。这个函数非常简单：满足约束时值为0，违反约束时值为1。这种方法避免了引入额外的变量，直接、清晰地区分了可行与不可行解。

3. 主要贡献

1. 提出了无虚拟变量的罚函数方法：该方法直接使用阶跃函数作为惩罚，无需引入任何额外的“slack”变量，从而大幅减少了求解问题所需的量子比特数量，简化了优化空间。
2. 高效的非线性惩罚计算方法：针对非线性罚函数在量子计算机上计算期望值困难的问题，创新性地采用了“有限采样”方法，避免了指数级的计算复杂度，使得该方法在更大规模问题上依然可行。
3. 结合了条件风险价值提升优化效果：在采样计算的基础上，进一步引入条件风险价值优化目标，引导算法专注于寻找质量最高的解，显著提升了最终解的质量（更小的优化间隙）和求解的稳定性。
4. 在真实量子硬件上验证了可行性：不仅在数值模拟上取得了优于传统方法的结果，还在Quantinuum H2离子阱量子计算机上对一个小规模实例进行了实验，成功找到了问题的最优解，展示了该方法的实际应用潜力。

4. 研究方法

论文的研究方法主要包括以下步骤：

1. 问题建模：将多维背包问题这类带约束的优化问题，建模成最小化一个目标函数加上一个自定义惩罚函数的总和。这个惩罚函数是阶跃函数，用于标记违反约束的情况。
2. 量子电路设计：使用一个通用的、硬件高效的硬件高效拟设电路来生成试探态。该电路仅包含单比特旋转门和两比特的控制-Z门，无需任何复杂的约束保持电路或额外的辅助量子比特。
3. 期望值计算：通过有限采样方法，从量子电路中采样大量的比特串（候选解），然后直接计算每个样本对应的总损失函数值，并用其平均值来估计能量期望。这样巧妙地避开了直接计算非线性罚函数期望值的指数级困难。
4. 优化增强：在计算期望值时，可以选择性地使用条件风险价值方法，即仅对采得的、损失值最低的前α比例的样本取平均，以此作为优化目标，从而更鲁棒地引导优化方向。
5. 实验验证：在多个标准的多维背包问题上，与传统的“slack变量+QUBO”方法进行对比。实验中，通过IBM Qiskit模拟器进行无噪声模拟，并在Quantinuum H2量子计算机及其模拟器上进行了含噪声的测试。

5. 实验结果与结论

关键结论:

• 性能领先：在无噪声模拟的12个测试实例中，使用自定义罚函数和条件风险价值的方法，在所有实例上的优化间隙（解的质量与最优解的差距）都低于传统的slack变量方法。最优时，对于50变量的最大实例，其中位优化间隙可低至0.0076。
• 更鲁棒：相比有限采样，结合条件风险价值的方法在优化间隙和采样到最优解的概率这两个指标上，表现得更稳定，方差更小。
• 硬件可行性：在Quantinuum H2量子计算机上的测试表明，对于10比特的小实例，该方法训练出的电路能在真实硬件上成功找到最优解（条件风险价值方法），证明了该方法在当前噪声量子硬件上的可行性。

对领域的启示与开放性问题:

• 这篇论文表明，精心设计罚函数是解决量子优化问题中复杂约束的一个关键且有效的方向，特别是在近期的噪声量子设备上。
• 实验也暴露了当前量子硬件的局限性，如训练VQE时存在的队列时间长、连接不稳定等问题。未来的研究方向是探索非变分的量子优化算法（如Grover自适应搜索），或利用量子比特重置和中途测量等非酉操作，以克服这些实际困难。

6. 论文标签

量子算法, 编译与优化, 模拟

📄 点击此处展开/折叠原文 PDF

原文链接： CVaR-Assisted Custom Penalty Function for Constrained Optimization