论文标题
用于模拟高斯玻色子采样的二次加速
Quadratic speedup for simulating Gaussian boson sampling
论文作者
论文摘要
我们引入了一种用于对高斯玻色子采样的经典模拟算法，该算法比以前已知的方法更快。该算法的复杂性在检测到的光子对数中是指数级的，而不是光子的数量，并且与计算纯高斯状态的概率幅度所需的时间成正比。主要的创新是使用辅助调节变量将采样问题减少到计算纯态概率幅度的问题，为此，最昂贵的步骤是计算循环hafnian。我们实施并基准了改进的循环hafnian算法，并表明它可用于计算纯状态概率，即采样算法的主要步骤，即在单个工作站中最多50 photon事件，即无需超级计算机。
We introduce an algorithm for the classical simulation of Gaussian boson sampling that is quadratically faster than previously known methods. The complexity of the algorithm is exponential in the number of photon pairs detected, not the number of photons, and is directly proportional to the time required to calculate a probability amplitude for a pure Gaussian state. The main innovation is to use auxiliary conditioning variables to reduce the problem of sampling to computing pure-state probability amplitudes, for which the most computationally-expensive step is calculating a loop hafnian. We implement and benchmark an improved loop hafnian algorithm and show that it can be used to compute pure-state probabilities, the dominant step in the sampling algorithm, of up to 50-photon events in a single workstation, i.e., without the need of a supercomputer.
