在2024年ICLR上，Hao Wang、Chenyi Zhang和Tongyang Li三位研究人员发表了一篇引人注目的论文，题为“近似最优的最大损失函数量子优化算法”。这篇论文深入探讨了在优化和机器学习领域中一个关键问题——最小化多个凸、Lipschitz函数的最大值。这一问题在支持向量机（SVMs）等监督学习场景中尤为重要，因为它直接关联到最小化损失函数的最大值，这对于提升模型的训练效率和泛化性能具有显著意义。
在论文中，作者首先回顾了传统算法在处理此类问题上的进展。他们指出，现有的经典算法在查询一阶导数时会导致查询复杂度的显著增加。为了克服这一限制，作者提出了一种创新的量子算法，该算法在查询复杂度上实现了显著的优化，并接近于最优性能。
量子算法的核心在于量子零阶预言机（quantum zeroth-order oracle）的应用，这是一种在量子算法中广泛使用的机制，它允许算法在量子叠加状态下进行高效的查询。这种机制使得量子算法能够在较少的查询次数下达到与经典算法相同的优化效果。具体来说，作者提出的量子算法在查询复杂度上达到了O(√Nε^(-5/3) + ε^(-8/3))，相较于现有经典算法的O(Nε^(-2/3) + ε^(-8/3))，实现了二次量子加速。
为了证明量子算法的优越性，作者不仅提出了算法，还建立了量子下界，即量子算法至少需要O(√Nε^(-2/3))次查询。这一结果表明，他们提出的算法在处理大量函数时的效率是近似最优的。此外，作者还讨论了量子算法在实际应用中可能面临的挑战，如量子算法的实现难度和量子硬件的限制。
在技术层面，作者的量子算法基于经典的球优化加速方案，并利用量子采样来加速关键的采样步骤。他们首先准备了一系列量子态，然后通过量子算法识别出概率值最大的几个索引。在经典算法中，这一步骤需要O(N)次查询，而在量子算法中，这一复杂度被降低到了O(√NT)次查询，实现了查询复杂度的显著降低。
作者还提出了一种量子采样算法，用于从softmax分布中生成样本。这一算法结合了量子最大值查找和量子态准备等量子算法，能够在O(√NK log(1/δ))次查询内生成K个样本，其中K代表样本数量，δ代表失败概率。
在论文的最后部分，作者通过构建量子进度控制方法，提出了量子算法的量子下界。他们证明了任何试图解决优化问题的量子算法都必须通过一个适应性的“链结构”来获取足够的信息。这一链结构在经典优化问题下界证明中是一个成熟的概念。作者展示了在量子算法试图沿链结构前进时，必须解决一个无结构搜索问题。他们进一步证明了，对于任何量子算法，如果它在多轮无结构搜索问题上进行最多O(N)次查询，那么它在解决整个多轮问题时的总体成功概率是非常小的。
这篇论文在量子优化算法领域取得了重要进展。作者不仅提出了一种新的量子算法，还建立了量子下界，为量子计算在优化问题上的应用提供了理论基础。同时，他们也指出了量子算法在实际应用中可能遇到的挑战，为未来的研究指明了方向。
