量子凸优化：Oracle 转换、近似梯度与维数平方加速

凸优化没有局部伪极小值，但在黑盒模型中仍要花大量查询定位可行域和目标斜率。量子算法可在叠加网格上估计全部梯度分量，并把 membership oracle 近常数次转换成 separation oracle；配合 cutting-plane 方法，\(d\) 维优化的查询数从经典近二次降到近线性。优势依赖 oracle 类型，若已直接给完整 gradient，某些 nonsmooth 问题没有量子加速。

1. Convex body 与 oracle 层级

设 \(K\subset\mathbb R^d\) convex，已知

\[ B(0,r)\subseteq K\subseteq B(0,R), \]

condition ratio \(\kappa=R/r\) 有界。常见 oracle：

  1. Membership \(\operatorname{MEM}_K(x)\)：判断 \(x\in K\)（允许边界 tolerance）。

  2. Separation：若 \(x\notin K\)，返回 \((a,b)\) 使 $\( a\cdot x>b,\qquad a\cdot y\le b\quad\forall y\in K. \)$

  3. Optimization：给方向 \(c\)，近似求 \(\min_{x\in K}c\cdot x\)。

目标函数版本再给 convex \(f\) 的 value oracle。不同 oracle 信息量不同，复杂度比较必须通过显式 reduction。

2. Separation 为何是 cutting plane 核心

Ellipsoid/center-of-gravity/volumetric cutting-plane 算法维护包含最优点的 localization region \(K_t\)。在 query point \(x_t\)：

  • 若不可行，separation hyperplane 切掉不含 \(K\) 的一侧；

  • 若可行但目标未最优，subgradient \(g_t\in\partial f(x_t)\) 给 $\( f(y)\ge f(x_t)+g_t\cdot(y-x_t), \)$ 用目标 cut 缩小候选区域。

适当中心选择每次把体积按常数/可控比例缩小，迭代约

\[ \widetilde O(d) \]

次 separation calls。经典瓶颈是从 weak membership/value 数据构造 \(d\) 维分离向量，常需 \(\Omega(d)\) 次局部探测，总 membership queries 近 \(d^2\)。

3. 一次量子查询如何给全部梯度分量

在 \(x_0\) 周围网格制备

\[ \frac1{M^{d/2}} \sum_{z\in\{-M/2,\ldots,M/2-1\}^d}|z\rangle. \]

相位查询

\[ |z\rangle \mapsto e^{2\pi i S f(x_0+h z)}|z\rangle. \]

若 \(f\) 在小盒内近似线性：

\[ f(x_0+hz) =f(x_0)+h\nabla f(x_0)\cdot z+O(h^2\|z\|^2L), \]

忽略全局相位后，各坐标寄存器携带线性 phase。分别逆 QFT，测量得到全部 \(d\) 个梯度分量的离散估计。经典 value oracle 至少需 \(d+1\) 个点形成有限差分；量子 query 将它们相干合并。

精度不免费：选择 \(h,M,S\) 要平衡 Taylor remainder、oracle value error 和 Fourier resolution，复杂度含 smoothness 与 \(1/\epsilon\)。

4. Membership 到 Separation 的量子转换

Membership 是不连续 bit，不能直接求梯度。算法构造平滑 convex surrogate，例如到 \(K\) 的 gauge/radial boundary/distance 的近似：沿射线用 membership binary search 找边界，再随机平滑使函数 Lipschitz 可微。

对外点 \(x\)，surrogate 的近似 gradient \(a\) 指向支持超平面法向。量子 gradient estimation 用

\[ \widetilde O(1) \]

次相干 membership/value queries 得近似 \(a\)，而经典需要 \(\Omega(d)\) membership queries。误差 hyperplane 允许一个 boundary slack，与 weak oracle tolerance 匹配。

把该转换插入 \(\widetilde O(d)\) 次 cutting-plane 迭代，得到

\[ \widetilde O(d) \]

membership/evaluation queries 的 convex optimization algorithm，相对最佳已知经典黑盒查询约平方改善。

5. Lower bounds 与 interior point

通过随机隐藏方向/凸体 packing，可构造大量 oracle 在少量查询下几乎不可分。已知 quantum lower bounds：

\[ \widetilde\Omega(\sqrt d) \]

级 evaluation/membership queries；若没有已知 interior point，separation queries 甚至需 \(\Omega(d)\)。所以一般 convex optimization 不存在指数维数加速，当前上界与 lower bound 最多留 polynomial gap。

若 oracle 直接返回完整 subgradient \(g\in\mathbb R^d\)，一次经典 query 已含 \(d\) 个数。对 nonsmooth convex optimization，迭代 lower bounds 显示量子不能普遍优于 gradient descent/subgradient 方法；Jordan 型“同时读 d 分量”优势已被 oracle 预付。

6. Volume estimation

凸体体积可沿 nested bodies

\[ K_0\subset K_1\subset\cdots\subset K_L=K \]

写成比值乘积

\[ \operatorname{vol}(K) =\operatorname{vol}(K_0) \prod_i \frac{\operatorname{vol}(K_{i+1})} {\operatorname{vol}(K_i)}. \]

经典 hit-and-run/ball walk 采样每个 \(K_i\)；量子 walk 平方改善 mixing gap，amplitude/mean estimation 改善比值精度。整体在维数与误差上获得 polynomial（常为近 quadratic）speedup，但仍依 rounding、warm start、isoperimetric gap 和 membership oracle。

7. 结构化特殊问题

二次函数

\[ f(x)=\tfrac12x^TAx-b^Tx \]

的 gradient \(Ax-b\)；量子高阶 derivative/interpolation 可用 \(O(d)\) 而非 \(O(d^2)\) value queries 学矩阵/求 minimum（输出 \(d\) 维点仍需线性时间）。有限域 multilinear polynomial 也有类似 query factor-\(d\)。

Linear programming 可用 quantum interior-point linear-system 子程序获得 polynomial speedups，但 condition number、tomography/classical iterate 和精度常决定实际优势。Norm-constrained linear regression 属于有结构 convex problem，也有匹配 lower-bound 分析。

8. 小结与习题

  • Cutting-plane 需要 separation/subgradient，约 \(\widetilde O(d)\) 轮。

  • 量子 Fourier gradient estimation 同时读出 \(d\) 个斜率，近常数 membership queries 可构造 separation。

  • 总 query 近 \(d\)，相对经典近 \(d^2\)；general lower bounds 排除普适指数优势。

  • Oracle 若已返回 gradient，或要求完整高维输出，优势会缩小。

  1. 推导 convex subgradient cut 为什么保留 minimizer。

  2. 对线性函数计算网格 phase 与逆 QFT 输出。

  3. 解释 membership bit 需要平滑后才能求 gradient。

  4. 比较 value、gradient、separation 三种 oracle 的每次输出信息量。

参考文献与 Zoo 覆盖