# 量子凸优化：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 覆盖

- Zoo 418、420：[Quantum Algorithms and Lower Bounds for Convex Optimization](https://arxiv.org/abs/1809.01731) 与 [Convex Optimization Using Quantum Oracles](https://arxiv.org/abs/1809.00643).
- Zoo 419：convex-body volume estimation。
- Zoo 130、146--148、223：quadratic/multilinear polynomial 与 Hamming-basin 结构化搜索。
- Zoo 461、477、497：linear programming、nonsmooth no-go 与 norm-constrained regression。