Li Zhenghao, Solomons Naomi R, Bulmer Jacob F F, Patel Raj B, Walmsley Ian A
Department of Physics, Imperial College London, London, UK.
Quantum Engineering Centre for Doctoral Training, Centre for Nanoscience and Quantum Information, University of Bristol, Bristol, UK.
npj Quantum Inf. 2025;11(1):119. doi: 10.1038/s41534-025-01062-5. Epub 2025 Jul 9.
Gaussian Boson Sampling (GBS) is the problem of sampling from the output of photon-number-resolving measurements of squeezed states input to a linear optical interferometer. For purposes of demonstrating quantum computational advantage as well as practical applications, a large photon number is often desirable. However, producing squeezed states with high photon numbers is experimentally challenging. In this work, we examine the computational complexity implications of increasing the photon number by introducing coherent states. This displaces the state in phase space and as such we call this modified problem . By utilising a connection to the matching polynomial in graph theory, we first describe an efficient classical algorithm for Displaced GBS when displacement is high or when the output state is represented by a non-negative graph. Then we provide complexity theoretic arguments for the quantum advantage of the problem in the low-displacement regime and numerically quantify where the complexity transition occurs.
高斯玻色子采样（GBS）是从输入到线性光学干涉仪的压缩态的光子数分辨测量输出中进行采样的问题。为了证明量子计算优势以及实际应用，通常需要大量的光子数。然而，产生具有高光子数的压缩态在实验上具有挑战性。在这项工作中，我们通过引入相干态来研究增加光子数对计算复杂度的影响。这在相空间中移动了态，因此我们将这个修改后的问题称为……通过利用与图论中的匹配多项式的联系，我们首先描述了一种高效经典算法，用于在位移较高或输出态由非负图表示时的位移GBS。然后，我们为低位移 regime 中该问题的量子优势提供了复杂度理论依据，并通过数值量化了复杂度转变发生的位置。 （注：原文中“we call this modified problem.”后面似乎缺失了具体内容）
