量子凸优化：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 搜索与振幅放大；本篇直接使用这些工具，不再重新推导。

本课知识点

  1. 凸集、凸函数与次梯度——能写出凸集与凸函数的定义不等式和次梯度不等式，解释支撑超平面的几何含义，并说明凸问题"任何局部极小值都是全局极小值"的根源。

  2. 黑盒模型与 oracle 层级——能写出 sandwich 条件 \(B(0,r)\subseteq K\subseteq B(0,R)\) 与弱 oracle 容差的含义，按信息量从小到大列出三种凸体 oracle 与两种函数 oracle，并解释比较复杂度为什么必须固定接口类型。

  3. 次梯度切割与体积收缩——能证明 Lemma 1（次梯度切割保留最优点），用每轮体积收缩推出迭代轮数 \(\widetilde O(d)\)，并把"每轮 \(\Omega(d)\) 次探测"乘成近 \(d^2\) 的经典总查询量。

  4. Jordan 量子梯度估计——能把梯度分量编码为叠加网格上的线性相位、说明相位态为何因子化为 \(d\) 个寄存器，并用逐寄存器逆 QFT 按 \(g_i=k_i/(SMh)\) 读出全部分量、手算 \(d=1,2\) 小例子。

  5. 误差预算与参数平衡——能列出 Taylor 余项、oracle 值误差与 Fourier 分辨率三条约束，并演示联立消元得到 \(S\gtrsim Ld/\epsilon^2\)、\(M\sim 1/(Sh\epsilon)\) 的参数选择。

  6. Gauge 代理与分离超平面——能验证 gauge 函数的正齐次性，用 Euler 齐次函数定理与支撑不等式证明其梯度给出合法分离超平面，并说明随机平滑的 slack 如何被弱 oracle 容差吸收。

  7. 查询下界与 no-go 边界——能写出 \(\widetilde\Omega(\sqrt d)\) 查询下界与 \(\widetilde O(d)\) 上界，解释凸性为何使下界停在 \(\sqrt d\)，并说明 gradient oracle 预付梯度信息后 nonsmooth 问题上的量子优势为何消失。

  8. 体积估计：望远镜乘积与量子加速——能写出嵌套凸体的望远镜乘积恒等式并说明比值估计的原理，指出量子行走与振幅估计各自贡献的平方根加速，并解释直接采样体积比为何指数慢。

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

\[ \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 容差匹配。

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 为什么是一切的核心

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\) 局部线性 + 相位乘法结构的直接推论。

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\) 的一个固定比例，否则线性相位态被破坏。）

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

\[ S\epsilon_{\mathrm{or}}\lesssim 1. \]

  1. **Fourier 分辨率。**要分辨梯度到精度 \(\epsilon\)，要求

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

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 节的三项预算并列，最终同样只贡献对数级因子。

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. 下界：为什么没有指数加速

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)\)。它是计数类问题的连续化身，经典最优算法是随机行走采样式，量子行走提供了另一处平方加速的用武之地。

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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  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 节）

  1. 基础：写出已知的量子查询下界与本文算法的上界（\(\widetilde\Omega(\sqrt d)\) 对 \(\widetilde O(d)\)），并指出"没有已知内点"时 separation 查询需要 \(\Omega(d)\) 次意味着什么。

  2. 进阶：说明下界证明为什么要用随机隐藏方向/凸体 packing 构造困难实例，并解释"凸性限制了对手的隐藏能力，所以下界停在 \(\sqrt d\) 而不是 \(d\)"这句话的含义；再说明为什么上界与下界之间的多项式 gap 已足以排除指数级的维数加速。

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

练习 8【体积估计：望远镜乘积与量子加速】（→ 6.1 节）

  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 覆盖