量子概率采样：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 的精度成本。

参考文献