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

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

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

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

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

:::{admonition} 本课知识点
:class: tip

1. **[凸集、凸函数与次梯度](#convexity-subgradient)**——能写出凸集与凸函数的定义不等式和次梯度不等式，解释支撑超平面的几何含义，并说明凸问题"任何局部极小值都是全局极小值"的根源。
2. **[黑盒模型与 oracle 层级](#oracle-hierarchy)**——能写出 sandwich 条件 $B(0,r)\subseteq K\subseteq B(0,R)$ 与弱 oracle 容差的含义，按信息量从小到大列出三种凸体 oracle 与两种函数 oracle，并解释比较复杂度为什么必须固定接口类型。
3. **[次梯度切割与体积收缩](#subgradient-cut-localization)**——能证明 Lemma 1（次梯度切割保留最优点），用每轮体积收缩推出迭代轮数 $\widetilde O(d)$，并把"每轮 $\Omega(d)$ 次探测"乘成近 $d^2$ 的经典总查询量。
4. **[Jordan 量子梯度估计](#jordan-gradient-qft)**——能把梯度分量编码为叠加网格上的线性相位、说明相位态为何因子化为 $d$ 个寄存器，并用逐寄存器逆 QFT 按 $g_i=k_i/(SMh)$ 读出全部分量、手算 $d=1,2$ 小例子。
5. **[误差预算与参数平衡](#error-budget-parameters)**——能列出 Taylor 余项、oracle 值误差与 Fourier 分辨率三条约束，并演示联立消元得到 $S\gtrsim Ld/\epsilon^2$、$M\sim 1/(Sh\epsilon)$ 的参数选择。
6. **[Gauge 代理与分离超平面](#gauge-separation-hyperplane)**——能验证 gauge 函数的正齐次性，用 Euler 齐次函数定理与支撑不等式证明其梯度给出合法分离超平面，并说明随机平滑的 slack 如何被弱 oracle 容差吸收。
7. **[查询下界与 no-go 边界](#lower-bound-no-go)**——能写出 $\widetilde\Omega(\sqrt d)$ 查询下界与 $\widetilde O(d)$ 上界，解释凸性为何使下界停在 $\sqrt d$，并说明 gradient oracle 预付梯度信息后 nonsmooth 问题上的量子优势为何消失。
8. **[体积估计：望远镜乘积与量子加速](#volume-telescoping)**——能写出嵌套凸体的望远镜乘积恒等式并说明比值估计的原理，指出量子行走与振幅估计各自贡献的平方根加速，并解释直接采样体积比为何指数慢。

:::

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

(convexity-subgradient)=
### 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)\}$，上式就是凸函数"图像在切线上方"这一熟知性质。凸优化问题的标准形式是

$$
\min_{x\in K} 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 容差匹配。

(oracle-hierarchy)=
### 1.3 三种 oracle 的信息量

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

1. **Membership oracle** $\operatorname{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,\qquad a\cdot y\le b\quad\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 与更精细的中心选择把迭代轮数压到 $\widetilde O(d)$ 量级。这是一条"几何"路线：每轮用一个超平面切掉候选区域的一块，靠体积收缩保证收敛。另一条"内点"路线（interior point）沿障碍函数的中央路径走，是实践中的主力，也是第 7 节线性规划量子加速的载体。

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

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

(subgradient-cut-localization)=
### 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^\*$ 是最优点，则 $x^\*\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^\*$（它满足 $f(x^\*)\le f(x_t)$）——都必须落在 $H_t$ 内。等价地，被切掉的那一半 $\{y:g_t\cdot(y-x_t)>0\}$ 里的点全部可以安全丢弃。Q.E.D.

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

### 2.2 体积收缩与迭代轮数

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

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

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

$$
\widetilde O(d)
$$

量级——体积每轮按因子 $(1-c/d^{\alpha})$ 缩小，把体积比 $R^d/(r\epsilon)^d$ 的对数 $\Theta(d\log(R/(r\epsilon)))$ 除以每轮的收缩量 $\Theta(1/d^{\alpha})$，就得到 $\widetilde 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)$ 在下界意义上是真实的）。于是经典黑盒凸优化的总查询量为

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

次 membership/value 查询。量子加速的全部内容，就是把第二个因子从 $\Omega(d)$ 压到 $\widetilde 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\rangle\mapsto e^{2\pi i S f(x_0+h z)}|z\rangle,
$$

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

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

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

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

$$
\frac1{M^{d/2}}\sum_z e^{2\pi i S f(x_0+h z)}|z\rangle.
$$

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

### 3.3 线性化：每一步的依据

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

$$
f(x_0+hz)
=f(x_0)+h\,\nabla f(x_0)\cdot z+R(z),
\qquad
|R(z)|\le \tfrac12 L h^2\|z\|^2,
$$

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

$$
e^{2\pi i S f(x_0+hz)}
=e^{2\pi i S f(x_0)}\cdot
\exp\!\Big(2\pi i S h\sum_{i=1}^d g_i z_i\Big)\cdot e^{\,O(SLh^2\|z\|^2)},
\qquad g_i=\frac{\partial f}{\partial x_i}(x_0).
$$

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

$$
\bigotimes_{i=1}^d
\left(
\frac1{\sqrt M}\sum_{z_i} e^{2\pi i (S h g_i) z_i}|z_i\rangle
\right):
$$

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

(jordan-gradient-qft)=
### 3.4 逆 QFT 读出：小例子完整算一遍

回忆逆 QFT 的核心性质（第 3 章）：在 $M$ 维计算基上，线性相位态 $\frac1{\sqrt M}\sum_{z}e^{2\pi i kz/M}|z\rangle$（$k$ 为整数）经逆 QFT 恰好变为 $|k\rangle$。因此只要

$$
S h g_i=\frac{k_i}{M},\qquad 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,\ldots,3\}$（为计算方便等价地取 $z\in\{0,\ldots,7\}$，相位只差整体因子）。相位查询后（忽略全局相位 $e^{2\pi i f(x_0)}$）：

$$
\frac1{\sqrt8}\sum_{z=0}^{7} e^{2\pi i\,(3/8)\,z}|z\rangle
=\frac1{\sqrt8}\sum_{z=0}^{7} e^{2\pi i\,3z/8}|z\rangle.
$$

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

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

$$
\left(\frac1{\sqrt8}\sum_{z_1}e^{2\pi i\,3z_1/8}|z_1\rangle\right)
\otimes
\left(\frac1{\sqrt8}\sum_{z_2}e^{-2\pi i\,2z_2/8}|z_2\rangle\right),
$$

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

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

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

1. **Taylor 余项误差。**相位污染量级为 $S\cdot \tfrac12Lh^2\|z\|^2$。网格上 $\|z\|^2$ 的典型值为 $\sum_i z_i^2\sim dM^2/12$，故要求

$$
S L h^2 M^2 d\lesssim 1.
$$

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

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

$$
S\epsilon_{\mathrm{or}}\lesssim 1.
$$

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

$$
\Delta g=\frac1{SMh}\le\epsilon
\quad\Longleftrightarrow\quad
SMh\gtrsim\frac1\epsilon.
$$

(error-budget-parameters)=
### 3.6 参数平衡：把约束联立解掉

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

$$
M\sim\frac1{Sh\epsilon}.
$$

代入约束 1：

$$
SLh^2d\cdot\frac1{S^2h^2\epsilon^2}=\frac{Ld}{S\epsilon^2}\lesssim1
\quad\Longrightarrow\quad
S\gtrsim\frac{Ld}{\epsilon^2}.
$$

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

**结论（Jordan 型梯度估计）**：对近似线性（或一般光滑）的 $f$，用 $\widetilde O(1)$ 次相干 value/相位查询即可把 $\nabla f(x_0)$ 的全部 $d$ 个分量估计到精度 $\epsilon$；经典 value oracle 做同样的事至少需要 $d+1$ 次查询（有限差分）。"$\widetilde 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\operatorname{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\iff x\in(\lambda/t)K$，对 $\lambda$ 取下确界即得。
- **凸性**：这是 $K$ 凸的直接推论（Minkowski 泛函的标准性质）。
- **刻画 $K$**：$\gamma_K(x)\le1\iff x\in K$（在闭性/弱容差意义下）。

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

### 4.3 平滑：让代理函数可微

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

$$
\tilde\gamma(x)=\mathbb E_\xi\big[\gamma_K(x+\xi)\big].
$$

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

(gauge-separation-hyperplane)=
### 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\le1$ 对所有 $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)\le1$，故 $a\cdot y\le\gamma_K(y)\le1$。

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

$$
a\cdot x>1,\qquad a\cdot y\le1\quad\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)$ 到 $\widetilde O(1)$，再到 $\widetilde O(d)$

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

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

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

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

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

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

(lower-bound-no-go)=
### 5.1 查询下界

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

$$
\widetilde\Omega(\sqrt d)
$$

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

下界的证明思路（定性描述）是通过**随机隐藏方向/凸体 packing** 构造困难实例：在 $d$ 维空间中放置指数多个彼此"查询上几乎不可分"的凸体（或隐藏一个随机的最优方向），使得每次 oracle 回答——无论经典还是量子相干查询——泄露的关于隐藏结构的互信息都很少。用量子对抗法/多项式方法把这种"每次查询信息量"的界转化为查询次数下界。要点是：凸性限制了对手的隐藏能力（不能像 unstructured search 那样任意），所以下界停在 $\sqrt d$ 而不是 $d$；而上界停在近 $d$。当前上界 $\widetilde O(d)$ 与下界 $\widetilde\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/\epsilon^2)$ 轮等）没有可被相干并行的结构。这给出一个一般性的教训，也是本篇反复强调"按 oracle 类型比较"的原因：

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

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

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

(volume-telescoping)=
### 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\operatorname{vol}(K_i)/\operatorname{vol}(K_{i+1})\le1$，这可以通过取同心球的梯度序列 $K_i=K\cap B(0,2^{i/L}R)$ 之类的构造实现），然后把体积写成**望远镜乘积 (telescoping product)**：

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

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

### 6.2 量子加速的两个来源

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

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

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

## 7. 结构化特殊问题

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

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

考虑二次目标

$$
f(x)=\tfrac12x^TAx-b^Tx,
$$

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

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

**完整小例子（$d=2$）。**设 $A=\begin{pmatrix}2&1\\1&3\end{pmatrix}$，$b=\begin{pmatrix}1\\0\end{pmatrix}$。在 $x=0$ 处做一次量子梯度估计，读出 $\nabla f(0)=-b=(-1,0)^T$；在 $x=e_1$ 处再读一次，$\nabla f(e_1)=Ae_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$ 个点、每个点 $\widetilde O(1)$ 次相干查询，总共 $O(d)$ 次 value 查询恢复整个 $A$。经典 value oracle 要恢复 $A$ 的 $d^2$ 个二阶差分，需要 $\Theta(d^2)$ 次查询——这是又一处 factor-$d$ 的改善。学到 $A,b$ 后，最小点 $x^\*=A^{-1}b$ 由 $\nabla f=0$ 解出（凸性即 $A\succeq0$）。注意输出本身是一个 $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 步），把量子线性系统求解（第 6 章 HHL/线性求解器框架）嵌入其中可获得多项式加速。保留条款与 HHL 一脉相承：加速幅度由 condition number 决定，读出经典迭代点需要 tomography 或精心维护的经典表示，精度需求随迭代轮数累积——这些常决定实际优势的有无。此外，norm-constrained linear regression 作为有结构的凸问题，已有与下界匹配的精细分析（Zoo 497），说明在结构化问题上"上下界吻合"是可以做到的。

## 8. 本课小结

**本篇要点：**

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

## 练习题

**练习 1【凸集、凸函数与次梯度】**（→ [1.1 节](#convexity-subgradient)）

1. 基础：写出凸集与凸函数的定义不等式；对一维函数 $f(x)=|x|$，求出次梯度集合 $\partial f(0)$，并验证其中每个 $g$ 都满足次梯度不等式。
2. 进阶：证明凸函数的任何局部极小值都是全局极小值：设 $x^\*$ 是局部极小点且存在 $y$ 使 $f(y)<f(x^\*)$，对线段上的点 $x_\lambda=\lambda y+(1-\lambda)x^\*$（$\lambda>0$ 充分小）应用凸性不等式，导出与局部极小性的矛盾。

> 提示：$f(x_\lambda)\le\lambda f(y)+(1-\lambda)f(x^\*)<f(x^\*)$，而 $\lambda\to0$ 时 $x_\lambda$ 可以任意接近 $x^\*$。

**练习 2【黑盒模型与 oracle 层级】**（→ [1.3 节](#oracle-hierarchy)）

1. 基础：写出 sandwich 条件与条件比 $\kappa=R/r$，并分别说明没有外球 $B(0,R)$、没有内球 $B(0,r)$ 各会让算法失去什么。
2. 基础：按信息量从小到大列出 membership/separation/optimization 三种凸体 oracle 与 value/gradient 两种函数 oracle，写明每次查询各返回多少信息。
3. 进阶：设 gradient oracle 每次返回完整的 $\nabla f(x)$。论证在这种模型下，任何量子算法若只把 oracle 当作黑盒相位查询使用，相对经典 (sub)gradient 方法的每轮信息量没有本质优势；这与第 5.2 节的 no-go 结论如何衔接？

> 提示：数一数一次查询各返回多少个数——"按次数直接比较不同接口"正是第 1.3 节关键观察批评的做法。

**练习 3【次梯度切割与体积收缩】**（→ [2.1 节](#subgradient-cut-localization)）

1. 基础：复述 cutting-plane 一轮的两种情形（不可行切割与目标切割），写出目标切割半空间 $H_t$ 的定义，并说明被切掉的半空间为何可以安全丢弃。
2. 进阶：证明 Lemma 1 的逆命题不成立：给出 $f$、$x_t$ 与点 $y\in H_t$ 但 $f(y)>f(x_t)$ 的例子（一维即可）。这说明目标切割"保守"在哪一侧？
3. 进阶：设某中心选择方案保证每轮把定位区域体积缩小常数比例（如 $1-1/e$）。证明把体积从 $\sim R^d$ 收缩到 $\sim(r\epsilon)^d$ 需要 $\Theta(d\log(R/(r\epsilon)))$ 轮，并结合每轮 $d+1$ 次有限差分 value 查询推出经典总查询量近 $d^2$。

> 提示：体积比的对数是 $d\log(R/(r\epsilon))$，每轮只从中减去一个常数。

**练习 4【Jordan 量子梯度估计】**（→ [3.4 节](#jordan-gradient-qft)）

1. 基础：复述"编码—读出"两步，写出读出标签与梯度分量的关系 $g_i=k_i/(SMh)$ 和 Fourier 分辨率 $\Delta g=1/(SMh)$，并说明相位查询后的态为何恰好因子化为 $d$ 个单寄存器态。
2. 基础：对 $d=2$ 的梯度估计任务，经典有限差分至少需要几次 value 求值？说明"1 次相干查询对 $d+1$ 次求值"的对比如何推广到一般 $d$。
3. 进阶：取 $d=1$，$M=4$，$S=h=1$，$g=1/4$。写出相位查询后的 4 维态向量，并对它手工执行逆 QFT（可用 $\mathrm{QFT}_4$ 的矩阵），验证测量以概率 1 得到 $k=1$。若改为 $g=3/8$，测量分布如何变化？

> 提示：$g=3/8$ 时 $Shg$ 落在两个相邻标签 $k=1$（对应 $1/4$）与 $k=2$（对应 $1/2$）的正中间，分布随之分散。

**练习 5【误差预算与参数平衡】**（→ [3.6 节](#error-budget-parameters)）

1. 基础：列出三个误差源与对应约束 $SLh^2M^2d\lesssim1$、$S\epsilon_{\mathrm{or}}\lesssim1$、$SMh\gtrsim1/\epsilon$，并各用一句话说明每条约束防止哪类失败。
2. 基础：取 $L=1$、$d=100$、$\epsilon=0.01$，用联立消元的结果估计必需的相位放大倍数 $S$ 的量级；若 value oracle 的精度为 $\epsilon_{\mathrm{or}}=10^{-4}$，约束 2 的上限 $S\lesssim1/\epsilon_{\mathrm{or}}$ 是否允许这样的 $S$？
3. 进阶：在第 3.5 节的三条约束中，固定 $S$ 与 $\epsilon$，解出 $M$ 与 $h$ 应满足的关系；并解释为什么"把 $h$ 取得尽量小"不能同时满足所有约束。

> 提示：把 $M\sim 1/(Sh\epsilon)$ 代回约束 1 后 $h$ 会消去，只剩下界 $S\gtrsim Ld/\epsilon^2$；再想想 $h\to0$ 时 $M$ 与每个寄存器的量子比特数如何变化。

**练习 6【Gauge 代理与分离超平面】**（→ [4.4 节](#gauge-separation-hyperplane)）

1. 基础：写出 gauge 函数 $\gamma_K$ 的定义与正齐次性、凸性、刻画 $K$ 三条性质，并说明沿一条射线用 membership oracle 二分为什么只需 $\widetilde O(1)$ 次查询就能把 $\gamma_K(x)$ 定位到给定精度。
2. 进阶：设 $K=\{x\in\mathbb R^2:\|x\|_\infty\le1\}$（正方形）。写出 $\gamma_K(x)$ 的显式公式，并在外点 $x=(2,1)$ 处计算分离超平面，验证它满足第 4.4 节的两个不等式。该点处 $\gamma_K$ 可微吗？这与随机平滑的必要性有何关系？
3. 进阶：解释为什么不能对示性函数 $\mathbf 1_K$ 直接做 Jordan 梯度估计；并说明随机平滑引入的误差与分离超平面 slack 之间的关系。

> 提示：$\gamma_K=\|\cdot\|_\infty$ 只在最大分量并列的方向（如对角方向 $x=(2,2)$）上不可微，可对比体会随机平滑的必要性。

**练习 7【查询下界与 no-go 边界】**（→ [5.1 节](#lower-bound-no-go)）

1. 基础：写出已知的量子查询下界与本文算法的上界（$\widetilde\Omega(\sqrt d)$ 对 $\widetilde O(d)$），并指出"没有已知内点"时 separation 查询需要 $\Omega(d)$ 次意味着什么。
2. 进阶：说明下界证明为什么要用随机隐藏方向/凸体 packing 构造困难实例，并解释"凸性限制了对手的隐藏能力，所以下界停在 $\sqrt d$ 而不是 $d$"这句话的含义；再说明为什么上界与下界之间的多项式 gap 已足以排除指数级的维数加速。

> 提示：与 unstructured search 对比——那里对手可以任意隐藏标记项；这里的隐藏结构必须保持凸性。

**练习 8【体积估计：望远镜乘积与量子加速】**（→ [6.1 节](#volume-telescoping)）

1. 基础：写出嵌套凸体序列与望远镜乘积恒等式，并说明相邻体积比有界时，为什么"在 $K_{i+1}$ 中均匀采样、统计落入 $K_i$ 的频率"是比值 $\operatorname{vol}(K_i)/\operatorname{vol}(K_{i+1})$ 的无偏估计。
2. 进阶：指出量子加速的两个来源——量子行走把混合时间从 $\Theta(1/\delta)$ 降到 $\Theta(1/\sqrt\delta)$、振幅估计把 $\Theta(1/\epsilon'^2)$ 个样本降到 $\Theta(1/\epsilon')$——并解释为什么直接均匀采样估计 $K$ 相对 $B(0,R)$ 的体积比会指数慢。

> 提示：命中率 $\operatorname{vol}(K)/\operatorname{vol}(B(0,R))$ 可低至 $(r/R)^d$。

## 参考文献与 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。