快速且内存效率高的强模拟技术，用于模拟带有噪声的自适应线性光电路

线性光学电路的精确模拟算法LO-SLAP，通过多项式部分导数优化时间-内存权衡，内存需求为2^n，优于现有方法，并扩展至含噪声和自适应（feedforward）场景。

蒂莫西·古博·德·布鲁吉埃（Timothée Goubault De Brugière）| 尼古拉·埃尔特（Nicolas Heurtel）

Quandela，莱昂纳多·达·芬奇街7号（Rue Léonard de Vinci 7），马西（Massy），91300，法国

摘要

精确计算线性光学电路的完整输出分布仍然是一个挑战，因为现有的方法要么时间效率高但内存消耗大，要么内存效率高但速度慢。此外，任何现实的模拟都必须考虑噪声（如光子损耗），而任何基于线性光学的可行量子计算方案都需要前馈。这在经典模拟中增加了额外的复杂性，因为需要处理由于测量或损耗等情况而产生的额外组合问题。在本文中，我们提出了一种算法，该算法将输出幅度建模为多变量多项式的偏导数。该算法遍历所有中间偏导数的网格，每个导数都用于更高效地计算更高阶的导数。在内存方面，存储从根到叶子的单条路径就足以迭代所有幅度，只需要2^n个元素，而最快的现有技术方法则需要$\backslash left(\backslash frac\{n(m-1)\}\{2\}\backslash right)n$个元素。这种方法有效地平衡了时间与内存之间的权衡，同时可以轻松扩展到有噪声和前馈的场景中，且成本可以忽略不计。据我们所知，这是文献中第一个满足所有这些要求的算法。我们展示了这种方法如何使得以前无法模拟的系统变得可行，并提供了具体的实现和复杂性分析。

引言

线性光学作为一个自然且可行的平台，可用于传输量子信息，从而在安全通信[1]、[2]和量子网络[3]、[4]中得到应用。更重要的是，带有前馈的线性光学——利用一个阶段的结果动态调整后续阶段操作的适应过程——已被证明足以实现任何量子算法[5]。线性光学的多功能性和计算能力导致了在被动实现[6]、[7]、[8]、量子应用的适应方法[9]、[10]以及可扩展量子计算方案[11]、[12]、[13]、[14]、[15]、[16]方面的广泛研究。

为了有效地研究和表征光学过程，拥有高效的模拟算法至关重要，即计算输出概率（而不是采样任务的弱模拟）。一个研究较为透彻的案例是计算单个概率[6]，这可以通过具有重复行的矩阵的行列式来计算[18]、[19]、[20]，并且存在高效和优化的实现[21]、[22]、[23]。尽管在许多情况下，关注点不仅限于单个概率，而是扩展到多个概率甚至整个输出分布。对于输入为n个光子在m个模式中的情况，这个分布由$\backslash left(\backslash frac\{n(m-1)\}\{2\}\backslash right)n$种可能的结果组成。如果独立地为每个输出计算行列式来计算完整分布将非常耗时，因此优化计算时间至关重要。

已经提出了几种方法来通过存储中间结果来高效且精确地计算多个概率[24]，从而通过大量使用内存来节省时间。虽然这些方法提供了显著的时间优势，但现在瓶颈变成了内存，使得在任何具有合理内存要求的设备上快速计算变得难以实现。一种更节省内存的方法是遍历所有输出状态而不存储大型中间结果。此外，在涉及前馈的场景中，线性光学特别有用。最近用于实际应用的候选方案需要使用前馈[9]、[25]。拥有模拟和检查这些提案相关性的工具至关重要。然而，据作者所知，目前还没有提出一种能够高效模拟带有前馈的线性光学电路的有效算法。结合在物理实验中处理噪声[26]、[27]、[28]的现实需求，我们因此寻求一种能够有效平衡时间-空间权衡的方法，特别适合前馈和有噪声的模拟。

在本文中，我们介绍了LO-SLAP（通过多项式网格的线性光学模拟），这是一种内存效率高的算法，可以迭代输出幅度，并且可以以可忽略的成本扩展到前馈和有噪声的模拟中。迭代是通过利用幅度也可以被视为多变量多项式的n阶偏导数这一事实来实现的。通过存储关于低阶偏导数的信息，可以更高效地计算所有子导数。该算法使用2^n个内存，与SLOS方法[24]所需的存储量相比，我们消除了对模式数量m的依赖性。即使内存需求仍然是光子数量的指数级，理论上我们可以在笔记本电脑上处理多达30个光子。我们提供了LO-SLAP复杂性的理论分析，并展示了我们实际上显著增加了可以使用合理计算能力模拟的问题规模。

我们详细说明了LO-SLAP如何扩展到有噪声和前馈的情况：

1.

算法过程中计算的所有中间系数实际上是同一实验的不同输入状态下的输出幅度，但这些输入状态的光子数量较少。我们将展示LO-SLAP可以自然地计算任何输入状态（包含n个或更少光子）的所有可能输出。因此，无需额外成本，LO-SLAP也可以用于处理损耗的情况。我们还将展示如何结合其他噪声源，如可区分性。

2.

我们的方法也处理前馈，唯一的额外计算是在测量后更新实验矩阵——这是任何模拟前馈的算法都必须执行的操作。据我们所知，这是首次提出用于线性光学的处理前馈的强模拟方法。我们将其与SLOS的扩展版本[24]进行了比较，并展示了理论和实际优势。

文章的结构如下。首先在第2节中，我们介绍了线性光学实验的多项式形式主义，并回顾了现有的经典模拟方法。然后在第3节中介绍了LO-SLAP，详细说明了数据结构、更新方法以及如何遍历输出幅度。在第4节中，我们介绍了我们的两个扩展：前馈和有噪声的模拟。我们在第5节中进行了总结。

小节片段

福克态（Fock States）

我们考虑一个包含n个光子和m个模式的系统。系统的标准状态称为福克态$\backslash left|\backslash sum\_\{i=1\}^\{m\}s\_i\backslash right|=\backslash sum\_\{i=1\}^\{n\}U\_p|s\_i\backslash right$表示光子分配到不同模式中的可能方式（我们将在第i个模式中读取s_i个光子）。有$\backslash left(\backslash frac\{n(m-1)\}\{2\}\backslash right)n$种方式可以将n个光子分配到m个模式中（例如参见[29]中的“星号和条杠”定理）。我们用Φ_m,n表示所有福克态的集合。

我们自然地将福克态|s⟩与一个数组r_s∈[m^n]关联起来

精确强模拟的时间-内存权衡方法

LO-SLAP算法的主要步骤和公式在第3.1节中描述。第3.2节分析和比较了时间与内存复杂性，并与现有方法进行了对比。第3.3节提供了伪代码和实现细节。最后，第3.4节探讨了进一步改进时间复杂性的方法。

前馈（Feedforward）

通常来说，前馈或自适应线性光学是指根据中间测量结果应用不同的幺正变换的能力。这通常表示为多层计算，每一层都是一个幺正变换，然后是一些测量，这些测量将自适应地决定下一层，依此类推。给定m个模式、n个光子和k次自适应测量，自适应线性光学计算可以通过所有可能的幺正变换U_p|p∈Φ来总结

结论

我们介绍了LO-SLAP，这是一种用于精确强模拟线性光学电路的内存高效算法。该算法的第一个动机是提供比现有技术更好的时间-内存权衡，并且我们展示了与现有技术方法相比，我们的方法在问题规模上取得了显著改进。

我们的算法自然可以扩展到前馈和噪声的模拟。在这两种情况下，所需的额外计算都非常少。

CRediT作者贡献声明

蒂莫西·古博·德·布鲁吉埃（Timothée Goubault De Brugière）：撰写——原始草稿，软件，概念化。尼古拉·埃尔特（Nicolas Heurtel）：撰写——原始草稿，软件，概念化。

利益冲突声明

作者声明以下可能被视为潜在利益冲突的财务利益/个人关系：蒂莫西·古博报告与洛林计算机科学及其应用研究实验室（Lorraine Research Laboratory in Computer Science and its Applications）存在关系，包括就业。如果有其他作者，他们声明没有已知的可能会影响本文所报告工作的财务利益或个人关系。