# 量子概率采样：BosonSampling、IQP 与 Log-Concave 分布

量子计算的输出本来就是随机样本。有些任务利用这一点构造经典难模拟的分布（BosonSampling、IQP），另一些任务用量子 walk/MCMC 更快地从有结构的目标分布采样（log-concave sampling）。二者目标不同：前者提供条件性计算优势证据，后者给带条件数、维数与误差的算法上界。

## 1. Sampling 与 probability estimation 不同

给分布 $p$，sampling algorithm 每次输出 $x\sim\widetilde p$，要求

$$
\|p-\widetilde p\|_{TV}
=\frac12\sum_x|p(x)-\widetilde p(x)|
\le\epsilon.
$$

它不必计算任意指定 $p(x)$。概率可能 #P-hard 估计，但物理量子过程仍能直接产生样本；反过来，能估计某些边缘概率也不一定能高效生成全联合分布。

“经典难采样”证明通常是反证：假设存在经典 sampler，再用 Stockmeyer approximate counting 在 NP oracle 下估计 sampler 输出概率，进而解决 #P-hard 平均问题并导致 polynomial hierarchy collapse。推理强度取决于 exact/approx sampler 与所用 conjectures。

## 2. BosonSampling 的 permanent 概率

线性光学网络在 $m$ 个模式上施加 unitary $U$：

$$
a_i^\dagger\mapsto
\sum_{j=1}^mU_{ji}b_j^\dagger.
$$

输入 $n$ 个不可分辨单光子（例如前 $n$ 模式各一），输出 occupation

$$
S=(s_1,\ldots,s_m),\qquad\sum_js_j=n.
$$

把 $U$ 按输入/输出重复行列形成 $n\times n$ 子矩阵 $U_S$，则

$$
\Pr(S)=
\frac{|\operatorname{Per}(U_S)|^2}
{\prod_js_j!},
$$

（输入若也有重复占据再除输入 factorial）。Permanent

$$
\operatorname{Per}(A)
=\sum_{\pi\in S_n}\prod_iA_{i,\pi(i)}
$$

像 determinant 但没有符号相消，通用精确计算 #P-hard。Bosonic 多路径相长正好物理实现这条永久和。

## 3. BosonSampling 困难性结论的条件

Exact classical sampling 若可多项式完成，可结合 Stockmeyer 估计输出概率，从而在 $\mathrm{BPP}^{NP}$ 中处理 permanent 型量，导致复杂度类非预期塌缩。

对实验更相关的 approximate/noisy sampling，论证还依赖：

- Gaussian permanent 平均近似 #P-hard；
- permanent anti-concentration，使概率不常指数小到加性估计无意义；
- 损失、部分可区分光子与器件误差在允许 TV 距离内受控。

这些是明确 conjectures/噪声假设，不是无条件证明“任何经典算法永远不可能模拟”。BosonSampling 也不是通用量子计算模型；其价值正是受限线性光学仍可能有采样优势。

## 4. IQP：时间上无序的 commuting circuits

IQP 电路典型形式

$$
U_{IQP}=H^{\otimes n}D H^{\otimes n},
$$

$D$ 由彼此交换的 $Z$-diagonal gates 组成。输出振幅

$$
\langle z|U_{IQP}|0^n\rangle
=2^{-n}\sum_{x\in\{0,1\}^n}
(-1)^{z\cdot x}e^{i\phi(x)}.
$$

这是 Boolean polynomial exponential sum，也可映到复参数 Ising partition function。所有 $D$ 门可同时/任意顺序执行，“temporally unstructured” 仍产生全局干涉。

若经典算法以足够强的乘法或 TV 精度 weakly sample 某些 IQP family，类似 Stockmeyer + anti-concentration/平均困难性论证会导致 polynomial hierarchy collapse。具体门角、图结构和误差定义决定结论；Clifford-only 的 commuting 子族仍可经典模拟。

## 5. Log-concave sampling 是算法问题

给凸函数

$$
f:\mathbb R^d\to\mathbb R,
$$

目标密度

$$
\pi(x)=\frac{e^{-f(x)}}{Z},\qquad
Z=\int_{\mathbb R^d}e^{-f(x)}dx.
$$

若 $f$ 为 $\mu$-strongly convex、$L$-smooth，条件数

$$
\kappa=L/\mu.
$$

经典 Langevin diffusion

$$
dX_t=-\nabla f(X_t)dt+\sqrt2,dB_t
$$

以 $\pi$ 为稳态；离散化、warm start 与 Metropolis correction 控制 bias/mixing。

## 6. Quantum Langevin / MALA 的加速来源

量子算法相干表示 proposal 和 accept/reject Markov kernel，再用 Szegedy walk 平方改善 spectral gap/mixing。即使只给 zeroth-order $f(x)$ oracle，可用量子梯度/有限差分叠加构造 drift，使查询复杂度匹配某些使用 gradient oracle 的经典算法。

Quantum Metropolis-adjusted Langevin 结果给出（省略 polylog 与 warmness）：

$$
\widetilde O(\kappa^{1/2}d)
$$

次查询生成 log-concave 样本，以及

$$
\widetilde O\!\left(
\frac{\kappa^{1/2}d^{3/2}}{\epsilon}
\right)
$$

估计 normalizing constant。后者沿温度/势函数 schedule 写 $Z$ 比值，并用量子 mean/amplitude estimation 获得 $1/\epsilon$ 而非 $1/\epsilon^2$ 精度依赖；已有 $1/\epsilon^{1-o(1)}$ lower bound 表明近最优。

## 7. 输出与验证

Log-concave sampler 最终测量位置寄存器得到一个经典 $x$；若要 $M$ 个独立样本，通常要重复状态制备 $M$ 次，量子叠加不能一次打印指数多样本。

验证 sampler 的 TV 距离本身可能很难。理论保证依赖 oracle 正确、smooth/strong-convex 参数和离散误差界；实验可检查低阶 moments/energy，但不能由有限统计完全认证高维分布。

Boson/IQP 困难采样与 log-concave 高效采样不矛盾：前者故意生成 permanent/exponential-sum 干涉分布，后者利用凸性和快速混合结构。

## 8. 小结与习题

- Sampling 只需输出样本，不必显式计算每个概率。
- BosonSampling 概率由 permanent 平方给出；approx hardness 依赖平均困难与 anti-concentration conjectures。
- IQP commuting gates 的振幅是 Boolean exponential sum/复 Ising 值。
- Log-concave 量子采样用 quantum walk 与 Langevin 结构，复杂度显式依赖 $\kappa,d,\epsilon$。

1. 对两个光子、$2\times2$ beam splitter 写出 permanent 输出振幅。
2. 从 IQP 形式推导振幅 Fourier sum。
3. 解释 Stockmeyer 在采样困难性反证中的角色。
4. 比较 sampling 一个点与估计 normalizing constant 的精度成本。

## 参考文献

- Zoo 编号 473：Aaronson 与 Arkhipov, [The Computational Complexity of Linear Optics](https://arxiv.org/abs/1011.3245).
- Zoo 编号 474：Shepherd 与 Bremner, [Temporally Unstructured Quantum Computation](https://arxiv.org/abs/0809.0847).
- Zoo 编号 475：Childs、Li、Liu、Wang 与 Zhang, [Quantum Algorithms for Sampling Log-Concave Distributions and Estimating Normalizing Constants](https://arxiv.org/abs/2210.06539).