⚛️ quantum physics

Classical Algorithms for Function Computation in Gaussian Boson Sampling

本文通过分析固定光子数算符空间的不可约分解，证明了在有限挤压强度下，应用于高斯玻色采样光子数结果的函数的期望值可以通过经典方式进行评估，从而提供了一种经典算法以及对该类任务复杂性的新理论见解。

原作者： Ruoting Dou, Hao Zhan, Shengjun Wu, Lijian Zhang, Penghui Yao

发布于 2026-10-01

📖 1 分钟阅读🧠 深度阅读

原作者： Ruoting Dou, Hao Zhan, Shengjun Wu, Lijian Zhang, Penghui Yao

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在当前的量子计算时代，研究人员正致力于构建能够解决甚至连最强大的超级计算机都无法处理的问题的机器。一条极具前景的路径是利用光来进行计算。这些机器不再使用在硅芯片中移动的电子，而是使用在镜面和分束器网络中穿行的光子流（即光粒子）。一种被称为高斯玻色采样（Gaussian boson sampling）的特定实验已成为展示这种优势的主要候选方案。在这些实验中，研究人员将光挤压成一种特殊的态，并将其送入一个复杂的的光学电路。随后，机器会统计有多少光子到达了每个出口。这些计数模式极其难以预测或重现，因此它被视为证明量子优越性的潜在手段。

然而，量子计算的终极目标不仅仅是生成难以预测的随机数，而是执行有用的任务。许多针对这些基于光的机器提出的应用都涉及将随机的光子计数转化为计算特定值的过程，例如分子的化学特性或复杂网络的特征。这一过程被称为函数计算。一个关键问题一直悬而未决：如果目标是从这些随机结果中计算一个特定的平均值，而不是对所有可能性的完整分布进行采样，那么量子机器是否仍然具有优势？或者说，运行在标准硅片上的经典计算机是否也能同样出色地完成这项工作？

来自南京大学和合肥国家实验室的研究团队现在通过一项确定的理论结果回答了这个问题。他们开发了一种新的经典算法，可以高效地估计应用于高斯玻色采样实验结果的几乎任何函数的平均值。他们的研究表明，对于目前实验中使用的标准设置——即光被挤压到有限强度且镜面网络是随机选择的情况下——经典计算机可以高精度地计算出预期结果。这一发现并不意味着量子计算机在这些任务中是无用的，而是表明量子力学在这一特定语境下的优势比此前预期的更为有限。量子加速高度依赖于对整个输出分布进行采样的难度；一旦目标转向计算特定的平均值，经典模拟的障碍就会崩塌。

研究人员通过将光相互作用的复杂数学过程分解为更简单的层级，得出了这一结论。他们通过分析系统中存在的总光子数以及这些光子之间的相关性来分析系统。他们发现，在一个随机排列的网络中，许多光子之间复杂的、高阶的相关性变得非常微弱，以至于在计算平均值时可以安全地忽略它们。重要的信息包含在较低阶的相互作用中，而这些相互作用更容易计算。通过仅关注这些可控的部分，并从数学上证明被忽略的部分对最终平均值的贡献可以忽略不计，他们构建了一种运行时间为多项式时间的算法。这意味着随着系统规模的增大，所需计算时间呈可控的速率增长，而不是像进行完整模拟那样呈指数级爆炸式增长。

该研究还明确了量子优势究竟存在于何处。作者确定了使任务对经典计算机保持难度的资源需求边界。要维持这种难度，实验需要同时具备三个要素：挤压光输入、能够计数单个光子的探测器，以及对完整输出分布进行采样的要求。如果其中任何一个被移除——例如，如果目标仅仅是估计一个平均值，而不是生成全套随机模式——那么这项任务对于经典计算机来说就会变得容易。这种区分对于该领域的发展至关重要。它表明，虽然高斯玻色采样是证明量子机器能够完成经典机器无法完成之事的有力工具，但其在药物研发或图分析等实际应用中的效用，可能需要超越简单函数平均的新方法。

研究人员的工作为理解线性光学量子系统提供了一套新的理论工具。通过证明这些系统的平均情况行为可以通过经典方式模拟，他们帮助澄清了当前关于量子难度的证据来源。此前的证据是基于对完整输出进行采样的难度，但这项新分析表明，这种难度并不自动延伸到计算由这些输出导出的特定函数上。这一结果并未排除在所有场景下实现量子优势的可能性；例如，如果正在计算的函数以复杂的方式依赖于光学网络的特定排列，或者允许挤压强度无限增长，那么该经典算法可能不再适用。然而，对于当今实验中所使用的标准有限强度设置，通往经典解决方案的路径现在已经清晰。

这一发现为未来的研究和应用开发提供了指南。它鼓励科学家去寻找新的问题类型，即那些量子光的特性可以提供经典后处理无法复制的真正优势的任务。论文指出，最有前景的应用可能涉及那些需要完整量子分布复杂性的任务，而不仅仅是汇总统计量。通过在“难”与“易”之间划定一条清晰的界限，研究人员帮助整个学术界将精力集中在量子机器最有可能发挥作用的领域。这项工作是一个严谨的证明，表明在当前实验条件下，利用这些基于光的系统来单纯计算平均值的梦想，正处于经典计算机的能力范围之内，这重新塑造了下一代量子应用的路线图。

技术摘要：高斯玻色采样中函数计算的经典算法

问题陈述
高斯玻色采样（GBS）已成为展示量子计算优势的主要候选方案，这主要是由于通过挤压真空输入经过无源线性光学网络生成的光子数模式全输出分布的采样具有计算硬度。虽然采样问题本身被认为在经典上是困难的，但许多拟议的 GBS 应用并不旨在重现完整的分布，而是旨在计算测量结果的特定函数（例如，振动能谱、图核或团权重）。这些任务涉及对模分辨的光子数分辨（PNR）结果进行经典后处理，以估计特定可观测量的期望值。

本文探讨的核心问题是：GBS 分布的经典硬度是否必然意味着这些函数计算任务具有量子优势。具体而言，即使采样该分布在经典上是困难的，是否存在一种经典算法可以高效地估计函数 $f(s)$ 在 GBS 输出分布上的期望值？先前的研究已经确立了特定情况下的经典可模拟性（例如，零温谐振实例或具有自适应测量的电路），但对于哈尔随机（Haar-random）网络下任意多项式时间可求值的函数的通用结果仍然缺失。

方法论
作者开发了一个操作框架，通过将问题分解为固定光子数扇区，并进一步分解为相关阶数，来分析 G서 GBS 函数计算。其核心技术方法包括：

算符空间分解：将 $n$ -光子扇区的算符空间 $\mathcal{B}(\mathcal{H}_{m,n})$ 在酉群 $U(m)$ 的作用下分解为不可约子模 $V_{n,k}$ 。指数 $k$ 代表“相关阶数”，对应于包含 $k$ 个产生-湮灭对的正规排序单项式。
哈恩多项式（Hahn Polynomial）对应关系：对于在福克基底（Fock basis）中是对角化的可观测量（对应于结果函数），其在算符空间分解中的分量直接映射到多元哈恩多项式子空间的正交投影。这使得期望值 $\mu_f(U)$ 可以表示为来自不同相关阶贡献之和。
哈尔平均分析：通过假设线性光学网络 $U$ 是从哈尔测度中抽取的，作者利用舒尔正交性（Schur orthogonality）证明不同相关阶的贡献是不相关的。至关重要的是，他们证明了对于具有有限挤压强度（即挤压参数 $r_j$ 与模数 $m$ 无关地受限）的输入，高阶相关分量的权重随 $m$ 的增加呈多项式衰减。
截断与估计：期望值可以通过将求和限制在常数相关阶 $K$ $K$ 来进行近似。作者证明，对于由于这种截断引入的误差，以高概率而言是关于 $m$ $m$ 的反多项式级别的。作者构建了一种经典算法，该算法：
- 截断光子对数 $N$ 和相关阶 $k$ 。
- 计算保留扇区的约化密度矩阵。
- 在均匀的光子数模式测度上使用蒙特卡洛采样来估计截断均值，利用了对角权重可以从低阶约化态和小型矩阵的永久式（permanents）中重建这一事实。

主要贡献与结果
本文确立了以下主要结果：

定理 1（主要结果）：对于具有 $m$ 个模式、有限挤压强度以及任何满足以下条件的输出函数 $f$ （前提是提供了其均值和方差的已知多项式界限，且该界限与 $U$ 无关），存在一种随机化多项式时间经典算法。该算法能以高概率（在选择哈尔随机网络 $U$ 时，概率为 $1 - m^{-\kappa}$ ）将期望值 $\mu_f(U)$ 估计到反多项式加性误差（ $m^{-c}$ ）范围内。对于缺乏这些显式界限的一般函数，作者提供了一个相位重构扩展，通过评估一个多项式规模的有界特征函数族来估计均值。
资源边界识别：本研究划定了 GBS 实现经典硬度所需的精确资源。如论文表 I 所示，支持经典硬度的证据共同依赖于三个要素：
1. 挤压输入。
2. 模分辨光子检测（PNR 或阈值检测）。
3. 对完整输出分布进行采样。
  本文证明，如果目标仅仅是函数计算（估计平均值）而非完整的分布采样，那么只要挤压强度有限且函数满足所需的界限，该任务在经典上是高效的。
算法构建：作者提供了一个具体的经典算法来估计截断均值。该算法通过使用约化密度算符和低阶永久式，结合在模式空间上的蒙特卡洛采样，避免了计算完整哈夫尼安（Hafnians）的指数级成本。

意义与主张
本文声称通过澄清当前 GBS 硬度证据的来源，为分析线性光学量子系统提供了新的理论工具。具体而言，文章指出 GBS 的经典硬度与重现整个概率分布的难度有关，而不一定与计算输出的特定统计平均值的难度有关。

作者指出，其结果有助于明确哪些任务提供真正的量子优势，哪些任务可以被经典高效地模拟。他们强调，其发现并未使 GBS 的采样硬度失效，而是细化了量子优势所在之处：即在于全分布采样任务，而非目前用于 GBS 应用（如分子光谱学或图问题）的函数计算任务，除非这些特定应用依赖于超出本定理范围的特征（例如， $U$ 依赖的后处理、最坏情况网络，或缺乏所需多项式矩界限的函数）。

这项工作表明，寻求真正量子优势的未来 GBS 应用必须要么针对全分布采样问题，要么识别出违反本定理假设的函数计算任务（例如，使用无界挤压、非哈尔随机的网络，或没有已知多项式矩界限的函数）。作者指出，其结果在另一项工作中扩展到了使用不同输入（例如单光子输入）的其他采样算法，但在本文中，重点严格限定在 GBS 函数计算模型内。

技术摘要：高斯玻色采样中函数计算的经典算法

类似论文