论文标题
线性光学过程的强大模拟
Strong Simulation of Linear Optical Processes
论文作者
论文摘要
在本文中，我们为通过线性光学干涉仪的光子进行模拟提供了一种算法和一般框架。给定的$ n $光子在$ m $ - 模式干涉仪的输入下，我们的算法通过时间复杂性$ o \ left（{n \ binom {n+m-1} {m-1} {m-1}} {m-1}}} \ right计算所有可能输出状态的概率。它以指数因素优于基于永久的方法，并且对于计算一个给定输出的概率的有限问题，它提高了具有多个行或列的永久矩阵的最新时间复杂性，并在内存使用中取消了权衡。我们的算法由于使用记忆（中间结果的存储），还具有额外的多功能性，这在可能引起几种输入状态的情况下是有利的。此外，它允许进行混合模拟，其中将输出从概率超过给定阈值或受限一组状态的输出状态采样。我们考虑了一个具体，优化的实现，与现有工具相比，我们基准了方法的效率。
In this paper, we provide an algorithm and general framework for the simulation of photons passing through linear optical interferometers. Given $n$ photons at the input of an $m$-mode interferometer, our algorithm computes the probabilities of all possible output states with time complexity $O\left({n\binom{n+m-1}{m-1}}\right)$, linear in the number of output states $\binom{n+m-1}{m-1}$. It outperforms the permanent-based method by an exponential factor, and for the restricted problem of computing the probability for one given output it improves the time complexity over the state-of-the-art for the permanent of matrices with multiple rows or columns, with a tradeoff in the memory usage. Our algorithm also has additional versatility by virtue of its use of memorisation -- the storing of intermediate results -- which is advantageous in situations where several input states may be of interest. Additionally it allows for hybrid simulations, in which outputs are sampled from output states whose probability exceeds a given threshold, or from a restricted set of states. We consider a concrete, optimised implementation, and we benchmark the efficiency of our approach compared to existing tools.
