# 径向函数中心定位：高维 Curvelet 变换的方向性量子测量

给定未知中心 $c\in\mathbb R^d$ 与径向函数

$$
f(x)=g(\|x-c\|),
$$

怎样用尽量少的 oracle 查询定位 $c$？逐坐标探测至少要随维数增长；量子算法则在叠加中观察整个球壳，并用 curvelet transform 同时测出壳面上的位置和法向方向。每个样本给出一条大致穿过中心的直线，常数个样本即可在理想连续模型中恢复中心到固定精度。

## 1. 为什么普通 Fourier 变换不够

若 $f$ 在半径 $\beta$ 附近形成厚度 $\delta\ll\beta$ 的薄球壳，Fourier 变换能检测典型空间频率约为 $1/\delta$，却丢失“该频率来自壳面哪个位置”。球面不同位置的法向方向不同，只知道全局频谱不足以直接三角定位中心。

Curvelet 是带方向的多尺度波包。标签可概念性写成

$$
(a,b,\theta),
$$

其中 $a$ 是尺度，$b\in\mathbb R^d$ 是空间位置，$\theta\in S^{d-1}$ 是 Fourier 楔形的主方向。高频 curvelet 在频域局限于窄角楔，在空间域则沿与 $\theta$ 相关的各向异性区域局域，兼顾位置与法向信息。

## 2. 从 oracle 制备球壳量子态

在一个足够大的区域内制备位置均匀叠加，查询 $f(x)$，再通过相位、阈值或振幅变换突出快速变化的半径区间。理想化后得到归一化态

$$
|\psi_c\rangle
\propto\int
w(\|x-c\|-\beta)|x\rangle\,dx,
$$

其中窗函数 $w$ 支持在宽约 $\delta$ 的薄壳上。算法需要 $g$ 在足够小尺度上有可观测起伏；若 $g$ 几乎常数，任何模型都没有中心信息。

量子 curvelet transform 是一个酉换基：先做高维 Fourier 变换，再按半径频带与方向楔相干分箱，最后对每个楔做局部逆 Fourier 变换。只要网格、尺度数和方向精度均为多项式位数，其离散电路可由 QFT、可逆算术与受控旋转组成。

## 3. 为什么测得的方向指向中心

球面由相位函数

$$
\Phi(x)=\|x-c\|-\beta
$$

定义，其法向为

$$
\nabla\Phi(x)=\frac{x-c}{\|x-c\|}.
$$

薄壳的高频分量主要沿法向振荡。于是 curvelet 测量若返回位置 $b$ 与方向 $\theta$，在好事件中有

$$
\theta\approx\pm\frac{b-c}{\|b-c\|}.
$$

等价地，未知中心靠近直线

$$
L(b,\theta)=\{b-t\theta:t\in\mathbb R\}.
$$

Curvelet 的抛物尺度关系把角误差和横向位置误差同时压小：壳越薄，频率越高，法向估计越精确。与逐坐标梯度不同，一次测量返回 $d$ 维方向标签，因此查询数可以不随 $d$ 增长。

## 4. 从若干近似法线求交

对独立样本 $(b_i,\theta_i)$，中心应最小化到各直线的平方距离：

$$
\widehat c
=\arg\min_z
\sum_i\|(I-\theta_i\theta_i^T)(z-b_i)\|^2.
$$

令

$$
A=\sum_i(I-\theta_i\theta_i^T),\qquad
v=\sum_i(I-\theta_i\theta_i^T)b_i,
$$

则在 $A$ 条件良好时

$$
\widehat c=A^{-1}v.
$$

随机球面位置给出不同方向；常数个方向在论文的固定相对精度目标下以常数概率提供足够几何约束。若方向几乎平行，算法检测到 $A$ 病态并重新采样。查询复杂度仍为 $O(1)$，成功率通过常数重复放大。

## 5. 球内 quantum sample 的单次版本

若不是函数 oracle，而是直接得到球内均匀量子样本

$$
|B(c,\beta)\rangle,
$$

curvelet transform 主要响应球的边界奇异面。测得一个位置--方向对后，法线给出中心方向；结合已知半径和位置可用

$$
c\approx b\mp\beta\theta
$$

直接形成中心估计。这解释了为何 quantum sample 模型可近似“一次测量定位”，而 oracle 模型通常还要制备薄壳并做少量重复。

## 6. 经典下界与模型限定

在论文构造的随机径向函数分布下，每次经典查询只返回一个标量，查询点与随机细尺度起伏很难提供关于 $d$ 个中心方向的充分信息，得到固定精度中心需要 $\Omega(d)$ 次查询。量子查询同时作用于所有 $x$，curvelet 测量把全局干涉压成一个 $d$ 维方向标签，形成多项式查询差距。

不过，强结论是在理想连续模型中证明/论证的：

- 径向轮廓必须在足够细尺度变化；
- 目标精度、半径范围和查询区域有承诺；
- 连续 curvelet 的概率质量界是严格分析主体；
- 有限网格离散化误差主要给出非严格或条件性论证。

因此应称其为“理想模型下常数查询、具有离散实现证据”，而不是无条件的任意高维黑盒优化算法。

## 7. 小结与习题

- Fourier 变换给频率，curvelet 进一步保留位置和方向。
- 球壳的局部高频方向沿法线，测量结果定义一条近似穿过中心的直线。
- 多条法线的最小二乘交点给出中心，病态方向可重采样。
- 查询优势依赖薄壳、细尺度起伏和连续/离散模型假设。

1. 推导球面 level set 的法向 $\nabla\Phi(x)$。
2. 从最小二乘目标推导正规方程 $A\widehat c=v$。
3. 说明两个完全相同的方向为何使中心沿该方向不可辨识。
4. 比较“函数 oracle”与“已给 quantum sample”两种输入模型的资源差异。

## 参考文献

- Zoo 编号 110：Yi-Kai Liu, [Quantum Algorithms Using the Curvelet Transform](https://arxiv.org/abs/0810.4968), STOC 2009。