径向函数中心定位：高维 Curvelet 变换的方向性量子测量¶
给定一个未知的中心点 \(c \in \mathbb{R}^d\) 和一个径向函数 (radial function)
即函数值只依赖于采样点 \(x\) 到中心 \(c\) 的欧氏距离 \(\|x - c\|\)，我们希望用尽量少的 oracle 查询把 \(c\) 定位到固定的相对精度。
这个问题可以看作本章"隐藏结构"主题的一个几何变体：Simon 与 Shor 问题里被隐藏的是群里的子群或平移（代数结构），而这里被隐藏的参数 \(c\) 是一个几何结构——一个 \(d\) 维球面（更准确地说是函数等值面）的对称中心。与隐藏平移问题类似，中心 \(c\) 的信息并不直接写在函数值里，而是编码在函数的整体对称性中；区别在于这里的对称性是连续旋转对称，而非离散群作用。
为什么值得研究？首先是模型意义：经典算法要确定 \(d\) 个未知坐标，直觉上至少需要随 \(d\) 增长的查询数（例如逐坐标估计梯度就需要 \(\Theta(d)\) 次函数求值），而下面将看到，量子算法在理想化的连续模型中只需要与 \(d\) 无关的常数次查询——这是一个多项式量级的查询复杂度分离，而且问题是自然的几何问题，不是为此专门设计的预言机问题。其次是方法意义：该算法（Liu, STOC 2009，见文末参考文献）首次把调和分析中的 curvelet 变换 (curvelet transform) 引入量子算法设计。Curvelet 是经典信号处理中为"既定位又定向"地刻画波前（wavefront）而发展的工具，正好匹配量子测量的特点：一次测量可以同时吐出一个位置标签和一个方向标签，而我们要证明这两个标签合起来就近似地给出一条穿过未知中心的直线。
交代一下历史脉络，这有助于理解算法的设计动机。Curvelet 本身不是为量子计算发明的：它由 Candès 与 Donoho 等人在 2000 年前后发展起来，目标是最优地表示"沿光滑曲线有奇异性"的函数（图像中的边缘就是最典型的例子）。这类函数的波前既有位置又有方向，Fourier 基抓不住位置、小波基抓不住方向，curvelet 则证明了自己在渐近意义下是最稀疏的表示工具之一。Liu 的观察是：curvelet 的这个"位置 + 方向"双重标签结构，恰好可以嫁接到量子测量上——量子态制备可以借助叠加获得全局信息，而 curvelet 基下的测量把全局信息整理成几何上可解释的经典输出。同一篇论文还用类似技术处理了另一个几何问题（估计由两个平行超平面夹出的平板区域的朝向），方法骨架完全一致：制备态、curvelet 测量、从方向标签读出几何参数。本文集中讲径向函数这一个代表性问题。
本文的安排如下：先精确陈述问题和两种输入模型，解释经典算法的瓶颈；然后说明普通 Fourier 变换为什么不够、curvelet 为什么恰好够；接着给出算法的三个步骤（制备球壳态、量子 curvelet 测量、法线求交），并补上完整的推导与一个可手算的小例子；最后讨论经典下界、模型限定条件与复杂度账目。
本课知识点
问题模型与承诺条件——能写出径向函数的定义与"固定相对精度"目标 \(\|\widehat{c} - c\| \le \varepsilon\beta\)，并列出函数 oracle、quantum sample 两种输入模型与薄壳、半径已知等承诺条件。
经典瓶颈与三步算法总览——能解释经典逐坐标梯度方法为何需要 \(\Theta(d)\) 次查询，并能列出量子算法"制备薄壳态—curvelet 测量—最小二乘求交"三步及各步的查询/门开销量级。
Fourier 域的相位盲区——能推导 \(\hat{f}(\xi) = e^{-2\pi i\,\xi\cdot c}\,h(\|\xi\|)\)，并说明 Fourier 测量的输出分布为何对中心 \(c\) 没有任何依赖。
Curvelet 标签与抛物线尺度——能解释 \((a, b, \theta)\) 标签与"法向窄、切向长"的板状波包形状，并由弧高贴合条件推导 \(\ell_t \approx \sqrt{\beta\delta}\) 与方向分辨率 \(\Delta\theta \approx \sqrt{\delta/\beta}\)。
薄壳态的 oracle 制备——能写出"均匀叠加—查询—振幅整形"三步流程与理想化薄壳态 \(|\psi_c\rangle\)，并说明后选择开销为何不破坏常数次查询。
法向计算与定相原理——能计算球壳等值面的单位法向并验证模长为 1，能用分部积分的衰减估计说明高频质量沿法向集中、测得方向满足 \(\theta \approx \pm\frac{b - c}{\|b - c\|}\)。
近似法线的最小二乘求交——能推导正规方程 \(A\widehat{c} = v\)，能由 \(A\) 的谱判断哪些方向可辨识、何时病态，并完成 \(d = 2\) 的最小二乘手算。
单次测量定位与复杂度分离——能写出 quantum sample 模型中的单次定位公式 \(c \approx b \mp \beta\theta\) 并消解符号歧义，能比较量子 \(O(1)\) 对经典 \(\Omega(d)\) 的查询分离并列举模型限定条件。
1. 问题陈述与输入模型¶
1.1 函数 oracle 模型¶
第一种输入方式是标准的函数求值 oracle。离散化后，我们把空间限制在一个网格上：取足够大的区域，划分为 \(N^d\) 个格点（每个坐标方向 \(N = 2^n\) 个格点，\(n\) 为每坐标的比特数），\(x\) 用 \(dn\) 个比特记录。Oracle 按惯例实现为可逆映射
其中 \(\oplus\) 是逐比特异或，\(f(x)\) 以足够的精度存储。所谓"一次查询"就是调用一次 \(O_f\)（或其受控版本）。在论文的理想化连续模型中，空间就是 \(\mathbb{R}^d\) 本身，波函数是 \(L^2(\mathbb{R}^d)\) 中的函数，"查询"被抽象为对态制备的相干访问——我们将在第 3 节说明，核心结论是先在连续模型中严格建立、再讨论离散实现的。
问题有几个承诺条件（promise），它们都会在后面的分析中用到：
函数在半径 \(\beta\) 附近形成一个薄壳 (thin shell)：\(g(r)\) 在 \(|r - \beta| \lesssim \delta\) 的窄环带内有显著起伏，其中壳厚 \(\delta \ll \beta\)；
半径 \(\beta\)（或其所在区间）是已知的；
目标精度是固定相对精度：要求输出 \(\widehat{c}\) 满足 \(\|\widehat{c} - c\| \le \varepsilon \beta\)，其中 \(\varepsilon\) 视为常数。
1.2 Quantum sample 模型¶
第二种输入方式更强：我们直接得到一个量子样本 (quantum sample)，即球内均匀叠加态
（离散版本：对球内格点均匀叠加）。这相当于假设有某个外部过程能批量制备这样的态，我们不再需要函数 oracle。第 7 节会看到，在这个模型中算法有"一次测量定位"的味道。
1.3 经典算法的瓶颈¶
先建立直觉：为什么经典上这个问题随维数变难？
最朴素的想法是逐坐标探测。若我们能数值估计梯度 \(\nabla f\)，则对径向函数有（下一节会详细推导）
梯度方向直接指向中心。但用有限差分估计一个 \(d\) 维梯度需要 \(d+1\) 个点上的函数值——仅"求一次梯度"就要 \(\Theta(d)\) 次查询。更一般地，每次经典查询只返回一个标量 \(f(x)\)，而未知的 \(c\) 有 \(d\) 个自由度，信息论直觉就是"每次查询最多消除一个坐标方向上的不确定性"，所以查询数应当随 \(d\) 线性增长。论文把这一直觉严格化：在一个精心构造的随机径向函数分布下（函数带有随机的细尺度起伏），证明了任何经典算法要达到固定精度需要 \(\Omega(d)\) 次查询（见第 8 节）。
量子算法的机会在于：一次查询可以把 \(f\) 的信息叠加地写入整个态的振幅，而一次设计得当的测量可以一次性读出一个 \(d\) 维的方向标签。关键是怎么设计这个测量基——这正是 curvelet 登场的地方。
1.4 算法总览¶
在进入细节之前，先把整个算法压缩成三行，后文就是逐行展开：
制备（常数次查询）：用函数 oracle 制备"薄壳态"——位置振幅集中在以 \(c\) 为心、半径 \(\beta\)、厚度 \(\delta\) 的球壳上的量子态（第 4 节）；
测量（零查询，多项式门）：对薄壳态执行量子 curvelet 变换并在 \((a, b, \theta)\) 基下测量，得到一个位置标签 \(b\) 和一个方向标签 \(\theta\)；我们将证明 \(\theta\) 近似是壳面在 \(b\) 处的法向，即直线 \(L(b, \theta)\) 近似穿过 \(c\)（第 3、5 节）；
后处理（经典计算）：重复采样常数次，用最小二乘求这些直线的近似公共交点，输出中心估计 \(\widehat{c}\)（第 6 节）。
值得预先指出每一步为什么"便宜"：第 1 步的查询数是常数，因为它不随 \(d\) 分解——叠加态一次性覆盖整个空间；第 2 步的输出是一个字典索引，curvelet 字典大小是多项式的（第 3.2 节计数），所以一次测量读出的经典比特数足够编码一个 \(d\) 维方向，这与"一次测量只能提取少量信息"的直觉并不矛盾——我们不是在读取一个未知量子态的全部信息，而是在对一个专门制备的态做一次专门设计的计算基测量；第 3 步只需常数个样本，原因是精度目标是固定相对精度（第 6.2 节）。把这三点拼起来，就是"量子 \(O(1)\) 查询对经典 \(\Omega(d)\) 查询"的完整逻辑链。
2. 为什么普通 Fourier 变换不够¶
拿到一个"叠加了全空间信息"的量子态，本站读者（已学过 QFT 与相位估计）的第一反应应当是：做 Fourier 变换。本节说明这条路为什么走不通，这既是动机，也指明了需要什么性质的变换。
2.1 平移在 Fourier 域变成相位¶
对 \(f(x) = g(\|x-c\|)\) 做（连续）Fourier 变换。记 \(\hat{f}(\xi) = \int f(x)\,e^{-2\pi i\, \xi \cdot x}\,dx\)，做变量代换 \(y = x - c\)（平移不改变积分测度，\(dx = dy\)）：
其中 \(h(\|\xi\|) = \int g(\|y\|)e^{-2\pi i\,\xi\cdot y}\,dy\) 是以原点为中心的径向函数的 Fourier 变换。这里用到一个标准事实：径向函数的 Fourier 变换仍是径向函数（Fourier 变换与旋转可交换：对旋转矩阵 \(R\) 做代换 \(y \mapsto Ry\)，指数中的 \(\xi\cdot Ry = (R^T\xi)\cdot y\)，说明 \(\hat{f}_0(R\xi) = \hat{f}_0(\xi)\)）。
这个恒等式是整个动机的核心：中心 \(c\) 的全部信息都藏在相位因子 \(e^{-2\pi i\,\xi\cdot c}\) 里。而在 Fourier 基下做投影测量，测得频率 \(\xi\) 的概率是
模长平方把相位完全抹掉了。换句话说，Fourier 测量给出的概率分布对 \(c\) 根本没有任何依赖——它不仅"不够用"，而是一比特关于 \(c\) 的信息都没有。这与隐藏平移问题中的处境如出一辙：平移信息进入相位，直接测量基矢分布看不到它，必须换一个对相位敏感的测量方式。
2.2 Fourier 变换确实能看到"壳有多薄"¶
公平地说，Fourier 谱并非毫无用处：它能告诉我们壳的厚度尺度。直觉来源是缩放对应关系（不确定性原理的具体化）：若窗函数 \(w(r)\) 支撑在宽度 \(\delta\) 的区间上，则其 Fourier 变换 \(\widehat{w}(\rho)\) 的主要质量集中在 \(|\rho| \gtrsim 1/\delta\) 的频段——空间上越窄的鼓包，频域展得越宽。薄壳态（见第 3 节）的 Fourier 变换因而集中在半径 \(\approx 1/\delta\) 的频率球壳上。
但这只回答了"存在多高的频率"，回答不了"这个频率来自壳面上的哪个位置、沿什么方向振荡"。球面上不同位置的法向方向各不相同，全局频谱把所有方向的信息混合成一个标量函数 \(|h(\|\xi\|)|^2\)，无法从中做三角定位。
2.3 需要"既定位又定向"的基¶
把需求列出来，我们想要的测量基应满足：
空间局域性：每个基矢集中在壳面上一小块区域，测得它就知道"波前在哪里"（位置标签 \(b\)）；
方向选择性：每个基矢的 Fourier 支撑集中在一个窄的方向楔内，测得它就知道"波前沿什么方向振荡"（方向标签 \(\theta\)）；
多尺度：能自动匹配壳厚 \(\delta\) 对应的频率尺度。
经典的小波 (wavelet) 满足前两条中的第一条和多尺度，但它是各向同性的（或只沿坐标轴定向），不能分辨任意方向；Fourier 基方向性完美却完全没有空间局域性。Curvelet 正是调和分析中为同时满足这三条而构造的基（由 Candès 与 Donoho 等人为最优表示带奇异曲线的函数而发展）：它是带方向的多尺度波包，恰好提供 \((a, b, \theta)\) 三元组标签。下一节把它讲清楚。
3. Curvelet 变换：带方向的多尺度显微镜¶
3.1 Curvelet 的标签与几何¶
一个 curvelet 由三个标签参数化（概念性写法）：
其中：
\(a > 0\) 是尺度 (scale)，对应频率 \(\sim 1/a\)：\(a\) 越小，波包振荡得越快；
\(b \in \mathbb{R}^d\) 是空间位置：波包以 \(b\) 为中心局域化；
\(\theta \in S^{d-1}\) 是方向：\(S^{d-1}\) 表示 \(\mathbb{R}^d\) 中的单位球面，\(\theta\) 是波包在 Fourier 域中所占楔形的主方向。
高频（小 \(a\)）curvelet 在频域局限于一个窄角楔：楔的轴线沿 \(\theta\)，楔的半径范围大约是 \([1/a, 2/a]\)（这就是"尺度 \(a\) 对应频率 \(1/a\)"的含义），楔的角宽度约为 \(\sqrt{a/\beta}\) 量级（下一小节解释这个平方根的来历）。在空间域，它是沿 \(\theta\) 方向快速振荡、横向上缓慢衰减的各向异性波包：沿振荡方向的宽度 \(\approx a\)，垂直方向的"长度" \(\approx \sqrt{a\beta}\)。也就是说它像一块扁长的"小木板"，板面贴在波前上，法向沿 \(\theta\)——同时携带位置与法向两种信息，这正是 Fourier 基和小波基各自做不到的。
为了让"波包"这个概念落地，可以给出一个简化的显式模型（真实 curvelet 的构造更精细，但核心结构相同）。取一个钟形包络 \(u \ge 0\)（如高斯函数）与频率 \(k = 1/a\)，定义加窗平面波
其中坐标系的第 1 轴沿 \(\theta\) 方向，\(\ell_r \approx a\) 是法向宽度，\(\ell_t \approx \sqrt{a\beta}\) 是切向长度，前置因子保证 \(\|\gamma\|_2 = 1\)。对它做 Fourier 变换：包络的缩放 \(x \mapsto x/\ell\) 在频域变为 \(\xi \mapsto \ell\,\xi\)（缩放对偶性，与 2.2 节同一事实），平面波因子 \(e^{2\pi i k \theta\cdot x}\) 则把频谱整体平移到 \(k\theta\) 附近（Fourier 变换的调制性质）。合起来，\(\widehat{\gamma}\) 集中在以 \(k\theta\) 为中心、法向宽 \(1/\ell_r \approx k\)、切向宽 \(1/\ell_t\) 的盒子里——正是轴线沿 \(\theta\)、角宽 \(\approx 1/(k\ell_t)\) 的频域楔形。这个"空间盒子 \(\ell_r \times \ell_t^{\,d-1}\) 对偶于频域盒子 \(1/\ell_r \times 1/\ell_t^{\,d-1}\)"的对应关系（Heisenberg 盒）是理解一切波包变换的钥匙，下一小节的抛物线尺度关系就是在约束 Heisenberg 盒的形状。
3.2 抛物线尺度关系：宽度 ≈ 长度² 的由来¶
上面"宽度 \(a\)、长度 \(\sqrt{a\beta}\)"的形状不是随意取的，它是贴合弯曲波前的最优形状，推导如下，这就是著名的抛物线尺度关系 (parabolic scaling)。
考虑壳面（曲率半径 \(\beta\) 的球面）上沿法向以频率 \(k \approx 1/\delta\) 振荡的波。我们要用一个波包去"咬住"一小片波前，设波包沿法向的宽度为 \(\ell_r\)、沿切向的长度为 \(\ell_t\)，要求两条：
不确定性原理：沿法向要分辨频率 \(k\) 的振荡，宽度至多到 \(\ell_r \approx 1/k \approx \delta\) 量级（再宽就混入了壳外的空白区域或壳的对侧）；
贴合条件：波包是"平"的，而波前是弯的。沿切向走出距离 \(\ell_t\) 后，球面相对切平面的偏离量（即弧高，sagitta）为 \(\beta - \sqrt{\beta^2 - \ell_t^2} \approx \frac{\ell_t^2}{2\beta}\)（这里用了 \(\sqrt{1-u} \approx 1 - u/2\) 对小 \(u = \ell_t^2/\beta^2\) 的泰勒近似）。要让波前在波包覆盖范围内始终落在厚度 \(\ell_r\) 之内，需要
取 \(\ell_t\) 尽量大（切向覆盖越大，方向分辨越精细），令两边相等，解出平衡条件
这就是"长度是宽度的几何平均"——写成无量纲形式即 \(\ell_t^2 \sim \beta\,\ell_r\)，俗称 width ≈ length²（在 \(\beta \sim O(1)\) 的单位制下）。
由此立刻得到方向分辨率。一个横向长度为 \(\ell_t\)、振荡频率为 \(k\) 的波包，其 Fourier 支撑在横向的展宽约 \(1/\ell_t\)、沿 \(\theta\) 方向位于半径 \(k\) 处，因此角度不确定性为
壳越薄（\(\delta\) 越小），可用频率越高，法向估计越精确——这是后文一切精度估计的基本参数关系。同时它也解释了为什么需要薄壳与细尺度起伏：若 \(g\) 在大尺度上平缓变化，则没有高频成分，\(\Delta\theta\) 压不小，curvelet 也就无用武之地；极端地，若 \(g\) 几乎常数，则函数根本不携带中心信息，任何模型都无能为力。
附带计数：方向球面 \(S^{d-1}\) 用角宽 \(\Delta\theta\) 的楔去铺，需要 \(\approx (\Delta\theta)^{-(d-1)}\) 个方向；再乘上多项式个尺度与位置网格点，curvelet 字典的总大小是 \(d\)、\(1/\Delta\theta\) 与网格比特数的多项式。这一点保证了下面离散电路的规模是多项式的。
3.3 量子 curvelet 变换的电路¶
量子 curvelet 变换是一个酉换基操作，分三步：
高维 Fourier 变换：对 \(dn\) 个位置比特做 QFT（逐坐标做 \(d\) 次 \(n\) 比特 QFT），把态变到频率域，门数为 \(O(d\,n^2)\) 量级；
相干分箱 (coherent binning)：在频率域按"半径频带 × 方向楔"把振幅相干地重新分组到 \((a, \theta)\) 寄存器。分箱边界是可计算的几何条件（\(|\xi|\) 落在哪个频带、\(\xi/|\xi|\) 落在哪个楔），因此可用可逆算术电路实现，并把分箱结果转置 (uncompute) 回原寄存器；
逐楔局部逆 Fourier 变换：对每个楔内的频率数据做逆 QFT，得到该尺度-方向下的空间局域系数，即 \((a, b, \theta)\) 标签下的振幅。
只要网格规模、尺度个数与方向精度都是多项式位数（即 \(n\)、尺度数、\((\Delta\theta)^{-1}\) 的对数均为多项式），整个电路由 QFT、可逆算术与受控旋转组成，总门数是多项式的。需要强调：这一步不消耗任何查询——它是对已有量子态的纯酉加工。查询全部花在下一步的态制备上。
4. 从 oracle 制备球壳量子态¶
算法的第一个量子步骤是把函数 oracle 的信息转化为一个几何上集中的态。分三步：
均匀叠加：对位置寄存器做 Hadamard（或 QFT 的初态制备），得到查询区域内格点的均匀叠加 \(\propto \sum_x |x\rangle\)；
查询：调用 \(O_f\)，把 \(f(x)\) 写入辅助寄存器，得到 \(\sum_x |x\rangle|f(x)\rangle\)；
振幅整形：以 \(|f(x)\rangle\) 为控制条件，对辅助寄存器做相位或振幅变换（阈值化/带通），突出 \(f\) 快速变化的半径区间——也就是薄壳附近，最后用一次 \(O_f\) 把辅助寄存器复位（uncompute）。
理想化之后，得到的归一化态可写为
其中窗函数 \(w\) 支撑在宽度约 \(\delta\) 的薄壳上。直觉上，这就是"以 \(c\) 为心、半径 \(\beta\)、厚度 \(\delta\) 的一个发光球壳"的量子态：位置测量会落在壳附近，但单次位置测量给不出 \(c\)（球壳上一点到中心的距离都一样）。我们不直接测量位置，而是对它做 curvelet 测量。
两点说明。第一，第 3 步的阈值化若涉及后选择（成功的振幅比例是一个常数），可用振幅放大把期望查询数压回常数，不改变 \(O(1)\) 的结论。第二，这一步隐含使用了承诺条件：\(g\) 必须在尺度 \(\delta\) 上有可观测起伏，窗函数才"抓得住"壳。
5. 为什么测得的方向指向中心¶
本节证明核心几何事实：curvelet 测量返回的 \((b, \theta)\) 近似给出一条穿过中心的直线。
5.1 球壳的法向¶
球壳由相位函数
的零等值面 \(\{x : \Phi(x) = 0\}\) 定义。光滑等值面的法向由梯度给出，因此计算：
Lemma 1. 对 \(x \neq c\)，
证明。逐分量计算。记 \(x = (x_1, \dots, x_d)\)、\(c = (c_1, \dots, c_d)\)，则 \(\Phi(x) = \sqrt{\sum_{j=1}^d (x_j - c_j)^2} - \beta\)。对第 \(i\) 个分量用链式法则（外层是平方根，内层是平方和）：
把 \(d\) 个分量排成向量即得结论。注意 \(\|\nabla\Phi\| = 1\)：梯度本身就是单位法向量。Q.E.D.
5.2 高频振荡沿法向：定相直觉¶
薄壳态 \(w(\|x-c\|-\beta)\) 在壳内沿径向（即等值面法向）快速变化——它从壳外到壳内再出壳，横向跨越距离 \(\delta\)，这正是频率 \(k \approx 1/\delta\) 的来源；而沿切向，在 \(\sqrt{\beta\delta}\) 的尺度内函数几乎不变（球面局部近似为平面，半径方向在该尺度内偏转不超过 \(\Delta\theta \approx \sqrt{\delta/\beta}\)，见 3.2 节）。
调和分析中把这一观察严格化的工具是定相原理 (stationary phase) 与波前集 (wavefront set)：一个沿光滑曲面奇异/快变的函数，其高频 Fourier 质量集中在该曲面法线方向附近。定相原理的含义在此可以用一句话理解：对振荡积分 \(\int w(\Phi(x)) e^{-2\pi i \xi \cdot x} dx\)，当 \(\xi\) 不平行于 \(\nabla\Phi\) 时，积分沿壳面切向发生剧烈相消干涉，贡献指数级小；只有 \(\xi\) 接近法向时各点的相位才对齐、贡献相互加强。因此壳态的 curvelet 系数只在"位置 \(b\) 靠近壳面 且 方向 \(\theta\) 接近该处法向"的标签上显著。
这个"相消干涉"的论断可以在一维中严格地看出来，所用的工具只有分部积分。设 \(w\) 是光滑紧支撑函数，考虑其 Fourier 变换在 \(\xi \neq 0\) 处的值。利用 \(\frac{d}{dx}e^{-2\pi i \xi x} = -2\pi i \xi\, e^{-2\pi i \xi x}\)，把 \(e^{-2\pi i \xi x} = \frac{1}{-2\pi i \xi}\frac{d}{dx}e^{-2\pi i \xi x}\) 代入并分部积分一次（紧支撑保证边界项为零）：
最后一步把导数移到了 \(w\) 上。这个操作可以重复任意多次：每分部积分一次多出一个因子 \(\frac{1}{2\pi i \xi}\)，被积函数换为 \(w\) 的下一阶导数。于是对任意正整数 \(M\) 都有
即 \(\widehat{w}(\xi)\) 随 \(|\xi|\) 衰减得比任何多项式都快——没有驻相点时，高频贡献超多项式小。推广到壳面上的积分：当 \(\xi\) 不沿法向时，相位 \(\xi\cdot x\) 沿壳面切向没有驻点，同样的分部积分论证（沿切向方向进行）给出超多项式衰减；唯有 \(\xi\) 接近法向时切向相位变化率为零、驻点出现，衰减失效，贡献被保留。这就是"高频分量主要沿法向振荡"的定量内容。
于是，curvelet 测量若返回位置 \(b\) 与方向 \(\theta\)，在好事件（振幅集中在几何正确的标签上）中有
符号 \(\pm\) 的出现是因为 curvelet 的方向楔对 \(\theta \leftrightarrow -\theta\) 通常不加区分：波包沿 \(\theta\) 振荡与沿 \(-\theta\) 振荡是同一族波包。等价的陈述是：未知中心 \(c\) 落在直线
附近——这条直线过测量位置 \(b\)、沿测量方向 \(\theta\) 延伸，符号不确定性被吸收进参数 \(t \in \mathbb{R}\) 的双向取值中，不影响"直线"这一对象本身。
5.3 与逐坐标梯度的对比¶
回看 1.3 节：经典算法里，要得到一个方向需要 \(\Theta(d)\) 次查询去拼出整个梯度向量；而这里一次 curvelet 测量返回的标签 \(\theta\) 本身就是一个 \(d\) 维方向（记录它需要 \(O(d)\) 个比特，但量子测量的输出寄存器一次就能容纳）。位置-方向信息的获取不随 \(d\) 分解，这就是查询数可以不随 \(d\) 增长的根本原因。
6. 从若干近似法线求交：最小二乘¶
一次测量给出一条近似穿过 \(c\) 的直线；做若干次独立测量，得到若干条这样的直线，中心就近似地是它们的公共交点。由于每条直线都有误差，用最小二乘求"到所有直线总距离最小"的点。
6.1 正规方程的推导¶
点 \(z\) 到直线 \(L(b_i, \theta_i)\) 的平方距离，等于向量 \(z - b_i\) 去掉其在 \(\theta_i\) 方向上分量的长度平方。投影到 \(\theta_i\) 正交补空间的投影矩阵是 \(I - \theta_i\theta_i^T\)（验证：\((I - \theta_i\theta_i^T)z = z - (\theta_i\cdot z)\theta_i\)，确实减去了 \(\theta_i\) 分量；且该矩阵对称、幂等）。于是目标函数为
Lemma 2（正规方程）。记
则最小二乘解满足 \(A\widehat{c} = v\)；当 \(A\) 可逆时 \(\widehat{c} = A^{-1}v\)。
证明。把第 \(i\) 项展开。记 \(P_i = I - \theta_i\theta_i^T\)，利用 \(P_i^T P_i = P_i^2 = P_i\)（对称幂等）：
对 \(i\) 求和，得到关于 \(z\) 的二次函数
其中常数项 \(\sum_i b_i^T P_i b_i\) 与 \(z\) 无关。对 \(z\) 求梯度：\(\nabla_z(z^T A z) = 2Az\)（\(A\) 对称），\(\nabla_z(2z^T v) = 2v\)，故
令梯度为零得正规方程 \(Az = v\)。由于 \(A\) 是半正定矩阵之和（每个 \(P_i\) 半正定），\(A\) 半正定，\(F\) 是凸函数，驻点即最小值点；\(A\) 可逆时解唯一，为 \(\widehat{c} = A^{-1}v\)。Q.E.D.
6.2 什么时候 \(A\) 条件良好¶
\(A = \sum_i (I - \theta_i\theta_i^T)\) 的每个加项 \(I - \theta_i\theta_i^T\) 是"垂直于 \(\theta_i\)"方向的投影：它在 \(\theta_i\) 方向上的特征值为 \(0\)，在其余 \(d-1\) 个方向上的特征值为 \(1\)。直觉地，\(A\) 记录了"各样本在哪些方向上提供了约束"：第 \(i\) 条直线约束了除 \(\theta_i\) 以外的所有方向上的位置（沿直线本身的方向无约束）。因此：
若所有 \(\theta_i\) 几乎平行，则沿该公共方向的约束始终缺失，\(A\) 病态，中心沿该方向不可辨识（习题 3）；
若各 \(\theta_i\) 在球面上分散开，\(A\) 的最小特征值随样本数线性增长，条件良好。
"分散开时条件良好"可以算得很具体：
Lemma 3. 设 \(\theta\) 在单位球面 \(S^{d-1}\) 上均匀随机，则 \(\mathbb{E}[\theta\theta^T] = \frac{1}{d}I\)；从而对 \(m\) 个独立随机方向，
证明。记 \(M = \mathbb{E}[\theta\theta^T]\)。先证 \(M\) 与单位矩阵成比例：对任意正交矩阵 \(R\)，随机向量 \(R\theta\) 与 \(\theta\) 同分布（球面均匀分布在旋转下不变），因此
即 \(M\) 与所有旋转可交换；这样的矩阵必是恒等矩阵的倍数（否则取 \(M\) 的某个特征子空间，旋转作用会把它映到别的特征子空间，与"任意旋转下不变"矛盾）。设 \(M = \lambda I\)，用迹确定 \(\lambda\)：
（第二步用了迹的循环性 \(\mathrm{tr}(\theta\theta^T) = \mathrm{tr}(\theta^T\theta)\)，第三步用 \(\theta\) 是单位向量。）而 \(\mathrm{tr}(\lambda I) = \lambda d\)，故 \(\lambda = 1/d\)。对 \(A\) 的期望用期望的线性性质逐项代入即得第二个结论。Q.E.D.
这个引理的意义是：期望意义下 \(A\) 的每个特征值都是 \(m(1 - 1/d) \approx m\)——每增加一个样本，所有方向上的约束强度同步增加约 1，与 \(d\) 无关。集中到期望附近（随机方向的谱集中不等式）只需 \(m\) 为常数即可使 \(A\) 以常数概率条件良好。这正是"常数个样本以常数概率提供足够几何约束"的定量版本。
由于样本位置 \(b_i\) 落在球面上随机的位置，方向 \(\theta_i \approx \pm (b_i - c)/\beta\) 也随之随机分散。论文在固定相对精度目标下论证：常数个样本即以常数概率给出足够分散的方向集合；算法同时计算 \(A\) 的条件数，若发现病态就丢弃重采。因为只要求"常数概率成功 + 常数轮重采"，期望查询数仍是 \(O(1)\)，成功率可用标准的常数轮重复放大。
6.3 一个可以手算的例子¶
取 \(d = 2\)、\(\beta = 1\)、真实中心 \(c = (0,0)\)。假设做三次测量，前两次恰好精确，第三次的方向有微小误差：
\(b_1 = (1,0)\)，\(\theta_1 = (1,0)\)（精确：\(b_1 - c\) 确实沿 \(x\) 轴）；
\(b_2 = (0,1)\)，\(\theta_2 = (0,1)\)（精确）；
\(b_3 = (-1, 0)\)，\(\theta_3 = (-0.995, 0.1)\)（有 \(\approx 0.1\) 弧度的角误差；\(\|\theta_3\| = \sqrt{0.99 + 0.01} = 1\)，仍为单位向量）。
逐个计算投影矩阵 \(P_i = I - \theta_i\theta_i^T\)。对 \(\theta = (\theta_x, \theta_y)\)，有 \(\theta\theta^T = \begin{pmatrix} \theta_x^2 & \theta_x\theta_y \\ \theta_x\theta_y & \theta_y^2 \end{pmatrix}\)，于是
（\(P_3\) 中用 \((-0.995)(0.1) = -0.0995\)，两个负号相乘得 \(+0.0995\)。）求和：
再算 \(v = \sum_i P_i b_i\)：\(P_1 b_1 = P_1(1,0)^T = (0,0)^T\)（第一列），\(P_2 b_2 = (0,0)^T\)（第二列），\(P_3 b_3 = P_3(-1,0)^T = (-0.01, -0.0995)^T\)（第一列乘以 \(-1\)）。所以
解 \(A\widehat{c} = v\)。行列式 \(\det A = 1.01 \times 1.99 - 0.0995^2 = 2.0099 - 0.0099 = 2.00\)，用求逆公式 \(A^{-1} = \frac{1}{\det A}\begin{pmatrix} 1.99 & -0.0995 \\ -0.0995 & 1.01 \end{pmatrix}\)：
解读：\(\|\widehat{c} - c\| \approx 0.05\)，量级为 \(\beta \cdot \Delta\theta / \sqrt{m}\) 附近（\(\Delta\theta \approx 0.1\)、\(m = 3\) 个样本），与 3.2 节的误差标度一致——单条直线的固有横向误差 \(\sim \beta\Delta\theta\)，多个样本做最小二乘平均后大致缩小 \(\sqrt{m}\) 倍。若第三个测量也精确（\(\theta_3 = (-1, 0)\)），则 \(P_3 = \begin{pmatrix} 0 & 0 \\ 0 & 1 \end{pmatrix}\)，\(A = \mathrm{diag}(1, 2)\)、\(v = 0\)，得 \(\widehat{c} = (0,0)\)，精确恢复。这个例子同时说明：方向分散（三个方向张满平面）时 \(A\) 的条件很好，最小二乘解稳定。
7. Quantum sample 模型：单次测量版本¶
现在切换到更强的输入模型：假设直接得到球内均匀量子样本
与薄壳态的区别在于：这个态在球内部是平的，唯一的"特征"是边界 \(\|x-c\| = \beta\) 处振幅从常数跳变为零——一个阶梯型奇异性。按 5.2 节的波前集语言，阶梯奇异的波前集正是边界曲面的法线束：高频成分全部来自边界、且沿法向。因此对这个态做 curvelet 变换，响应集中在"位置 \(b\) 贴近边界、方向 \(\theta\) 沿边界法向"的标签上，机制与薄壳完全相同，只是"薄壳厚度 \(\delta\)"的角色由阶梯边缘的固有锐度扮演。
测得一个位置-方向对 \((b, \theta)\) 之后，由于 \(\theta\) 近似是边界点 \(b\) 处的单位法向、而球心位于边界点沿内法向退回半径 \(\beta\) 处，可以直接写出中心估计
符号 \(\mp\) 对应方向标签的 \(\pm\) 歧义（curvelet 不区分 \(\theta\) 与 \(-\theta\)）。消解歧义只需常数次额外操作：对两个候选中心 \(b \pm \beta\theta\) 各做一次检验（例如在其邻域内评估函数或比对量子样本），球内/球外的对比会立即排除错误候选。
这个版本解释了模型的资源差异：quantum sample 模型中"制备态"的成本被外部化，一次 curvelet 测量就已给出中心方向与半径臂长，近似"一次测量定位"；而函数 oracle 模型还要自己制备薄壳态（第 4 节）、用若干样本做最小二乘（第 6 节），查询数仍是常数，但常数更大。
8. 经典下界与模型限定¶
8.1 为什么经典需要 \(\Omega(d)\) 次查询¶
论文构造了一个随机径向函数分布：\(g\) 由缓慢变化的"大趋势"叠加随机的细尺度起伏组成，中心 \(c\) 随机选取。在这个分布下：
每次经典查询只返回一个标量 \(f(x)\)，且由于细尺度起伏是随机的，单点函数值携带的关于全局中心的信息被随机噪声严重稀释；
要确定 \(c\) 的 \(d\) 个坐标分量，需要累积关于 \(d\) 个独立方向的信息，每次查询的标量输出在信息论上不足以同时覆盖所有方向。
严格化这一直觉即得下界：在该分布上，任何经典算法（包括随机算法）要达到固定精度，需要 \(\Omega(d)\) 次查询。作为对照，量子查询把整个叠加态一次性作用于所有 \(x\)，curvelet 测量再把全局干涉"压缩"成一个 \(d\) 维方向标签——每次量子测量提取的是向量值信息。\(O(1)\) 对 \(\Omega(d)\)，构成一个多项式级的查询复杂度分离。
8.2 模型限定条件（务必注意）¶
上述强结论是在理想连续模型中证明或论证的，具体保留条款包括：
细尺度起伏：径向轮廓 \(g\) 必须在足够细的尺度 \(\delta\) 上变化，否则没有高频成分，curvelet 失去方向分辨率（3.2 节），极端情形（\(g\) 几乎常数）下问题本身无解；
承诺条件：目标精度是固定相对精度 \(\varepsilon\)、半径 \(\beta\) 已知或在已知区间内、查询区域有界；
连续模型的严格性：连续 curvelet 变换下"概率质量集中在几何正确标签上"的界是论文严格分析的主体；
离散化的地位：有限网格上的离散化误差分析主要是非严格或条件性的论证——算法有明确的离散电路实现（3.3 节），但其端到端精度保证依赖于对离散化误差的合理假设。
因此，对本算法的准确表述是"理想模型下常数查询、具有离散实现证据"，而不是一个无条件的、任意高维黑盒优化算法。这也是它与我们学过的 Grover、Shor 等算法在陈述强度上的重要区别。
8.3 复杂度账目小结¶
把查询与门的开销逐项列出（\(d\) 为维数，\(n\) 为每坐标比特数，\(\varepsilon\) 为相对精度，\(\delta\) 为壳厚）：
量子查询数：\(O(1)\)。来源：每次采样 = 常数次 oracle 调用（均匀叠加 + 查询 + 振幅整形，后选择开销用振幅放大吸收为常数因子），所需样本数 \(m = O(1)\)——由 3.2 节与 6.3 节的标度，\(m \sim \frac{\delta/\beta}{\varepsilon^2}\) 量级，只依赖精度参数与壳的相对厚度，不依赖 \(d\)；
量子门数：多项式。来源：每次采样的 curvelet 电路为 QFT（\(O(dn^2)\) 门）+ 可逆算术分箱 + 逐楔逆 QFT，curvelet 字典大小为多项式（3.2 节计数）；最小二乘后处理是纯经典的 \(O(m d^2)\) 量级计算；
经典查询数下界：\(\Omega(d)\)（论文的随机分布模型下）。
9. 本课小结¶
径向函数中心 \(c\) 的信息在 Fourier 域只存在于相位 \(e^{-2\pi i \xi\cdot c}\) 中，Fourier 测量对其完全无感；需要"既定位又定向"的测量基。
Curvelet 是带方向的多尺度波包，标签为 \((a, b, \theta)\)；抛物线尺度关系（宽度 \(\approx\) 长度²，\(\Delta\theta \approx \sqrt{\delta/\beta}\)）来自"波包贴合弯曲波前"的最优平衡，壳越薄、频率越高，法向估计越精确。
量子算法三步：制备薄壳态（常数次查询）→ 量子 curvelet 测量（多项式门，零查询）→ 多条近似法线的最小二乘求交（经典后处理，\(A\widehat{c} = v\)）。
Quantum sample 模型下，边界阶梯奇异的法向响应允许 \(c \approx b \mp \beta\theta\) 的近似单次定位。
查询复杂度：理想连续模型中量子 \(O(1)\) 对经典 \(\Omega(d)\)，多项式分离；结论依赖薄壳、细尺度起伏与连续/离散模型假设，应表述为"理想模型下常数查询、具有离散实现证据"。
练习题¶
练习 1【问题模型与承诺条件】（→ 1 节）
基础：写出径向函数的定义与目标精度 \(\|\widehat{c} - c\| \le \varepsilon\beta\)，并列出三条承诺条件（薄壳、半径已知、固定相对精度）。
进阶：解释承诺"\(g\) 在尺度 \(\delta\) 上有显著起伏"为何不可省略：若 \(g\) 几乎为常数，函数值还携带中心 \(c\) 的信息吗？可用的高频成分与方向分辨率会发生什么？
提示：方向分辨率 \(\Delta\theta \approx \sqrt{\delta/\beta}\) 依赖可用频率 \(k \approx 1/\delta\)，见 3.2 节。
练习 2【经典瓶颈与三步算法总览】（→ 1.4 节）
基础：说明用有限差分估计一个 \(d\) 维梯度为何需要 \(d+1\) 个点上的函数值；按顺序列出量子算法的制备、测量、后处理三步，并写出每一步的查询数与门数量级。
进阶："一次 curvelet 测量读出一个 \(d\) 维方向标签"与"一次量子测量只能提取少量信息"的直觉为何并不矛盾？请从被测的态、测量的基、字典的大小三方面作答。
提示：我们不是在读取一个未知量子态的全部信息，而是对专门制备的态做一次计算基测量，输出是多项式大小字典的一个索引。
练习 3【Fourier 域的相位盲区】（→ 2.1 节）
基础：对 \(f(x) = g(\|x - c\|)\) 做换元 \(y = x - c\)，推导 \(\hat{f}(\xi) = e^{-2\pi i\,\xi\cdot c}\,h(\|\xi\|)\)，并指出"\(h\) 只依赖 \(\|\xi\|\)"用到的关键事实。
进阶：证明 Fourier 基下测得频率 \(\xi\) 的概率与 \(c\) 无关；再说明薄壳态的谱为何集中在半径 \(\approx 1/\delta\) 的频率球壳上，以及为什么这仍不足以定位 \(c\)。
提示：模平方抹掉相位 \(e^{-2\pi i\,\xi\cdot c}\)；全局频谱把所有方向的信息混合成一个标量函数 \(|h(\|\xi\|)|^2\)。
练习 4【Curvelet 标签与抛物线尺度】（→ 3.1 节）
基础：分别说出 \((a, b, \theta)\) 三个标签的含义，并写出高频 curvelet 的空间形状——沿 \(\theta\) 方向的宽度与垂直方向的长度各是什么量级。
进阶：设壳厚 \(\delta\)、曲率半径 \(\beta\)。从贴合条件 \(\frac{\ell_t^2}{2\beta} \le \ell_r\) 与 \(\ell_r \approx \delta\) 出发，推出切向最优长度 \(\ell_t\) 与角分辨率 \(\Delta\theta\) 的标度；进一步说明：若要求中心相对误差 \(\|\widehat{c} - c\|/\beta \le \varepsilon\)，且各样本误差独立、最小二乘平均使误差缩小 \(\sqrt{m}\) 倍，则所需样本数的标度为 \(m \sim \frac{\delta/\beta}{\varepsilon^2}\)，从而与 \(d\) 无关。
提示：单条直线的固有横向误差 \(\sim \beta\Delta\theta\)，要求 \(\beta\Delta\theta/\sqrt{m} \le \varepsilon\beta\)。
练习 5【薄壳态的 oracle 制备】（→ 4 节）
基础：按顺序写出制备薄壳态的三步（均匀叠加、查询、振幅整形）及每步得到的态，并给出理想化末态 \(|\psi_c\rangle \propto \int w(\|x - c\| - \beta)\,|x\rangle\,dx\)。
进阶：说明第 3 步的阈值化涉及后选择时，振幅放大为何能把期望查询数压回常数；并解释为什么不直接测量位置 \(x\) 来定 \(c\)。
提示：球壳上每一点到中心的距离都是 \(\beta\)，位置分布关于 \(c\) 是旋转对称的。
练习 6【法向计算与定相原理】（→ 5.1 节）
基础：设 \(\Phi(x) = \|x - c\| - \beta\)。不引用 Lemma 1，逐分量写出 \(\frac{\partial \Phi}{\partial x_i}\) 的链式法则推导，并验证 \(\|\nabla\Phi(x)\| = 1\)。这个法向公式在 \(x = c\) 处为什么失效？
进阶：对光滑紧支撑的 \(w\)，用分部积分证明对任意正整数 \(M\) 有 \(|\widehat{w}(\xi)| \le \frac{1}{(2\pi |\xi|)^M}\int |w^{(M)}(x)|\,dx\)，并据此解释为什么壳态的 curvelet 系数只在"位置 \(b\) 贴近壳面且方向 \(\theta\) 接近法向"的标签上显著，测得方向满足 \(\theta \approx \pm\frac{b - c}{\|b - c\|}\)。
提示：每分部积分一次多出一个因子 \(\frac{1}{2\pi i \xi}\)；\(\xi\) 不沿法向时相位沿切向没有驻点。
练习 7【近似法线的最小二乘求交】（→ 6.1 节）
基础：取 \(d = 2\)，真实中心 \(c = (1, 2)\)。三个精确测量：\(b_1 = (2, 2)\)、\(\theta_1 = (1, 0)\)；\(b_2 = (1, 3)\)、\(\theta_2 = (0, 1)\)；\(b_3 = (1 + \tfrac{1}{\sqrt{2}}, 2 + \tfrac{1}{\sqrt{2}})\)、\(\theta_3 = (\tfrac{1}{\sqrt{2}}, \tfrac{1}{\sqrt{2}})\)。先验证每条直线 \(b_i - t\theta_i\) 都过 \((1, 2)\)，再计算 \(A\)、\(v\) 并解出 \(\widehat{c}\)。
进阶：从目标函数 \(F(z) = \sum_i \|(I - \theta_i\theta_i^T)(z - b_i)\|^2\) 出发，不引用 Lemma 2，自行展开二次型、求梯度并令其为零，推出正规方程 \(A\widehat{c} = v\)；并说明为什么 \(A\) 半正定保证驻点就是全局最小值点。
进阶：设 \(d = 2\)，只有两个样本且 \(\theta_1 = \theta_2 = (1, 0)\)。写出 \(A\) 并求其零空间；证明对任意实数 \(t\)，点 \(\widehat{c} + t\,(1, 0)\) 与 \(\widehat{c}\) 到两条直线的总平方距离相同，即中心沿 \((1, 0)\) 方向完全不可辨识。这解释了算法为什么要检测 \(A\) 的条件数并重采样。
提示：\(P_i = I - \theta_i\theta_i^T\) 对称幂等，且 \(P_i\,\theta_i = 0\)。
练习 8【单次测量定位与复杂度分离】（→ 7 节）
基础：写出 quantum sample 模型中由一次测量 \((b, \theta)\) 得到的中心估计 \(c \approx b \mp \beta\theta\)，并说明符号歧义 \(\mp\) 的来源与消解办法。
进阶：比较"函数 oracle"与"已给 quantum sample"两种模型的资源差异：各自的查询/样本成本是什么？为什么前者需要最小二乘而后者可以近似一次测量定位？如果 quantum sample 的制备本身需要 \(\Theta(d)\) 次经典操作，量子优势是否还存在？说明理由。
进阶：解释经典下界 \(\Omega(d)\) 的信息论直觉（每次查询只返回一个标量、未知中心有 \(d\) 个自由度），并列出量子 \(O(1)\) 结论依赖的至少两条模型限定条件。
提示：查询复杂度的分离不等于总计算成本的分离，把被外部化的制备成本记回账上再比较。
参考文献¶
Zoo 编号 110：Yi-Kai Liu, Quantum Algorithms Using the Curvelet Transform, STOC 2009。