具有收敛保证的迭代量子辅助最小二乘优化

《Journal of Computational Science》：Iterative quantum-assisted least squares optimization with convergence guarantees

量子辅助迭代线性回归方法i-QLS通过多阶段QUBO离散化与区间收缩机制，解决现有量子LS方法在硬件上的精度与可扩展性矛盾，并引入i-QLS+修正区间偏移问题，理论证明其几何收敛特性，实验验证支持175维非线性回归扩展。

　　

Supreeth Mysore Venkatesh|Antonio Macaluso|Diego Arenas|Matthias Klusch|Andreas Dengel

凯泽斯劳滕-兰道大学（RPTU），德国凯泽斯劳滕

摘要

本文介绍了i-QLS，这是一种基于量子辅助的迭代最小二乘优化方法，它利用量子退火技术来克服传统量子最小二乘方法的可扩展性和精度限制。与那些在当前量子退火器低量子比特数下表现不佳的基于QUBO的公式不同，i-QLS采用低精度运行，并通过迭代优化逐步提高精度。我们的贡献包括最小二乘问题的离散化方案、QUBO构建、优化动态，并提供了形式化的收敛性分析，证明一旦真实最优解位于预先定义的区间内，搜索范围的宽度在每次迭代中都会呈几何级数减小，从而实现参数估计的指数级收敛。我们还发现了一个问题：当真实最优解位于初始离散区间之外时，引入了i-QLS+版本，该版本通过边界选择时的确定性平移步骤来替代区间缩小机制。这种机制保证了在有限时间内进入正确的搜索区域，并恢复了与基线方法相同的快速几何级数优化效果。我们的实证评估涵盖了在多代D-Wave量子退火器上的实验、两种不同的硬件嵌入式实现、对错误指定区间的鲁棒性测试，以及针对多达175个特征的回归问题的可扩展性。此外，我们还展示了该框架如何通过基于样条的建模自然扩展到非线性回归。

总体而言，尽管i-QLS的性能尚未超过最先进的经典求解器，但它为近期量子硬件上的量子辅助回归提供了一个可扩展、理论上有依据且实际有效的框架。这项工作的早期版本已发表在我们的ICCS会议论文中（Venkatesh等人，2025年）。

引言

机器学习方法的一个关键区别在于它们的优化策略，这些策略受到模型对输入特征与目标变量之间关系的假设的影响。基于神经网络的模型依赖于非凸优化，通常需要大量的数据集和较长的训练时间，因为它们难以逃离局部最小值[1]。相比之下，基于最小二乘优化的参数模型（如样条[3]和支持向量机[4]）受益于凸优化，从而确保了全局最优性和理论上的鲁棒性。然而，最小二乘优化中的矩阵运算的多项式复杂性随着特征数量的增加而引入了显著的计算限制，限制了其可扩展性。

最近，已经提出了几种用于监督学习任务的量子机器学习模型[5]。然而，很少有研究探索了仅利用近期量子计算进行训练和参数估计的潜力，同时保持经典模型用于推理[6]、[7]。特别是，量子退火被提出作为一种方法，将最小二乘（LS）优化问题重新表述为二次无约束二进制优化（QUBO）问题，以便在量子硬件上执行[8]、[9]、[10]。尽管取得了这些进展，量子退火方法仍面临两个根本性瓶颈。首先，可扩展性仍然是一个主要挑战，因为量子比特数量与优化权重的精度之间存在权衡。其次，这些方法主要适用于线性模型，无法捕捉现实世界问题的复杂性。我们并不声称量子优势；相反，我们提出了一种迭代优化策略，在当前硬件限制下通过牺牲精度来提高可扩展性，任何未来的优势将取决于改进的硬件和问题类型，届时经典求解器将变得不切实际。

在这项工作中，我们引入了i-QLS，这是一种迭代量子辅助的最小二乘优化方法，它用一系列固定大小的QUBO替换了单个高精度QUBO，并在退火迭代过程中逐步细化这些QUBO的区间。这使得该方法具有随时可用的特性，并通过牺牲精度来适应当前的硬件限制。我们为在范围内解决问题的情况提供了收敛性分析（引理4.1），指出了在错误指定边界下的缓慢漂移故障模式（引理4.2），并引入了i-QLS+，这是一种在边界选择时通过确定性平移步骤来替代区间缩小的变体。这种机制保证了在有限时间内进入正确的搜索区域，并恢复了与基线方法相同的快速几何级数优化效果。我们的实证评估包括在多代D-Wave量子退火器上的实验、两种不同的算法硬件实现、对错误指定区间的鲁棒性测试，以及对具有多达175个特征的回归问题的可扩展性测试。我们还展示了该框架如何通过基于样条的建模自然扩展到非线性回归。

总之，虽然i-QLS的性能尚未超过最先进的经典求解器，但它为近期量子硬件上的量子辅助回归建立了一个可扩展、理论上有依据且实际有效的框架。这项工作的早期版本已发表在我们的ICCS会议论文中（Venkatesh等人，2025年）。

引言

机器学习方法的一个关键区别在于它们的优化策略，这些策略受到模型对输入特征与目标变量之间关系假设的影响。基于神经网络的模型依赖于非凸优化，通常需要大量的数据集和较长的训练时间，因为它们难以逃离局部最小值[1]。相比之下，基于最小二乘优化的参数模型（如样条[3]和支持向量机[4]）受益于凸优化，从而确保了全局最优性和理论上的鲁棒性。然而，最小二乘优化中的矩阵运算的多项式复杂性随着特征数量的增加而引入了显著的计算限制，限制了其可扩展性。

最近，已经提出了几种用于监督学习任务的量子机器学习模型[5]。然而，相对较少的研究探索了仅利用近期量子计算进行训练和参数估计的潜力，同时保持经典模型用于推理[6]、[7]。特别是，量子退火被提出作为一种方法，将最小二乘（LS）优化问题重新表述为二次无约束二进制优化（QUBO）问题，以便在量子硬件上执行[8]、[9]、[10]。尽管取得了这些进展，量子退火方法仍面临两个根本性瓶颈。首先，可扩展性仍然是一个主要挑战，因为量子比特数量与优化权重的精度之间存在权衡。其次，这些方法主要适用于线性模型，无法捕捉现实世界问题的复杂性。我们并不声称量子优势；相反，我们提出了一种迭代优化策略，在当前硬件限制下通过牺牲精度来提高可扩展性，任何未来的优势将取决于改进的硬件和问题类型，届时经典求解器将变得不切实际。

在这项工作中，我们引入了i-QLS，这是一种迭代量子辅助的最小二乘优化方法，它用一系列固定大小的QUBO替换了单个高精度QUBO，并在退火迭代过程中逐步细化这些QUBO的区间。这使得该方法具有随时可用的特性，并通过牺牲迭代次数来适应当前的硬件限制。我们为在范围内解决问题的情况提供了收敛性分析（引理4.1），指出了在错误指定边界下的缓慢漂移故障模式（引理4.2），并引入了i-QLS+，这是一种在边界选择时通过确定性平移步骤来替代区间缩小的变体。通过实验证实了其收敛行为、对错误指定的鲁棒性以及在两代D-Wave硬件上的可扩展性，并将框架扩展到了基于样条的非线性回归。

总结来说，尽管i-QLS的性能尚未超过最先进的经典求解器，但它为近期量子硬件上的量子辅助回归提供了一个可扩展、理论上有依据且实际有效的框架。这项工作的早期版本已发表在我们的ICCS会议论文中（Venkatesh等人，2025年）。

介绍

机器学习方法的一个关键区别在于它们的优化策略，这些策略受到模型对输入特征与目标变量之间关系假设的影响。基于神经网络的模型依赖于非凸优化，通常需要大量的数据集和较长的训练时间，因为它们难以逃离局部最小值[1]。相比之下，基于最小二乘优化的参数模型（如样条[3]和支持向量机[4]）受益于凸优化，从而确保了全局最优性和理论上的鲁棒性。然而，最小二乘优化中的矩阵运算的多项式复杂性随着特征数量的增加而引入了显著的计算限制，限制了其可扩展性。

最近，已经提出了几种用于监督学习任务的量子机器学习模型[5]。然而，相对较少的研究探索了仅利用近期量子计算进行训练和参数估计的潜力，同时保持经典模型用于推理[6]、[7]。特别是，量子退火被提出作为一种方法，将最小二乘（LS）优化问题重新表述为二次无约束二进制优化（QUBO）问题，以便在量子硬件上执行[8]、[9]、[10]。尽管取得了这些进展，量子退火方法仍面临两个根本性瓶颈。首先，可扩展性仍然是一个主要挑战，因为量子比特数量与优化权重的精度之间存在权衡。其次，这些方法主要适用于线性模型，无法捕捉现实世界问题的复杂性。我们并不声称量子优势；相反，我们提出了一种迭代优化策略，在当前硬件限制下通过牺牲精度来提高可扩展性，任何未来的优势将取决于改进的硬件和问题类型，届时经典求解器将变得不切实际。

在这项工作中，我们引入了i-QLS，这是一种迭代量子辅助的最小二乘优化方法，它用一系列固定大小的QUBO替换了单个高精度QUBO，并在退火迭代过程中逐步细化这些QUBO的区间。这使得该方法具有随时可用的特性，并通过牺牲迭代次数来适应当前的硬件限制。我们为在范围内解决问题的情况提供了收敛性分析（引理4.1），指出了在错误指定边界下的缓慢漂移故障模式（引理4.2），并引入了i-QLS+，这是一种在边界选择时通过确定性平移步骤来替代区间缩小的变体。通过实验证实了其收敛行为、对错误指定的鲁棒性以及在两代D-Wave硬件上的可扩展性，并将框架扩展到了基于样条的非线性回归。

总结来说，本文的主要贡献包括：

• •
  i-QLS：迭代QUBO细化。 我们提出了一种量子辅助的最小二乘优化策略，用一系列小尺寸的固定大小QUBO替换了单个高精度QUBO，从而克服了限制单次优化的精度-量子比特数量权衡。此外，我们阐明了该框架如何扩展和与现有工作（如[11]、[12]）的关系，并明确指出了与先前迭代范围细化方法的概念和技术差异。
• •
  理论保证。 引理4.1表明，只要真实权重位于初始区间内，i-QLS就能以指数级速度收敛到最优解。相反，引理4.2表明，如果最优解位于初始边界之外，区间中点向最优解的移动速度非常缓慢，导致总移动距离有限。
• •
  i-QLS+：鲁棒区间校正。 为了解决这种缓慢漂移行为，我们引入了i-QLS${}^{+}$
  ，它在选择边界值时用确定性平移步骤替代了区间缩小。这种修改保证了在有限时间内进入正确的区间，之后恢复几何级数优化。
• •
  可扩展性、鲁棒性和随时计算。
  我们展示了所提出的混合迭代方案如何支持随时评估，并在固定量子比特预算下实现逐步优化。
• •
  扩展到非线性回归。
  我们通过结合基于样条的非线性函数近似，将迭代框架扩展到了非线性回归。
• •
  全面的实证验证。
  我们通过实验证实了引理4.1和引理4.2预测的行为，观察到了指数级收敛和指数级缓慢的边界漂移，并证明i-QLS+消除了后者。此外，我们还将我们的方法与经典最小二乘求解器和经典QUBO求解器进行了比较，并在两代D-Wave量子硬件（Advantage和Advantage2）上进行了评估。

本文的其余部分组织如下。第2节回顾了量子辅助回归和基于样条的建模的相关工作。第3节介绍了最小二乘优化和样条公式所需的预备知识。第4节介绍了我们的方法框架，包括离散化策略、QUBO构建、i-QLS算法以及用于校正区间错误指定的增强型i-QLS+变体。第5节提供了全面的实证评估，涵盖了收敛行为、在经典和量子后端上的可扩展性、在错误指定区间下的鲁棒性，以及通过样条扩展到非线性回归。最后，第6节讨论了我们的发现的意义并总结了本文。

相关工作

基于门的量子计算最近被提出用于通过开发量子样条[13]、[14]来处理非线性近似。样条是一种具有平滑约束的分段多项式函数，为在结构化回归框架内建模非线性关系提供了有效工具。在量子样条的初始公式[13]中，采用了基于B样条[15]的特定最小二乘公式来利用计算优势

预备知识

最小二乘优化旨在最小化回归问题中观测值和预测值之间的平方差之和，以确定输入变量和目标之间的最佳线性关系。由于其简单性和效率，这种方法成为许多统计模型的基础[2]。形式上，给定设计矩阵$X\in R^N$和目标向量$y\in R^N$，经典最小二乘估计器寻找参数向量