量子凸优化

凸优化是应用数学中最重要的”可解”问题类：只要问题是凸的，就不存在局部伪极小值，任何下降方向都通向全局最优。但这不等于便宜。在黑盒（oracle）模型中，算法看不到目标函数和可行域的解析表达式，只能通过查询一点点挖信息：这个点可行吗？函数值是多少？谁给我一个分离超平面？经典算法要在 $d$ 维空间里逐个坐标探测，仅”把 membership oracle 变成 separation oracle”这一步就要花近 $d$ 次查询，导致总查询量随维数近二次增长。

量子算法提供了两个新的杠杆。第一个是 Jordan 型梯度估计：在叠加网格上做一次相位查询，配合逐坐标逆量子 Fourier 变换（QFT），就能一次读出全部 $d$ 个梯度分量，而经典有限差分至少要 $d+1$ 个点。第二个是把这套梯度估计嫁接到”membership oracle $\to$ separation oracle”的转换上：经典需要 $\Omega (d)$ 次局部探测的分离方向，量子用近常数次相干查询就能近似构造。配合 cutting-plane 方法的 $\tilde{O}(d)$ 轮迭代，$d$ 维凸优化的总查询数从经典的近 $d^2$ 降到近 $d$，实现维数上的平方加速。

但本词条同样强调边界。优势依赖 oracle 类型：如果 oracle 一次就返回完整的梯度向量（$d$ 个数），Jordan 型”同时读 $d$ 个分量”的优势已经被预付，对一般 nonsmooth 凸优化量子方法没有普遍加速。而且已知下界排除了指数级的维数加速。本词条将按”oracle 层级 $\to$ cutting-plane 框架 $\to$ 量子梯度估计 $\to$ membership 到 separation 的转换 $\to$ 下界 $\to$ 体积估计 $\to$ 结构化问题”的顺序，把这条链条的每一环讲清楚。

记号约定：$\tilde{O}(\cdot )$ 与 $\tilde{\Omega }(\cdot )$ 隐藏对数因子（对维数 $d$、精度 $1/ϵ$、条件比 $R/r$ 的多重对数）。读者应已熟悉的 QFT 与相位估计、Grover 搜索与振幅放大；本词条直接使用这些工具，不再重新推导。

1. 问题设定：凸体、凸函数与 oracle 层级

1.1 凸集与凸函数

集合 $K\subset {\mathbb{R}}^d$ 是凸的 (convex)，如果对任意 $x,y\in K$ 和任意 $\lambda \in [0,1]$，连接两点的线段 $\lambda x+(1-\lambda )y$ 仍落在 $K$ 内。函数 $f:{\mathbb{R}}^d\to \mathbb{R}$ 是凸的，如果对任意 $x,y$ 与 $\lambda \in [0,1]$ 有

$$f(\lambda x+(1-\lambda )y)\le \lambda f(x)+(1-\lambda )f(y).$$

几何含义：函数图像上任意两点的连线不低于图像本身。凸函数可能没有解析梯度（例如 $f(x)=|x|$ 在 $x=0$ 处），但总有次梯度 (subgradient)：称 $g\in {\mathbb{R}}^d$ 是 $f$ 在 $x$ 处的次梯度，记作 $g\in \partial f(x)$，如果对所有 $y$ 有

$$f(y)\ge f(x)+g\cdot (y-x).$$

几何含义：以 $g$ 为斜率、过点 $(x,f(x))$ 的超平面整体托住函数图像（支撑超平面）。若 $f$ 在 $x$ 处可微，则 $\partial f(x)=\{\nabla f(x)\}$，上式就是凸函数”图像在切线上方”这一熟知性质。凸优化问题的标准形式是

$$\underset{x\in K}{\min }f(x),$$

其中 $K$ 凸、$f$ 凸。任何局部极小值都是全局极小值——这正是凸问题”可解”的根源。

1.2 Sandwich 条件与弱 oracle

黑盒模型还需要两个结构性假设。第一，可行域不能离原点太远、也不能太薄：已知

$$B(0,r)\subseteq K\subseteq B(0,R),$$

即 $K$ 夹在以原点为中心、半径分别为 $r$ 与 $R$ 的两个球之间，且条件比 (condition ratio) $\kappa =R/r$ 有界。这个假设看似技术性的，实则必要：没有外球 $B(0,R)$，算法不知道去哪里找 $K$；没有内球 $B(0,r)$，$K$ 可能薄到任何有限次查询都碰不到它的内部。

第二，oracle 允许容差 (tolerance)。在浮点世界里”恰好在边界上”没有意义，所以实际模型是弱 oracle：查询点距边界的距离在某个小参数之内时，oracle 可以任意回答。所有复杂度都隐含对这个容差的依赖（通常是对数依赖），后文第 4 节会看到量子构造的误差 slack 恰好与弱 oracle 容差匹配。

1.3 三种 oracle 的信息量

对凸体 $K$，常见的查询接口按信息量从小到大排列：

1. Membership oracle ${\mathrm{MEM}}_K(x)$：输入点 $x$，输出一个 bit——$x\in K$ 与否（允许边界容差）。这是信息量最少的接口：一次查询只给 1 个 bit。
2. Separation oracle：输入点 $x$；若 $x\in K$ 回答”可行”，若 $x\notin K$ 返回一个分离超平面 $(a,b)$，满足

$$a\cdot x>b,a\cdot y\le b\forall y\in K.$$

一次查询返回 $d+1$ 个实数：它不只是说”你不行”，还给出”哪一侧整个被排除”。 3. Optimization oracle：给定方向 $c\in {\mathbb{R}}^d$，近似求 ${\min }_{x\in K}c\cdot x$。一次查询解一个子优化问题，信息量最大。

对目标函数 $f$，对应地有 value oracle（返回 $f(x)$，一个数）与 gradient oracle（返回 $g\in \partial f(x)$，$d$ 个数）。

**关键观察：比较复杂度必须固定 oracle 类型，并通过显式 reduction 转换。**说”量子比经典快”而不指明接口是没有意义的：gradient oracle 每次输出 $d$ 个数，把它和 value oracle 按”次数”直接比较，等于让一方每次免费携带 $d$ 倍的信息。本词条第 3–5 节的全部工作，就是把这些接口之间的转换成本算清楚。

1.4 经典版图与历史背景

凸优化的 cutting-plane 传统源远流长：中心重力法 (center of gravity) 早在 1960 年代就被提出，椭球法 (ellipsoid method) 因 Khachiyan 用它证明线性规划多项式时间可解而闻名，后续 volumetric-center 与更精细的中心选择把迭代轮数压到 $\tilde{O}(d)$ 量级。这是一条”几何”路线：每轮用一个超平面切掉候选区域的一块，靠体积收缩保证收敛。另一条”内点”路线（interior point）沿障碍函数的中央路径走，是实践中的主力，也是第 7 节线性规划量子加速的载体。

在黑盒查询模型下，几何路线的经典瓶颈不在迭代轮数，而在每轮的代价：从只有 value/membership 信息的弱 oracle 出发，构造一个 $d$ 维分离方向本质上要做 $d$ 个坐标方向的探测，每轮 $\Omega (d)$ 次查询，$\tilde{O}(d)$ 轮下来总查询量近 $d^2$。量子算法（2018 年前后两篇代表性工作，见文末 Zoo 418、420）正是瞄准这个 $d\times d$ 的乘积结构，把”每轮造方向”的代价降到近常数。

2. Cutting-plane 框架：separation 为什么是一切的核心

2.1 定位区域与切割

所有 cutting-plane 算法维护一个定位区域 (localization region) $K_t$——一个我们确信包含最优点的显式集合（比如一个椭球或单纯形）。第 $t$ 轮在某个查询点 (query point) $x_t$（通常取 $K_t$ 的某种”中心”）发问，分两种情形：

• **不可行情形。**若 $x_t\notin K$，separation oracle 返回 $(a,b)$ 满足 $a\cdot x_t>b$ 而 $a\cdot y\le b$ 对所有 $y\in K$ 成立。于是整个半空间 $\{y:a\cdot y>b\}$ 里没有任何可行点，把它从 $K_t$ 里切掉，余下部分仍包含全部可行点（从而包含最优点）。
• 可行但未最优情形。若 $x_t\in K$ 但目标值还能改进，取次梯度 $g_t\in \partial f(x_t)$，用目标切割 (objective cut) 缩小候选区域。

下面这个引理是目标切割合法性的全部依据，值得完整证明一遍。

Lemma 1（次梯度切割保留最优点）. 设 $f$ 凸，$g_t\in \partial f(x_t)$，定义半空间

$$H_t=\{y\in {\mathbb{R}}^d:g_t\cdot (y-x_t)\le 0\}.$$

则任何满足 $f(y)\le f(x_t)$ 的点 $y$ 都在 $H_t$ 内。特别地，若 $x^{\text{*}}$ 是最优点，则 $x^{\text{*}}\in H_t$。

证明。由次梯度的定义（第 1.1 节），对任意 $y$ 有

$$f(y)\ge f(x_t)+g_t\cdot (y-x_t).$$

若 $y\notin H_t$，即 $g_t\cdot (y-x_t)>0$，代入上式得

$$f(y)\ge f(x_t)+g_t\cdot (y-x_t)>f(x_t),$$

也就是说 $H_t$ 之外的点的函数值严格大于当前点的函数值。因此所有不比 $x_t$ 差的点——包括最优点 $x^{\text{*}}$（它满足 $f(x^{\text{*}})\le f(x_t)$）——都必须落在 $H_t$ 内。等价地，被切掉的那一半 $\{y:g_t\cdot (y-x_t)>0\}$ 里的点全部可以安全丢弃。Q.E.D.

直觉上，$g_t$ 指向函数上升的方向，所以”值得去的点”必在反方向那一侧；切掉上升侧永远不会误伤最优点。这与一维二分查找的逻辑完全一样，只是”中点左/右”被换成了”超平面哪一侧”。

2.2 体积收缩与迭代轮数

切割合法只是故事的一半；另一半是切得够狠。如果每轮都在边缘切掉一小条，迭代次数会爆炸。精心选择查询点（中心重力点、体积中心、近似重心等）可以保证每轮把定位区域的体积按常数或可控比例缩小：

$$\mathrm{vol}(K_{t+1})\le (1-\Omega (1/d^{\alpha }))\mathrm{vol}(K_t),$$

其中指数 $\alpha$ 依赖具体的中心选择方案。从初始外球（体积 $\sim R^d$）收缩到足以确定 $ϵ$ 最优（体积 $\sim (rϵ{)}^d$ 量级）所需的轮数为

$$\tilde{O}(d)$$

量级——体积每轮按因子 $(1-c/d^{\alpha })$ 缩小，把体积比 $R^d/(rϵ{)}^d$ 的对数 $\Theta (d\log (R/(rϵ)))$ 除以每轮的收缩量 $\Theta (1/d^{\alpha })$，就得到 $\tilde{O}(d)$ 级别（$\alpha$ 被吸收进隐藏的对数记号中）。迭代轮数不是量子加速的对象：轮数由几何收缩决定，量子与经典一样要跑这么多轮。

2.3 经典瓶颈：每轮一个分离方向要 $\Omega (d)$ 次探测

瓶颈在每一轮内部。假设我们只有 value oracle 和 membership oracle（这是最弱的接口），要执行上面的一次切割，必须先回答两个问题：$x_t$ 可行吗？不可行的话，分离方向 $a$ 朝哪？

经典地，从一个点出发要”看见”一个 $d$ 维方向，本质上是估计某个局部量（目标函数的梯度、或边界面的法向）的 $d$ 个分量。以有限差分为例，第 $i$ 个分量

$$\frac{\partial f}{\partial x_i}\approx \frac{f(x_t+\delta e_i)-f(x_t)}{\delta }$$

需要一个额外查询，$d$ 个分量就要 $d$ 次（连上基点共 $d+1$ 次）。membership 情形更糟：oracle 只返回 0/1 bit，要恢复边界法向需要沿多个方向做二分搜索找边界点，$\Omega (d)$ 次局部探测是不可避免的（第 5 节会看到这个 $\Omega (d)$ 在下界意义上是真实的）。于是经典黑盒凸优化的总查询量为

$$\underset{\text{迭代轮数}}{\underbrace{\tilde{O}(d)}}\times \underset{\text{每轮造方向}}{\underbrace{\Omega (d)}}\approx \tilde{O}(d^2)$$

次 membership/value 查询。量子加速的全部内容，就是把第二个因子从 $\Omega (d)$ 压到 $\tilde{O}(1)$，乘积变为近 $d$。这正是第 3、4 两节的任务。

3. 量子梯度估计：一次相干查询读出全部 $d$ 个分量

3.1 核心思想：把斜率写进相位，让 QFT 去读

经典估计梯度的思路是”一个坐标一个坐标地扰动”，$d$ 个分量就要 $d$ 次串行探测。量子思路完全不同，它分两步：

1. 编码。在 $x_0$ 周围的一个离散网格上制备均匀叠加，用一次相位查询 (phase query) 把每个网格点的函数值写成相位。若 $f$ 局部近似线性，相位关于网格坐标 $z$ 就是线性的，斜率正比于梯度分量 $g_i=\partial f/\partial x_i$。
2. 读出。“相位关于 $z_i$ 的线性斜率”正是 Fourier 变换的本征对象：对每个坐标寄存器分别做逆 QFT，斜率就转化为可测量的计算基标签。一次测量读出全部 $d$ 个分量。

也就是说，经典方法把 $d$ 个分量分摊到 $d$ 次查询里，量子方法把它们相干地合并进一次查询的不同自由度中。这就是 Jordan 提出的梯度估计算法，也是后面一切 oracle 转换的发动机。

3.2 相位 oracle 与网格态

设我们能通过 value oracle 实现相位查询

$$|z⟩\mapsto e^{2\pi iSf(x_0+hz)}|z⟩,$$

其中 $z$ 是网格坐标，$h>0$ 是网格步长（物理位移是 $hz$），$S>0$ 是把函数值放大成相位弧度的比例因子。（从标准 value oracle $|z⟩|0⟩\mapsto |z⟩|f(x_0+hz)⟩$ 出发，对输出寄存器施加逐基矢的相位旋转再反算，即可实现这一映射；相位 kickback 技巧，与相位估计中把本征值写进相位的做法同源。）

取每个坐标 $M$ 个点（为对称起见写成 $z_i\in \{-M/2,\dots ,M/2-1\}$），网格共 $M^d$ 个点。制备均匀叠加（每个坐标寄存器用 Hadamard 与少量门即可）：

$$\frac{1}{M^{d/2}}\sum _{z\in \{-M/2,\dots ,M/2-1{\}}^d}|z⟩.$$

对它做一次相位查询，得到

$$\frac{1}{M^{d/2}}\sum _z{e}^{2\pi iSf(x_0+hz)}|z⟩.$$

注意：这是一次 oracle 调用，却同时载入了全部 $M^d$ 个网格点的函数值——不是逐个求值，而是叠加求值。

3.3 线性化：每一步的依据

假设 $f$ 在 $x_0$ 附近有 Lipschitz 连续的梯度（常数记为 $L$，即 $\Vert \nabla f(x)-\nabla f(x_0)\Vert \le L\Vert x-x_0\Vert$），Taylor 展开给出

$$f(x_0+hz)=f(x_0)+h\nabla f(x_0)\cdot z+R(z),|R(z)|\le \frac{1}{2}L{h}^2\Vert z{\Vert }^2,$$

其中余项估计来自带积分余项的 Taylor 定理：一阶余项 ${\int }_0^1[\nabla f(x_0+thz)-\nabla f(x_0)]\cdot hz\mathrm{d}t$ 的绝对值不超过 ${\int }_0^{1}Lt\Vert hz{\Vert }^2\mathrm{d}t=\frac{1}{2}L{h}^2\Vert z{\Vert }^2$。当 $h\Vert z\Vert$ 足够小时余项可忽略，代入相位并把 $f(x_0)$ 这一项提出来：

$$e^{2\pi iSf(x_0+hz)}=e^{2\pi iSf(x_0)}\cdot \exp \left(2\pi iSh\sum _{i=1}^d{g}_i{z}_i\right)\cdot e^{O(SL{h}^2\Vert z{\Vert }^2)},g_i=\frac{\partial f}{\partial x_i}(x_0).$$

第一个因子 $e^{2\pi iSf(x_0)}$ 不依赖 $z$，是全局相位，测量不可观测，直接丢弃。第三个因子是 Taylor 余项造成的相位污染，只要 $SL{h}^2\Vert z{\Vert }^2\ll 1$ 就近似为 1，其代价在第 3.6 节统一核算。于是相位查询后的态近似为

$$\underset{i=1}{\overset{d}{⨂}}\left(\frac{1}{\sqrt{M}}\sum _{z_i}{e}^{2\pi i(Sh{g}_i)z_i}|z_i⟩\right):$$

$d$ 个寄存器恰好因子化，第 $i$ 个寄存器只携带第 $i$ 个梯度分量 $g_i$，且以”线性相位”的形式携带。这一因子化是整个算法能并行读出 $d$ 个分量的数学原因——它不是额外假设，而是 $f$ 局部线性 + 相位乘法结构的直接推论。

3.4 逆 QFT 读出：小例子完整算一遍

回忆逆 QFT 的核心性质：在 $M$ 维计算基上，线性相位态 $\frac{1}{\sqrt{M}}{\sum }_z{e}^{2\pi ikz/M}|z⟩$（$k$ 为整数）经逆 QFT 恰好变为 $|k⟩$。因此只要

$$Sh{g}_i=\frac{k_i}{M},k_i\in \mathbb{Z},$$

对第 $i$ 个寄存器做逆 QFT 后测量，就以高概率得到 $k_i$，进而

$$g_i=\frac{k_i}{SMh}.$$

Fourier 分辨率——相邻可区分斜率的间隔——为 $\Delta g=1/(SMh)$。这三个参数的分工非常清晰：$M$ 决定网格点数与可表示的相位频率范围，$S$ 和 $h$ 把物理斜率缩放到这个频率范围内。

**小例子（$d=1$）。**取 $M=8$，$S=h=1$，设 $f$ 在 $x_0$ 附近严格线性、斜率 $g=3/8$。网格 $z\in \{-4,\dots ,3\}$（为计算方便等价地取 $z\in \{0,\dots ,7\}$，相位只差整体因子）。相位查询后（忽略全局相位 $e^{2\pi if(x_0)}$）：

$$\frac{1}{\sqrt{8}}\sum _{z=0}^7{e}^{2\pi i(3/8)z}|z⟩=\frac{1}{\sqrt{8}}\sum _{z=0}^7{e}^{2\pi i3z/8}|z⟩.$$

这正是 $k=3$ 的线性相位态，逆 QFT 输出 $|3⟩$，测量必得 $3$，还原 $g=3/(1\cdot 1\cdot 8)=3/8$，与真值完全一致。

**小例子（$d=2$）。**取 $M=8$，$S=h=1$，$g=(3/8,-2/8)$。相位态因子化为

$$\left(\frac{1}{\sqrt{8}}\sum _{z_1}{e}^{2\pi i3z_1/8}|z_1⟩\right)\otimes \left(\frac{1}{\sqrt{8}}\sum _{z_2}{e}^{-2\pi i2z_2/8}|z_2⟩\right),$$

两个寄存器各自逆 QFT 读出 $k_1=3$ 与 $k_2=-2\equiv 6(\mathrm{mod}8)$（负频率在循环网格上以补码形式出现，还原时按最近整数解释），于是 $g=(3/8,-2/8)$。**一次相位查询、一次测量，两个分量同时到手。**经典有限差分做同样的事需要至少 $d+1=3$ 次求值（基点加两个方向扰动）；对一般的 $d$，这个对比是 $1$ 次（相干）对 $d+1$ 次。若 $Sh{g}_i$ 不是 $1/M$ 的整数倍，测量结果以最接近的整数为主、分布集中在其附近（标准相位估计分析），把 $M$ 取大使量化误差低于目标精度即可。

3.5 精度不免费：三个误差源

上面的干净图景依赖三个近似，每一个都对应一类误差，也都对应复杂度表达式里的一个因子：

1. **Taylor 余项误差。**相位污染量级为 $S\cdot \frac{1}{2}L{h}^2\Vert z{\Vert }^2$。网格上 $\Vert z{\Vert }^2$ 的典型值为 ${\sum }_i{z}_i^2\sim d{M}^2/12$，故要求

$$SL{h}^2{M}^{2}d\lesssim 1.$$

（要求相位污染远小于 $2\pi$ 的一个固定比例，否则线性相位态被破坏。）

2. **Oracle 值误差。**弱 value oracle 只返回精度 ${ϵ}_{\mathrm{or}}$ 内的函数值，直接造成相位不确定性 $S{ϵ}_{\mathrm{or}}$，要求

$$S{ϵ}_{\mathrm{or}}\lesssim 1.$$

3. **Fourier 分辨率。**要分辨梯度到精度 $ϵ$，要求

$$\Delta g=\frac{1}{SMh}\le ϵ⟺SMh\gtrsim \frac{1}{ϵ}.$$

3.6 参数平衡：把约束联立解掉

三个约束构成一个关于 $(S,h,M)$ 的不等式组。演示一遍消元过程。由约束 3 解出

$$M\sim \frac{1}{Shϵ}.$$

代入约束 1：

$$SL{h}^{2}d\cdot \frac{1}{S^2{h}^2{ϵ}^2}=\frac{Ld}{S{ϵ}^2}\lesssim 1⟹S\gtrsim \frac{Ld}{{ϵ}^2}.$$

也就是说，光滑性越差（$L$ 大）、维数越高、目标精度越高，就需要越大的相位放大倍数 $S$ 来同时满足”余项小”与”分辨率够”。而约束 2 给 $S$ 封顶：$S\lesssim 1/{ϵ}_{\mathrm{or}}$。当 oracle 有噪声时，单次梯度估计的参数空间被上下挤压；标准的处理是把估计重复若干次取中位数/多数投票（把每次测量的失败概率压到 $1/\mathrm{poly}(d)$，使 $d$ 个分量同时正确的联合概率仍为常数），代价只是对数级的重复因子。这就是”复杂度含 smoothness 参数与 $1/ϵ$，并带对数因子”这句话的完整含义——它不是一个笼统的免责声明，而是三条具体误差预算联立求解的结果。

结论（Jordan 型梯度估计）：对近似线性（或一般光滑）的 $f$，用 $\tilde{O}(1)$ 次相干 value/相位查询即可把 $\nabla f(x_0)$ 的全部 $d$ 个分量估计到精度 $ϵ$；经典 value oracle 做同样的事至少需要 $d+1$ 次查询（有限差分）。”$\tilde{O}(1)$ 对 $d+1$“就是全部量子优势的引擎，下一节把它接到 cutting-plane 上。

4. Membership 到 Separation 的量子转换

4.1 困难所在：0/1 bit 没有梯度

第 3 节的机器要求一个光滑可微的标量函数作为相位来源。但 membership oracle 返回的是一个不连续的 bit：$K$ 内为 1、$K$ 外为 0。这个示性函数在边界上跳变，任何点上的”梯度”要么是 0（内部/外部的平坦区域），要么不存在（边界处）——对它直接做 Jordan 梯度估计什么也得不到。要调用第 3 节的引擎，必须先造一个光滑的凸代理函数 (convex surrogate)，使得：

• 它只通过 membership/value 查询就能（近似）求值；
• 它的梯度在外点处恰好指向一个合法的分离方向。

4.2 代理函数之一：gauge 函数与射线二分

设 $0\in \mathrm{int}K$（由内球 $B(0,r)\subseteq K$ 保证，必要时平移）。$K$ 的 gauge 函数定义为

$${\gamma }_K(x)=\inf \{\lambda >0:x\in \lambda K\}.$$

它有三个可直接验证的性质：

• 正齐次性：${\gamma }_K(tx)=t{\gamma }_K(x)$（$t>0$）。由定义，$tx\in \lambda K⟺x\in (\lambda /t)K$，对 $\lambda$ 取下确界即得。
• 凸性：这是 $K$ 凸的直接推论（Minkowski 泛函的标准性质）。
• 刻画 $K$：${\gamma }_K(x)\le 1⟺x\in K$（在闭性/弱容差意义下）。

${\gamma }_K$ 在固定方向 $u$ 上是一条射线问题：${\gamma }_K(x)$ 等于使 $x/\lambda$ 落到边界上的那个刻度。沿射线用 membership oracle 做二分搜索，用 $\tilde{O}(1)$ 次 ${\mathrm{MEM}}_K$ 查询即可把边界点（从而 ${\gamma }_K(x)$ 的值）定位到任意精度——这是 gauge 函数”便宜”的原因，也是弱 membership oracle 能被提升为连续值函数的第一个台阶。

4.3 平滑：让代理函数可微

${\gamma }_K$ 凸但不一定光滑（多面体的 gauge 在棱上不可微）。标准的修补是随机平滑 (random smoothing)：对小尺度噪声 $\xi$（如小球或高斯分布）取卷积

$$\tilde{\gamma }(x)={\mathbb{E}}_{\xi }[{\gamma }_K(x+\xi )].$$

凸函数的局部平均仍凸（期望保持凸性不等式方向），而卷积抹平了不可微点，使 $\tilde{\gamma }$ Lipschitz 可微，且与原函数的偏差被平滑尺度控制。平滑尺度是一个新的误差预算项：太大则梯度方向偏离真实法向，太小则不够光滑——与第 3.6 节的三项预算并列，最终同样只贡献对数级因子。

4.4 代理函数的梯度给出分离超平面：完整推导

现在证明整条链的关键一步：外点 $x$ 处 $\tilde{\gamma }$ 的梯度（近似）给出合法的分离超平面。先对未平滑的 ${\gamma }_K$ 严格论证，平滑只引入可控误差。

设 $x\notin K$，即 ${\gamma }_K(x)>1$。记边界点 $p=x/{\gamma }_K(x)$（由正齐次性，${\gamma }_K(p)={\gamma }_K(x)/{\gamma }_K(x)=1$，即 $p$ 在边界上）。设 ${\gamma }_K$ 在 $p$ 附近可微，记 $a=\nabla {\gamma }_K(p)$。两个事实：

事实一：$a\cdot p=1$。 正齐次函数满足 Euler 齐次函数定理：对 ${\gamma }_K(tp)=t{\gamma }_K(p)$ 两边在 $t=1$ 处求导，左边由链式法则得 $\nabla {\gamma }_K(p)\cdot p$，右边为 ${\gamma }_K(p)=1$，即 $a\cdot p=1$。

事实二：$a\cdot y\le 1$ 对所有 $y\in K$ 成立。 由凸性（支撑不等式），

$${\gamma }_K(y)\ge {\gamma }_K(p)+a\cdot (y-p)=1+a\cdot y-1=a\cdot y,$$

而 $y\in K$ 蕴含 ${\gamma }_K(y)\le 1$，故 $a\cdot y\le {\gamma }_K(y)\le 1$。

合起来：对外点 $x={\gamma }_K(x)p$，由正齐次性（或等价地，沿同一射线的方向一致性），$a\cdot x={\gamma }_K(x)(a\cdot p)={\gamma }_K(x)>1$；而 $a\cdot y\le 1$ 对所有 $y\in K$ 成立。于是

$$a\cdot x>1,a\cdot y\le 1\forall y\in K,$$

这正是第 1.3 节 separation oracle 要求的输出（取 $b=1$）。直观解释：gauge 函数沿”指向体外”的方向增长最快，所以它的梯度天然垂直于边界面、指向外侧——就是我们要的分离法向。随机平滑把 $a$ 换成近似方向，分离不等式相应地出现一个 boundary slack（$a\cdot y\le 1+\text{slack}$），这个 slack 恰好被吸收进弱 separation oracle 的容差里——第 1.2 节强调的弱 oracle 模型在这里闭环。

4.5 组装：从 $\Omega (d)$ 到 $\tilde{O}(1)$，再到 $\tilde{O}(d)$

把各环按依赖顺序装起来：

1. gauge/距离类代理函数的每个值，用 $\tilde{O}(1)$ 次 membership 查询（射线二分）近似求得——于是一个”相位化的代理 value oracle”只需近常数次 membership 查询即可实现；
2. 对平滑后的代理函数跑第 3 节的 Jordan 梯度估计：$\tilde{O}(1)$ 次相干查询读出近似梯度 $a$（$d$ 个分量一次到手）；
3. 由第 4.4 节的推导，$a$ 给出一个带 slack 的合法分离超平面。

于是一次 separation 调用被模拟为 $\tilde{O}(1)$ 次 membership/value 查询，而经典做同样的转换需要 $\Omega (d)$ 次。把它插入第 2 节的 cutting-plane 框架（$\tilde{O}(d)$ 轮迭代，每轮常数次 separation），总查询复杂度为

$$\underset{\text{迭代轮数}}{\underbrace{\tilde{O}(d)}}\times \underset{\text{量子造方向}}{\underbrace{\tilde{O}(1)}}=\tilde{O}(d)$$

次 membership/evaluation 查询，相对最佳已知经典黑盒查询（近 $d^2$）取得平方级改善。这就是本词条标题中”维数平方加速”的确切含义：加速发生在维数 $d$ 的指数上（从 2 到 1），而不是在对精度或条件比的依赖上——那些依赖被 $\tilde{O}$ 记号吸收，量子与经典大体相同。

5. 下界：为什么没有指数加速

5.1 查询下界

平方加速已是这个框架的上限，不是指数加速的开始。已知的量子下界为

$$\tilde{\Omega }(\sqrt{d})$$

级 evaluation/membership 查询；而如果算法没有已知内点可用（即 sandwich 条件中内球的位置不被免费告知），separation 查询甚至需要 $\Omega (d)$ 次，此时没有量子优势。

下界的证明思路（定性描述）是通过随机隐藏方向/凸体 packing 构造困难实例：在 $d$ 维空间中放置指数多个彼此”查询上几乎不可分”的凸体（或隐藏一个随机的最优方向），使得每次 oracle 回答——无论经典还是量子相干查询——泄露的关于隐藏结构的互信息都很少。用量子对抗法/多项式方法把这种”每次查询信息量”的界转化为查询次数下界。要点是：凸性限制了对手的隐藏能力（不能像 unstructured search 那样任意），所以下界停在 $\sqrt{d}$ 而不是 $d$；而上界停在近 $d$。当前上界 $\tilde{O}(d)$ 与下界 $\tilde{\Omega }(\sqrt{d})$ 之间最多留一个多项式 gap，但指数级的维数加速被排除——一般凸优化不是又一个”量子指数加速”的例子。

5.2 Oracle 预付优势的情形：nonsmooth no-go

另一个重要的保留条款：以上所有加速都以弱 oracle（membership/value，每次输出一个 bit 或一个数）为起点。如果 oracle 直接返回完整的次梯度 $g\in {\mathbb{R}}^d$，一次经典查询已经携带 $d$ 个数，第 3 节”相干合并 $d$ 个分量”的技巧就无用武之地了——Jordan 型优势被 oracle 预付了。

事实上，对 nonsmooth 凸优化（目标函数只满足 Lipschitz、不光滑），迭代复杂度下界分析显示量子算法不能普遍优于经典的 (sub)gradient descent 类方法：当每轮的梯度已经免费到手时，剩下的工作量（平均迭代、最坏情形下的 $\Theta (1/{ϵ}^2)$ 轮等）没有可被相干并行的结构。这给出一个一般性的教训，也是本词条反复强调”按 oracle 类型比较”的原因：

**量子梯度估计的价值恰好等于梯度信息的”稀缺程度”。**value oracle 下梯度稀缺，量子把 $d$ 次探测压成近 1 次，价值最大；gradient oracle 下梯度已被预付，量子优势消失。

6. 体积估计：同一引擎的另一台机器

与凸优化紧邻的一个基本问题是体积估计 (volume estimation)：给定凸体 $K$ 的 membership oracle，近似计算 $\mathrm{vol}(K)$。它是计数类问题的连续化身，经典最优算法是随机行走采样式，量子行走提供了另一处平方加速的用武之地。

6.1 望远镜乘积

直接估计 $K$ 相对于外球的体积比不可行：若 $K$ 只占 $B(0,R)$ 的 $(r/R{)}^d$ 比例，采样命中率指数小。标准技巧是插一串嵌套凸体 (nested bodies)

$$K_0\subset K_1\subset \cdots \subset K_L=K,$$

使相邻体积比有界（例如 $1/2\le \mathrm{vol}(K_i)/\mathrm{vol}(K_{i+1})\le 1$，这可以通过取同心球的梯度序列 $K_i=K\cap B(0,2^{i/L}R)$ 之类的构造实现），然后把体积写成望远镜乘积 (telescoping product)：

$$\mathrm{vol}(K)=\mathrm{vol}(K_0)\cdot \frac{\mathrm{vol}(K_1)}{\mathrm{vol}(K_0)}\cdot \frac{\mathrm{vol}(K_2)}{\mathrm{vol}(K_1)}\cdots \frac{\mathrm{vol}(K_L)}{\mathrm{vol}(K_{L-1})}=\mathrm{vol}(K_0)\prod _{i=0}^{L-1}\frac{\mathrm{vol}(K_{i+1})}{\mathrm{vol}(K_i)},$$

中间的体积两两相消，恒等式直接成立。$K_0$ 取内球，体积有解析公式；于是总体积的估计分解为 $L$ 个有界比值的估计，每个比值用采样估计：“在 $K_{i+1}$ 中均匀采样，落在 $K_i$ 内的频率”即为 $\mathrm{vol}(K_i)/\mathrm{vol}(K_{i+1})$ 的无偏估计。相对误差随 $L$ 可控地累积（每个比值只需 $O(1/L)$ 级相对精度）。

6.2 量子加速的两个来源

这台机器里有两个可被量子化的子程序，各贡献一个平方根：

1. **采样：量子行走加速混合。**经典用 hit-and-run 或 ball walk 在凸体上近似均匀采样，收敛速度由 Markov 链的谱隙 (spectral gap) 决定。量子行走（量子行走一篇的框架）对可逆 Markov 链的混合时间给出平方改善：gap 为 $\delta$ 的链，经典混合 $\Theta (1/\delta )$ 步，量子约 $\Theta (1/\sqrt{\delta })$ 步。
2. **比值：振幅/均值估计加速精度。**每个体积比值是采样点的均值，经典 Monte Carlo 把相对误差压到 ${ϵ}^{\prime }$ 需 $\Theta (1/{ϵ}^{\prime 2})$ 个样本；振幅估计（相位估计 + Grover 的组合）只需 $\Theta (1/{ϵ}^{\prime })$ 次相干采样查询。

整体在维数与误差参数上获得多项式（常为近二次）的加速。保留条款同样要明确：实际复杂度还依赖 rounding（把 $K$ 预处理成近各向同性位置）、warm start（初始样本的质量）、isoperimetric gap（凸体的几何集中度，它决定行走链的谱隙）和 membership oracle 本身——这些参数出现在 $\tilde{O}$ 记号里，量子加速的是查询结构，不是这些几何条件数。

7. 结构化特殊问题

一般凸优化的故事讲完了；当问题带有额外代数结构时，同一套思想能走得更远，也更精细。

7.1 二次函数：$O(d)$ 对 $O(d^2)$

考虑二次目标

$$f(x)=\frac{1}{2}{x}^{T}Ax-b^{T}x,$$

其梯度是仿射函数 $\nabla f(x)=Ax-b$（直接验证：$\partial f/\partial x_i={\sum }_j{A}_{ij}{x}_j-b_i$）。梯度的仿射性带来两点简化：Taylor 展开没有余项（第 3 节的约束 1 消失），而且不同点处的梯度之差直接暴露矩阵列：

$$\nabla f(e_j)-\nabla f(0)=A{e}_j=A\text{ 的第 }j\text{ 列}.$$

**完整小例子（$d=2$）。**设 $A=\left(\begin{array}{cc}2& 1\\ 1& 3\end{array}\right)$，$b=\left(\begin{array}{c}1\\ 0\end{array}\right)$。在 $x=0$ 处做一次量子梯度估计，读出 $\nabla f(0)=-b=(-1,0{)}^T$；在 $x=e_1$ 处再读一次，$\nabla f(e_1)=A{e}_1-b=(2,1{)}^T-(1,0{)}^T=(1,1{)}^T$，相减得第一列 $(2,1{)}^T$；同理 $x=e_2$ 处读出 $(1,3{)}^T-(1,0{)}^T=(0,3{)}^T$，相减得第二列 $(1,3{)}^T$。$d+1$ 个点、每个点 $\tilde{O}(1)$ 次相干查询，总共 $O(d)$ 次 value 查询恢复整个 $A$。经典 value oracle 要恢复 $A$ 的 $d^2$ 个二阶差分，需要 $\Theta (d^2)$ 次查询——这是又一处 factor-$d$ 的改善。学到 $A,b$ 后，最小点 $x^{\text{*}}=A^{-1}b$ 由 $\nabla f=0$ 解出（凸性即 $A⪰0$）。注意输出本身是一个 $d$ 维点，写出答案就需要 $\Omega (d)$ 时间，所以 $O(d)$ 在这个意义下已经是线性最优。

7.2 有限域上的 multilinear polynomial

同样的”高阶导数/插值一次读出一块”的思想适用于有限域上的 multilinear polynomial：函数关于每个变量至多一次的代数结构，使其系数与局部导数精确对应（没有 Taylor 余项问题），量子算法用 factor-$d$ 更少的查询恢复多项式或求其结构化最优。细节见本词条习题与文末 Zoo 130、146–148、223 对应条目。

7.3 线性规划与内点法

线性规划 (linear programming) 是凸优化中实践价值最高的特例。量子加速的载体不是 cutting-plane 而是 interior-point：内点法每轮迭代的核心是解一个（加权的）线性系统（Newton 步），把量子线性系统求解（ HHL/线性求解器框架）嵌入其中可获得多项式加速。保留条款与 HHL 一脉相承：加速幅度由 condition number 决定，读出经典迭代点需要 tomography 或精心维护的经典表示，精度需求随迭代轮数累积——这些常决定实际优势的有无。此外，norm-constrained linear regression 作为有结构的凸问题，已有与下界匹配的精细分析（Zoo 497），说明在结构化问题上”上下界吻合”是可以做到的。

8. 小结与习题

本词条要点：

• Cutting-plane 框架把凸优化化为 $\tilde{O}(d)$ 轮 separation/subgradient 切割；轮数由几何体积收缩决定，量子与经典相同。
• 经典瓶颈在每轮内部：从 value/membership 弱 oracle 构造一个 $d$ 维分离方向需 $\Omega (d)$ 次探测，总查询量近 $d^2$。
• Jordan 梯度估计把斜率编码进叠加网格的线性相位、用逐寄存器逆 QFT 一次读出全部 $d$ 个分量；精度由 Taylor 余项、oracle 噪声、Fourier 分辨率三项预算联立决定。
• 对 membership oracle，先用 gauge/距离类凸代理 + 射线二分 + 随机平滑造出光滑标量场，其梯度由 Euler 定理与支撑不等式给出合法分离超平面；一次 separation 折合 $\tilde{O}(1)$ 次 membership 查询，总复杂度近 $d$，相对经典近 $d^2$ 实现维数平方加速。
• 下界 $\tilde{\Omega }(\sqrt{d})$ 与无内点情形的 $\Omega (d)$ 排除普适指数加速；oracle 若已直接返回完整梯度，nonsmooth 问题上没有量子优势——Jordan 型优势被 oracle 预付。
• 同一引擎（量子行走 + 振幅估计）驱动体积估计的近二次加速；二次函数、multilinear polynomial、线性规划等结构化问题有各自的 factor-$d$ 或条件数依赖的加速。

习题：

1. **（次梯度切割）**证明 Lemma 1 的逆命题不成立：给出 $f$、$x_t$ 与点 $y\in H_t$ 但 $f(y)>f(x_t)$ 的例子（一维即可）。这说明目标切割”保守”在哪一侧？
2. **（线性相位态）**取 $d=1$，$M=4$，$S=h=1$，$g=1/4$。写出相位查询后的 4 维态向量，并对它手工执行逆 QFT（可用 ${\mathrm{QFT}}_4$ 的矩阵），验证测量以概率 1 得到 $k=1$。若改为 $g=3/8$，测量分布如何变化？
3. **（参数平衡）**在第 3.5 节的三条约束中，固定 $S$ 与 $ϵ$，解出 $M$ 与 $h$ 应满足的关系；并解释为什么”把 $h$ 取得尽量小”不能同时满足所有约束。
4. **（gauge 函数）**设 $K=\{x\in {\mathbb{R}}^2:\Vert x{\Vert }_{\infty }\le 1\}$（正方形）。写出 ${\gamma }_K(x)$ 的显式公式，并在外点 $x=(2,1)$ 处计算分离超平面，验证它满足第 4.4 节的两个不等式。该点处 ${\gamma }_K$ 可微吗？这与随机平滑的必要性有何关系？
5. **（membership 为何需要平滑）**解释为什么不能对示性函数 $1_K$ 直接做 Jordan 梯度估计；并说明随机平滑引入的误差与分离超平面 slack 之间的关系。
6. **（oracle 信息量）**设 gradient oracle 每次返回完整的 $\nabla f(x)$。论证在这种模型下，任何量子算法若只把 oracle 当作黑盒相位查询使用，相对经典 (sub)gradient 方法的每轮信息量没有本质优势；这与第 5.2 节的 no-go 结论如何衔接？

参考文献与 Zoo 覆盖

• Zoo 418、420：Quantum Algorithms and Lower Bounds for Convex Optimization 与 Convex Optimization Using Quantum Oracles.
• 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。

---

参考资料

• 本词条整理自《量子计算算法教程》原文：ch14-optimization-numerics/convex-optimization
• 内容遵循 CC BY-NC-SA 4.0 许可协议