Exact sampling beyond Fock inputs and linear optics: photon-number superpositions, photonic matrix-product states, adaptive and non-linear circuits

技术摘要：超越 Fock 输入与线性光学系统的精确采样

问题陈述
光子系统量子优越性的主张依赖于设备采样内容与经典计算机能够精确采样的内容之间的计算差距。标准的玻色子采样（涉及 $n$ 个单光子在 $m$ 个模式的线性干涉仪中）在经典上是困难的，因为输出概率对应于矩阵的永久值（permanent），这是一个 #P-难问题。然而，现实世界的光子设备偏离了这种理想化模型。光源可能会发射相干叠加态（真空与单光子的叠加，即叠加源）或纠缠序列（光子矩阵乘积态）。此外，电路可能包含中途测量与前馈（自适应光学）或非线性元件（非线性位点）。现有的精确经典采样器（例如针对单光子的 Clifford 和 Clifford 算法）并不直接适用于这些广义场景。本文旨在解决针对这些非标准输入和电路配置的精确采样器需求，以确定经典模拟的极限。

方法论：集合链引理 (The Set-Chain Lemma)
其核心方法论贡献是推广了 Clifford 和 Clifford 使用的“随机顺序”采样技术。作者引入了一个集合链引理（Lemma 1），它提供了一个基于“链一致集合权重”的精确采样准则。

• 机制： 算法不再根据固定的输入顺序顺序采样输出模式，而是抽取输入槽（光源或发射）的一个均匀随机顺序。然后，它逐一采样输出行。
• 条件： 为了使采样器是精确的，与部分输出序列 $z$ 和活跃输入槽集合 $T$ 相关联的权重 $f_j(z; T)$ 必须满足特定的边缘恒等式（条件 C2）。该恒等式确保了对下一个可能的输出行求和可以得到前一步的正确权重，从而有效地将永久值（或其推广形式）的拉普拉斯展开转化为对较小集合的求和。
• 后验推断： 该构造的一个关键特征是，它可以在不进行显式枚举所有子集的情况下，同时提供关于“隐藏”输入集合（例如，哪些光源实际发射了光子，或哪些发射被追踪掉了）的后验分布。

核心贡献：四种精确采样器
作者基于集合链引理构建了四种特定的采样器，以应对对标准模型的不同偏离：

1. 叠加源（真空 + 单光子）：

   • 模型： 光源发射 $\cos \alpha |0\rangle + \sin \alpha |1\rangle$。总光子数 $k$ 服从二项分布。
   • 方法： 采样器使用“偏移起始”顺序。它不是从空输入集开始，而是从 $n-k$ 个光源开始（其中 $n$ 是总光源数）。
   • 权重： 权重是平方矩形永久值 $|\text{Per}_{\square} A[z, T]|^2$。
   • 代价： 计算成本随单光子在损耗 $\eta = \sin^2 \alpha$ 下的指数级缩放。算法有效地将问题视为具有减少有效光子数的单光子采样。

2. 光子矩阵乘积态 (MPS)：

   • 模型： 一个具有内部记忆（维度 $\chi$）的量子发射器顺序发射 $n$ 个光子，从而创建一个纠缠的 MPS（例如线性簇态）。
   • 方法： 作者引入了“间隔间隙 Kraus 收缩”（gap-by-gap Kraus contraction）。由于随机顺序在保留的发射之间创造了被追踪掉的发射形成的间隙，保留光子的混合态被分解为平方振幅之和。
   • 权重： 权重是 $R_j$ 个平方振幅之和，其中每个振幅都使用矩阵值 Glynn 和进行评估。
   • 代价： 成本由项数 $R_j$ 决定。对线性簇态的经验测量显示，$R_j$ 保持较小（在中间阶段达到峰值约为 $n/2.5$，并在最后几步降至 1–2），使得对于测试实例（$n \le 20$）而言，开销处于可控范围内。

3. 自适应线性光学：

   • 模型： 中途光子计数配合前馈改变了随后模式应用的酉变换。
   • 方法： 采样器根据观察到的自适应计数对标准的 Fock（单光子）链进行条件化处理。它首先采样“前缀”（自适应结果），然后继续执行标准的 Clifford-Clifford 步骤。
   • 拒绝： “未来的光子不会落在已测量的自适应模式上”这一约束并不符合链一致性。采样器通过拒绝机制强制执行：如果一条链在前缀固定后将光子放置在自适应模式上，则该链会被中止并重新绘制。
   • 代价： 开销由满足前缀约束所需的链的数量决定。对于固定的自适应模式数量 $K$，其成本保持在标准采样器的常数倍以内（例如，当 $K=3$ 时，约为 1.1 倍）。

4. 非线性位点：

   • 模型： 线性干涉仪之间的一个单模非线性（例如 Kerr 相位）。
   • 方法： 由于不同的线性分支耦合了隐藏的输入集合，自然权重会违反链一致性条件。作者对线性分支的混合应用了拒绝原理。
   • 算法： 选择一个分支 $b$ 的概率与 $|c_b|$ 成正比，绘制一个标准的 Fock 样本，并根据柯西-施瓦茨不等式接受该样本。
   • 代价： 接受概率恰好为 $1/\|c\|_1^2$。对于具有短周期（如 $\phi = \pi/2$）的非线性，分支数 $B$ 很小，导致常数级开销（约 4 倍）。对于一般的响应，成本随 $n$ 呈多项式增长。

结果与验证

• 验证： 所有四种采样器都在小规模实例上通过强模拟（使用 SLOS 和其他精确方法）进行了验证。测量得到的采样器输出与预言机（oracle）之间的全变差距离（TVD）处于统计噪声范围内（约为精确抽取的 1.7 个标准差）。
• 性能：
  • 叠加源： 成本遵循损耗指数。在 $\sin^2 \alpha = 0.8$ 时，成本大约是同规模单光子采样器的 4 倍。
  • 光子 MPS： 在测量序列（$n \le 20$）上，开销很低，因为在最昂贵的最后几步中，$R_j$ 保持很小。
  • 自适应光学： 使用最多三个自适应模式的采样成本在标准单光子采样器的 10% 范围内。
  • 非线性位点： $\phi = \pi/2$ 的非线性位点成本约为标准采样器的 4 倍。

意义与主张
论文声称，“随机顺序”采样范式比此前认为的更具鲁棒性，能够超越乘积 Fock 输入，扩展到纠缠态和叠加态，前提是满足集合链引理的边缘恒等式。

• 指数速率： 作者证明了对于叠加源、自适应光学（具有固定 $K$）和短周期非线性，精确经典模拟的指数速率保持不变（或随有效损耗缩放）。这些特征本身并不会将问题推入相对于单光子情况而言变得不可解的范畴。
• 开放问题： 作者谦虚地指出，随着 $n$ 的增加，光子 MPS 中项数 $R_j$ 的增长仍是一个开放问题；如果 $R_j$ 呈指数级增长，则前缀振幅采样器（具有多项式开销）最终可能会更优。同样，目前尚不知道适用于一般非线性的链一致族，且拒绝方法对于一般的响应会变得代价高昂。
• 实现： 这些采样器实现在统一的 GPU 代码库（photonic-engines）中，并在 Lean 4 中进行了形式化，为基准测试光子量子优越性提供了经过验证的工具集。

总之，这项工作提供了一个统一的理论框架和实用的算法，用于精确模拟广泛的光子设备，阐明了哪些对标准玻色子采样模型的扩展仍保持在经典可处理范围内，以及哪些引入了显著的开销。