技术摘要：量子次模函数最大化

问题陈述

本研究调查了在两种基本设定下，最大化非负次模函数的量子查询复杂度：

1. 无约束最大化： 寻找一个子集 $S \subseteq N$ 以最大化 $f(S)$，其中 $f$ 是一个非负次模函数。
2. 基数约束最大化： 寻找一个满足 $|S| \le k$ 的子集 $S$ 以最大化 $f(S)$，其中 $f$ 额外满足单调性。

本研究在**精确可逆数字值查询模型（exact reversible digital value-oracle model）**下运行。在该模型中，算法可以通过一个可逆查询算子 $O_f: |S\rangle|z\rangle \mapsto |S\rangle|z \oplus \text{enc}(f(S))\rangle$ 来查询任何子集（无论是否可行）的函数值。复杂度衡量标准是查询次数，包括在相干叠加态及其逆过程中的查询调用。目标是确定实现特定近似比（相对于最优值 $OPT_u$ 或 $OPT_k$）所需的查询复杂度。

方法论

本文介绍了一种量子算法，利用其准备编码函数值的相位态并进行同步测量以提取边际信息的能力。

1. 无约束最大化

无约束算法结合了同步双贪婪框架（simultaneous double-greedy framework）与量子梯度估计器。

• 框架： 它维护两个分数向量 $x \le y$，并根据估计的梯度将它们向共同解移动。移动过程按添加元素到 $x$ 的正增益与从 $y$ 中移除元素的增益比例进行拆分。
• 量子估计器： 该算法并非逐个坐标评估梯度，而是准备一个子集的乘积分布叠加态，并应用相位 $e^{i\lambda f(S)}$。通过对其他寄存器进行迹运算并在赤道面上测量量子比特，它采样边际增益的特征函数。
• 傅里叶重构： 为了将三角统计量转换为均值，估计器将边际增益分解为几何级数增长幅度的“层”。它使用傅里叶重构来估计这些层，并采用一种筛选机制来抑制来自非活跃坐标的误差。这使得总误差能够随实际端点边际增益缩放，而非受全局界限限制。
• 随机初始化： 算法使用随机括号（即一对集合 $X \subseteq Y$）进行初始化，以确保势函数保持有界且量子信号强度非零。

2. 基数约束最大化

约束算法利用同步边际得分估计和振幅放大。

• 联合评分： 它通过估计随机候选元素的“得分”来评估一个随机池，得分定义为在均匀随机前驱上下文中的期望边际增益，并被截断在某个密度阈值。单个量子电路准备一个状态，通过测量所有池量子比特，可以同时获得所有得分的有界估计量。
• 批处理过滤： 高得分元素被过滤进一个“认证批次（certified batch）”。由于次模性质（收益递减），这些得分之和可作为整个批次增益的证明。
• 摊销搜索： 算法采用量子搜索（振幅放大）来寻找具有足够归一化增益的批次。至关重要的是，搜索成本是摊销的：寻找一个批次的成本被计入其产生的增益中。这避免了经典贪婪轮次中的乘法惩罚——在经典算法中，无论搜索是否成功，每一轮都要支付搜索代价。
• 目标搜索： 通过在目标值的几何网格上进行二分查找来确定最优近似，并利用认证批次来验证可行性。

3. 下界

本文使用改编自 Bennett 等人 (1997) 的**混合论证（hybrid argument）**建立了量子下界。

• 困难族： 构建了一系列次模函数，这些函数在大多数输入上与公共参考函数完全一致，但在极小比例的“隐藏”实例上存在差异。
• 一致区域： 对于无约束最大化，困难实例基于隐藏划分（Feige 等，2011）。对于基数约束，则使用了 Feldman 和 Kuhnle (2025) 的构造。
• 数字编码： 为了适配精确数字查询模型，作者引入了一种技术，通过添加公共松弛量（public slack）并进行二进取舍（dyadic rounding）来保持次模性、单调性以及在非隐藏输入上与参考函数的精确一致性。

核心贡献与结果

1. 无约束最大化

• 算法： 该量子算法实现了 $(1/2 - \varepsilon)$-近似。
• 查询复杂度： 使用 $O_\varepsilon(\log n)$ 次查询。
• 分离度： 这确立了与经典下界的指数级分离。任何实现严格高于 $1/4$ 近似比的经典随机算法都需要 $\Omega(n / \log n)$ 次查询 (Li 等，2022)。

2. 基数约束最大化

• 算法： 该有界误差量子算法实现了 $(1 - 1/e - \varepsilon)$-近似。
• 查询复杂度： 复杂度为 $\tilde{O}_\varepsilon(\min\{\sqrt{n}, n/k\})$。
  • 当 $k = o(n)$ 时，相比于经典近线性下界 ($\Omega(n / \log n)$ 或 $\Omega(n / \log^2 n)$)，提供了二次加速（忽略对数因子）。
  • 当 $k = cn$且固定有理数$c < 1 - 1/e - \varepsilon$时，复杂度降至$O_{\varepsilon, c}(\log n)$，从而实现了相对于经典$\Omega(n / \log n)$ 下界的指数级分离。
• 机制： 加速源于同时估计边际得分，并将搜索成本摊销到所获增益中，而不是在每一次贪婪步骤中都支付完整的搜索代价。

3. 量子下界

本文证明了在某些近似阈值下，量子计算并不提供指数级加速：

• 无约束： 实现优于 $1/2 + \varepsilon$ 的比例需要 $\exp(\Omega(\varepsilon^2 n))$ 次查询。
• 基数约束： 当 $k/n \le \varepsilon$ 时，实现优于 $1 - 1/e + \varepsilon$ 的比例需要 $\exp(\Omega(\varepsilon^2 k))$ 次查询。
• 常数因子： 对于任何常数近似比 $a$，实现该比例需要 $\Omega(\sqrt{n/k})$ 次查询。这在对数因子范围内与上界相匹配，表明对于小预算，$\sqrt{n}$ 的依赖关系是优化的。

意义与主张

作者声称这项工作提供了针对两种通用离散次模最大化问题的首个量子值查询近似算法。

• 指数级分离： 其主要意义在于展示了量子查询可以在特定参数范围内解决无约束次模最大化和稠密基数约束最大化问题，其查询复杂度仅为多项式对数级，而经典算法若要超越特定的近似阈值（分别为 $1/4$ 和 $1-1/e$），则需要多项式（通常是线性）级别的查询。
• 进一步加速的障碍： 本文阐明了量子优势的极限。虽然在特定区间内存在指数级加速，但作者证明，试图超越经典的近似阈值（例如在无约束情况下超过 $1/2$，或在约束情况下超过 $1-1/e$）对于量子算法而言仍然是指数级困难的。
• 方法论进展： 该工作引入了通过相位态进行同步边际估计以及通过傅里叶重构进行处理的技术，并提出了一种在优化循环中对量子搜索进行摊销分析的新颖方法，这些方法可能适用于其他组合优化问题。

文章总结道，尽管量子计算在特定参数区间内能显著降低查询复杂度，但它并不能绕过与提高经典近似阈值相关的根本困难障碍。